標籤：

具體數學書籍數學遞歸

具體數學-第2課（成套方法求解遞歸式）

05-17

具體數學-第2課（成套方法求解遞歸式）

來自專欄自然語言處理與深度學習

原文鏈接：

具體數學-第2課 - WeiYang Blog?

godweiyang.com

今天主要講了關於遞推式和求和的一些方法，主要是成套方法。

約瑟夫環推廣

上一節課說到，約瑟夫環問題的解是

$[f(n) = 2l + 1]$

其中 $(n = {2^m} + l)$

將 $(n)$ 寫成二進位可以發現， $(f(n))$ 就是 $(n)$ 的二進位循環左移1位。

現在做一下推廣，求解如下遞推式：

$egin{array}{l}f(1) = alpha \f(2n) = 2f(n) + eta \f(2n + 1) = 2f(n) + gamma end{array}$

可以設

$[f(n) = A(n)alpha + B(n)eta + C(n)gamma ]$

同樣，令 $(n = {2^m} + l)$

可以解出

$egin{array}{l}A(n) = {2^m}\B(n) = {2^m} - 1 - l\C(n) = lend{array}$

再從二進位角度理解一下，將遞推式繼續推廣：

$[egin{array}{*{20}{l}}{f(j) = {alpha _j},1 le j < d}\{f(dn + j) = cf(n) + {eta _j},0 le j le d,n ge 1}end{array}]$

可以得到解為

$[f({({b_m}{b_{m - 1}} ldots {b_1}{b_0})_d}) = {({alpha _{{b_m}}}{eta _{{b_{m - 1}}}}{eta _{{b_{m - 2}}}} ldots {eta _{{b_1}}}{eta _{{b_0}}})_c}]$

遞推式求和

求解如下遞推式：

$egin{array}{l}{R_0} = alpha \{R_n} = {R_{n - 1}} + eta n + gamma end{array}$

用成套方法求解，設

$[{Rn} = A(n)alpha + B(n)eta + C(n)gamma ]$

首先令 ${R_n} = 1$ ，可以得到 $alpha = 1,eta = 0,gamma = 0$ ，所以 $(A(n) = 1)$ 。

再令 ${R_n} = 1$ ，可以得到 $(alpha = 0,eta = 0,gamma = 1)$ ，所以 $(C(n) = n)$ 。

最後令 $({R_n} = {n^2})$ ，可以得到 $(alpha = 0,eta = 2,gamma = - 1)$ ，所以 $(2B(n) - C(n) = {n^2})$ ，所以 $(B(n) = ({n^2} + n)/2)$

再來一個更複雜的遞推式：

$egin{array}{l}{R_0} = alpha \{R_n} = 2{R_{n - 1}} + eta n + gamma end{array}$

同樣的方法，設

${R_n} = A(n)alpha + B(n)eta + C(n)gamma$

首先令 $({R_n} = 1)$ ，可以得到 $(alpha = 1,eta = 0,gamma = -1)$ ，所以 $(A(n) - C(n) = 1)$ 。

再令 $({R_n} = n)$ ，可以得到 $(alpha = 0,eta = -1,gamma = 2)$ ，所以 $(2C(n) - B(n) = n)$ 。

這時候能不能令 $({Rn} = {n^2})$ 呢？答案是不能，因為如果 $({R_n} = {n^2})$ ，那麼

$[{n^2} = 2{(n - 1)^2} + eta n + gamma ]$ 顯然不可能成立。

觀察係數，可以令 $({R_n} = 2^n)$ ，可以得到 $(alpha = 1,eta = 0,gamma = 0)$ ，所以 $(A(n) = 2^n)$ 。

所以

$[A(n) = {2^n},B(n) = {2^{n + 1}} - n + 2,C(n) = {2^n} + 1]$

推薦閱讀：

※具體數學-第1課（遞歸求解實際問題）
※POJ 2694：逆波蘭表達式
※漢諾塔問題的遞歸求解
※DAY31：Climbing Stairs
※你好，類型（七）：Recursive type

TAG:具體數學書籍 | 數學 | 遞歸 |