小升初的数学：汉诺塔 Hanoi Tower

xfhaoym

这是不是培训班的问题?

永远

xfhaoym老爷子我小学毕不了业啦

图老师2

递归算法。计算机程序；

永远

求数列1,3,7,15,31,… 的通项公式



你可以发现两数之差分别为2的一次方，二次方…n次方！说以第n个数为1 2的一次方 … 2的(n-1)次方等于2的n次方-1
通项公式为an=Σ(i=1,2...n)2^i=2^n-1
1=2^1-1
3=2^2-1
7=2^3-1
15=2^4-1
31=2^5-1

图老师2

enter the number:8
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
C --> B
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
B --> A
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
C --> B
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
B --> A
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
C --> B
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
C --> B
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
B --> A
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
B --> A
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
C --> B
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
B --> A
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
C --> B
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
B --> A
C --> A
C --> B
A --> B
C --> A
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
----------------------------------------------------------------------------------------------------
python3.6程序运行 14.740522384643555 秒。
----------------------------------------------------------------------------------------------------

图老师2

def hanoi(n,x,y,z):

    if n==1:

        print(x,"-->",z)

    else:

        hanoi(n-1,x,z,y)

        print(x,"-->",y)

        hanoi(n-1,y,x,z)

while True:

    n=int(input("请输入汉诺塔的层数："))


    hanoi(n,"x","y","z")

图老师2

Python实现汉诺塔问题的可视化

图老师2

import turtle

class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return len(self.items) == 0
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        if not self.isEmpty():
            return self.items[len(self.items) - 1]
    def size(self):
        return len(self.items)

def drawpole_3():#画出汉诺塔的poles
    t = turtle.Turtle()
    t.hideturtle()
    def drawpole_1(k):
        t.up()
        t.pensize(10)
        t.speed(100)
        t.goto(400*(k-1), 100)
        t.down()
        t.goto(400*(k-1), -100)
        t.goto(400*(k-1)-20, -100)
        t.goto(400*(k-1)+20, -100)
    drawpole_1(0)#画出汉诺塔的poles[0]
    drawpole_1(1)#画出汉诺塔的poles[1]
    drawpole_1(2)#画出汉诺塔的poles[2]

def creat_plates(n):#制造n个盘子
    plates=[turtle.Turtle() for i in range(n)]
    for i in range(n):
        plates[i].up()
        plates[i].hideturtle()
        plates[i].shape("square")
        plates[i].shapesize(1,8-i)
        plates[i].goto(-400,-90+20*i)
        plates[i].showturtle()
    return plates

def pole_stack():#制造poles的栈
    poles=[Stack() for i in range(3)]
    return poles

def moveDisk(plates,poles,fp,tp):#把poles[fp]顶端的盘子plates[mov]从poles[fp]移到poles[tp]
    mov=poles[fp].peek()
    plates[mov].goto((fp-1)*400,150)
    plates[mov].goto((tp-1)*400,150)
    l=poles[tp].size()#确定移动到底部的高度（恰好放在原来最上面的盘子上面）
    plates[mov].goto((tp-1)*400,-90+20*l)

def moveTower(plates,poles,height,fromPole, toPole, withPole):#递归放盘子
    if height >= 1:
        moveTower(plates,poles,height-1,fromPole,withPole,toPole)
        moveDisk(plates,poles,fromPole,toPole)
        poles[toPole].push(poles[fromPole].pop())
        moveTower(plates,poles,height-1,withPole,toPole,fromPole)

myscreen=turtle.Screen()
drawpole_3()
n=int(input("请输入汉诺塔的层数并回车:\n"))
plates=creat_plates(n)
poles=pole_stack()
for i in range(n):
    poles[0].push(i)
moveTower(plates,poles,n,0,2,1)
myscreen.exitonclick()

luyuanhong

这是网友 elim 过去发表在《数学中国》论坛上的一个帖子：

汉诺塔 Hanoi Tower

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针从下到上地穿好了由大到小的６４片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

我们现在要问，如果从头开始，按每秒完成一片金片的搬动计算，世界末日离我们多远？

搞数学的人有时候是有一点癫狂。这个问题已经不好一下子回答，竟有人还要用更虚无缥缈的函数来表达：

假定金片的数目不是64而是n, 那么游戏规则确定了这种从针x到针y的搬运的最捷工作量f(n). 考虑这样的情形：金片起初都在宝石针0处，经过若干次搬动，宝石针0上面n-1片金片都搬到宝石针1处（按照规定的大小上下秩序），宝石针0剩下最大最后的一片金片。宝石针2依然独身一柱撑天。按照f的定义，我们需要 f(n-1)次搬动来达到这个状态。现在我们把最大最后的那片金片套入宝石针2，然后我们再需要另外f(n-1)次搬动才能把宝石针1处的金片移至宝石针2。这个手续是必要的，又是充分（足够达到目的）的。所以我们得到一个关系式

f(n) = 2f(n-1)+1 即  f(n)+1 = 2(f(n-1)+1)

令 a(n) = f(n)+1 得到 a(n) = 2a(n-1) 即 a(n) = 2^(n-1)a(1)  (n ≥ 1)

注意f(1)=1, a(1)=2. 上面的式子表明 a(n)=2^n  即 f(n) = 2^n-1

所以原问题的答案是我们还有 2^(64)-1 秒。这表明移完这些金片需要5845亿年以上。

luyuanhong

下面是我过去在《数学中国》发表过的一个帖子：

题  有三个杆子，一个杆子上从上到下有 n 个从小到大的环，要求将这些环逐步移动到

另一个杆子上，移动时大环不能放在小环上，问：最少要移动几次？

解  设 n 个环从一个杆子移动到另一个杆子，最少要移动 a(n) 次。

    现在考虑有 n+1 个环的问题。

    移动中，总是有一步要将最大的第 n+1 个环移到另一个杆子上。而在此之前，必须要

将在这最大环上面的 n 个环移走，移到第三根杆子上。移动这 n 个环，最少要 a(n) 次。

然后移动 1 次，将最大的第 n+1 个环移到另一个杆子上。然后，还需要将在第三根杆子上

的 n 个环移动到最大的第 n+1 个环上面。移动这 n 个环，又最少要 a(n) 次。所以，n+1

个环最少要移动 a(n)+1+a(n) = 2a(n)+1 次。

   也就是说，有递推公式： a(n+1) = 2a(n)+1 ，n=1,2,3,… 。

   下面，用数学归纳法证明：a(n) = 2^n-1 ，n=1,2,3,… 。

（1）当 n=1 时，最少要移动一次，a(1) = 2^1-1 = 1 ，结论显然成立。

（2）设已知对某个给定的正整数 n ，结论成立，有 a(n) = 2^n-1 ，下面看 n+1 时的情形：

    a(n+1) = 2a(n)+1 = 2×(2^n-1)+1 = 2^(n+1)-2+1 = 2^(n+1)-1 。

    可见，n+1 时结论也成立。

（3）所以，对任何正整数 n ，结论都成立。