怎么进入网站管理页面,cms电影网站模板,网站开发项目中的rd,网站建设亻金手指科杰想写一系列文章#xff0c;总结一些题目#xff0c;看看解决问题、优化方法的过程到底是什么样子的。 系列问题一#xff1a;斐波那契数列问题
在数学上#xff0c;斐波纳契数列以如下被以递归的方法定义#xff1a;F(0)0#xff0c;F(1)1, F(n)F(n-1)F(n-2)#xff08…想写一系列文章总结一些题目看看解决问题、优化方法的过程到底是什么样子的。 系列问题一斐波那契数列问题
在数学上斐波纳契数列以如下被以递归的方法定义F(0)0F(1)1, F(n)F(n-1)F(n-2)n2n∈N*根据定义前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55
问题一
给定一个正整数n求出斐波那契数列第n项这时n较小
解法一最笨效率最低暴力递归完全是抄定义。请看代码
def f0(n):if n1 or n2:return 1return f(n-1)f(n-2) 分析一下为什么说递归效率很低呢咱们来试着运行一下就知道了 比如想求f(10)计算机里怎么运行的 每次要计算的函数量都是指数型增长时间复杂度O(2^(N/2))T(N)O(2^N),效率很低。效率低的原因是进行了大量重复计算比如图中的f(8),f(7).....等等你会发现f(8)其实早就算过了但是你后来又要算一遍。
如果我们把计算的结果全都保存下来按照一定的顺序推出n项就可以提升效率 斐波那契所有的一维的顺序已经很明显了就是依次往下求。。
优化1
def f1(n):if n1 or n2:return 1l[0]*nl[0],l[1]1,1for i in range(2,n):l[i]l[i-1]l[i-2]return l[-1] 时间复杂度o(n)依次往下打表就行空间o(n).
继续优化既然只求第n项而斐波那契又严格依赖前两项那我们何必记录那么多值呢记录前两项就行了 优化2
def f2(n):a,b1,1for i in range(n-1):a,bb,abreturn a
此次优化做到了时间o(n),空间o(1)
附这道题掌握到这里就可以了但是其实有时间o(log2n)的方法 优化三
学习过线性代数的同学们能够理解 结合快速幂算法我们可以在o(log2n)内求出某个对象的n次幂。(在其它专题详细讲解)
注意只有递归式不变才可以用矩阵快速幂的方法。
注优化三可能只有在面试上或竞赛中用当然快速幂还是要掌握的。 经过这个最简单的斐波那契大家有没有一点感觉了
好我们继续往下走
(补充pat、蓝桥杯原题让求到一万多位结果模一个数。
可以每个结果都对这个数取模否则爆内存另对于有多组输入并且所求结果类似的题可以先求出所有结果存起来然后直接接受每一个元素在表中查找相应答案) 问题二
一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
依旧是找递推关系分析跳一阶就一种方法跳两阶它可以一次跳两个也可以一个一个跳所以有两种三个及三个以上假设为n阶青蛙可以是跳一阶来到这里或者跳两阶来到这里只有这两种方法。它跳一阶来到这里说明它上一次跳到n-1阶同理它也可以从n-2跳过来fn为跳到n的方法数所以f(n)f(n-1)f(n-2)
和上题的优化二类似。
因为递推式没变过所以可以用优化三 问题三
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形总共有多少种方法提示大矩形看做是长度吧
请读者自己先思考一下吧。。。仔细看题。。仔细思考
如果n是1只有一种竖着放呗n是2两种 n等于3三种 题意应该理解了吧
读到这里你们应该能很快想到依旧是斐波那契式递归啊。
对于n3:怎么能覆盖到三只有两种办法从n-1的地方竖着放了一块或者从n-2的位置横着放了两块呗。
和问题二的代码都不用变。 问题四
给定一个由0-9组成的字符串1可以转化成A2可以转化成B。依此类推。。25可以转化成Y26可以转化成z给一个字符串返回能转化的字母串的有几种
比如123可以转化成
1 2 3变成ABC
12 3变成LC
1 23变成AW三种返回三
99999就一种iiiii返回一。
分析求i位置及之前字符能转化多少种。
两种转化方法一字符i自己转换成自己对应的字母二和前面那个数组成两位数然后转换成对应的字母
假设遍历到i位置判断i-1位置和i位置组成的两位数是否大于26大于就没有第二种方法f(i)f(i-1),想反等于f(i-1)f(i-2)
注意递归式不确定不能用矩阵快速幂 (这几个题放到这里就是为了锻炼找递归关系的能力不要只会那个烂大街的斐波那契) 斐波那契问题
斐波纳契数列以如下被以递归的方法定义
F(1)1
F(2)1
F(n)F(n-1)F(n-2)n2n∈N*#暴力抄定义,过多重复计算
def f0(n):if n1 or n2:return 1return f(n-1)f(n-2)
#记录结果后依次递推的优化时间O(N)
def f1(n):if n1 or n2:return 1l[0]*nl[0],l[1]1,1for i in range(2,n):l[i]l[i-1]l[i-2]return l[-1]
#既然严格依赖前两项不必记录每一个结果优化空间到O(1)
def f2(n):a,b1,1for i in range(n-1):a,bb,abreturn a
