第一次課實驗題題解

第一節課的前三道實驗題，題目要求“使用遞回”，但遞回好像對很多同學來說都比較陌生，再加上題目本身（尤其是第三題）真的很難，所以這篇文章將先大體講一下遞回是什么，然后以“從遞推到遞回”的思路完成前兩道題，并給出遞推版本題解和符合要求的遞回版本題解，等大家對遞回熟悉后，再直接運用遞回解決最難的第三題，

遞回

總而言之，遞回就是函式自己呼叫自己，遞回是一個很難理解的演算法，我們先看下面這個引例來了解一下，對遞回已經很熟悉的同學可以跳過這部分，

遞回的引例

int num=0; //計數器，用于記錄遞回呼叫次數
int find(int n){
    if(n==1)return num; //遞回結束，回傳結果
    n=n-1; //n減小
    num++; //num++表示運行了一次
    return find(n); //遞回呼叫
}
}

• 如果n=1，函式在第一個if直接結束，此時num=0直接被回傳；
• 如果n=2，函式不會在第一個if時終止，而是執行它下面的陳述句，最后回傳find(1)，然后程式再掉過頭來找find(1)是什么，這時候n經過一次n=n-1后，已經為1了，所以在第一個if里終止，而此時num也經歷過一次增大，所以回傳的num將是1

現在要求程式執行find(n)，其中n=4，我們來手推這段程式：

1. n=4因此不會觸發return num，而是執行下面的陳述句，n=n-1=3，num=1，下一句話是return find(3)，但目前還不知道find(3)是什么，所以這個函式運行到這里先暫停，去找find(3)到底是什么

2. n=3因此不會觸發return num，而是執行下面的陳述句，n=n-1=2，num=2，下一句話是return find(2)，但目前還不知道find(2)是什么，所以這個函式運行到這里先暫停，去找find(2)到底是什么

3. n=2因此不會觸發return num，而是執行下面的陳述句，n=n-1=1，num=3，下一句話是return find(1)，但目前還不知道find(1)是什么，所以這個函式運行到這里先暫停，去找find(1)到底是什么

4. n=1觸發return num，此時的num=3，也就是說經歷多次遞回呼叫后，我們找到了這時候的find(1)=3，那么函式find(2)可以繼續了，回傳3；那么函式find(3)可以繼續了，回傳3；那么函式find(4)可以繼續了，回傳3；

綜上，如果在主函式中這樣寫：

int main()
{
    int n=4;
    cout<<find(n);
    return 0;
}

輸出：

3

遞回大概就是這樣的一個程序：函式執行的時候，遇到了“引數不同的它自己”，然后它先放下手里的其他作業，去探索這個新的“它自己”是什么，在探索程序中又遇到了一個“更新的它自己”，于是現在的作業暫停，出發去探索新的“它自己”是什么······等最后終于沒有”新的自己“出現了，再把探索的結果一層一層地往回帶，最后回到原來想要問題，得到結果，

從上面的程序中，我們可以總結出兩個遞推的普遍特點：

1. 需要有一個遞推終點，“新的自己”不應該是無限多的，這樣程式才有停下來的可能，比如上面程式中的if(n==1)return num;
2. 需要通過操作來靠近遞推終點，比如上面程式中的n--;

遞回的確不是很好懂，希望你看完上面的程序后，對它能有一個初步的理解，再通過后續的練習加深理解，

btw. 有句老話說的好，人理解遞推，神理解遞回

第一題——遞回求和

題目鏈接：傳送門

描述

遞回是一種非常有效的程式設計方法，應用相當廣泛,遞回求和就是其中的一種，現在定義數列通項An = n * n,給定一個整數n（1 <= n <= 1000），要你求前n項和Sn，即Sn = 1 * 1 + 2 * 2 + … + n * n，要求使用遞回的方法進行計算，

輸入

輸入只有一行，包括一個整數n，表示要求的項數，

輸出

輸出只有一行，為一個整數Sn，表示對應的前n項和，

樣例輸入

7

樣例輸出

140

解題思路

題意很清晰，數列An=n*n, 它還有個和數列Sn=A1+A2+...+An，我們的任務就是對一個給定的n，求Sn

遞推解

因為我們對遞回還不夠熟悉，不妨先用遞推寫一下試試，可以得到遞推關系：S(n)=S(n-1)+n*n

#include <iostream>
using namespace std;
int s[1010]; //和數列S
int main()
{
    s[1]=1;
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)
        s[i]=s[i-1]+i*i; //遞推關系
    cout<<s[n];
    return 0;
}

提交結果是Accepted

遞回解

我們直接把遞推公式以遞回的形式表述出來（暫時不考慮遞推終點和操作）

int s(int n){
    return s(n-1)+n*n;
}

代入遞推公式后，我們發現它已經滿足了第二個條件——n在不斷減小，而n越小，題目越簡單，當n=1的時候，我們知道結果是1，可以把它設為遞推終點

int s(int n){
    if(n==1)return 1; //如果當前n=1，遞回結束，回傳1
    return s(n-1)+n*n; //否則，繼續遞回
}

上面這個遞回函式，就能完美滿足題目要求

附一下完整程式，提交結果Accepted

#include <iostream>
using namespace std;
int s(int n){
    if(n==1)return 1;
    return s(n-1)+n*n;
}
int main()
{
    int n;
    cin>>n;
    cout<<s(n);
    return 0;
}

第二題——遞回求最大公約數

題目鏈接：傳送門

描述

給定兩個正整數，求它們的最大公約數

輸入

輸入一行，包含兩個正整數，兩數都在32位有符號整型的表示范圍之內，（也就是在int范圍內）

輸出

輸出一個正整數，即這兩個正整數的最大公約數

樣例輸入

6 9

樣例輸出

3

提示

整數x和y的最大公約數是能夠同時整除x和y的最大整數，撰寫遞回函式gcd來回傳x和y的最大公約數，x和y的gcd函式按如下方式進行遞回定義：如果y等于0，那么gcd(x, y)等于x；否則gcd(x,y)等于gcd(y, x % y)，這里%是求模運算子，

解體思路

老師給的提示，運用到的數學方法稱為“輾轉相除法”，是一種求兩個數最大公約數的套路化方法，有興趣了解其證明的同學可以自行百度，這里將直接對其進行運用，按照從遞推到遞回的思路給出題解

ps. gcd只是一個自己起的名字，你想把它改成任何名字都可以，只不過實際應用中為了增強代碼的可讀性，往往都把“用來求最大公因數的函式”取名為gcd

遞推解

使用輾轉相除法和while(r!=0)進行遞推，當r=0時while結束，輸出b，詳見下方代碼：

#include <iostream>
using namespace std;
int main()
{
    int a, b; //待輸入的兩個數
    cin>>a>>b;
    int r=a%b; //定義r為a/b的余數
    while(r!=0){ //r為0時的b即為最大公約數
        a=b;
        b=r;
        r=a%b;
    }
    cout<<b;
    return 0;
}

有關輾轉相除法，建議自己隨便寫兩個數，然后手推一下，驗證它的可行性，同時也加深記憶，這里給出一個手推例子：24和16

a=24,b=16,r=24%16=8,c!=0;
a=b=16,b=r=8,r=16%8=0,c==0;

r=0時，b=8即為24和16的最大公因數

提交結果Accepted

遞回解

#include <iostream>
using namespace std;
int gcd(int x, int y){
    int r=x%y; //余數r
    if(r==0)return y; //遞回終點
    x=y;
    y=r;
    return gcd(x, y); //執行新的遞回
}

int main()
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
}

第三題——遞回：爬樓梯

題目鏈接：傳送門

描述

小明爬樓梯，他可以每次走1級或者2級，輸入樓梯的級數，求不同的走法數，
例如：樓梯一共有3級，他可以每次都走一級，或者第一次走一級，第二次走兩級；也可以第一次走兩級，第二次走一級，一共3種方法，

輸入

輸入包含若干行正整數，第一行正整數K代表資料組數；后面K行，每行包含一個正整數N，代表樓梯級數，1 <= N <= 30

輸出

不同的走法數，每一行輸入對應一行輸出

樣例輸入

3
5
8
9

樣例輸出

8
34
89

解題思路

這個題真的是宇宙無敵超級好題，我想詳細講一下這個題的遞推公式是怎么來的，再順便說一下

“輸入包含若干行正整數，第一行正整數K代表資料組數；后面K行，每行包含…”

這種題目要求，應該如何處理

遞推公式

我們現在考慮一般情況，用f(n)表示到第n階的走法種類數，且我們假設已經算出來f(n-1)和它之前的所有項，那么問自己這樣一個問題：

想要到達第n階，有幾種可能？

1. 從第(n-1)階出發，邁一步過來
2. 從第(n-2)階出發，邁兩步過來

想要到第n階，只有這兩種可能性

等等，我從第n-2階出發，先邁一步，再邁一步，不也是一種可能嗎？

不是，因為你先邁一步，到了n-1階以后，問題變成了“從第n-1階到第n階”，這種可能性已經被算入第一種情況

綜上，到達第n階的f(n)種走法被分成了兩部分：

• 來自第n-1階的一部分，有f(n-1)種
• 來自第n-2階的另一部分，有f(n-2)種

也就是說，我們得到了遞推公式：

f(n)=f(n-1)+f(n-2);

做到這，你已經可以用遞推寫出答案來了，但我們能不能嘗試一下不經過遞推，直接寫遞回？

我們之前給過一個假設，那就是“已經算出來f(n-1)和它之前的所有項”，但事實上我們根本不知道它們是多少，而是需要現算：

如果遇到f(n-1)，我們需要用f(n-2)+f(n-3)去算它，而f(n-2)和f(n-3)也不知道，也需要用這樣的規律繼續去算，直到不依賴規律，我們也能得到結果，比如算到f(3)=f(2)+f(1)，我們知道f(1)=1，f(2)=2，

這其實跟計算機的遞回呼叫程序是一樣的，

int f(int n){
    if(n==1)return 1; //遞回終點
    if(n==2)return 2; //遞回終點
    return f(n-1)+f(n-2); //遞回呼叫
}

n組輸入&輸出的處理

這個東西就像一個“套路”一樣，只要記住就可以，并且也不難理解

int t; //t組資料
cin>>t; 
while(t--){
    ...
}

題解代碼

#include <iostream>
using namespace std;
int f(int n){
    if(n==1)return 1;
    if(n==2)return 2;
    return f(n-1)+f(n-2);
}
int main()
{
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<f(n)<<endl;
    }
    return 0;
}