Harry Potter eta Harri filosofalaren amaieran asmakizun interesgarri bat dago. Harry eta Hermione gelara sartzen dira, eta, ondoren, bertako sarrerak su magikoz blokeatzen dira, eta hurrengo asmakizuna ebatziz soilik irten ahal izango dira:
["Harry Potter and the Philosopher's Stone" liburuaren "herri itzulpenetik"]Zure aurrean arriskua dago, eta zure atzean salbazioa,
Gure artean aurkitzen dituzun bi lagunek lagunduko dizute;
Zazpietako batekin aurrera jarraituko duzu
Besteak berehala itzuliko zaitu.
Gu biotan ortiga ardoa besterik ez duzu aurkituko,
Eta hiruk suntsipena ekartzen dute, segidan ezkutuan.
Beraz, aukeratu zeinetatik dastatu nahi duzun,
Horretarako, lau aholku ematen ditugu.
Alferrik saiatu zen pozoia bere bero hilgarria ezkutatzen,
Beti aurkituko duzu ardoaren ezkerrean,
Eta jakin ertzetan daudenek beste opari bat dutela,
Baina jarraitu nahi baduzu, inork ez du lagunduko.
Denok tamaina desberdina dugu, ertzetik ertzera,
Zure heriotza ez da txikian esertzen, baina ez handian ere;
Bigarrena eskuineko muturretik eta bigarrena ezkerretik
Bikien zaporea dute, nahiz eta itxurarik ez izan.
Besterik gabe, ulertu behar dute zein botila duten edabeak.
Artikulu honetan, puzzle honen 42 aldaera posible guztiak ebatziko ditugu programazioa erabiliz eta emaitzen diagrama bat marraztuko dugu (goiko irudian bezala, askoz handiagoa bakarrik).
Itxaron, nondik atera dira 42 aukera?
Hau da, edabe "txikiagoen" eta "handiagoen" kokapenak ez direlako adierazten. Handiena zazpi lekuetako batean egon daiteke, eta horrek geratzen zaizkion 6 aukera ematen dizkio txikiagoari, guztira 7 * 6 = 42. Ezin izango da jakin JK Rowling-ek zer antolaketa zuen buruan sortu zenean. asmakizun honekin, zure Twitter-en horri buruz hitz egiten ez badu behintzat. Tira, ezinbesteko egun hori iritsi arte, ausaz bertsio bat aukeratu eta horrekin lan egin dezakegu. Dena den, ez da bere konpongarritasunaren bermerik izango, eta horregatik egiten dugu lan onaren alde, igarkizunaren 42 aldaera guztiak ebatziz (edo haien konponbiderik eza frogatuz).
ERABAKI DAGOENEKO
Lehenik eta behin, hona hemen puzzlearen muga guztiak, termino sinpleetan berreginak:
- Kalterik gabeko bi edabe daude, 3 pozoitsu, aurrera egiteko aukera ematen duena eta atzera egiteko aukera ematen duena.
- Kalterik gabeko bi edabe bakoitzaren ezkerraldean pozoitsu bat dago.
- Bi aldeetako edabeak desberdinak dira, eta inork ez dizu aurrera egiten uzten.
- Botila handienek eta txikienek ez dute pozoirik.
- Ezkerreko bigarren botilak eta eskuineko bigarren botilak edabe bera dute.
Nola aurre egin horri? Kontuan izan dezagun hurrengo aukera. Kontuan izan, igarkizunak dioen bezala, errenkadan beste guztiak baino botila 1 txikiagoa dagoela tamainaz, eta botila 1 beste guztiak baino handiagoa.
Saia gaitezen ergelki aukera guztiak aztertzen - hartu botila bat aldi berean eta hautatu edukietarako aukera posible guztiak.
Esaterako, lehen botilak ezin du eduki 3. zk.ko murrizketa dela eta aurrera eramaten gaituen edaberik. Gainera, ez du edabe segururik 2. zk. murrizketa dela eta - ezin da pozoirik egon haren ezkerraldean. Honek edabe pozoitsuaren eta itzuleraren edabearen aukerak uzten dizkigu. Proba ditzagun bi aukerak.
Hurrengo irudietan, edabe berdeek pozoia adierazten dute, laranja edariak seguruak dira, urdinak atzera egiten duten edabeak dira eta moreak aurrera egiten duten edabeak dira.
Errepikatu dezagun prozesu hau bi lan aukeretarako: hartu bigarren botila eta probatu txandaka eduki onargarrien aukera guztiak. Honek honako hau emango digu:
Ildo honetan jokatzen jarraituz, eta zerrendatutako murrizketak hautsi gabe botila batzuk edabe batekin bete ezin diren lan-aukera guztiak baztertuz, aukera onargarri bakarrera iritsiko gara:
Jakina, ez genuen irtenbiderik aurkitzeko bermerik. Ezin liteke irtenbiderik egon, edo hainbat izan daitezke (eta hainbat soluzio badituzu, hau bera da asmakizuna ezinezkoa izatea, ez baitakizu zein edabe den zuzena).
Algoritmoa aukera guztiei aplikatzeak honako irtenbide hauek ematen dizkigu. Asmakizunaren 8 bertsio ebatzigarriak dira, 8k ez dute soluziorik eta 26k hainbat soluzio dituzte.
Irtenbideei buruz gehiago
Asmakizunaren ebatzitako bertsio guztiek badute zerbait komunean? Bai! Kontuan izan horietan botila txikienak edo handienak 2. edo 6. postuetan daudela. Horri esker, 2. eta 6. botilek edabe seguruak dituztela ondorioztatzen dugu #4 eta #5 murrizketengatik. Urrats hori gabe, ezin dugu botila hauek pozoia edukitzeko aukera kendu, eta hainbat irtenbide posible aurkitzen ditugu. Ebatzitako aukerak ere eskatzen du bigarren botila "berezia" (txikiena edo handiena) 3. edo 4. postuan jartzea. Bestela, ezin da aurkitu aurrera eramaten gaituen edabearen kokapen zehatza.
Emaitzak
Liburuaren aipu batekin amaituko dut.
Hermionek arnasa bota zuen ozen, eta Harry harrituta geratu zen irribarre egiten ari zela ohartzean - bururatu zitzaiokeen azken gauza zen. "Birria", esan zuen Hermionek. - Hau ez da magia - hau logika da, asmakizun bat. Mago handienetako askok ez dute logika bat ere, eta hemen geratuko lirateke betikoΒ».
Baina itxaron pixka bat - agian liburuko elkarrizketan oinarrituta asmakizunaren bertsio kanonikoa asmatuko dugu:
"Ados dut", esan zuen. "Botila txikienak su beltzean zehar eta Harrira eramango gaitu".
...
"Eta zeinek utziko dizu su moretik itzultzen?"
Hermionek botila biribil bat seinalatu zuen ilararen eskuinaldean.
Arraioa. Aukera honek oraindik hainbat irtenbide ematen dizkigu. Txio, DR.
Code
Puzzle hau konpontzeko eta diagramak marrazteko kodea interesatzen bazaizu, egin dezakezu .
Iturria: www.habr.com