遞歸經典整數劃分問題

整數劃分問題是将一個正整數n拆成一組數連加并等于n的形式，且這組數中的最大加數不大于n。

比如6的整數劃分為

    最大數（m）  

      6         6

      5            5 + 1（結果為（6-5）的劃分數且m<=5）

      4         4 + 2, 4 + 1 + 1(結果為（6-4）的劃分數且m<=4)

      3         3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1（結果為（6-3）的劃分數且m<=3）

      2            2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1（結果為（6-2）的劃分數且m<=2）

      1         1 + 1 + 1 + 1 + 1 + 1（結果為（6-1）的劃分數且m<=1）

遞歸函數的聲明為 int solve(int n, int m);其中n為要劃分的正整數，m是劃分中的最大加數(當m > n時，最大加數為n)，

    1 當n = 1或m = 1時，solve的值為1，可根據上例看出，隻有一個劃分1 或 1 + 1 + 1 + 1 + 1 + 1

    可用程式表示為if(n == 1 || m == 1) return 1;（這個地友善是遞歸程式的出口）

    2 下面看一看m 和 n的關系。它們有三種關系

    (1) m > n

    在整數劃分中實際上最大加數不能大于n，是以在這種情況可以等價為solve(n, n);

    可用程式表示為if(m > n) return solve(n, n);    

    (2) m = n

    這種情況可用遞歸表示為solve(n, m - 1) + 1，從以上例子中可以看出，就是最大加

    數為6和小于6的劃分之和

    用程式表示為if(m == n) return solve(n, m - 1) + 1;

    (3) m < n

    這是最一般的情況，在劃分的大多數時都是這種情況。

    從上例可以看出，設m = 4，那solve(6, 4)的值是最大加數小于4劃分數和整數2的劃分數的和。

    是以，solve(n, m)可表示為solve(n, m - 1) + solve(n - m, m)；（m<=4的值，肯定等于m<4的值加上m=4的值，m<4的值肯定會在後面解決，那m=4的值會在目前解決，比如說我已經确定最大數是4（m）了，那麼決定劃分數的因素就是6-4（n-m）怎樣去劃分了，當然你目前的最大m為4，是以你剩下的劃分的最大值要小于等于4）

     代碼

#include <iostream>
using namespace std;
int solve(int n,int m)//n是目前被劃分值，m是劃分快中最大的值
{
    if(n==1||m==1)//問題的出口
        return 1;
        
    //以下是三種情況的讨論。
    if(m>n)//
        return solve(n,n);
    if(m==n)
        return solve(n,m-1)+1;
    if(m<n)
        return solve(n,m-1)+solve(n-m,m);//這一句最難了解，模拟一下過程。
}
int main()
{
    int x;
    cin>>x;
    cout<<solve(x,x)<<endl;
}
           

總結：

使用遞歸的一般條件：

1.遞歸算法一定要有一個邊界出口，能夠結束程式。

2.參數收斂，參數都是收斂于邊界的。（感覺跟第一條沒什麼差別）

3.自身調用。（個人了解就是，你可以通過邊界的加加減減，并通過幾個值之間的關系，遞推出最終的結果，類似于整數劃分斐波那契。。。。hanoi問題我現在還是搞不懂！！）