图片 19

听郝斌老师_汉诺塔,汉诺塔问题

代码实现

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)

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

    汉诺塔代码如下:

规则

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

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 i%100 == 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)))

 

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

方法

假设共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,然后再把原先柱子作为辅助柱子,重复

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

           3.再用图片 1次移动将B柱子上的n-1个圆盘移到C柱子上并且放到最大圆盘上面。

1、把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:

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

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

 

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

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

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

                           
 图片 2

 

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

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

 

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

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

 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)

 

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

      图片 3

 

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

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

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

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

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

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

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

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

 

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

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

     

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

                                       
 图片 5

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

    从这里开始:

             
1.将A上的n-2个盘子先移动到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     }

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

2.

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

                                     
  图片 6

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

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

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

    解:

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

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

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

    

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

                                         
 图片 8

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

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

                         
  图片 9

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

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

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

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

                                     
  图片 10

 

 

         

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

     
那么,我们可以得出结论:n个盘子总共需要移动的次数为图片 11

 

 

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

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

 

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

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

图片 12

 

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

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

1.

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

                           
 图片 14

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上。

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

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

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

 

if(n>1)

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

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

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

         接下来的步骤就是

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

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

 

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

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

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

 

        3.再用图片 16次移动将B柱子上的n-1个圆盘移到C柱子上并且放到最大圆盘上面。

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

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

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

    如下图:

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

 

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

独乐乐,不如众乐乐!

写这个文章参考的资料:

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

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

感谢以上文章的发表者!

 

           
对于我们人来说,要移动n个盘子的第一步是什么?两种选择:将1号盘子从A挪到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  }

                         
  图片 19

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

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

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

       
完美解决,prefect。