汉诺塔
问题描述
有三根柱子，分别名为A,B,C。
初始时，在柱子A上有n个圆盘，他们从上往下，盘子的大小是从小到大。
在移动和摆放的过程中，小盘子必须在大盘子上面。
在保证规则的情况下，将柱子A上的所有盘子，移动到柱子C，移动中可以借助柱子B。
请打印出移动过程
大概过程
问题分析
递归的过程：
1、将最上面的n-1个盘子，从A借助C移动到B
2、将最下面的一个盘子，从A移动到C
3、将最上面的n-1个盘子，从B借助A移动到C
递归的结束条件：
问题规模变成盘子数为0时，因为当盘子数为0时就不需要移动了！
代码部分
def hano(n, a, b, c):
if n > 0:
hano(n - 1, a, c, b)
print(f"{n}号盘子从{a}移动到{c}")
hano(n - 1, b, a, c)
if __name__ == '__main__':
hano(3, "A", "B", "C")
"""
1号盘子从A移动到C
2号盘子从A移动到B
1号盘子从C移动到B
3号盘子从A移动到C
1号盘子从B移动到A
2号盘子从B移动到C
1号盘子从A移动到C
"""
可以看到，一致递归到最里层才会开始打印中间那一行，所以可以将n作为序号来使用
斐波那契数列
斐波那契数列定义
这个数列从第3项开始，每一项都等于前两项之和。
例如
1，1，2，3，5，8，13，21，34，55，89...
问题
获得第40个数
递归解法
返回前两个数之和
"""
斐波那契数列
"""
def fibo(n):
if n == 1 or n == 2:
return 1
return fibo(n - 1) + fibo(n - 2)
if __name__ == '__main__':
print(fibo(40))
"""
102334155
"""
缓存解法
利用lru_cache缓存装饰器
"""
斐波那契数列
"""
from functools import lru_cache
@lru_cache
def fibo(n):
if n == 1 or n == 2:
return 1
return fibo(n - 1) + fibo(n - 2)
if __name__ == '__main__':
print(fibo(40))
go的问题
go也可以利用缓存来解决
但是go的数据类型上限是uint64类型的18446744073709551615
但是斐波那契数的第93位是12200160415121876738，94位就超了，所以超的部分就会被切掉
所以go中只能计算到93位，多了就不准了
这里就选择求尾数
package main
import (
"fmt"
"math"
"time"
)
var (
cache = make(map[uint64]uint64, 10000)
)
func fibo(n uint64) uint64 {
if n == 1 || n == 2 {
return 1
}
if value, ok := cache[n]; ok {
return value
}
res := fibo(n-1) + fibo(n-2)
// 93以内为完整的，93以上求尾数
if n >= 93 {
res = res % uint64(math.Pow10(18))
}
cache[n] = res
return res
}
func main() {
star := time.Now()
fmt.Println(fibo(2000))
fmt.Println("耗时：", time.Since(star))
}
阶乘
定义
一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。
问题
给出任意一个正整数n，求解其阶乘？
代码部分
"""
阶乘
"""
def jiechen(n):
if n == 1:
return 1
return n * jiechen(n - 1)
if __name__ == '__main__':
print(jiechen(20))
同样
go中超过20，就只能取部分尾数
package main
import (
"fmt"
"math"
)
func jiechen(n uint64) uint64 {
if n == 1 {
return 1
}
res := n * jiechen(n-1)
if n >= 20 {
res = res % uint64(math.Pow10(18))
}
return res
}
func main() {
fmt.Println(jiechen(20))
}