四汉诺塔问题

思路

• 类似于经典汉诺塔问题 ,需要借助中间的两个柱子移动弄到第三个柱子上

  过程

• 有 a, b, c, d 三个柱子 , 将a柱子上的n个圆盘放到d柱子上

1. 将a上的n -k个圆盘通过c,d 柱子移动到b柱子上(递归,)
2. 将a上剩余的k个圆盘通过c柱子移动到d柱子上(递归, 三汉诺塔问题)
3. 将b上的n-k个圆盘,通过a,c柱子移动到d柱子上(递归)

详细过程

1. k 的确定

• n个三汉诺塔的移动次数为2-1
• 设f(n)为四柱汉诺塔的移动次数 ,则有 : f(n) = 2f(n-k) + 2- 1
  • 其中k ∈ (1,n) , 由于k 会影响f(n)的大小 , 所以最小移动次数为 MIN{2f(n-k) + 2- 1 | k ∈ (1,n) }
  • k 是第一次移动后底部剩余的圆盘数量
  • 四汉诺塔问题的核心是 , 当k为何值时 , 有最优解
• 如何求MIN { f(n) }
  • 求解 MIN f(n) 就是求解K值
  1. 枚举k
     • 当n=1, k= 0 时 , MIN{f(n)} = 1
     • 然后通过 MIN{2f(n-k) + 2- 1 | k ∈ (1,n) } , 从 (n,k) = (1,0 ) , 求到 (n,k) = (n,n)
       • 初始条件为f(1) = 1
  2. 动态规划

2. a [n-k] —c,d—> b

• 将a柱子上的n-k个圆盘借助c,d 移动到b柱子上 , 调用hanio4

  3. a[k] —c—>d

• 然后将a柱子上的剩余的k个圆盘借助c , 移动到b柱子上

• 注意 : 由于b柱子上的所有圆盘都大于b柱子上的 , 所以只可以借助c圆盘 ,此时就相当于是三柱子汉诺塔

  4. b[n-k] —a,c—>d

• 将b柱子上的n-k个圆盘借助a ,c柱子移动到d柱子上 , 调用hanio4

代码 :

#include<stdio.h>
#include<math.h>
typedef long long ll; 
//通过公式计算出的移动步数
double moves[100];
//第一类移动后a柱剩余的盘子
int Ks[100]={0};
//通过hanio4 方法计算出的移动步数
int step_nums = 0;
void move(char a, char b) {
    //输出移动的起点和终点
    //printf("%c -> %c\n", a, b);
    step_nums++;
}
//三柱汉诺塔移动问题
void hanio3(int n,char a,char b,char c){
    if(n==1){
        move(a,c);
    }else{
        hanio3(n-1,a,c,b);
        move(a,c);
        hanio3(n-1,b,a,c);
    }
}
//四柱汉诺塔移动问题
void hanio4(int n, char a, char b, char c, char d) {
    if (n == 1) {
        move(a, d);
    }
    else {
        hanio4(n - Ks[n], a, c, d, b);
        hanio3(Ks[n],a,c,d);
        hanio4(n - Ks[n], b, a, c, d);
    }
}
int main()
{
    {
        //有零个的不需要移动  
        moves[0] = 0;
        moves[1] = 1;
        int i= 0;
        int min = 0xFFFF;
        //计算第一类移动的底部剩余盘子的数量   求解满足最小移动次数的K值
        for(int n = 2;n<64;n++){// 盘子的数量 
            moves[n] = min;
            for(int k = 1;k<n;k++){ //第一次移动剩余盘子的数量 
                ll tmp = 2*moves[n-k] + pow(2,k) - 1 ; 
                if(k==0||tmp<=moves[n]){
                    moves[n] =  tmp;
                    Ks[n] = k;
                }
            }
        } 
    }
    int n;
    do
    {
        scanf("%d", &n);
        if (n < 0) {
            break;
        }
        hanio4(n, 'a', 'b', 'c', 'd');
        printf("步骤数量 : %d   (校验 : %.0lf)\n", step_nums,moves[n]);
        step_nums = 0;
    } while (true);
    return 0;
}