大家好,欢迎来到IT知识分享网。
1. 递推公式
证明 f ( n ) = 5 n + 3 f(n)=5^n+3 f(n)=5n+3可以被4整除
先看几个具体的case,看看能不能被4整除
n n n | f ( n ) = 5 n + 3 f(n)=5^n+3 f(n)=5n+3 |
---|---|
n = 1 n=1 n=1 | f ( 1 ) = 5 1 + 3 = 8 f(1)=5^1+3=8 f(1)=51+3=8 |
n = 2 n=2 n=2 | f ( 2 ) = 5 2 + 3 = 28 f(2)=5^2+3=28 f(2)=52+3=28 |
n = 3 n=3 n=3 | f ( 3 ) = 5 3 + 3 = 128 f(3)=5^3+3=128 f(3)=53+3=128 |
查看了几个case发现都是可以被4整除的,那么如何证明任意一个n都可以让 5 n + 3 5^n+3 5n+3被4整除呢?前面通过实际的数据表明n=3的时候是可以被4整除的,那么n=4可以被4整除吗
f ( 4 ) = 5 4 + 3 = 5 × 5 3 + 3 = 4 × 5 3 + 5 3 + 3 = 4 × 5 3 + f ( 3 ) \begin{aligned} f(4) & =5^4+3\\ & =5\times 5^3+3\\ &=4\times 5^3+5^3+3\\ &=4\times 5^3+f(3) \end{aligned} f(4)=54+3=5×53+3=4×53+53+3=4×53+f(3)
可以发现 4 × 5 3 4\times 5^3 4×53可以被4整除,而且 f ( 3 ) f(3) f(3)也是可以被4整除的,因此 f ( 4 ) f(4) f(4)可以被4整除。更一般的有递推公式
f ( k + 1 ) = 5 k + 1 + 3 = 5 × 5 k + 3 = 4 × 5 k + 5 k + 3 = 4 × 5 k + f ( k ) \begin{aligned} f(k+1) & =5^{k+1}+3\\ & =5\times 5^k+3\\ &=4\times 5^k+5^k+3\\ &=4\times 5^k+f(k) \end{aligned} f(k+1)=5k+1+3=5×5k+3=4×5k+5k+3=4×5k+f(k)
递推公式已经被我们写出来了,可以看到如果 f ( k ) f(k) f(k)可以被4整除,那么 f ( k + 1 ) f(k+1) f(k+1)就一定可以被4整除。我们从1开始计算
- 1可以被4整除,那么一定有2可以被4整除
- 2可以被4整除,那么一定有3可以被4整除
- …
依次进行下去,也就是说任意一个整数都可以符合。
2. 如何求解 n ! n! n!
再看一个问题,如何求解 n ! n! n!,这个问题也非常的简单,我们直接从1开始一直乘到n就可以得到了
res = 1 for i in range(1,n+1): res *= i
我们这里可以考虑递归,说白了就是求递推公式,我们也从最简单的n=1开始计算
n n n | f ( n ) = n ! f(n)=n! f(n)=n! |
---|---|
n = 1 n=1 n=1 | f ( 1 ) = 1 f(1)=1 f(1)=1 |
n = 2 n=2 n=2 | f ( 2 ) = 1 ∗ 2 f(2)=1*2 f(2)=1∗2 |
n = 3 n=3 n=3 | f ( 3 ) = 1 ∗ 2 ∗ 3 f(3)=1*2*3 f(3)=1∗2∗3 |
n = 4 n=4 n=4 | f ( 4 ) = 1 ∗ 2 ∗ 3 ∗ 4 f(4)=1*2*3*4 f(4)=1∗2∗3∗4 |
n = 5 n=5 n=5 | f ( 5 ) = 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 f(5)=1*2*3*4*5 f(5)=1∗2∗3∗4∗5 |
也就是说我想要求解 f ( n ) f(n) f(n),那么我只需要把 f ( n − 1 ) f(n-1) f(n−1)求解出来即可,但是为了求解 f ( n − 1 ) f(n-1) f(n−1),我需要把 f ( n − 2 ) f(n-2) f(n−2)求解出来,说白了就是不断的套娃。简单看一下 f ( 6 ) f(6) f(6)是如何计算
f ( 6 ) = 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ 6 = f ( 5 ) ∗ 6 = f ( 4 ) ∗ 5 ∗ 6 = f ( 3 ) ∗ 4 ∗ 5 ∗ 6 = f ( 2 ) ∗ 3 ∗ 4 ∗ 5 ∗ 6 = f ( 1 ) ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ 6 = 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ 6 \begin{aligned} f(6)&=1*2*3*4*5*6\\ &=f(5)*6\\ &=f(4)*5*6\\ &=f(3)*4*5*6\\ &=f(2)*3*4*5*6\\ &=f(1)*2*3*4*5*6\\ &=1*2*3*4*5*6\ \end{aligned} f(6)=1∗2∗3∗4∗5∗6=f(5)∗6=f(4)∗5∗6=f(3)∗4∗5∗6=f(2)∗3∗4∗5∗6=f(1)∗2∗3∗4∗5∗6=1∗2∗3∗4∗5∗6
老实说这有种脱裤子放屁的感觉,还不如直接从1开始直接乘到n,这个case是没有任何问题的,不过越往后case会越复杂,也越会接近递归。我们先用递归的方式写出来
def f(n): if n == 1:return 1 return f(n-1)*n
3. 如何求解 x n x^n xn
这个问题也是非常的简单,我们依然通过循环就可以解决
def f(x,n): res = 1 for _ in range(n): res *= x return res
def f(x,n): if n == 0: return 1 return f(x,n-1)*x
f ( 13 ) f(13) f(13) | f 2 ( 6 ) ∗ x f^2(6)*x f2(6)∗x | 13 % 2 = 1 13 \% 2=1 13%2=1 |
f ( 6 ) f(6) f(6) | f 2 ( 3 ) f^2(3) f2(3) | 6 % 2 = 0 6 \% 2=0 6%2=0 |
f ( 3 ) f(3) f(3) | f 2 ( 1 ) ∗ x f^2(1)*x f2(1)∗x | 3 % 2 = 1 3 \% 2=1 3%2=1 |
f ( 1 ) f(1) f(1) | f 2 ( 0 ) ∗ x f^2(0)*x f2(0)∗x | 1 % 2 = 1 1 \% 2=1 1%2=1 |
f ( 0 ) f(0) f(0) | 1 1 1 | base |
也就是说,我们现在只需要求解 f ( 1 ) , f ( 3 ) , f ( 6 ) , f ( 13 ) f(1),f(3),f(6),f(13) f(1),f(3),f(6),f(13)只需要求解4次就可以得到结果了,而如果使用循环的话,我们则需要求解13次,高下立判。
这个case说明了一个问题,不同的递推公式,会得到不同的求解复杂度。在这个case中,常规的递推公式是一步一步的缩小问题求解规模的,也就是得到 f ( n ) f(n) f(n)和 f ( n − 1 ) f(n-1) f(n−1)的关系,然后每次减少1来不断缩小问题规模,但是修改之后得到的是 f ( n ) f(n) f(n)和 f ( n / / 2 ) f(n//2) f(n//2)的关系,每次是 n / / 2 n//2 n//2的指数方式缩小问题规模。
4. 斐波那契数列
你会发现从前往后算是非常复杂的,这个问题可以从后往前思考。例如当n=4时,如果想要跳上去,只能从2和3两个台阶跳上来, f ( 2 ) = 2 , f ( 3 ) = 3 f(2)=2,f(3)=3 f(2)=2,f(3)=3,所以跳到4阶台阶时有 f ( 4 ) = f ( 2 ) + f ( 3 ) = 5 f(4)=f(2)+f(3)=5 f(4)=f(2)+f(3)=5种方式。我之前一直考虑的一个问题时,为什么是两种方法的相加,为什么不是想乘或者其他的结合方式呢?我把递归树给绘制了一下,每个圆圈中的值就是这个台阶的名称,0表示地面,每一条路径就是一种跳上去的方法。例如最左侧的这条路径0-1-2-4-5,
- 先跳1步到1上面去,
- 然后再跳1步到2上面去,
- 然后再跳2部跳到4上面去,
- 最后再跳1步跳到5上面去。
可以很容易的写成递归方法
def f(n): if n == 1:return 1 if n == 2:return 2 return f(n-1)+f(n-2)
如果用递归,你会发现一个问题,就是很多节点都重复计算了,因此考虑直接使用循环来解决
def f(n): fn1 = 1 fn2 = 2 fn = 0 for i in range(3,n+1): fn = fn1+fn2 fn2 = fn1 fn1 = fn
5. 小总结
上面的递推问题,本质都是不断减小问题规模,要求 f ( n ) f(n) f(n),先求出较小规模的 f ( n − 1 ) , f ( n / / 2 ) f(n-1),f(n//2) f(n−1),f(n//2)等等,所以,最重要的就是如何分析问题得到递推公式。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/135113.html