一、問題背景

　 整數拆分，指把一個整數分解成若干個整數的和

　　如 3=2+1=1+1+1 共2種拆分

　　我們認為2+1與1+2為同一種拆分

二、定義

　　在整數n的拆分中，最大的拆分數為m，我們記它的方案數為 f(n,m)

　　即 n=x1+x2+??????+xk-1+xk ，任意 x≤m

　　在此我們采用遞歸遞推法

三、遞推關系

　　1、n=1或m=1時　

　　　 拆分方案僅為 n=1 或 n=1+1+1+??????

　　　　　f(n,m)=1

　　2、n=m時

　　　　　S1選取m時，f(n,m)=1，即n=m

　　　　　S2不選取m時，f(n,m)=f(n,m-1)=f(n,n-1)，此時討論最大拆分數為m-1時的情況

　　　　可歸納 f(n,m)=f(n,n-1)+1

　　3、n<m時

　　　　　因為不能選取m，所以可將m看作n，進行n=m時的方案，f(n,m)=f(n,n)

　　4、n>m時

　　　　　S1選取m時，f(n,m)=f(n-m,m)，被拆分數因選取了m則變為n-m，且n-m中可能還能選取最大為m的數

　　　　　S2不選取m時，f(n,m)=f(n,m-1)，此時討論最大拆分數為m-1時的情況

　　　　　可歸納 f(n,m)=f(n,m-1)+f(n-m,m)

總遞推式為

代碼如下

#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>#include <cmath>using namespace std;int f(int n,int m){if ((n!=1)&&(m!=1)){if (n>m) return f(n-m,m)+f(n,m-1);else return 1+f(n,n-1);}else return 1;}void work(){int n,m;cin>>n>>m;cout<<f(n,m);}int main(){freopen("cut.in","r",stdin);freopen("cut.out","w",stdout);work();return 0;}

以上所述是小編給大家介紹的C++ 整數拆分方法詳解，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對武林網網站的支持！