C++ 整數(shù)拆分方法詳解
一、問(wèn)題背景
整數(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ì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
- JavaScript將數(shù)據(jù)轉(zhuǎn)換成整數(shù)的方法
- javascript 計(jì)算兩個(gè)整數(shù)的百分比值
- JavaScript 正則表達(dá)式 驗(yàn)證整數(shù)、小數(shù)、實(shí)數(shù)、有效位小數(shù)最簡(jiǎn)單
- C++求四個(gè)正整數(shù)最大公約數(shù)的方法
- C++初學(xué)者之根據(jù)輸入的任何一個(gè)正整數(shù)，輸出可能被表示的連續(xù)正整數(shù)
- C++實(shí)現(xiàn)十六進(jìn)制字符串轉(zhuǎn)換為十進(jìn)制整數(shù)的方法
- C++通過(guò)自定義函數(shù)找出一個(gè)整數(shù)數(shù)組中第二大數(shù)的方法
- c++ 一個(gè)二進(jìn)制串轉(zhuǎn)化為整數(shù)的解決方法
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言版猜數(shù)字小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-07-07
這篇文章主要介紹了C++的虛析構(gòu)詳解及實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05
C++11 引入了智能指針的概念，使用了引用計(jì)數(shù)的想法，讓程序員不再需要關(guān)心手動(dòng)釋放內(nèi)存。關(guān)于C++指針得內(nèi)容下面文章將為大家做一個(gè)詳細(xì)介紹2021-09-09
這篇文章主要介紹了VC枚舉串口端口應(yīng)用,羅列了常見(jiàn)的一些串口端口的應(yīng)用實(shí)例,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了C++?自定義單向鏈表?ListNode詳情，文章將介紹鏈表中不帶頭結(jié)點(diǎn)，沒(méi)有存放鏈表長(zhǎng)度的節(jié)點(diǎn)，從頭結(jié)點(diǎn)開(kāi)始就存放數(shù)據(jù)得一種，具有一定得參考價(jià)值，需要的小伙伴可以參考一下2022-03-03
所謂“位域”是把一個(gè)字節(jié)中的二進(jìn)位劃分為幾個(gè)不同的區(qū)域， 并說(shuō)明每個(gè)區(qū)域的位數(shù)。每個(gè)域有一個(gè)域名，允許在程序中按域名進(jìn)行操作。 這樣就可以把幾個(gè)不同的對(duì)象用一個(gè)字節(jié)的二進(jìn)制位域來(lái)表示。下面這篇文章就給大家介紹下關(guān)于C語(yǔ)言中位域的使用與注意事項(xiàng)。2016-12-12
如何在Qt中實(shí)現(xiàn)關(guān)于Json?的操作
JSON是一種輕量級(jí)數(shù)據(jù)交換格式,常用于客戶(hù)端和服務(wù)端的數(shù)據(jù)交互,不依賴(lài)于編程語(yǔ)言,在很多編程語(yǔ)言中都可以使用JSON,這篇文章主要介紹了在Qt中實(shí)現(xiàn)關(guān)于Json的操作,需要的朋友可以參考下2023-08-08
數(shù)組是一組有序的數(shù)據(jù)的集合，本篇將帶你結(jié)合數(shù)組來(lái)實(shí)現(xiàn)三子棋小游戲，上手實(shí)練更快的能夠掌握數(shù)組使用，感興趣的朋友來(lái)看看吧2022-04-04
一般在C/C++中，如果我們使用了pointer來(lái)指向某塊heap區(qū)域，當(dāng)不再需要這塊區(qū)域的時(shí)候，我們需要手動(dòng)刪除它。如果忘了的話(huà)，就會(huì)產(chǎn)生memory?leak2022-08-08
這篇文章主要介紹了C++模板特化與偏特化的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下2020-08-08