遞推方程的兩種特殊解法及其在程序設(shè)計(jì)中的應(yīng)用

金淵智

（三門峽職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，河南三門峽472000）

0 引言

由于遞歸具有直觀、易理解等特性，因此，在程序設(shè)計(jì)時(shí)，我們經(jīng)常使用遞歸來解決某些特定問題。遞歸[1-3]（Recursion）即某個(gè)函數(shù)（或功能）一次或多次地在函數(shù)體內(nèi)調(diào)用自身來解決相關(guān)子問題。當(dāng)一個(gè)問題規(guī)模較大時(shí)，可以通過遞歸方法將問題規(guī)模逐步減小，最后再合并所有的遞歸結(jié)果，得出整個(gè)問題的解。

將函數(shù)的遞歸調(diào)用寫成方程的形式就是遞推方程[4（]Recurrence Equation）。其數(shù)學(xué)定義是：設(shè)序列a0,a1,a2…,an,…,簡記為 {an}，一個(gè)把a(bǔ)n與某些個(gè)ai(i＜n)聯(lián)系起來的等式叫做關(guān)于序列 {an}的遞推方程。當(dāng)給定遞推方程和適當(dāng)?shù)某踔担臀ㄒ坏卮_定了序列。

在計(jì)算機(jī)算法分析和程序設(shè)計(jì)中，使用遞歸技術(shù)往往使得函數(shù)的定義和算法的描述非常簡潔，通俗易懂，但是有許多問題隨著問題規(guī)模的增大，計(jì)算量呈指數(shù)形式增長，那么再高的CPU處理速度，也無法滿足人們對算法執(zhí)行時(shí)間的需求。因此在處理實(shí)際問題時(shí)，通常將時(shí)間復(fù)雜度為指數(shù)級別的算法先求出遞推方程的解，再來對算法進(jìn)行設(shè)計(jì)、改進(jìn)和效率評估。

常見遞推方程的求解方法有迭代法、嘗試法、遞歸樹和主公式法等。本文主要討論特征方程法和生成函數(shù)法，利用Hanoi塔的例子分別驗(yàn)證了這兩種方法的正確性。最后利用MATLAB程序測試了Hanoi塔的遞歸函數(shù)運(yùn)行時(shí)間以及求解方程后的程序運(yùn)行時(shí)間。

1 常系數(shù)線性遞推方程的解法

文獻(xiàn)[5]給出常系數(shù)線性遞推方程的一般定義：

其中a1,a2,…,ak為常數(shù)，ak≠0，當(dāng)f(n)=0稱為k階常系數(shù)線性齊次遞推方程，b0,b1,b2,…,bk-1為k個(gè)初值。當(dāng)f(n)≠0稱為k階常系數(shù)線性非齊次遞推方程。

公式（1）的齊次特征方程為

該特征方程的根就是原遞推方程的特征根，根據(jù)方程階的不同，公式（2）可能多重根，利用多重根來構(gòu)造通解的線性組合，然后再根據(jù)初值列出方程組，求出待定常數(shù)。如果構(gòu)造的線性組合有兩個(gè)或多個(gè)線性相關(guān)的話，就無法求出待定系數(shù)。對于非齊次的情況可以通過先求齊次通解再加上一個(gè)非齊特解來構(gòu)造。

Hanoi塔的遞推方程如下

根據(jù)定義這是一個(gè)非齊次方程，其齊次特征方程為：x-2=0，即x=2，因此構(gòu)造線性無關(guān)的通解是c2n，設(shè)P為原方程的特解，代入原方程得

即P=-1，再加上齊次通解既是公式（3）的解

再代入初值T(1)=1，得c=1，最終公式（3）的解

2 利用生成函數(shù)求解遞推方程

生成函數(shù)[6]也可以用于求解遞推方程。一個(gè)序列對應(yīng)一個(gè)生成函數(shù)，同時(shí)一個(gè)序列可以滿足某個(gè)遞推關(guān)系，因此，可以將遞推關(guān)系表示成生成函數(shù)，然后在利用生成函數(shù)與冪級數(shù)的關(guān)系來求解遞推方程。對于公式（3）Hanoi塔的例子使用生成函數(shù)求解的過程如下：

1）先計(jì)算生成函數(shù)

整理得

2）用生成函數(shù)表達(dá)遞推序列

與前述方法求解結(jié)果一致。

3 求解遞推方程對于程序設(shè)計(jì)的意義

如果要編寫計(jì)算Hanoi塔盤子的移動次數(shù)的程序，最簡單的就是使用遞推公式編寫遞歸函數(shù)，

其中xn項(xiàng)的系數(shù)就是遞推方程的解，即其MATLAB程序代碼如下：

隨著問題規(guī)模n（盤子個(gè)數(shù)）的增加，這個(gè)遞歸函數(shù)的計(jì)算量程指數(shù)級增長，這是我們無法接受的。印度僧侶預(yù)測，將64盤子轉(zhuǎn)移完畢，就是世界末日?？梢姰?dāng)n=64時(shí)問題的規(guī)模已經(jīng)相當(dāng)大了。那么，利用公式（8）遞推方程的求解結(jié)果，我們很容易計(jì)算盤子的移動次數(shù)，其MATLAB的程序代碼如下：

為了程序計(jì)時(shí)，引入t0和t1變量。為了對比遞歸程序和求解遞推方程后的程序效率，對不同大小的n做了實(shí)驗(yàn)，數(shù)據(jù)如表1所示。

表1 遞歸程序與求解方程后的程序運(yùn)行時(shí)間對比

其中的“0”表示時(shí)間太短，MATLAB系統(tǒng)無法計(jì)時(shí)，“-”表示時(shí)間過長，大于100分鐘。由此可以看出，當(dāng)n=25兩種方法的求解用時(shí)已經(jīng)差距非常大了；當(dāng)n=35時(shí)，遞歸算法用時(shí)已經(jīng)接近80分鐘；當(dāng)n=40時(shí)，實(shí)驗(yàn)用的計(jì)算機(jī)已經(jīng)無法快速計(jì)算遞歸算法了。求解遞歸方程后的程序運(yùn)行時(shí)間幾乎全部為“0”秒，當(dāng)n=64時(shí)，若采用配置較高的計(jì)算機(jī)，程序用時(shí)也是“0”秒。

4 結(jié)束語

由于遞推方程的類型較多，求解的方法很難統(tǒng)一，因此對于遞推方程解法的研究從未停止。本文討論了兩種特殊的遞推方程解法，對于非數(shù)學(xué)領(lǐng)域，特別是計(jì)算機(jī)程序員有一定的參考價(jià)值。最后通過MATLAB實(shí)例仿真對比，論證了求解遞推方程的必要性和現(xiàn)實(shí)意義。因此，在程序設(shè)計(jì)時(shí)盡量避免使用遞歸算法，可以先將遞歸算法利用求解遞推方程轉(zhuǎn)化為非遞歸算法，再編寫程序代碼，以提高程序的執(zhí)行效率。