當前位置:網站首頁>死磕遞歸1:遞推公式

死磕遞歸1:遞推公式

2022-07-23 17:05:50我家大寶最可愛

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)=12
n = 3 n=3 n=3 f ( 3 ) = 1 ∗ 2 ∗ 3 f(3)=1*2*3 f(3)=123
n = 4 n=4 n=4 f ( 4 ) = 1 ∗ 2 ∗ 3 ∗ 4 f(4)=1*2*3*4 f(4)=1234
n = 5 n=5 n=5 f ( 5 ) = 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 f(5)=1*2*3*4*5 f(5)=12345

更一般的遞推公式有
f ( n ) = f ( n − 1 ) ∗ n f(n)=f(n-1)*n f(n)=f(n1)n

也就是說我想要求解 f ( n ) f(n) f(n),那麼我只需要把 f ( n − 1 ) f(n-1) f(n1)求解出來即可,但是為了求解 f ( n − 1 ) f(n-1) f(n1),我需要把 f ( n − 2 ) f(n-2) f(n2)求解出來,說白了就是不斷的套娃。簡單看一下 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)=123456=f(5)6=f(4)56=f(3)456=f(2)3456=f(1)23456=123456 

老實說這有種脫褲子放屁的感覺,還不如直接從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

同樣可以寫出遞推公式
f ( n ) = f ( n − 1 ) ∗ x f(n)=f(n-1)*x f(n)=f(n1)x
寫出他的遞歸方法

def f(x,n):
	if n == 0:
		return 1
	return f(x,n-1)*x

同樣這個case也是脫褲子放屁,明明可以用循環解决為什麼要考慮使用遞歸呢?因為有一種巧妙的解决方法,我們把遞歸公式改一改
f ( n ) = { f 2 ( ⌊ n 2 ⌋ ) n % 2 = = 0 f 2 ( ⌊ n 2 ⌋ ) ∗ x n % 2 = = 1 f(n)= \begin{cases} f^2(\lfloor \frac{n}{2}\rfloor) & n\%2==0 \\ f^2(\lfloor \frac{n}{2}\rfloor)*x & n\%2==1 \end{cases} f(n)={ f2(⌊2n⌋)f2(⌊2n⌋)xn%2==0n%2==1
這個方法不是我想出來的,但是看到之後覺得非常的巧妙。我們看一下 f ( 13 ) f(13) f(13)怎麼求。

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 1base

也就是說,我們現在只需要求解 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(n1)的關系,然後每次减少1來不斷縮小問題規模,但是修改之後得到的是 f ( n ) f(n) f(n) f ( n / / 2 ) f(n//2) f(n//2)的關系,每次是 n / / 2 n//2 n//2的指數方式縮小問題規模。

4. 斐波那契數列

1、樓梯問題:一個階梯共n級,剛開始時人在第1級,若每次只能跨一級或兩級,要走上第n級,共有多少種走法?
假如現在有5階樓梯,我們給每一階樓梯編碼1,2,3,4,5。從最簡單的case開始算起
當n=1時,只有一種方法
當n=2時,可以一步一步跳上去,也可以直接跳上去1-2,2
當n=3時,一步一步跳上去,或者先跳上去兩層,然後再上去一層,或者先走一層再跳上去兩層1-2-3,1-3,2-3

你會發現從前往後算是非常複雜的,這個問題可以從後往前思考。例如當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上面去。

可以看到最上面的節點4有5條路徑,節點3有3條路徑,所以節點5總共就有3+5=8條路徑,因此就是相加的關系
在這裏插入圖片描述
根據上面的分析很容易寫成遞推公式
f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n1)+f(n2)

可以很容易的寫成遞歸方法

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

2、矩形覆蓋問題:用1×2的小矩形覆蓋2×n的大矩形,總共有多少種方法?
這個問題跟斐波那契數列如出一轍,繪制出來也非常容易理解。假如n=5,如果想要全部填充完成,有兩種方式,一種是將前4個填充完,最後補一個就行,或者就是將前3個填充完,最後需要補兩個
在這裏插入圖片描述

5. 小總結

上面的遞推問題,本質都是不斷减小問題規模,要求 f ( n ) f(n) f(n),先求出較小規模的 f ( n − 1 ) , f ( n / / 2 ) f(n-1),f(n//2) f(n1),f(n//2)等等,所以,最重要的就是如何分析問題得到遞推公式。

版權聲明
本文為[我家大寶最可愛]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/204/202207231359540429.html

隨機推薦