python Hanno塔

作者:操作系统    发布时间:2020-02-02 23:44     浏览次数 :

[返回]

图片 1

基本介绍

图片 2汉诺塔是由三根杆子A,B,C组成的。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:每次只能移动一个圆盘;大盘不能叠在小盘上面。提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。问:如何移?最少要移动多少次?汉诺塔是根据一个传说形成的一个问题:

有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:

每次只能移动一个圆盘;

大盘不能叠在小盘上面。

提示:可将圆盘临时置于A杆,也可将从B杆移出的圆盘重新移回B杆,但都必须尊循上述两条规则。

问:如何移?最少要移动多少次?

python实现方法:递归法

我们最终得到的结果是将所有的圆盘按规定的方法从B移到C,对于C来说,当第n个盘子(最大的那个盘子)移动到C时,已经固定了,以后的操作都不用动这块盘子,而当这个盘子从A移动到C的前一步是其它n-1个盘子应该是在B上了,依次类推,当第n-1个盘子从B移动到C前,之前的n-2个盘子应该是在A上

总结以上的思路,可以将整个过程分三步走:

Step1.把除了最大的环之外的环,从A移动到B
A -> B
Step2.将最大的环从A移动到C
A -> C
Step3.把除了最大的环之外的环,从B移动到C
B -> C

参照下图

图片 3

(a)是初始状态,也就是递归的起点,我们假设n=4, move(4,A,B,C)还是请参考现在最高的分的代码哈~写这个是帮助大家更清楚那个让人压力大的(“抽象”)两个字,哈哈
<这个函数要实现的功能是把n个环从A按照一定的规则,借助B,移动到C>

(b)是step1完成的时候的状态,已经将所有的n-1,这里也就是3个环从A挪到了B
<第一处递归,move(n-1,A,C,B) 这个函数要实现将n-1个环从A,借助C,移动到B>

(c)是step2,此时需要将第n个,也就是第四个最大的环从A挪到C
<move(1,A,B,C),或者干脆直接print("A -> C")>

(d)是step3,此时需要将B上面的n-1个环从B挪到C<第二处递归>
<第二处递归,move(n-1,B,A,C) 这个函数要实现将n-1个环从B,借助A,移动到C>

 

Python编写代码如下:

#!/usr/bin/python

def move(n,a,b,c):

If n == 1:

  Print(a,’-->’,c)

else:

  Move(n-1,a,c,b)  #将A上面的n-1个盘子通过C移动到B

  Move(1,a,b,c)     #将A上最大的那个盘子通过B移动到C

  Move(n-1,b,a,c)  #将B上的n-1个盘子通过A移动到C

 

题目:把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。输入n,打印出S的所有可能的值出现的概率。

面试的时候,碰到最后一道题,如下:一开始我以为这是他们公司自己出的道普通的算法题,就没有多想,就画了图,把代码补充完整,代码如下:UpAll{if(n==1)UpOne(1);elseif(n==2)UpOne(1);UpOne(2);elseUpAll(n-1)DownAll(n-2);UpOne(n);}本来做完就好了,但是回过头去看那条件的时候,我就发现很纠结,一根棒子串过环,而且还是按顺序的串起来,那怎么可能做到前面还有环的时候,还可以取下后面的环,思来前后,实在受不了,叫HR过来,想问问出题的技术总监,这题是不是他们自己出,我感觉这题有问题,想聊聊,但是HR说总监没在,说题没有问题,迫于坚持真理的情况下,我把上面写的代码划掉,如上图所看到的,我只写了:基于理性,我实在是无法想象怎么在没有去掉前环的情况下,取掉后面的环!这就和我当初读书考试写作文的时候,一直鸟穿越太平洋,请发挥你的想象力,写一篇不少于800字的作文,请试想一下你让一个理科生如何接受一只鸟能横穿太平洋,那次作文我也只答了:无法想象一只鸟能穿越太平洋,违法了常理!这些不按常理出牌的东西,让我这个理科生很是难受,也不会去接受!于是面试完我回来查了下九连环,百度了下,原来是真的存在的东西,当时吓尿,世界三大智力玩具之一,好叼,玩法也和上面的介绍的一样,要取下或者装上n,那么n-1必须在且n-2必须取下,真是涨见识了,中国发明的东西真是高深莫测,又再一次毁了我的理念观,特来发此贴,让大家知道我们中国人的智力不是常理能够解释的!像中国的智力玩具-----九连环致敬!其实九连环的算法十分简单,我这也简单介绍,网上也有了,按上面的题,你画个图就可以清楚得出思路要取掉这个九连环必须从最低层开始,也就是2或者3环开始,这就涉及到你要取环是单数还是双数,如果输入的双数,那你就从2环开始取下,如果是单数,那得从1环开始,所以,得先判断然后再递归,if(n==1){DownOne(1)}elseif(n==2){DownOne(2);DownOne(1);}然后才是第3种情况开始的递归取,假设这个n是5,你要取掉5,那么你必须取掉5-2之前的环也就是第3个环,DownAll,现在5-1的环也就是4环还在,所以可以取掉5环也就是n,DownOne,那现在5环取掉了,接着就是取掉第4个环,要取掉第4个环就必须第3个环在,前2个环不在,现在前3个环不在,所以要UpAll,然后就是去下个环的参数了递归DownAll,这是取环的思路,装环的思路也和这个差不多,我这里就不多解释了,代码上面有,不过我没有经过检验,错了可以提出,我改,这里就不做多检验了。完成代码:DownAll{ifDownOne;elseif{DownOne;DownOne;elseDownAll;DownOne;UpAll;DownAll;}UpAll{if(n==1)UpOne(1);elseif(n==2)UpOne(1);UpOne(2);elseUpAll(n-1)DownAll(n-2);UpOne(n);}特此声明,我写此贴不是想吐槽面试,而是想多点人认识下中国的传统东西,不只是只要外国人的东西才考智力的,中国的东西也很博大精深的,希望可以看到多点这些把中国传统东西用代码解出来的帖子!好了,散分!

分析:玩过麻将的都知道,骰子一共6个面,每个面上都有一个点数,对应的数字是1到 6之间的一个数字。所以,n个骰子的点数和的最小值为n,最大值为6n。因此,一个直观的思路就是定义一个长度为6n-n的数组,和为S的点数出现的次数保存到数组第S-n个元素里。另外,我们还知道n个骰子的所有点数的排列数6^n。一旦我们统计出每一点数出现的次数之后,因此只要把每一点数出现的次数除以n^6,就得到了对应的概率。

该思路的关键就是统计每一点数出现的次数。要求出n个骰子的点数和,我们可以先把n个骰子分为两堆:第一堆只有一个,另一个有n-1个。单独的那一个有可能出现从1到6的点数。我们需要计算从1到6的每一种点数和剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子还是分成两堆,第一堆只有一个,第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加,再和剩下的n-2个骰子来计算点数和。分析到这里,我们不难发现,这是一种递归的思路。递归结束的条件就是最后只剩下一个骰子了。

 

 

 1 int g_maxValue = 6;
 2   
 3  void PrintSumProbabilityOfDices_1(int number)
 4  {
 5      if(number < 1)
 6          return;
 7   
 8      int maxSum = number * g_maxValue;
 9      int* pProbabilities = new int[maxSum - number + 1];
10      for(int i = number; i <= maxSum; ++i)
11          pProbabilities[i - number] = 0;
12   
13      SumProbabilityOfDices(number, pProbabilities);
14   
15      int total = pow((float)g_maxValue, number);
16      for(int i = number; i <= maxSum; ++i)
17      {
18          float ratio = (float)pProbabilities[i - number] / total;
19          printf("%d: %fn", i, ratio);
20      }
21   
22      delete[] pProbabilities;
23  }
24   
25  void SumProbabilityOfDices(int number, int* pProbabilities)
26  {
27      for(int i = 1; i <= g_maxValue; ++i)
28          SumProbabilityOfDices(number, number, i, 0, pProbabilities);
29  }
30   
31  void SumProbabilityOfDices(int original, int current, int value, int tempSum, int* pProbabilities)
32  {
33      if(current == 1)
34      {
35          int sum = value + tempSum;
36          pProbabilities[sum - original]++;
37      }
38      else
39      {
40          for(int i = 1; i <= g_maxValue; ++i)
41          {
42              int sum = value + tempSum;
43              SumProbabilityOfDices(original, current - 1, i, sum, pProbabilities);
44          }
45      }
46  }

 

下一篇:没有了