您的位置:新葡亰496net > 奥门新萄京娱乐场 > 新葡亰496net:汉诺塔问题,河内之塔

新葡亰496net:汉诺塔问题,河内之塔

发布时间:2019-10-12 01:42编辑:奥门新萄京娱乐场浏览(164)

    写在前面:笔记全部是跟着老师一起敲的代码,最近电脑瓦特了,所以只能用老爷机的日记本记下老师上课讲的东西,但我运行不了

    规则

    1. 每次移动一个盘子
    2. 任何时候大盘子在下面,小盘子在上面
    • 递归函数

    河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家Edouard Lucas曾提及这个故事,据说创世

        首先,把汉诺塔的问题写下来:

    特别感谢的是xx学院的的刘老师,我都是边看他的课,边学他一起敲代码,然后晚上自己看,自己理解,感谢老师。

    方法

    假设共n个盘子

    • 当n=1时:
      1. 直接把A上的一个盘子移动到C上(A->C)
    • 当n=2时:
      1. 把小盘子从A放到B上(A->B)这里开始采用参数,rsc源地址=A,dst目的地址=B
      2. 把大盘子从A放到C上( A->C)rsc=A, dst=C
      3. 把小盘子从B放到C上(B->C)rsc=B, dst=C
    • 当n=3时:
      1. 把A上的两个盘子,通过C移动到B上去, 调用递归实现(A-C->B)rsc=A, trans中转=C, dst=B
      2. 把A上剩下的一个最大盘子移动到C上(A->C)rsc=A, dst=C
      3. 把B上两个盘子,借助于A,挪到C上去, 调用递归(B-A->C)rsc=B, trans=A, dst=C
    • 当n=n时:

      1. 把A上的n-1个盘子,借助于C,移动到B上去,调用递归(A-C->B)rsc=A, trans=C, dst=B

      2. 把A上的最大一个盘子,移动到C上(A->C)rsc=A, dst=C

      3. 把B上n-1个盘子,借助于A,移动到C上, 调用递归(B-A->C)rsc=B, trans=A, dst=C

    每次都是先将其他圆盘移到辅助柱子上,再将最底下的移到C,然后再把原先柱子作为辅助柱子,重复

    Python对递归的深度有限制,超过即会报错。所以一定一要注意跳出条件。

    纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根

        由三根固定的柱子ABC和不同尺寸的n个圆盘组成.开始时,这些个大小不同的圆盘依其半径大小依次套在A柱上,使大圆盘在底下。

     

    代码实现

    def move(n, a, b, c):
    '''
    汉诺塔的递归实现
    n:代表几个盘子
    a:代表第一个塔,rsc
    b:代表第二个塔,trans
    c:代表第三个塔, dst
    '''
        if n == 1:
            print(a, '=>', c)
        else:
            move(n-1, a, c, b)
            print(a, '=>', c)
            move(n-1, b, a, c)
    
    #斐波拉契数列
    #一个数列,第一个数是1,第二个数也是1,从第三个数开始,每一个数是前两个数之和
    #公式:f(1) =1, f(2) = 1, f(3) = f(1)   f(2), ..., f(n) = f(n-2)   f(n-1)
    #例如:1, 2, 3, 5, 8, 13, 21...
    
    def fib(n):
        if n == 1:
            return 1
        elif n == 2:
            return 1
        else:
            return fib(n-2)   fib(n-1)
    
    print(fib(6))
    

    石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。

        游戏的规则是:每次的圆盘从一根柱子移到另一根柱子上,但是不允许这个圆盘放在比它小的圆盘上面。

    汉诺塔问题
    - 规则
    1、每次移动一个盘子
    2、任何时候大盘子在下面,小盘子在上面

    查找指定目录下的所有文件:

    我们来把这个故事变成一个算法:

        游戏的目标是: 把所有的圆盘从按照大小的次序从A柱都移到C根柱子上,可以利用中间的B柱子,在移动过程中要始终将最大的圆盘放在最下面。

    • 方法
      1、n=1:直接把A上的一个盘子移动到C上,A-》C
      2、n=2:
      1、把小盘子从A放到B上,A->B
      2、把大盘子从A放到C上,A->C
      3、把小盘子从B放到C上,B->C
      3、n=3:
    import os
    
    def readfiles(filepath, n):
        files = os.listdir(filepath) #获取当前文件夹中的所有文件
        for fi in files: #遍历文件夹中的文件,这里获取的只是本层文件名
            fi_d = os.path.join(filepath,fi) #加入文件夹,获取到文件夹 文件,即将filepath和fi拼接,组成该文件/文件夹的绝对路径
            if os.path.isdir(fi_d): #如果该路径下的文件是文件夹
                print("*"*n)
                readfiles(fi_d,n 1)
            else:
                print("@"*n,fi)
    
    readfiles("d:/my_dir/",0)
    

     把三个柱子标为ABC 如果只有一个盘子时,将它直接搬到c,当有两个盘子,就将B做为辅助。如果盘数超过2个,将第三个以下的盘子遮起来,就很简单了,每次处理两个盘子,也就是

        声明:盘子从小到大依次编号:1,2,3...n。

    1、把A上的两个盘子,通过C移动到B上,调用递归实现

     汉诺塔
        n = 1
            1. 直接把盘子从A挪到C,A->C
        n = 2
            1. 把小盘子从A挪到B,A->B
            2. 把大盘子从A挪到C,A->C
            3. 把小盘子从B挪到C,B->C
        n = 3
            1. 把A上的两个盘子,借助C挪到B,调用递归实现
            2. 把A上剩下的大盘子挪到C,A->C
            3. 把B上的两个盘子,借助A挪到C,调用递归实现
        n = n
            1. 把A上的n-1个盘子,借助C挪到B,调用递归实现
            2. 把A上剩下的大盘子,挪到C,A->C
            3. 把B上的n-1个盘子,借助A挪到C,调用递归实现

    A->B  A->C B->C这三个步骤,而被遮住的部分是一个递归处理。如果有n个盘子,则移动完毕所需的次数为2^n-1。

        如下图:

    2、把A上剩下的一个最大盘子移动到C上,A->C

    def hano(n, a, b, c):
        if n == 1:
            print(a,"--->",c)
        elif n == 2:
            print(a, "--->", b)
            print(a, "--->", c)
            print(b, "--->", c)
        else:
            hano(n-1, a, c, b)
            print(a, "--->", c)
            hano(n-1, b, a, c)
    
    hano(5,"A","B","C") # 塔A上的5个盘子,挪到塔C
    

    看一下图,代码我会用c#和c 两种语言给出算法,然后我会把算法详细分解给大家

    新葡亰496net 1

    3、把B上两个盘子,借助于A,移动到C上去,调用递归
    4、n=n:

    • 匿名函数

      #匿名函数,计算n的n次方 f = lambda n:n**n print(f(2)) #输出结果为4 print(f(3)) #输出结果为27

    新葡亰496net 2

    总之,我们现在要解决的问题就是:将A柱子上的盘子 借助 B柱子全部挪到C柱子上,在这个过程中,小盘子永远只能在大盘子上。(借助一词用的很精妙,慢慢体会)

    1、把A上的n-1个大盘子,借助于C,移动到B上去,调用递归

    语法:函数名= lambda 参数1,参数2,参数3:返回值

    c 代码

        解决这个问题先将伪代码的思路写下来:

    2、把A上的最大盘子,也是唯一一个,移动到C上去,A->C

    注意:

    ?

    if(n>1)

    3、把B上n-1个盘子,借助于A,移动到C上去,调用递归

      1.函数的参数可以有多个,多个参数之间用逗号隔开

    void hanoi(int n,char A,char B,char C)
    {
        if(n==1)
        {
            cout<<"Move "<<n<<" from "<<A<<"  to "<< C <<endl;
        }
        else
        {
            hanoi(n-1,A,C,B); //把A柱子上第N-1个盘子通过C放到B柱子上
            cout<<"Move "<< n<<" from "<< A <<" to "<< C <<endl;
            hanoi(n-1,B,A,C); //把B上所有盘子通过A放到C上
        }
    }
      
      
    int main()
    {
        cout<<"请输入盘子数量"<<endl;
        int n;
        cin>>n;
        hanoi(n,'A','B','C');
        return 0;
    }

    {
        如果:是1个盘子
              直接将A的盘子从A移到C
        否则:
              A的n-1个盘子从A借助C移到B
              A的第n个盘子直接从A移到C
              B的n-1个盘子借助A移到C
    }

     1 def hano(n,a,b,c):
     2     '''
     3     汉诺塔的递归实现
     4     n:代表几个盘子
     5     a:代表第一个塔,开始的塔
     6     b:代表第二个塔,中间过度的塔
     7     c:代表第三个塔,目标塔
     8     '''
     9     if n==1:
    10         print(a, "-->", b)
    11     if n==2:
    12         print(a, "-->", b)
    13         print(a, "-->", c)
    14         print(b, "-->", c)
    15         return None
    16     #把n-1个盘子,从a塔借助于c塔,挪到b塔上去
    17     hano(n-1,a,c,b)
    18     print(a,"-->",c)
    19     #把n-1个盘子,从b塔,借助于a塔,挪到c塔上去
    20     hano(n-1,b,a,c)
    21 
    22 a="A"
    23 b="B"
    24 c="C"
    25 n=1
    26 hano(n,a,b,c)
    27 n=2
    28 hano(n,a,b,c)
    29 n=3
    30 hano(n,a,b,c)
    31 n=5
    32 hano(n,a,b,c)
    

      2.匿名函数不管多复杂,只能写一行,且逻辑结束后直接返回数据

    c#代码

        该思路使用递归方式解决问题,递归的精髓我还是没有掌握,总感觉少些什么,每次做题都是自己想不到怎样使用递归,但是看了解决题目的代码之后就有种恍然大悟的感觉,希望有掌握递归的朋友可以留言,解决我的困惑,非常感谢!

    List(列表)

    del:删除命令,如果使del之后,id的值和删除前不一样,则说明生成了一个新的list

    a=[1,2,3,4,5,6]
    prin(id(a))
    del a(2)
    print(id(a))
    

    del一个变量后不能继续使用此变量

    del a
    print(a) 
    报错
    

     

    列表运算

    • 使用加号链接两个列表

      a=[1,2,3,4,5] b=[5,6,7,8,9] d=['a','b','c'] c=a b d print(c)

    -使用乘号操作列表
    列表直接跟一个整数相乘
    相当于把N个列表接在一起

    a=[1,2,3,4,5]
    b=a*3
    print(b)
    

    -成员资格运算
    -就是判断一个元素是否在list里面

    a=[1,2,3,4,5]
    b=8
    #c是一个布尔值
    c= b in a 
    print(c)
    b=4
    print(b in a )
    
    #  not in
    a=[1,2,3,4,5]
    b=9
    print(b not in a )
    

     

    链表的遍历

    - for
    - while
    # for in list
    a=[1,2,3,4,5]
    #挨个打印出来里面的元素
    for i in a:
        print(i)
    
    b=["i love zhangsiqi"]
    for i in b:
        print(i)
    

    range
    in 后面的变量要求是可迭代的内容

    for i in range(1,10):
        print(i)
    print(tyoe(range(1,10)))
    

    while循环访问list(但一般不用while遍历list)

    a=[1,2,3,4,5,6]
    length = len(a)
    #index表示的是list的下标
    index = 0
    while index < length:
        print(a[index])
        index  = 1
    

     

    双层列表循环
    -a为嵌套列表,或者叫做双层列表

    a = [["one,1"],["two",2],["three",3]]
    for k,v in a :
        print(k."---",v)
    

    双层列表循环变异1
    -a为嵌套列表,或者叫做双层列表

    a = [["one",1,"eins"],["two",2],["three",3,4,5,6,7]]
    for k,v in a :
        print(k."---",v)
    报错
    

    双层列表循环变异2
    a为嵌套列表,或者叫做双层列表

    a = [["one",1,"eins"],["two",2,"zwei"],["three",3,"drei"]]
    #这个例子说明,k,v,w的个数应该跟解包出来的变量个数一致
    for k,v ,win a :
        print(k."---",v,"--",w)
    

     

    新葡亰496net:汉诺塔问题,河内之塔。列表内涵:list content

    • 通过简单方法创建列表
    • for创建

      a = ["a","b","c"] #用list a创建一个list b #下面代码的含义是,对于所有a中的元素,逐个放入新列表b中 b = [i for i in a ] print(b)

    -对a中所有元素乘以10,生成一个新的list

    a = [1,2,3,4,5,6]
    #用list a创建一个list b
    #下面代码的含义是,对于所有a中的元素,逐个放入新列表b中
    b = [i*10 for i in a ]
    print(b)
    

    -还可以过滤原来list中的内容并放入新列表中

    -比如原有裂变a,需要把所有a中的偶数生成新的列表b

    a = [x for x in range(1,35)] #生成一个从1到34的一个列表
    #把a中所有偶数生成一个新列表b
    b = [m for m in a if m%2 ==0]
    print(b)
    

    -列表生成式可以嵌套

    两个列表a,b

    a = [i for i in range(1,10)] #生成list a
    print(a)
    b = [i for i in range(100,400) if i0 == 0]#求偶数
    print(b)
    
    #列表生成可以嵌套,此时等于两个for循环嵌套
    c = [m n for m in a for n in b]
    print(c)
    
    #上面代码跟下面代码等价
    for m in a :
        for n in b:
            print(m n,end=" ")
    print()
    
    #嵌套的列表生成式也可以用条件表达式
    c = [m n for m in a for n in b if m n<250]
    print(c)
    

    关于列表的常用函数

    #len:求列表的长度
    a = [x for x in range(1,100)]
    print(len(a))
    
    #max:求列表中的最大值
    #min:同理
    print(max(a))
    
    b = ["man","female","python"]
    print(max(a))
    
    #list:将其他格式的数据转换成list
    a = [1,2,3]
    print(list(a))
    
    s = "i love zhangsiqi"
    print(list(s))
    
    #把range产生的内容转换成list
    print(list(range(12,19)))
    

     

      3.返回值和正常的函数一样,可以是任意数据类型

    ?

        汉诺塔代码如下:

    • 过滤函数
    static void Main(string[] args)
           {
               Console.WriteLine("输入盘子数量");
               int _n = Convert.ToInt32(Console.ReadLine());
               Hanoi(_n, 'A', 'B', 'C');
                 
               Console.ReadLine();
           }
     
           static void Hanoi(int n, char A, char B, char C)
           {
               if (n == 1)
               {
                   Console.WriteLine("Move {0} From {1} to {2}", n, A, C);
               }
               else
               {
                   Hanoi(n - 1, A, C, B);
                   Console.WriteLine("Move {0} From {1} to {2}", n, A, C);
                   Hanoi(n - 1, B, A, C);
               }
           }
     1 /*
     2   伪算法:
     3 if(n>1){
     4 如果:是1个盘子
     5     直接将A的盘子从A移到C
     6 否则:
     7     A的n-1个盘子从A借助C移到B
     8         A的第n个盘子直接从A移到C
     9         B的n-1个盘子借助A移到C
    10 }
    11 */
    12 #include <stdio.h>
    13 
    14 int m = 0;
    15 
    16 void HanNuoTa(int n, char A,char B, char C)
    17 {
    18     if(1 == n)
    19     {
    20         printf("将编号为%d的盘子直接从%c柱子移到%c柱子n", n, A, C);
    21           m;
    22     }
    23     else
    24     {
    25         HanNuoTa(n-1, A, C, B);
    26         printf("将编号为%d的盘子直接从%c柱子移到%c柱子n", n, A, C);
    27           m;
    28         HanNuoTa(n-1, B, A, C);
    29     }
    30 }
    31 int main(void)
    32 {
    33     char A = 'A';
    34     char B = 'B';
    35     char C = 'C';
    36     int n;
    37 
    38     printf("请输入要移动盘子的个数:");
    39     scanf("%d", &n);
    40 
    41     HanNuoTa(n, A, B, C);
    42     printf("一共挪动 %d 次n", m);
    43 
    44     return 0;
    45  }
    

    语法:filter(function,iterable)

      

        

    新葡亰496net:汉诺塔问题,河内之塔。function:用来筛选的函数,在filter中会自动的把iterable中的元素传递给function,然后根据function返回的True或者False来判断是否保留此项数据

    我们用数量为3个盘子的时候来看一下这个Hanoi(int n, char A, char B, char C)方法

        上面的代码没有注释,因为我不知道该怎样下手,下面听我分析:

    iterable:可迭代对象

     

        先来看一看汉诺塔在数学中的求解过程,

    返回一个迭代器

    1.Hanoi(n - 1, A, C, B);这个递归是把n-1个盘子按从大到小的顺序放到B柱子上,

        从这里开始:

    lst1 = [1,2,3,4,5,6,7,8,9,0]
    lst2 = filter(lambda x:x%2==0,lst1) #筛选出lst1中的偶数
    print(lst2)
    print(list(lst2))
    
    lst3 = [{"id":1,"name":'zhangsan',"age":18},
            {"id":2,"name":'lisi',"age":19},
            {"id": 3, "name": 'wangwu', "age": 20},
            {"id": 4, "name": 'zhaoliu', "age": 21}]
    
    lst4 = filter(lambda item:item['age']>19,lst3) #筛选出lst3中年龄大于19的人
    print(list(lst4))
    

         也就是n为3-1=2个盘子的时候,即Hanoi(2,A,C,B);

        令Hn表示解n个圆盘的汉诺塔游戏所需要的移动次数,建立关于序列{Hn}递推关系

      输出为:

           这个时候的B是原来的C,C为原来的B

        解:

    <filter object at 0x000002060C6F2748>
    [2, 4, 6, 8, 0]
    [{'id': 3, 'name': 'wangwu', 'age': 20}, {'id': 4, 'name': 'zhaoliu', 'age': 21}]
    

           n>1还要访问Hanoi(n - 1, A, C, B);也就是Hanoi(1,A,C,B);会把A柱子最上边的1盘子放到C柱子上去

            1. 开始时n个圆盘在A柱上,按照游戏规则用新葡亰496net 3次移动,将上面的n-1个圆盘移到B柱子上,在这些移动中最大圆盘不动。

     

          n为2 时执行完 Hanoi(n - 1, A, C, B);

            2.然后,用1次移动将最大圆盘移到C柱子上.

                                    Console.WriteLine("Move {0} From {1} to {2}", n, A, C);这是把A柱子上的第2盘子放到B(因为这个时候的C为B)柱子上去

            3.再用新葡亰496net 4次移动将B柱子上的n-1个圆盘移到C柱子上并且放到最大圆盘上面。

            Hanoi(n - 1, B, A, C);这相当于Hanoi(1,C,A,B) 把C柱子上的1盘子放到B上

            于是,得到所求递推关系:

    2 Console.WriteLine("Move {0} From {1} to {2}", n, A, C);

                                               新葡亰496net 5

      把A柱子上的最后一个盘子3放到C柱子上

            其中,初始条件新葡亰496net 6因为根据游戏规则,一个圆盘可用1次移动从A柱子放到C柱子上(这句话很重要)。

    到这个时候 A柱子已经空了

            上面的解题思路要看懂,仔细品味一下。

                   B柱子上最小的盘子1在2盘子上边

            为求解上述递推关系,对该问题首先用构造方法导出其解公式如下:

           C柱子上有最大的盘子3

            新葡亰496net 7这个公式很复杂,我没有看懂(原谅我数学没有学好),有会的朋友可以推导一下增长数学知识。但是,重点不是这个,公式没看懂没有关系,继续向下看。

    3 Hanoi(n - 1, B, A, C);上一个递归我们已经把n-1个盘子放到了B柱子上,这个方法就是把B柱子上的盘子放到C柱子上

          新葡亰496net 8

         也就是Hanoi(2,B,A,C)它再递归

          那么,我们可以得出结论:n个盘子总共需要移动的次数为新葡亰496net 9

                 先调用Hanoi(n - 1, A, C, B); 这个时候 的A是B  B为C,C为A  就是把B上的1盘子放到A柱子上

     

             Console.WriteLine("Move {0} From {1} to {2}", n, A, C); 把B柱子上的2盘子放到C柱子上

          答案有了,代码有了并且能够运行正确。好,我们的问题解决了。

              Hanoi(n - 1, B, A, C);也就是Hanoi(1,A,B,C);会把A柱子上的C盘子入到C柱子上去

          有的朋友到了这一步可能会觉得大功告成就不管了,反正要用到的时候复制一下代码就好 。那么朋友你可以去做别的事情了,下面我们讲的代码思路就和你没有关系了。

     

          首先,汉诺塔使用递归方法是很容易写出代码的,但是盘子数不能过大,否则运行的结果会刷屏并且停不下来(不信你用64个盘子试试)。

          那么递归要注意的是关键步骤,中间的过程我们是不用去关注的,那是计算机要做的事情。如果想要了解具体过程最好用盘子数为3或者4来体验。

          什么是关键步骤?(递归的精髓就在这里,我只是掌握了一点,如果有朋友看下面的思路有感觉了,那么请你在继续努力一下。)

               1.初始条件,我也称它为终止递归的条件。对于人类的思维来说就是第一步我们要做什么,但是对于计算机的递归来说就是递归到最后的结束条件。

                       其中,初始条件新葡亰496net 10因为根据游戏规则,一个圆盘可用1次移动从A柱子放到C柱子上。上面的这句话还记得吗?

                  通过这句话我们得到了下面的代码:

    1 if(1 == n)
    2     {
    3         printf("将编号为%d的盘子直接从%c柱子移到%c柱子n", n, A, C);
    4           m;
    5     }
    

               这就是在只有一个盘子的时候,我们要做的步骤,将1号盘子从A柱子移动到C柱子上。

               这时候就会有个疑问,你怎么知道在移动的过程中A变量 就是A柱子,C变量就是C柱子?万一A变量表示的是B柱子或C柱子怎么办?不是万一,是肯定在移动的过程中A变量代表的就是B柱子或者C柱子。有这个疑问说明你在思考,带着这个疑问看下面的分析

               下面的代码将会解决你的问题:

     

    1 else
    2     {
    3         HanNuoTa(n-1, A, C, B);
    4         printf("将编号为%d的盘子直接从%c柱子移到%c柱子n", n, A, C);
    5           m;
    6         HanNuoTa(n-1, B, A, C);
    7     }
    

     

    void HanNuoTa(int n, char A,char B, char C)
    

               HanNuoTa(n - 1, A, C, B);//这句话的解析是

               1. 开始时n个圆盘在A柱上,按照游戏规则用新葡亰496net 11次移动,将上面的n-1个圆盘移到B柱子上,在这些移动中最大圆盘不动。(也就是将A柱子上的n-1个盘子,借助C柱子移动到B柱子上)。

                对于我们人来说,要移动n个盘子的第一步是什么?两种选择:将1号盘子从A挪到B上,或者从A挪到C上。但是我们不确定到底怎样移动才是正确的做法。

                这时候,递归的威力发挥出来了,我们不考虑第一步是什么,万一第一步走错了那么接下来再怎么移动都是白费力气。

    好,我们换种思考方式,如果A柱子上面的n-1个盘子 借助 C柱子全部移到了B柱子上面,移动次数为新葡亰496net 12

    HanNuoTa(n-1, A, C, B);
    

     

                                             新葡亰496net 13

     

                2.然后,用1次移动将最大圆盘移到C柱子上.

     

     printf("将编号为%d的盘子直接从%c柱子移到%c柱子n", n, A, C);
    

     

                如上面第2步所述,我们要做的事情就是,把A上的第n个盘子移动到C柱子上:

                                            新葡亰496net 14

     

               3.再用新葡亰496net 15次移动将B柱子上的n-1个圆盘移到C柱子上并且放到最大圆盘上面。

    HanNuoTa(n-1, B, A, C);
    

     

               同样,如第3步所述,再将B柱子上面的n-1个盘子 借助 A柱子移动到C上:

                                            新葡亰496net 16

     

             就这样我们把n个盘子全部移动到了C上。

         

             我们看第1步、第3步的函数,和HanNuoTa原函数对比:

    void HanNuoTa(int n, char A,char B, char C)
    
         HanNuoTa(  n-1,      A,     C,      B);//第一步
    
         HanNuoTa(  n-1,      B,     A,      C);//第二步
    
         printf("将编号为%d的盘子直接从%c柱子移到%c柱子n", n, A, C);//输出目标永远是这句话,A->C,因为我们题目告诉我们把A柱子上的盘子全部移动到C上。
    

            函数在调用自己的时候,A B C三者原来的值,在调用的时候就已经被替换了,其中,我们输出的目标始终是A->C,B柱子永远是被A借助的,所以在调用的时候

            如第一步:A的n-1个盘子移动到B上,这时候A柱子上的n-1个盘子要移动,所以A = A;C柱子是被借助的,所以我们让B = C,目标是移动到B柱子上,所以要让C = B。这样就又符合我们的目标了A->C ,这时候的C已经是B了。

            同理,第二步:B上的n-1个盘子移动到C上,根据输出目标A->C,我们让A = B,B = A,C = C;这时候的A->C其实等价于B->C。

     

            对了,还有源代码中m变量是计算移动的次数的。

            这时候A柱子的n个盘子全部移动到了C柱子上,但是还有一个问题没有解决好,就是第一步:A上的n-1个盘子是怎样移动到B柱子上的,还有第三步:B上的n-1个盘子是怎样移动到C柱子上的。如果想到了这个,说明你和我当时的问题是一样的,这个问题也正是困扰我的地方。

            我当时听到的解答就是在重复上面的步骤,如上面第一步A上的n-1个盘子是怎样移动到B柱子上的可以这样解决:

                  1.将A上的n-2个盘子先移动到C上

                  2.然后,将A上的第n-1个盘子移动到B上

                  3.最后将C上的n-2个盘子移动到B上

            完美解决,prefect。

            可是我想的有点多,就是之前的A上的第n个盘子怎么办?

     

            其实,认真思考一下,画张图就很好理解了:

            1.将A上的n-2个盘子先移动到C上

                                新葡亰496net 17

     

            2.然后,将A上的第n-1个盘子移动到B上

                                 新葡亰496net 18

           3.最后将C上的n-2个盘子移动到B上

                                 新葡亰496net 19

             因为,A上是第n个盘子,比前n-1个盘子都要大,所以C的n-2个盘子是可以借助A柱子全部移动到B上的。

             接下来的步骤就是

                                新葡亰496net 20

             把A上的第n个盘子移动到C上,就和上面讲的把n-1个盘子移动到C上一样了。

             同理,第三步:B上的n-1个盘子是怎样移动到C柱子上的,也是与上面的类似的移动步骤。

             这就是我们所说的当n个盘子的时候考虑n-1个怎样移动,n-1个考虑n-2个怎样移动,一直递推到n=1,这个时候计算机已经知道A变量和C变量具体代表的是哪根柱子了,于是它就会移动,当移动完成之后,就会返回来移动第2个盘子,第2个移动完成后,在移动第3个...最终完成第n个的移动。

             

             写了这么多,不知道有没有解析清楚,完成这样一篇文章就是为了和大家分享学习中的心得。同时,朋友们看了之后,有什么地方我思考错了,帮助我指正一下。非常感谢!

     

    独乐乐,不如众乐乐!

     

    写这个文章参考的资料:

    1.

    2.

    感谢以上文章的发表者!

     

    本文由新葡亰496net发布于奥门新萄京娱乐场,转载请注明出处:新葡亰496net:汉诺塔问题,河内之塔

    关键词: