经典递归
汉诺塔问题
背景故事
传说印度某间寺院有三根柱子，上串64个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说，还是他受他人启发。
若传说属实，僧侣们需要 (2的64次方 − 1) 步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要5845亿年才能完成。整个宇宙现在也不过137亿年。
游戏规则:
1.借助B柱子将A柱子上面的圆盘移动到C柱子
2.小圆盘上不能放大圆盘
3.在三根柱子之间一次只能移动一个圆盘
源码(python实现):
def hanoi(n, a, buffer, c):
if(n == 1):
print(a,"--->",c)
return
hanoi(n-1, a, c, buffer)
hanoi(1, a, buffer, c)
hanoi(n-1, buffer, a, c)
def main():
n = int(input("请输入汉诺塔铜盘的个数:"))
hanoi(n, "a", "b", "c")
if __name__ == "__main__":
main()
求斐波那契数列
背景故事:
在西方，最先研究这个数列的人是比萨的列奥那多(意大利人斐波那契Leonardo Fibonacci)，他描述兔子生长的数目时用上了这数列:
第一个月初有一对刚诞生的兔子
第二个月之后(第三个月初)它们可以生育
每月每对可生育的兔子会诞生下一对新兔子
兔子永不死去
假设在n月有兔子总共a对，n+1月总共有b对。在n+2月必定总共有a+b对：因为在n+2月的时候，前一月(n+1月)的b对兔子可以存留至第n+2月(在当月属于新诞生的兔子尚不能生育)。而新生育出的兔子对数等于所有在n月就已存在的a对.
游戏规则:
费波那契数列由0和1开始，之后的费波那契系数就是由之前的两数相加而得出
源码(python实现):
def Fibonacci(num):
if num == 1 or num == 2:
return 1
elif num == 0:
return 0
else:
return Fibonacci(num-1) + Fibonacci(num - 2)
def main():
num = int(input("请输入斐波那契的位数:"))
result = Fibonacci(num)
print("第%d位斐波那契数的值为%d"%(num, result))
if __name__ == "__main__":
main()
求阶乘
一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积，并且0的阶乘为1
源码(python实现):
def factorial(num):
if num == 1 or num == 0:
return 1
else:
return num *factorial(num-1)
def main():
num = int(input("请输入需要求阶乘的整数:"))
result = factorial(num)
print("%d的阶乘为%d"%(num, result))
pass
if __name__ == "__main__":
main()
