为什么这些额外的代码行会导致 "Towers of Hanoi" 步数增加?

Why does these extra lines of code cause the "Towers of Hanoi" number of moves to increase?

我的讲师在测试中问了我们以下问题:

"给定以下代码:

int count=0;
static void towersOfhanoi(int n, char source, char target, char spare)
    {    
        count++;
        if (n==1)
            System.out.println("move a disk from "+source+" to "+target);
         else
         {  
            towersOfhanoi(n-1, source, spare, target); 

            System.out.println("move a disk from "+source+" to "+target);

            towersOfhanoi(n-1, spare, target, source); 
            towersOfhanoi(1, spare, source, target); 
            towersOfhanoi(n-1, source, spare, target); 

towersofhanoi(11, A,B,C) 执行后的移动值是多少?

我回家编了这个程序,移动次数增加了,在我插入这些代码行之前,我将其称为A(使用11个磁盘,产生118097移动!):

            towersOfhanoi(n-1, spare, target, source); 
            towersOfhanoi(1, spare, source, target); 
            towersOfhanoi(n-1, source, spare, target); 

在插入这些代码之前,我将这些代码行放在了原位。我将其称为 B(使用 11 个磁盘,产生 2047 次移动):

            towersOfhanoi(n-1, spare, target, source); 

我的问题是,A中的3行代码做了什么?为什么步数会改变,有没有计算步数的公式?我知道可以使用 B 的“(2^11) -1”计算移动量。任何反馈都会有所帮助。

嗯,B 行是汉诺塔问题的正确解法。 A 而不是 B 的三行完全按照他们所说的去做:他们用这些参数递归地调用函数。第一行与B相同,所以是正确的。就问题而言,其他两行没有意义。你把它们放在那里,所以问题更多:你为什么要那样做?

我猜您想改为执行以下操作:

   if (n==1) {
        System.out.println("move a disk from "+source+" to "+target);
   } else {
        towersOfhanoi(n-1, source, spare, target); 
        towersOfhanoi(1, source, target, spare); 
        towersOfhanoi(n-1, spare, target, source); 
   }

这将是汉诺塔问题的另一个正确表达式,移动次数与原始 B.

关于公式:如果我们定义n盘的移动次数为N(n),则原解的解为移动次数(见源码):

N(n) = N(n-1) + 1 + N(n-1) 
     = 2 * N(n-1) + 1
     = 2 * (2 * (2 * ... (2 * 1 + 1) ... + 1) + 1) + 1)
     = 2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 1
     = (1 - 2^n) / (1 - 2)
     = 2^n - 1

对于您的 A 代码也有类似的推理:

N(n) = N(n-1) + 1 + N(n-1) + 1 + N(n-1)
     = 3 * N(n-1) + 2
     = 3^(n-1) + 2 * (3^(n-2) + ... + 1)
     = 3^(n-1) + 2 * (1-3^(n-1)) / (1-3)
     = 2 * 3^(n-1) - 1