Hanoi Tower´s problem using recursion

9 views (last 30 days)
Hello i´m developping a program to solve the hanoi tower problem using a recoursive function but it doesn´t seens to work.I´m going to put the code that i have writen and going to explain the ideia and the data matrixes.
Main program:
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
N=5;
torre_final =1;
vec_movimentos = zeros ((power(2,N)-1),4);
for i=1:size(vec_movimentos,1)
vec_movimentos(i,1)=i;
end
tabuleiro = zeros(N,3);
tabuleiro(:,1)=1:N;
n_jogada =1;
[vec_movimentos] = hanoi_code(N,torre_final,vec_movimentos,n_jogada,tabuleiro);
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
hanoi_code is my recursive function and the matrix 'tabuleiro' represents the 3 tower´s with N disk. 'vec_movimentos' is a matrix that describes the moves that the user has to do in order to resolve the problem. The first column of 'vec_movimentos' is the counter of the number of moves; the second column is what piece the user has to move; the third column is the inicial tower that the piece is located at; the forth column is the final cloumn that the piece is going to be move to;'torre_final' is a variable with 2 possible values: 1 or 2. If torre_final = 1 then the solution is going to be formed in the center tower; if torre_final=2 then the solution is going to exist in the final right tower
hanoi_code:
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
function [vec_movimentos] =hanoi_code(N,torre_final,vec_movimentos,n_jogada,tabuleiro)
%torre_final == 1 consiste no deslocamento para a torre 1 posição à direita
%torre_final == 2 consiste no deslocamento para a torre 2 posições à
%direita
if N > 0;
hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);
shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro);
hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);
else
return;
end
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
we have here the recursive code ,'n_jogada' indicates what the current move is.
shift:
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
function [vec_movimentos] =shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro)
vec_movimentos(n_jogada,2)=N;
[inicio,fim]= game(N,tabuleiro,torre_final);
vec_movimentos(n_jogada,3)=inicio;
vec_movimentos(n_jogada,4)=fim;
n_jogada =n_jogada+1;
end
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
It´s not necessary to display the game code because the program doesn´t get there and i have already test this part of the code and it seens to work.
My main problem is that the recursion seens not to work. When i run the program the 'vec_movimentos' remains the same , and the 'tabuleiro' also remains in the original configuration. The 'n_jogadas' that should = 31 , is equal =1. 31 because the numbers of moves if 2^(N)-1 , and N=5. Any ideia what´s the problem? What´s wrong with the recursion part?
Thank you in advance

Accepted Answer

Walter Roberson
Walter Roberson on 29 Jul 2015
Remember that calling
hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);
computes a value by calling hanoi_code, and then discards the value because you did not assign it to a variable and the semi-colon says not to bother to print the result either.
  3 Comments
Stephen23
Stephen23 on 29 Jul 2015
Edited: Stephen23 on 29 Jul 2015
vec_movimentos = hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);
vec_movimentos = shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro);
MATLAB uses pass-by-value, not pass-by-reference, so if you want the variable to change then you need to allocate it as an output.
João Domingos
João Domingos on 29 Jul 2015
Thank you Stephen Cobeldick , with my recent changes and your help the code already works perfectly. Ignore the second version of the code that i posted that´s not the final version. If anyone what´s to try it i will post the final version here. Thank you again for the help Stephen Cobeldick

Sign in to comment.

More Answers (1)

João Domingos
João Domingos on 29 Jul 2015
Edited: Walter Roberson on 29 Jul 2015
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
%Inputs
N=5;
torre_final =1;
%Vector com os movimentos a tomar. Linhas representam a peça a mexer , e a
%coluna representa qual o destino. Por exemplo entrada i ,j indica que
%temos de mover a peça i para a torre j. A terceira dimensão indica o
%número da jogada , por exemplo entrada i,j,k indica que a jogada k
%consiste em mover a peça i para a torre j
vec_movimentos = zeros ((power(2,N)-1),4);
for i=1:size(vec_movimentos,1)
vec_movimentos(i,1)=i;
end
tabuleiro = zeros(N,3);
tabuleiro(:,1)=1:N;
n_jogada =1;
[vec_movimentos,n_jogada,tabuleiro] = hanoi_code(N,torre_final,vec_movimentos,n_jogada,tabuleiro);
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
function [vec_movimentos, n_jogada,tabuleiro] =hanoi_code(N,torre_final,vec_movimentos,n_jogada,tabuleiro)
%torre_final == 1 consiste no deslocamento para a torre 1 posição à direita
%torre_final == 2 consiste no deslocamento para a torre 2 posições à
%direita
if N == 0;
return
else
hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);
[vec_movimentos, n_jogada, tabuleiro]= shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro);
hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);
end
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
function [vec_movimentos, n_jogada, tabuleiro]
=shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro)
vec_movimentos(n_jogada,2)=N;
[inicio,fim,comparacao]= game(N,tabuleiro,torre_final);
vec_movimentos(n_jogada,3)=inicio;
vec_movimentos(n_jogada,4)=fim;
aux_1 = find(tabuleiro(:,inicio)==0);
if isequal(isempty(aux_1),1)==0
tabuleiro(max(aux_1)+1,inicio)=0;
else
tabuleiro(1,inicio)=0;
end
aux = find(tabuleiro(:,fim)==0);
if isequal(isempty(aux_1),1)==0
tabuleiro(max(aux),fim)=N;
else
tabuleiro(5,fim)=N;
end
n_jogada =n_jogada+1;
end
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
function [inicio,fim,comparacao]= game(N,tabuleiro,torre_final)
fim = 0;
%No vector de comparações vamos adicionar uma linha a mais que contém
%informação sobre quais as 2 torres possíveis para movimentação. As
%restantes linhas e colunas formam o tabuleiro com portas e paredes de
%jogadas possíveis
comparacao = zeros(2,2);
indice = find(tabuleiro ==N);
%Ver posição dos indices e conforme estejamos na primeira, segunda , ou
%terceira coluna o vector de comparações contém informação relativa às
%outras 2 torres. 1 indica que é possivel mover a peça para essa posição 0
%indica que não. Vector comparações com 2 linhas e 2 colunas. 1 linha
%indica as 2 torres que são analisadas. Segunda linha indica se a repectiva
%torre é possível ou não a movimentação.
if (indice >=1 & indice<=5)
inicio=1;
comparacao(1,1)=2;
comparacao(1,2)=3;
aux = find(tabuleiro(:,2));
if isequal(isempty(aux),1)==0
if (tabuleiro(min(aux),2)>N)==1
comparacao(2,1)=1;
end
end
if any(tabuleiro(:,2))==0
comparacao(2,1)=1;
end
aux = find(tabuleiro(:,3));
if isequal(isempty(aux),1)==0
if (tabuleiro(min(aux),3)>N)==1
comparacao(2,2)=1;
end
end
if any(tabuleiro(:,3))==0
comparacao(2,2)=1;
end
end
if (indice >=6 & indice<=10)
inicio= 2;
comparacao(1,1)=3;
comparacao(1,2)=1;
aux = find(tabuleiro(:,3));
if isequal(isempty(aux),1)==0
if(tabuleiro(min(aux),3)>N)==1
comparacao(2,1)=1;
end
end
if any(tabuleiro(:,3))==0
comparacao(2,1)=1;
end
aux = find(tabuleiro(:,1));
if isequal(isempty(aux),1)==0
if (tabuleiro(min(aux),1)>N)==1
comparacao(2,2)=1;
end
end
if any(tabuleiro(:,1))==0
comparacao(2,2)=1;
end
end
if (indice >=11 & indice<=15)
inicio=3;
comparacao(1,1)=1;
comparacao(1,2)=2;
aux = find(tabuleiro(:,1));
if isequal(isempty(aux),1)==0
if (tabuleiro(min(aux),1)>N)==1
comparacao(2,1)=1;
end
end
if any(tabuleiro(:,1))==0
comparacao(2,1)=1;
end
aux = find(tabuleiro(:,2));
if isequal(isempty(aux),1)==0
if (tabuleiro(min(aux),2)>N)==1
comparacao(2,2)=1;
end
end
if any(tabuleiro(:,2))==0
comparacao(2,2)=1;
end
end
%Tomar decisão conforme torre_final
if torre_final ==1
if comparacao(2,1)==1
fim = comparacao(1,1);
else if comparacao(2,2)==1
fim = comparacao(1,2);
end
end
end
if torre_final ==2
if comparacao(2,2)==1
fim = comparacao(1,2);
else if comparacao(2,1)==1
fim = comparacao(1,1);
end
end
end
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
Here´s the code so you can run ti and try it. The first line of the movements matrix appears values both wrong ones. I dont get get why the first N to be used in shift is N=5 , it should be N=1 , because the recursion goes from N=5 to N=0 then the hanoi_code function return´s , and we have N=1 for the first shift call.
Thank you in advance

Categories

Find more on Chemistry in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!