def move(n, a, b, c):
if n == 1:
print(a, '-->', c)
else:
move(n-1, a, c, b) # 先把n-1个盘子移到B
print(a, '-->', c) # 把最底下的移到C
move(n-1, b, c, a) # 再把B上的n-1个移回A
move(n-1, a, b, c) # 这样问题就由之前的移动A上n个盘子到C变成了移动n-1个
该方法由于把原本可以直接移动到C的n-1移回了A,所以步骤上变多了,但是最终还是可以完成目标。
解法二:
def move2(n, a, b, c):
if n == 1:
print(a, '-->', c)
elif n == 2:
print(a, '-->', b)
print(a, '-->', c)
print(b, '-->', c)
else:
move(n - 1, a, c, b) # 先把n-1个盘子移到B
print(a, '-->', c) # 把最底下的移到C
move(n - 2, b, c, a) # 把B上的n-2个移回A,留下一个
print(b, '-->', c) # 把B上的一个移到C
move(n - 2, a, b, c) # 这样问题就由之前的移动A上n个盘子到C变成了移动n-2个
该方法由于在把B上的n-2个移回A时没有做无用功,因为留了一个可以移到C,所以该解法计算出的步骤和廖老师的答案比一样多,不会多走冤枉路。
蓝e随风
这里写廖老师解法外的另外两种解法(方法其实类似,目的是加深对递归的理解): 解法一:
def move(n, a, b, c): if n == 1: print(a, '-->', c) else: move(n-1, a, c, b) # 先把n-1个盘子移到B print(a, '-->', c) # 把最底下的移到C move(n-1, b, c, a) # 再把B上的n-1个移回A move(n-1, a, b, c) # 这样问题就由之前的移动A上n个盘子到C变成了移动n-1个 该方法由于把原本可以直接移动到C的n-1移回了A,所以步骤上变多了,但是最终还是可以完成目标。
解法二:
def move2(n, a, b, c): if n == 1: print(a, '-->', c) elif n == 2: print(a, '-->', b) print(a, '-->', c) print(b, '-->', c) else: move(n - 1, a, c, b) # 先把n-1个盘子移到B print(a, '-->', c) # 把最底下的移到C move(n - 2, b, c, a) # 把B上的n-2个移回A,留下一个 print(b, '-->', c) # 把B上的一个移到C move(n - 2, a, b, c) # 这样问题就由之前的移动A上n个盘子到C变成了移动n-2个 该方法由于在把B上的n-2个移回A时没有做无用功,因为留了一个可以移到C,所以该解法计算出的步骤和廖老师的答案比一样多,不会多走冤枉路。