递归函数来计数。河内塔的台阶

Question

写一个递归函数，其中 returns 步解决 N 个圆盘的汉诺塔问题。

输入 n=3 输出 7

这是代码-

private static int counttoh(int n,String T1,String T2,String T3)
 {int count=0;

     if(n==0)
     return 1; 


     count+=counttoh(n-1,T1,T3,T2);
     count+=counttoh(n-1,T3,T2,T1);

     return count;
 }

我的函数 counttoh 给出 4 作为输出，如果我正在做 return count-1 它给出 1 ，任何人都可以帮我解决这个问题。

Answer 1

为了解决汉内塔，需要将所有环移到底部 (n - 1) 的顶部，然后移动底部 (+ 1)，然后将所有其他环移回顶部 (n - 1)再次）。

public static int countMoves(int n) {

    if (n == 0) return 0;

    // count(n-1) + 1 + count(n-1)
    return 2 * countMoves(n - 1) + 1;
}

Answer 2

public long toh(int N, int from, int to, int aux) 
{
    int count = 1;
        
    if(N == 1)
    {
        System.out.println("move disk "+N+" from rod "+from+" to rod "+to);
        return count;
    }
    else
    {
        count +=toh(N-1, from, aux, to);
        System.out.println("move disk "+N+" from rod "+from+" to rod "+to);
        count +=toh(N-1, aux, to, from);
    }
    return count;
}

Answer 3

#include <stdio.h>

int move(int n, char source, char destination, char spare)
{ int count = 1;
if (n==1){
    printf("\n\nMove a disc from %c to %c", source, destination);
}
else{
    count += move(n-1, source, spare, destination);
             move(1, source, destination, spare);
    count += move(n-1, spare, destination, source);
}
return count;
}

int main()
{
int n, steps;
char A, B, C;
printf("Enter the number of disc :- ");
scanf("%d", &n);
printf("\nHere A is source, B is destination, C is spare.");
steps = move(n, 'A', 'B', 'C');
printf("\n\nNumber of steps taken is %d", steps);
return 0;
}

Answer 4

带步数的汉诺塔 - 递归法代码 C++

long long toh(int N, int from, int to, int aux) {
    int count=1;
    if(N==0){
        return 0;
    }
    count+=toh(N-1, from, aux, to);
    cout<<"move disk "<<N<<" from rod "<<from<<" to rod "<<to<<endl;
    count+=toh(N-1, aux, to, from);

    return count;

}

Answer 5

long long toh(int N, int s, int d, int h) { 长长cnt=1； // 计算步数

    if(N==0) {
        return 0;
    }
    cnt += toh(N-1,s,h,d);
    cout<<"move disk "<<N<<" from rod "<<s<< " to rod "<<d<<endl;
    cnt += toh(N-1,h,d,s);

    return cnt; 
}

递归函数来计数。河内塔的台阶

Recursion function to count no. of steps in tower of hanoi

recursion

towers-of-hanoi