首页 > 试题广场 >

汉诺塔一共为2*N，2个一样大小，有编号顺序每次只能移动一个

[问答题]

汉诺塔一共为2*N，2个一样大小，有编号顺序每次只能移动一个大的不能叠在小得上面移动完之后，相同大小的编号必须和原来一样问最小要移动多少次？如A1 A2 B1 B2 C1 C2……这样叠，A<B<C ….B 不能放在 A 上面， C 不能放 BA 上面，移动到另外一个柱子后，还必须是 A1 A2 B1 B2 C1 C2….

帕瞳瞳~

#include <stdio.h>
#include <stdlib.h>

void move(int n,char a,char b,char c)
{
    if(n==1)
        printf("\t%c->%c\n",a,c);    //当n只有1个的时候直接从a移动到c
    else
    {
        move(n-1,a,c,b);            //第n-1个要从a通过c移动到b
        printf("\t%c->%c\n",a,c);
        move(n-1,b,a,c);            //n-1个移动过来之后b变开始盘，b通过a移动到c，这边很难理解
    }
}
main()
{
   int n;
   printf("please put in the number you need to move:\n");
    scanf("%d",&n);
    move(n,'a','b','c');
}

发表于 2015-05-30 11:15:02 回复(1)

问天

如果每个大小都不相同，一共2N个，那么移动(2^2N) -1。。

同大小的总有两个，是否可以当做一个，因为大小一样可以覆盖，那就是(2^N) -1 次，但是毕竟还是两个，当做一个还是要分两步移动，也只需要分两步移动（同大小的可颠倒覆盖），【 (2^N) -1 】* 2

发表于 2015-09-06 15:35:51 回复(0)

樱桃诗翡雨

n = 1，f(n) = 2;

n = 2, f(n) = 2 + 2 +2 = 2f(n-1)+2;

n = 3, f(n) = f(2)+ 2 + 2 +2+2 = 2f(2) +2 = 2f(n-1) +2

可证的 f(n) = 2f(n-1)+2 ,n 属于正整数，且 f(0) = 0;

#include "stdafx.h"
#include <conio.h>

static int c = 1 ; //局部变量i申明为 static
void move(int i ,int j, char x , char y)
{
printf("第%d步: %d_%d from %c --> %c \n", c++ , i ,j , x , y);
}
void hanoi(int i , char A , char B , char C)
{
    if(i == 1)
    {
        for( int j = 0;j<2;j++ )
        {
            move(i ,j, A , C);

        }
    }
    else
    {
        hanoi(i - 1 , A , C , B); //函数递归调用
        for( int j = 0;j<2;j++ )
        {
            move(i ,j, A , C);
        }
        hanoi(i - 1 , B , A , C);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    char z = 'z';

    while ( z != 'b' && z != 'B')
    {
        int n ;
        printf("请输入n的值：");
        scanf("%d",&n);

        hanoi(n , 'A' , 'B' , 'C');
        printf( "按任意键继续，输入 B 退出程序\n" );

        z = getch();
        c = 1;
    }


    return 0;
}

发表于 2015-06-03 11:11:28 回复(0)

MaoNiu

2^(2*N)-1

发表于 2015-05-30 22:49:47 回复(0)

igigmn

(2N)*2-1 = 4N-1

发表于 2015-05-30 21:17:57 回复(0)

247077346@qq.com

public class Test2 {

public static void main(String[] args) {
  int n =2;
  Test2 Q = new Test2();
  Q.Hanoi(n, 'A', 'B', 'C');
}
public void Hanoi(int n ,char A ,char B, char C){

  if (n>0){
   Hanoi(n-1, A,C,B);
   System.out.println("移动"+A+"到" +B);
   Hanoi(n-1,C,B,A);
  }
}

}

发表于 2015-05-30 20:21:49 回复(0)