C++ 整數拆分辦法詳解

C++ 整數拆分辦法詳解。本站提示廣大學習愛好者：（C++ 整數拆分辦法詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C++ 整數拆分辦法詳解正文

1、成績配景

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

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

　　我們以為2+1與1+2為統一種拆分

2、界說

　　在整數n的拆分中，最年夜的拆分數為m，我們記它的計劃數為 f(n,m)

　　即 n=x1+x2+······+xk-1+xk ，隨意率性 x≤m

　　在此我們采取遞歸遞推法

3、遞推關系

　　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++ 整數拆分辦法詳解，願望對年夜家有所贊助，假如年夜家有任何疑問請給我留言，小編會實時答復年夜家的。在此也異常感激年夜家對網站的支撐！