Enviat per: Escola Mata de Jonc | 23/02/2009

La torre de Hanoi

tower_of_hanoi

La Torre de Hanoi en fusta. Imatge extreta de Wikimedia Commons

La Torre de Hanoi és un trencaclosques o joc matemàtic inventat en 1883 pel matemàtic francès Éduard Lucas.

Consisteix en tres varetes verticals i un nombre indeterminat de discos que determinaran la complexitat de la solució. No hi ha dos discos iguals, estan col·locats de major a menor en la primera vareta ascendentment, i no es pot col·locar cap disc major sobre un menor a ell en cap moment.

El joc consisteix a passar tots els discos a la tercera vareta col·locats de major a menor ascendentment.

Si voleu jugar-hi en línia, podeu fer-ho aquí.

hanoi1

Advertisements

Responses

  1. És un joc entretingut i crec que n’hauríeu de penjar més com aquest i alguns de lògica.
    Salutacions!

  2. És un joc molt entretingut i molt divertit per passar l’estona.

  3. Molt bona iniciativa, aquest blog! El seu nom m’ha recordat els meus (llunyans) estudis! I és que el joc de les Torres de Hanoi és un exemple clàssic per il·lustrar com resoldre un problema mitjançant l’anàlisi recurrent (recursivitat). De manera molt grollera vol dir definir una cosa emprant “la mateixa cosa”. Tot plegat es fonamenta en una base matemàtica: definició recurrent de conjunts i de funcions, demostracions per recurrència, etc. Per fer una definició recursiva s’han de donar, com a mínim, dues fases de raonament: base i recurrència. Per exemple, el conjunt dels sencers positius imparells (I) es pot definir per recurrència de la següent manera:
    – Base: el número 1 pertany a I
    – Recurrència: si un número “x” pertany a I, aleshores x+2 pertany a I (fàcil, no?)

    La recurrència aporta una tècnica particularment interessant en INFORMÀTICA. De fet, molts llenguatges de programació admeten funcions o procediments recursius. Aquest joc sol ser una de les primeres pràctiques ens els primers cursos d’enginyeria de software.

    Us adjunt un pseudocodi que resol les Torres. Suposem un número de discs “x” i els tres “pals”, A, B i C. Volem passar els “x” discs del pal A al pal C, emprant el pal B com a auxiliar. El que hi ha {entre claus} són comentaris al codi.

    programa el_meu_hanoi
    inici
    si x = 1 aleshores {tenim un sol disc}
    mou(A,C) {cas trivial: moure disc d’A a C, i ja està, hem acabat!}
    sinó {num_discs > 1}
    hanoi (x,A,B,C) {cridam a una acció recursiva que ens ho resoldrà}
    fsi
    fi.

    i l’acció recursiva seria:

    acció hanoi (x: sencer; A,B,C: torres) {nom de l’acció i els paràmetres que rep}
    inici
    si x = 2 aleshores {2 discs, BASE: condició de finalització}
    mou(A,B); mou(A,C); mou(B,C)
    sinó {RECURRÈNCIA, l’acció es crida a ella mateixa:}
    hanoi(x-1,A,C,B); {moure els x-1 discs de dalt de A a B, passant per C}
    mou(A,C); {moure el disc restant de A a C}
    hanoi(x-1,B,A,C) {moure els x-1 discs de dalt de B a C, passant per A}
    fsi
    fi;

    FONT: P.C.SCHOLL Algorítmica y representación de datos Ed. MASSON.

  4. El pseudocodi no ha quedat massa bé, perquè el comentari no ha conservat les tabulacions, però si cercau a Internet trobareu codis a vessar.

  5. mencanta la pagina pero podrieu posar algun joc relasinat amb un nom dalguna classe com:tangram,origami,sudokus…

  6. m’agrada julia!!! m’agrada molt lidea


Categories

%d bloggers like this: