Cyclic Hanoi问题 李凯旭.

Presentation on theme: "Cyclic Hanoi问题 李凯旭."— Presentation transcript:

1 Cyclic Hanoi问题 李凯旭

2 Hanoi 问题 subroutine move N from A to B using C: (1) if N is 1 then output “move A to B ”; (2) otherwise (that is, if N is greater than 1) do the following: (2.1) call move N - 1 from A to C using B ; (2.2) output “move A to B”; (2.3) call move N - 1 from C to B using A; (3) return.

3 Cyclic Hanoi问题 B C A

4 尝试直接用Hanoi方法 B C A 错！ Define all the moving clockwise:
subroutine move N from A to B using C: (1) if N is 1 then output “move A to B ”; (2) otherwise (that is, if N is greater than 1) do the following: (2.1) call move N - 1 from A to C using B ; (2.2) output “move A to B”; (2.3) call move N - 1 from C to B using A; (3) return.

5 回头再看Hanoi 问题 move N from X to Y using Z 递归的操作与N的规模是无关的
subroutine move N from A to B using C: (1) if N is 1 then output “move A to B ”; (2) otherwise (that is, if N is greater than 1) do the following: (2.1) call move N - 1 from A to C using B ; (2.2) output “move A to B”; (2.3) call move N - 1 from C to B using A; (3) return.

6 B C A A B A C subroutine move N from A to B using C: (1) if N is 1 then output “move A to B ”; (2) otherwise (that is, if N is greater than 1) do the following: (2.1) call move N - 1 from A to C using B ; (2.2) output “move A to B”; (2.3) call move N - 1 from C to B using A; (3) return.

7 Cyclic Hanoi问题(几乎全是这个！)
using two mutually recursive procedures: To move n disks counterclockwise to the neighboring target peg: (1)move n − 1 disks counterclockwise to the target peg (2)move disk #n one step clockwise (3)move n − 1 disks clockwise to the start peg (4)move disk #n one step clockwise (5)move n − 1 disks counterclockwise to the target peg To move n disks clockwise to the neighboring target peg: (1)move n − 1 disks counterclockwise to a spare peg (3)move n − 1 disks counterclockwise to the target peg

8 递归的关系 Let C(n) and A(n) represent moving n disks clockwise and counterclockwise, then we can write down both formulas: C(n) = A(n-1) n A(n-1) A(n) = A(n-1) n C(n-1) n A(n-1).

9 Hanoi是怎么证明的？ Cyclic Hanoi算法正确性的证明 部分正确性:数学归纳法
终止：n -> n-1 并且 n>=1

10 Cyclic Hanoi算法正确性的证明 终止：和Hanoi相同 部分正确性：同样用数学归纳法证明
(2)n-1 -> n 若n-1的情况成立，那么可以保证n-1个环可以顺时针移动一位或逆时针移动一位，那么推导出n的情况： 顺时针移动n个环与逆时针移动n个环

11 Cyclic Hanoi算法正确性的证明 Let C(n) and A(n) represent moving n disks clockwise and counterclockwise, then we can write down both formulas: C(n) = A(n-1) n A(n-1) A(n) = A(n-1) n C(n-1) n A(n-1). 一共需要三个函数： clockwise_move(N,X,Y,Z) counter_clockwise_move(N,X,Y,Z) move(N,X,Y,)

12 Cyclic Hanoi算法 subroutine move N from A to B using C(clockwise_move(N,A,B,C)): (1) if N is 1 then output “move A to B ”;(move(1,A,B)) (2) otherwise (that is, if N is greater than 1) do the following: (2.1) call move N - 1 from A to C using B ;(call counter_clockwise_move(N-1,A,C,B)) (2.2) output “move A to B”;(move(N,A,B)) (2.3) call move N - 1 from C to B using A;(call counter_clockwise_move(N-1,C,B,A)) (3) return.

13 B C A 自己的想法 subroutine move N from A to B using C: (1) if N is 1 then output “move A to B ”; (2) otherwise (that is, if N is greater than 1) do the following: (2.1) call move N - 1 from A to B using C ; (2.2) call move N - 1 from B to C using A ; (2.3) output “move A to B”; (2.4) call move N - 1 from C to A using B; (2.5) call move N - 1 from A to B using C; (3) return.

14 Cyclic Hanoi算法正确性的证明 终止：基本和Hanoi相同 部分正确性：同样用数学归纳法证明 (1)n = 1,即顺时针移动一位
(2)n-1 -> n 若n-1的情况成立，那么可以保证n-1个环可以顺时针移动，那么推n的情况： A(n) = A(n-1) A(n-1) n A(n-1) A(n-1). hanoi(N,X,Y,Z) move(N,X,Y)

15 Cyclic Hanoi算法的复杂程度 Let C(n) and A(n) represent moving n disks clockwise and counterclockwise, then we can write down both formulas: C(n) = A(n-1) n A(n-1) A(n) = A(n-1) n C(n-1) n A(n-1). 定性的感受一下步骤的增长速度： C(n) = 2A(n-1)+1 A(n) = 2A(n-1)+C(n-1)+2 -> A(n+1) = 2A(n)+C(n)+2 A(n+1) = 2A(n)+ 2A(n-1)+3 -> A(n+1) + (√ 3-1)A(n)= (√ 3+1)A(n)+ 2A(n-1)+3 A(n+1) + (√ 3-1)A(n) + a=p*(√ 3+1)^n (√ 3+1)A(n) < p*(√ 3+1)^n A(n) < p*(√ 3+1)^(n-1)

16 自己想法的复杂程度 B C A A(n) = 4A(n-1)+1 -> A(n) ≈ 4^(n-1)
subroutine move N from A to B using C: (1) if N is 1 then output “move A to B ”; (2) otherwise (that is, if N is greater than 1) do the following: (2.1) call move N - 1 from A to B using C ; (2.2) call move N - 1 from B to C using A ; (2.3) output “move A to B”; (2.4) call move N - 1 from C to A using B; (2.5) call move N - 1 from A to B using C; (3) return. A(n) = 4A(n-1)+1 -> A(n) ≈ 4^(n-1)

17 Cyclic Hanoi问题 using two mutually recursive procedures:
To move n disks counterclockwise to the neighboring target peg: To move n disks clockwise to the neighboring target peg: (wiki)The solution for the Cyclic Hanoi has some interesting properties: 1)The move-patterns of transferring a tower of disks from a peg to another peg are symmetric with respect to the center points. 2)The smallest disk is the first and last disk to move. (……) 3)Groups of the smallest disk moves alternate with single moves of other disks. C(n) = A(n-1) n A(n-1) A(n) = A(n-1) n C(n-1) n A(n-1). 4)The number of disks moves specified by C(n) and A(n) are minimal

18

19 谢谢！