Nan fen liv "Harry Potter ak wòch filozòf la" gen yon devinèt enteresan. Harry ak Hermione antre nan chanm nan, apre sa antre yo nan li yo bloke pa dife majik, epi yo ka sèlman kite li lè yo rezoud devinèt sa a:
Devan ou gen danje, e dèyè ou gen delivrans,
De moun w'a jwenn nan mitan nou an ap ede ou;
Avèk youn nan sèt pi devan w ap kontinye avanse
Lòt la pral pote ou tounen imedyatman.
Nan de nan nou w ap jwenn sèlman diven orti,
Apre sa, twa pote lanmò, kanpe nan yon ranje an kachèt.
Se konsa, chwazi ki youn ou destine gou,
Pou fè sa, nou bay kat konsèy.
Pou gremesi pwazon an te eseye kache chalè ki ka touye moun li yo,
W ap toujou jwenn li sou bò gòch diven an,
Epi konnen ke moun ki nan kwen yo gen yon kado diferan,
Men, si ou vle ale pi lwen, pa gen yonn ap ede.
Nou diferan nan gwosè tout bagay, soti nan kwen nan kwen,
Lanmò ou pa chita nan yonn ki pi piti, men se pa nan yonn ki pi gwo tou;
Dezyèm soti nan fen dwat la ak dezyèm soti nan bò gòch la
Yo gou tankou marasa, menm si yo sanble diferan.
[soti nan "tradiksyon popilè" nan liv "Harry Potter ak wòch filozòf la"]
Senpleman mete, yo bezwen konnen ki boutèy ki genyen ki posyon.
Nan atik sa a, nou pral rezoud tout 42 varyant posib devinèt sa a lè l sèvi avèk pwogramasyon epi trase yon graf rezilta yo (tankou foto ki anwo a, sèlman pi gwo).
Tann yon segond, ki kote 42 opsyon soti?
Sa a se paske kote yo nan "pi piti" ak "pi gwo" posyon yo pa endike. Pi gwo a ka nan youn nan sèt kote, ki bay 6 opsyon ki rete pou yon sèl ki pi piti a, pou yon total de 7 * 6 \u42d 42. Li pa pral posib pou chèche konnen egzakteman ki aranjman JK Rowling te gen nan tèt ou lè l ap vini. moute ak devinèt sa a, sof si li di sou li nan twitter ou. Antretan, jiskaske jou inevitab sa a rive, nou ka chwazi yon vèsyon o aza epi travay avèk li. Sepandan, pa pral gen okenn garanti sou solisyon li yo, ki se poukisa nou ap travay pou byen komen an, rezoud tout XNUMX varyant devinèt la (oswa pwouve ensolvabilite yo).
WI DESIDE DEJA
Premyèman, isit la se tout restriksyon yo nan devinèt la, refòmile nan yon fason ki senp:
- Gen de posyon inofansif, 3 anpwazonnen, youn ki pèmèt ou ale pi devan, ak youn ki pèmèt ou tounen.
- Sou bò gòch chak nan de posyon inofansif yo se yon pwazon.
- Posyon yo sou tou de bò yo diferan, e okenn nan yo pa pèmèt ou ale pi devan.
- Pi gwo ak pi piti boutèy yo pa gen pwazon.
- Dezyèm boutèy la sou bò gòch la ak dezyèm boutèy la sou bò dwat la gen menm posyon an.
Ki jan fè fas ak li? Konsidere opsyon sa a. Remake byen ke, jan devinèt la di, nan ranje a gen 1 boutèy ki pi piti pase tout lòt yo nan gwosè, ak 1 boutèy ki pi gwo pase tout lòt yo.
Ann eseye estipid ale nan tout opsyon yo - pran yon boutèy nan yon moman epi chwazi tout opsyon posib pou kontni an.
Pa egzanp, premye boutèy la pa ka genyen yon posyon ki fè nou avanse akòz restriksyon #3. Epitou, li pa gen yon posyon ki an sekirite akòz restriksyon #2 - pa gen okenn pwazon ka mete sou bò gòch la nan li. Sa a kite nou ak opsyon Petyon anpwazonnen ak Petyon ki retounen. Ann eseye tou de opsyon.
Nan imaj sa yo, posyon vèt yo se pwazon, posyon zoranj yo se bwason ki an sekirite, posyon ble yo ap deplase bak, ak posyon koulè wouj violèt yo ap avanse.
Ann repete pwosesis sa a pou tou de opsyon k ap travay - pran dezyèm boutèy la epi altènativman eseye tout opsyon kontni ki valab yo. Sa a pral ban nou bagay sa yo:
Kontinye nan sans sa a, epi jete tout opsyon k ap travay kote kèk boutèy pa ka ranpli ak yon posyon san yo pa vyole restriksyon ki anwo yo, nou pral rive nan sèlman opsyon ki akseptab la:
Natirèlman, nou pa te gen okenn garanti pou jwenn yon solisyon. Pa gen yon solisyon, oswa ta ka gen plis pase yon sèl (e si ou gen plizyè solisyon, sa a ekivalan a lefèt ke devinèt la pa ka rezoud, paske li pa konnen kilès nan posyon yo ki kòrèk).
Aplike algorithm nan tout varyant ba nou solisyon sa yo. 8 opsyon devinèt yo ka rezoud, 8 pa gen solisyon, ak 26 gen solisyon miltip.
Plis sou solisyon yo
Èske gen yon bagay an komen ant tout variants rezoud devinèt la? Wi! Tanpri sonje ke nan yo pi piti oswa pi gwo boutèy yo nan 2yèm oswa 6yèm plas. Sa a pèmèt nou konkli ke 2yèm ak 6yèm boutèy yo gen posyon ki an sekirite akòz restriksyon #4 ak #5. San etap sa a, nou pa ka elimine posiblite pou boutèy sa yo gen pwazon, epi fini ak plizyè solisyon posib. Opsyon rezoud tou mande pou dezyèm "espesyal" boutèy la (pi piti oswa pi gwo) yo dwe nan 3yèm oswa 4yèm plas. Sinon, yo pa ka jwenn kote egzak petyon ki fè nou avanse.
Rezilta
Mwen pral fini ak yon sitasyon nan liv la.
Hermione te soufle byen fò, e Harry te sezi wè li t ap souri - se dènye bagay li te kapab panse a. "Briyan," te di Hermione. "Se pa majik-se lojik, yon devinèt. Anpil nan pi gwo majisyen yo pa gen yon ons nan lojik epi yo ta dwe bloke isit la pou tout tan."
Men, hey, petèt nou ka konnen vèsyon an kanon nan devinèt la ki baze sou dyalòg la nan liv la:
"Konprann," li te di. "Pi piti boutèy la pral mennen nou nan dife nwa a, ak nan wòch la."
...
"Kilès ki pral kite ou tounen nan dife a koulè wouj violèt?"
Hermione lonje dwèt sou yon boutèy wonn sou bò dwat ranje a.
Damn li. Opsyon sa a toujou ba nou plizyè solisyon. Tweet, DR.
Kòd
Si w enterese nan kòd pou rezoud devinèt sa a ak desen dyagram, ou kapab .
Sous: www.habr.com