• Tower of Hanoi Konstantin Knap • ismeretterjesztő feladatok a „elemek» • Matematika
Logikai „Tower of Hanoi”, általában nem kell bemutatni.
Vannak három sáv: A, B és C. A pin A 8 visel gyűrűt (lemezek), a legkisebb a tetején, az egymást követő magasabb, mint az előző, és az alján a legnagyobb. Két másik rúd alakú nyersdarabból. Meg kell át az összes a gyűrűk a rúd A rúd C, a B, mint a kiegészítő rúd. Ennek eredményeként, a gyűrűt a tengelyre C kell lennie ugyanabban a sorrendben, ahogyan eredetileg az interneten A. Vegyünk egy pedig több gyűrű nem. Továbbá egy soha nem hozott több gyűrű felett kevesebb.
Ez egy klasszikus változata a puzzle. A mi feladatunk, eltér a klasszikus minden egy darabban:
Ne hordja a gyűrűt csatlakozók között az A és C közvetlenül. Egy lépés, transzfer gyűrű csak vagy A, a B (vagy a B vissza A), vagy a B és C (vagy fordítva).
Hány mozog szükséges átadni a torony 8 gyűrűk ból C?
Tipp 1
Gróf mozog egy kis számú csengetés - először egy, majd két és három.
Tipp 2
Legyen k torony gyűrű. Hány lépéseket meg kell tennie, mielőtt képes lesz mozgatni a helyéről, a legalacsonyabb gyűrű a rúd B? És akkor hány mozog kell tennie, mielőtt lehetséges lesz mozgatni a B és C?
Kezdjük néhány jelölést. Legyen H (k) - a legkisebb számú mozog, melyek sikerül megoldani a feladatot, hogy ak gyűrű. Ha az előírtnál tanácsot az első nyomokat, akkor már tudja, hogy a H (1) = 2, H (2) = 8, és talán sikerült pontosan megszámolni és H (3) = 26.
Most válaszoljon a feltett kérdésekre a prompt 2. átadása előtt alacsonyabb (k-adik) a gyűrű vele kell távolítani a teljes felső része a torony a (k - 1) gyűrűt. Ehhez szükségünk van H (k - 1) mozog, és nem kevesebb. Ennek eredményeként ezek a gyűrűk lesz a C rúd, amely lehetővé teszi, hogy mozgatni az alsó gyűrűt a B (1 pass). Ezt követően, sajnos, meg kell ismételni minden korábban végzett az ellenkező irányba: hogy legyen hely az alsó gyűrű a C csapot, szükségünk van rá az egész felső része a torony, hogy távolítsa el a rúd A. Ez több H (k - 1) mozog. Ezután (1 pass) át az alsó B gyűrű a C, és újra ismétlő H (k - 1) lépés annak érdekében, hogy összegyűjtse a felső része a rúd C újra. Összesen tartott mire háromszor H (k - 1), és két egyéni haladást. Lehet azt az eredményt kapjuk gyorsabban? Nem. A lassabb? Meglepő - sem, kivéve, hogy mi lett volna egy bizonyos ponton hozta vissza a lépés, amely pontosan ezt tette.
Mi a közbenső eredmény érünk? És ez az, ami:
Az ilyen arányok, amelyekben a következő ciklusban a szekvencia lineárisan (azaz, a lineáris függvény) fejezzük ki az előző (egy vagy több) nevezzük lineáris kiújulás. A legegyszerűbb példa - beállítási módját számtani sor: ak + 1 = ak + d. Egy kissé bonyolultabb (de nagyon híres) példa - Fibonacci számok: fk + 2 = fk + 1 + fk.
Mi a következő lépés? Végtére is, ne használja ugyanazt az általános képlet - ez, mint a forgatás fegyvert a verebek.
Nyolc gyűrűk egyszerűen számolni a válasz „head-on” sorozata számítások rekurzív fenti képlet. Ő lesz egyenlő 6560. Azonban van egy módja szebb.
Hozzá yedinichku H: H '(k) = H (k) + 1. Ekkor H' (k), az ilyen képlet érvényes:
Következésképpen, H '(k) - mértani haladvány 3. Mivel ez a H' (1) = 2 + 1 = 3, akkor H „(k) = 3 k. ahonnan
utószó
Vegye figyelembe, hogy a válasz egy formula nagyon hasonló a képlet a lépések számát a klasszikus puzzle a Tower of Hanoi, már csak 2 helyett álló 3. Nem véletlen - és ennek okait nem véletlenszerű az alábbiakban ismertetjük.
Egy másik figyelemre méltó következménye az eredmény már az, hogy a folyamat változó a gyűrűk megfelelnek érvényes hely gyűrűk három bár, hogy úgy mondjam, „minden helyzetben”. Miért lehetséges érvelni? Mivel az összes pozíció számával egyenlő 3 k (határozza meg a helyzetét, mi az egyes k gyűrűk kell választani egyet a három rúd, amelyen ebben a helyzetben van - és az, hogy a gyűrűk a rúd mereven meghatározott méretük), és az egyszerű mert nincs pozíció megtalálható a folyamat változó kétszer (egyébként a folyamat lerövidíthető). És mivel kénytelenek vagyunk megtenni (3 k - 1) mozog, minden alkalommal megkapta az ismétlődő elemeket, minden pozíció érhető el.
És most - egy kis történelem.
Az egyik a templomok az indiai város Benares egy bronz lemez három gyémánt rúd. A világ teremtése a legfőbb hindu isten Brahma helyezni az első rúd 64 lemezt tiszta aranyból, annak érdekében, hogy csökkentsék a méretét, és elrendelte, hogy a szerzetesek mozgatni őket, hogy egy harmadik rúd, tiltó így egy időben, hogy egynél több lemezt és tegyük nagyobb lemez a kisebbik. Azóta Szerzetesek, nappal és éjjel, egyik a másik után, dolgozik ezen a problémán. Ha a probléma megoldódott, a templom leomlanak porrá, és a végén az élet Brahma. Ezután egy új Brahma születik, és még egyszer.
Ahhoz, hogy a legtöbb poreshat puzzle nem kell megvenni a boltban, vagy töltse le a számítógépes változata az interneten. Kisgyermekek, ez ideális a gyermekek számára meghatározott formák:
Azonban a segítségével felnőtt puzzle tehető a legváratlanabb „részletek”:
Azonban térjünk vissza a matematikai része a problémának. Bebizonyosodott, hogy az út az eredeti (összes gyűrűk vannak összeállítva a bal bar), a végső (összes gyűrűk vannak összeállítva a jobb oldalon a három rúd) állam halad át teljesen az összes érvényes pozíciókat. Csak meg kell megérteni, hogy pontosan hogyan történik. Ehhez tegyük ábrázolják minden lehetséges helyzetben a játék formájában egy grafikon:
Ábra. 4 ábra grafikon, H1 -H4 tornyok a gyűrűk száma 1-től 4 mozog oldalai mentén a legkisebb háromszögek megfelelnek az átadás a legkisebb gyűrű között mozog ezek a háromszögek (de a következő háromszög méret) - .. Az, hogy a következő gyűrű, stb Ez szabvány puzzle amikor az összes transzfer engedélyezett. De mi történik a változat, ha terminálok között az A és C nem bírja semmit?
A kép a kép a grafikon, amely nyert H3. ábrán látható. 5:
Próbáljuk megérteni, hogy miért a számlálás „nyírni”, így, ahogy ezen a képen. Erre a „nagyítás” a képpontok az eredeti dobozt és tedd információt, hogy milyen irányban a gyűrűk felel meg ezen a ponton (6. ábra) .:
Van «CBB», például azt jelenti, hogy a legkisebb gyűrű a rúd C, és a két másik - az interneten B. Ebben az esetben lehet, vagy át a kis gyűrű (standard görbét - bármely, a rudak vagy B, azaz fogadhassa ABB vagy bbb), vagy mozgassa a következő gyűrű szabadon a rúd (azaz, hogy megkapja a fülke). A mi változata az átadás-ból C és C A tiltott, úgyhogy pontosan egy ilyen két mozgás lehetetlen -, ami azt jelenti, hogy minden helyzetben, kivéve az első és az utolsó, pontosan két szomszéd. Így végig a gráf egy hosszú szaggatott vonal egy elágazás nélküli. Valójában, mert ez a mi feladatunk.
Érdekes, hogy az általunk épített utat a grafikonon (vagy inkább annak alfabetikus bejegyzés típusát aaa - BAA -. - ccc) megtalálható sok komoly matematikai (és nem csak matematikailag) a kutatás és van egy speciális neve - Gray-kód. A fő jellemzője a Gray-kód, hogy a szomszédos értékeket a „kódszó” szekvenciák különböznek csak egy számjegyet.
A fő célja a Gray-kód korunkban - az adatvédelem, az interferencia és az átviteli hibákat a kommunikációs csatornákat. Kódokat használni és a fejlesztők az elektronikus eszközöket. Például egy cikket a grafikus tablettát, hogyan történt az 1960-as grafikus RAND társaság eszközöket. Vicces, hogy a feltaláló a rajztáblát úgy vélik, Elisha Gray - a „atyja” kódot Frank Gray, úgy tűnik, nem is egy rokona Elisha és csak névrokon.
Azonban ezek a kódok és több móka alkalmazásokat. Képzeld el, hogy megpróbálja megtalálni a kulcsot a kódzár (például az állomás tároló kamrába, vagy a biztonsági öv, amit tavaly nyáron kötötte kerékpár a falnak a pajta, 7. ábra). Ha végignézi az összes kódot annak érdekében, hogy a felsorolás folyamat gyakran kell fordulni a zár túl sokáig. Például, hogy menjen 999-1000 kell forgatni mind a négy bit kerék.
Azonban, ha használja a kiválasztás a „titkos” Gray-kód (nem bináris, ami le van írva a Wikipedia bejegyzés linkre, és háromkomponensű, ami magasabb, mint az általunk épített és tizedes!) Mellszobra az „egy kis csavar a második,” hogy van annyi időt, hogy hány van kódok, mert minden következő kerül elő az előző pontosan egy fordulatot. Ez estvse 9999 másodperc. Ez, persze, ez körülbelül három órát, de még mindig nem olyan hosszú, mint egy normál keresést.
Apropó idő. Ha a klasszikus legenda a Tower of Brahma Luke és „a világ vége”, a támadó a világ vége után várható (2 64-1) mozog, a mi változata a puzzle lenne szükség szerzetesek (3 64-1) mozog. Próbáld mentálisan feltételezni, hogy hányszor több. Legalább egy nagyságrenddel - 100? 1000? 10000? Biztos vagyok abban, hogy a helyes eljárás nem hiszem szinte senki. A válasz több mint egy klasszikus több mint 10-szer 11.
És mivel mi már érintettük a téma az idő, nem tudok nem is beszélve ebben az összefüggésben figyelemre méltó történetét Eric Frank Russell „A játék a túlélésre.” Ez brutális idegenek-gombariytsy halálra ítélt főhős, földlakó a halál, de az egyéni lehetővé teszi számára, hogy játsszon semmilyen tábla végrehajtása előtt. Az eredmény a mérkőzés nem old meg semmit, de amíg a játéknak vége, a fogoly él. Mit gondol, milyen játékot választ egy hős?