初级编程通关练习题 #7 – 约瑟夫环

约瑟夫环问题是一个著名的倒数游戏,规则如下:给定N个游戏者,从第一个人开始计数,每K个人出局一人,继续从当前位置倒数,一直到最后剩下一个人为止。计算最后一个人在N个人中的位置。 譬如我们现在有八个人,每数三人就出局一人: [ 1,2,3,4,5,6,7,8 ] - 初始数列[ 1,2,4,5,6,7,8 ] => 3号出局[ 1,2,4,5,7,8 ] => 6号出局[ 2,4,5,7,8 ] => 1号出局[ 2,4,7,8 ] => 5号出局[ 4,7,8 ] => 2号出局[ 4,7 ] =>…

初级编程通关练习题 #6 – 斐波那契数列和DP算法

斐波那契数列中第N个数值的标准计算方式如下: def fibonacci(n): if n in [0, 1]: return n return fibonacci(n - 1) + fibonacci(n - 2) 上面的代码最大的缺陷是运行效率低下,因为存在太多重复计算。现在我们可以借助动态规划算法(Dynamic Programming)的两种方式Dp Tablulation 和 Dp Memoization 来改善上面代码的问题。 输入样例: N = 70 输出样例:…