Linguagem de Programação Torre de Hanoi a torre de Hanoi é um “Jogo”, onde você tem N



Baixar 34.06 Kb.
Encontro27.07.2016
Tamanho34.06 Kb.

Linguagem de Programação

Torre de Hanoi

A Torre de Hanoi é um “Jogo”, onde você tem N torres e N Peças . O jogo consiste em retirar todas as peças de uma torre e passar para uma outra torre, sem que uma peça de maior tamanho fique em cima de uma de menor tamanho.


Ex.:

Quatro (4) peças e três torres.















A B C
Neste caso deve-se retirar todas as peças da torre A e colocar na torre C. O programa deve contar o numero de movimentos necessários para isso, e mostrar o total de movimentos.

O número de movimentos dobra cada vez que se acrescenta uma nova peça, obedecendo a formula: 2n - 1
Faça um teste:
Pegue um pedaço de papel e corte 4 pedaços de tamanhos diferentes e os numere de 1 a 4, imagine três torres (A,B,C), coloque todas as peças na torre A e faça todos os movimentos necessários (e os conte) para retirar todas as peças da torre A para a torre C. Aumente uma peça (5 cinco) e faça o mesmo teste e assim sucessivamente.
História:

“Foi proposto a um grupo de monges fazer este jogo com três torres e 64 peças.


264 - 1 = 1,844674 x 10 19 - 1 = 18.446.740.000.000.000.000, de movimentos
O tempo estimado é ?
Em um computador que realize um movimento por ciclo (milhões de instruções) teríamos.

1,844674 x 10 19 movimentos, se cada ciclo fosse de 1 segundo teríamos:


1,844674 x 10 19 Segundos
3,074457 x 10 17 Minutos
5,124095 x 10 15 Horas
2,135039 x 10 14 Dias
5,849424 x 10 11 Anos = 584.942.4000.000,



Peças

Movimentos

Tempo Estimado em Segundos

3

7

7

4

15

15

5

31

31

6

63

63

7

127

127

8

255

255

9

511

511

10

1023




11

2047




12

4095




13

8191




14








Fluxograma do Programa Torre de Hanoi



Programa da Torre de Hanoi em C
#include "conio.h"

#include "stdio.h"

#include "dos.h"

#include "stdlib.h"

double cont=0;

main()


{

void hanoi(int,char,char,char);

int n,t;

char a='A',b='B',c='C';

clrscr();

printf("entre com o numero de aneis: ");

scanf("%d",&n);

clrscr();

t=time(0);

hanoi(n,a,b,c);

printf("\n%2.0f movimentos em %d segundos",cont,time(0)-t);

getch();


}

void hanoi(int n,char orige,char inter,char desti)

{

if (n>0)


{

cont++;


hanoi(n-1,orige,desti,inter);

printf("mova de %c para %c\n",orige,desti);

hanoi(n-1,inter,orige,desti);

}

}




Programa da Torre de Hanoi em Basic ou Qbasic
REM

REM Programa da calculo da torre de Hanoi

REM ETE - Cachoeira Paulista - 1996

REM
DECLARE SUB hanoi (n, orige$, inter$, desti$, cont)

CLS

cont = 0


n = 0

a$ = "A"


b$ = "B"

c$ = "C"


PRINT "Entre com o numero de aneis: "

INPUT n


t$ = TIME$

CALL hanoi(n, a$, b$, c$, cont)

PRINT

PRINT cont, " Movimentos em ", t$, TIME$, "segundos"



END
SUB hanoi (n, orige$, inter$, desti$, cont)

IF (n > 0) THEN

cont = cont + 1

CALL hanoi(n - 1, orige$, desti$, inter$, cont)

PRINT "Mova de ", orige$, "para", desti$

CALL hanoi(n - 1, inter$, orige$, desti$, cont)

END IF

END SUB


Programa da Torre de Hanoi em Pascal
program hanoit;

var


cont , n , t : integer;

a , b , c : char;


function hanoi(var n:integer;orige:char):

var


n1 : integer;

orige , inter, desti : char ;

begin

if (n>0) then



begin

cont:=cont + 1;

hanoi(n-1,orige,desti,inter);

printf("mova de %c para %c\n",orige,desti);

hanoi(n-1,inter,orige,desti);

end;


end;
begin

a:='A';


b:='B';

c:='C';


write("entre com o numero de aneis: ");

readln(n);

t:=time(0);

hanoi(n,a,b,c);

writeln(cont ,"movimentos em ",time(0) - t,"segundos");

readln(a);



end.

_


Pag.:


©principo.org 2016
enviar mensagem

    Página principal