澳门新萄京官方网站-www.8455.com-澳门新萄京赌场网址

澳门新萄京官方网站:河内之塔,听郝斌老师_汉

2019-11-10 作者:www.8455.com   |   浏览(115)

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

规则

  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 两种语言给出算法,然后我会把算法详细分解给大家

澳门新萄京官方网站 1

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

  • 匿名函数

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

澳门新萄京官方网站 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)

 

列表内涵: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)

  

    

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柱上,按照游戏规则用澳门新萄京官方网站 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.再用澳门新萄京官方网站 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);

                                           澳门新萄京官方网站 5

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

        其中,初始条件澳门新萄京官方网站 6因为根据游戏规则,一个圆盘可用1次移动从A柱子放到C柱子上(这句话很重要)。

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

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

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

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

       C柱子上有最大的盘子3

        澳门新萄京官方网站 7这个公式很复杂,我没有看懂(原谅我数学没有学好),有会的朋友可以推导一下增长数学知识。但是,重点不是这个,公式没看懂没有关系,继续向下看。

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

      澳门新萄京官方网站 8

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

      那么,我们可以得出结论:n个盘子总共需要移动的次数为澳门新萄京官方网站 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.初始条件,我也称它为终止递归的条件。对于人类的思维来说就是第一步我们要做什么,但是对于计算机的递归来说就是递归到最后的结束条件。

                   其中,初始条件澳门新萄京官方网站 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柱上,按照游戏规则用澳门新萄京官方网站 11次移动,将上面的n-1个圆盘移到B柱子上,在这些移动中最大圆盘不动。(也就是将A柱子上的n-1个盘子,借助C柱子移动到B柱子上)。

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

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

好,我们换种思考方式,如果A柱子上面的n-1个盘子 借助 C柱子全部移到了B柱子上面,移动次数为澳门新萄京官方网站 12

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

 

                                         澳门新萄京官方网站 13

 

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

 

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

 

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

                                        澳门新萄京官方网站 14

 

           3.再用澳门新萄京官方网站 15次移动将B柱子上的n-1个圆盘移到C柱子上并且放到最大圆盘上面。

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

 

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

                                        澳门新萄京官方网站 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上

                            澳门新萄京官方网站 17

 

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

                             澳门新萄京官方网站 18

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

                             澳门新萄京官方网站 19

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

         接下来的步骤就是

                            澳门新萄京官方网站 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.

感谢以上文章的发表者!

 

本文由澳门新萄京官方网站发布于www.8455.com,转载请注明出处:澳门新萄京官方网站:河内之塔,听郝斌老师_汉

关键词: