专栏首页木子昭的博客<递归>汉诺塔 | 斐波那契数列 | 阶乘 (附python实现源码)汉诺塔问题求斐波那契数列背景故事:求阶乘

<递归>汉诺塔 | 斐波那契数列 | 阶乘 (附python实现源码)汉诺塔问题求斐波那契数列背景故事:求阶乘

经典递归

汉诺塔问题

背景故事

传说印度某间寺院有三根柱子,上串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()

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • <脚本>用python检测python | 批量检查注释率是否达标以python3.5/lib目录下执行结果为例:执行结果:

    一份好的代码一定要有很好的可读性,所以在实际开发过程中,注释要占源码一定的比例,才是一份合格的代码,我这里写了一个脚本,可以用来检测同一目录下,所有pytho...

    zhaoolee
  • 尾递归是怎么一回事?什么是尾递归?

    50%的算法问题都能通过递归来解决,倒不是说递归本身有多厉害,只是说明递归的思想让很多复杂的问题变得简单! 啥? 了解数据结构的人都知道, 树结构本身就是用递...

    zhaoolee
  • <技巧>python模块性能测试以python列表的内置函数append和insert为例以python列表insert方法和append方法快速创建1至1000的列表为例:

    算法是程序的灵魂,优秀的算法能给程序的效率带来极大的提升,而算法的优劣,往往要经过大量的测试. 在硬件环境基本不变的前提下,对算法实验的次数越多,测试算法运...

    zhaoolee
  • 各位相加,直到得到一个一位的整数

    从1开始,结果依次是1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9····

    你好戴先生
  • 【leetcode刷题】T203-完美数

    https://leetcode-cn.com/problems/perfect-number/

    木又AI帮
  • JAVA递归

         //斐波那契      // num 第几个数      // search(num - 1)临近的第一个+move(num - 2)临近的...

    用户2192970
  • 漫画:六九式是一道简单有趣的算法题(开车...)

    今天是小浩算法 “365刷题计划” 第94天 。69式是一种。。。咳咳,六九问题是一道很有趣的算法题。嗯,不服来辩。

    程序员小浩
  • javascript 判断参数是否为非0整数数字或者整数数字字符串的简单方法(小装逼)

    我们来判断一个值是否为数字,可以把它转化为数字,看是否为NaN 然后,再判断是否等于0即可简单的来实现判断了。

    FungLeo
  • Leetcode_342_Power of Four

    http://blog.csdn.net/pistolove/article/details/52198328

    bear_fish
  • String - 273. Integer to English Words

    Convert a non-negative integer to its english words representation. Given input ...

    用户5705150

扫码关注云+社区

领取腾讯云代金券