Puzzle-ul "Turnul din Hanoi", în general, nu are nevoie de o prezentare.
Există trei nuclee: A, B și C. Pe tija A sunt așezate pe 8 inele (discuri), în partea de sus este cel mai mic, fiecare urmând este mai mare decât cel precedent, iar la partea inferioară este cel mai mare. Celelalte două tije sunt goale. Este necesar să transferați toate inelele din tija A pe tija C, folosind tija B ca auxiliar. Ca urmare, inelele de pe tija C trebuie să fie în aceeași ordine în care au fost inițial pe tija A. Nu puteți lua mai multe inele într-o mișcare. În plus, niciodată nu puteți pune un inel mai mare pe unul mai mic.
Aceasta este versiunea clasică a puzzle-ului. Sarcina noastră diferă de cele clasice într-un singur detaliu:
Este interzisă purtarea inelelor între tijele A și C direct. Într-o mișcare, inelul poate fi transferat numai de la A la B (sau înapoi de la B la A) sau de la B la C (sau invers).
Câte mișcări vor fi necesare pentru a transfera un turn cu 8 inele de la A la C?
Sfat 1
Numără mișcările pentru un număr mic de inele - primul, apoi două și trei.
Sfat 2
Să fie inelul k în turn. Câte mișcări trebuie să faceți înainte de a putea muta cel mai jos inel la bara B din locul său? Și câte mișcări trebuie să fie făcute înainte ca acesta să poată fi mutat de la B la C?
Începem cu notația. Fie H (k) cel mai mic număr de mișcări pentru care ne putem rezolva problema pentru transferul inelelor k. Dacă luați sfatul primelor indicii, atunci știți deja că H (1) = 2, H (2) = 8, și, probabil, a reușit să numere cu precizie și H (3) = 26.
Acum, să răspundă la întrebările adresate în promptă 2. Înainte de a transfera inferior (k-lea), în inelul cu el este necesar pentru a elimina toată partea superioară a turnului de (k - 1) inel. Pentru aceasta avem nevoie de miscari H (k - 1), si nu mai putin. Ca rezultat al tuturor acestor inele va fi pe tija C, ceea ce va face posibilă deplasarea inelul inferior cu A la B (1 trecere). După aceea, din păcate, va trebui să repete tot ce sa făcut mai înainte în direcția opusă: pentru a face loc pentru inelul inferior PIN-C, avem nevoie de el toată partea superioară a turnului pentru a îndepărta tija A. Aceasta necesită mai mult H (k - 1) se mișcă. Apoi (1 trecere) pentru a transfera inelul inferior B la C, și din nou se repetă H (k - 1) se deplasează pentru a colecta pe porțiunea superioară a tijei de C din nou. În total, ne-a luat de trei ori pentru H (k - 1) și pentru încă două mișcări separate. Am putea obține rezultatul mai repede? Nu, nu este. Și mai lent? În mod surprinzător, nici nu este, cu excepția faptului că într-un anumit moment am fi revenit la mișcarea pe care tocmai am făcut-o.
Care este rezultatul intermediar pe care l-am primit? Și iată ce:
Astfel de relații, în care următorul termen al secvenței este liniar (adică, folosind o funcție liniară) este exprimat prin cel precedent (sau mai multe), se numesc recurențe liniare. Cel mai simplu exemplu este modul de setare a progresiei aritmetice: ak + 1 = ak + d. Un exemplu puțin mai complex (dar foarte renumit) este numerele Fibonacci: fk + 2 = fk + 1 + fk.
Ce trebuie să faceți în continuare? La urma urmei, nu folosiți aceleași formule generale - este ca și cum ai trage de la tun la vrăbii.
Pentru opt sonerii, puteți număra pur și simplu răspunsul "pe frunte" prin calcule succesive folosind formula de recurență de mai sus. Va fi egal cu 6560. Cu toate acestea, există un mod mai frumos.
Adăugăm o unitate la H: H '(k) = H (k) + 1. Apoi pentru H' (k) se aplică următoarea formulă:
În consecință, H '(k) este o progresie geometrică cu numitorul 3. Deoarece H' (1) = 2 + 1 = 3, atunci H '(k) = 3 k. de unde
postfață
Rețineți că răspunsul este o formulă foarte asemănătoare cu formula pentru numărul de mișcări în puzzle-ului clasic al Turnul din Hanoi, avem doar 2 în loc de picioare 3. Nu este o coincidență - și motivele pentru acest non-randomizare vor fi explicate mai jos.
O altă consecință remarcabilă a acestui rezultat o avem este că în procesul de schimbare a inelelor satisface toate inelele de locații valide pe trei bare, ca să spunem așa, „toate pozițiile“. De ce poate fi afirmat acest lucru? Deoarece numărul total de poziții egale cu 3 k (pentru a specifica poziția, suntem pentru fiecare dintre k inele nevoie pentru a alege una din cele trei bare pe care este în această poziție este - și ordinea inelelor de pe tija definite rigid de dimensiunea lor), iar pentru simplu Motivul este că nu există nicio poziție în procesul de schimbare de două ori (altfel procesul ar putea fi scurtat). Și pentru că suntem obligați să o facă (3 k - 1) se deplasează, de fiecare dată când a primit elemente recurente, vor fi obținute toate pozițiile.
Și acum - o scurtă deviere în poveste.
Într-unul dintre templele din orașul Benares din India există o placă de bronz cu trei tije de diamante. La crearea lumii suprem zeului hindus Brahma plasat pe prima tijă 64 un disc de aur pur, în scopul de a reduce dimensiunea lor, și a ordonat călugărilor pentru a le muta la o a treia tijă, interzicerea astfel la un moment dat pentru a transporta mai mult de un disc și plasați disc mai mare pe cel mai mic. De atunci, călugării zi și noapte, înlocuindu-se reciproc, lucrează la această sarcină. Odată ce problema este rezolvată, templul se va prăbuși în praf și se termină viața lui Brahma. Apoi se va naște un nou Brahma și totul se va repeta.
Pentru a rezolva singur puzzle-ul, nu trebuie să-l cumpărați în magazin sau să descărcați o versiune de calculator de pe Internet. Pentru copiii mici este ideal pentru un set de forme de copii:
Cu toate acestea, cu ajutorul unui puzzle adult puteți face și cele mai neașteptate "detalii":
Totuși, revenim la partea matematică a problemei. S-a arătat că calea originalului (toate inelele sunt asamblate pe bara din stânga) la un final (toate inelele sunt asamblate pe dreapta trei tije) de stat trece complet prin toate pozițiile valide. Rămâne doar pentru noi să înțelegem exact cum se întâmplă acest lucru. Pentru a face acest lucru, să descriem toate pozițiile posibile ale jocului sub forma unui grafic:
În Fig. 4 prezintă grafice turnuri H1 -H4 cu numărul de apeluri 1 la 4 se deplasează de-a lungul laturilor mai mici triunghiuri corespund transferului celor mai mici se deplasează în inel între aceste triunghiuri (dar în următoarea mărime triunghi) - .. Transferul inelul următor, etc. Un puzzle standard în care toate transferurile sunt permise. Și ce se întâmplă în versiunea noastră, când între barele A și C nimic nu poate fi transferat?
O imagine reprezentând un grafic care este obținut de la H3. este prezentat în Fig. 5:
Să încercăm să înțelegem de ce graficul este "tăiat" exact așa cum se arată în această imagine. Pentru a face acest lucru, vom "mări" imaginile punctelor de pe graficul original și le punem informații despre locația inelelor corespunzătoare acestui punct (Figura 6):
Acolo «CBB», de exemplu, înseamnă că cel mai mic inel este în tijă C, iar alte două - pe web B. In acest caz, se poate fie să transfere inelul mic (grafic standard, - prin oricare dintre tije A sau B, adică primesc abb sau bbb) sau transferați inelul următor la o tijă liberă (adică, apelați la o cabină). În versiunea noastră a transferului de la A la C și de la C la A este interzisă, astfel încât exact una dintre aceste două mișcări este imposibil - ceea ce înseamnă că fiecare poziție, cu excepția prima și ultima, are exact doi vecini. Astfel, tot drumul prin grafic se dovedește a fi o lungă linie întreruptă fără ramuri. De fapt, aceasta este exact sarcina noastră.
Este interesant faptul că ne-am construit cale prin graficul (sau, mai degrabă, în ordine alfabetică tipul de intrare aaa sa - BAA -. - CCV) se găsește în multe cercetări serioase matematică (și nu numai matematic) și are un nume special - cod Gray. Caracteristica principală a codurilor Gray este aceea că valorile adiacente din secvența "cuvintelor de cod" diferă doar într-o singură cifră.
Scopul principal al codurilor Gray în zilele noastre este de a proteja informațiile de interferențe și erori atunci când transmit prin canale de comunicare. Utilizați codurile și dezvoltatorii de dispozitive electronice. De exemplu, articolul despre tablete grafice arată cum a fost făcut în anii 1960 în dispozitivele grafice ale RAND. Este amuzant că inventatorul a tabletei grafice cred că Elisha Gray - ca „părintele“ cod Frank Gray, se pare că, nici măcar o rudă de Elisei și doar un tiz.
Cu toate acestea, aceste coduri au aplicații mai amuzante. Imaginați-vă că încercați să găsiți cheia de blocare de cod (de exemplu, pe camera de stocare sau stație de pe o bandă pe care vara trecută legat bicicleta pe peretele hambar; Figura 7.). Dacă treceți prin toate codurile în ordine, atunci în procesul de busting, va trebui de multe ori să închideți blocarea prea mult timp. De exemplu, pentru a vă deplasa de la 999 la 1000, trebuie să rotiți toți cei patru biți ai roții.
Cu toate acestea, dacă utilizați pentru selectarea codului „secret“ Gray (nu binar, care este descrisă în link-ul de intrare Wikipedia, și ternare, care este mai mare decât ne-am construit și zecimale!), Bustul în „o poftă de mâncare mică în al doilea,“ să ia aveți la fel de mult timp, cât de multe sunt coduri, pentru că vor fi obținute de cel precedent prin exact un viraj fiecare următoare. Asta este tot 9999 secunde. Desigur, tot timpul aproximativ trei ore, dar nu la fel de mult, ca la căutarea standard.
Apropo, cu timpul. În cazul în care legenda clasică a Turnului lui Brahma Luca și „sfârșitul lumii“, la sfârșitul ofensivei lumii este de așteptat după (2 64 - 1) se deplasează, în versiunea noastră a puzzle-ului ar avea nevoie de călugări (3 64 - 1) se mută. Încercați să vă imaginați în mintea dvs. de câte ori acest lucru este mai mult. Cel puțin în ordinea magnitudinii - în 100? La 1000? La 10.000? Sunt sigur că aproape nimeni nu va ghici ordinea corectă. Răspunsul nostru este mai clasic decât în 10 11 ori.
Și, din moment ce ne-am atins deja pe această temă de timp, nu pot să nu mai vorbim în legătură cu aceasta poveste remarcabila a lui Eric Frank Russell, „Jocul de supraviețuire.“ Este brutal străinilor-gombariytsy protagonist condamnat, pămîntean la moarte, dar obiceiul lor îi permite să joace în orice tabla de joc înainte de execuție. Rezultatul luptei nu rezolvă nimic, dar până la terminarea jocului, prizonierul va trăi. Ce crezi, ce joc alege eroul?
Articole similare
Trimiteți-le prietenilor: