亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C++ 整數(shù)拆分方法詳解

 更新時(shí)間：2016年08月03日 16:47:45   作者：Code·Hadilo  
整數(shù)拆分，指把一個(gè)整數(shù)分解成若干個(gè)整數(shù)的和。本文重點(diǎn)給大家介紹C++ 整數(shù)拆分方法詳解，非常不錯(cuò)，感興趣的朋友一起學(xué)習(xí)吧

一、問題背景

　 整數(shù)拆分，指把一個(gè)整數(shù)分解成若干個(gè)整數(shù)的和

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

　　我們認(rèn)為2+1與1+2為同一種拆分

二、定義

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

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

　　在此我們采用遞歸遞推法

三、遞推關(guān)系

　　1、n=1或m=1時(shí)　

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

　　　　　f(n,m)=1

　　2、n=m時(shí)

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

　　　　　S2不選取m時(shí)，f(n,m)=f(n,m-1)=f(n,n-1)，此時(shí)討論最大拆分?jǐn)?shù)為m-1時(shí)的情況

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

　　3、n<m時(shí)

　　　　　因?yàn)椴荒苓x取m，所以可將m看作n，進(jìn)行n=m時(shí)的方案，f(n,m)=f(n,n)

　　4、n>m時(shí)

　　　　　S1選取m時(shí)，f(n,m)=f(n-m,m)，被拆分?jǐn)?shù)因選取了m則變?yōu)閚-m，且n-m中可能還能選取最大為m的數(shù)

　　　　　S2不選取m時(shí)，f(n,m)=f(n,m-1)，此時(shí)討論最大拆分?jǐn)?shù)為m-1時(shí)的情況

　　　　　可歸納 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++ 整數(shù)拆分方法詳解，希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

相關(guān)文章

最新評(píng)論