描述

將正整數(shù)n 表示成一系列正整數(shù)之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。

正整數(shù)n 的這種表示稱為正整數(shù)n 的劃分。正整數(shù)n 的不同的劃分個(gè)數(shù)稱為正整數(shù)n 的劃分?jǐn)?shù)。

輸入

標(biāo)準(zhǔn)的輸入包含若干組測試數(shù)據(jù)。每組測試數(shù)據(jù)是一個(gè)整數(shù)N(0 < N <= 50)。

輸出

對于每組測試數(shù)據(jù)，輸出N的劃分?jǐn)?shù)。

樣例輸入

5

樣例輸出

7

提示

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

可能是因?yàn)楸救吮容^笨的原因吧，這道題提交了九遍才對。

一開始覺得像斐波那契的變式，但后來才發(fā)現(xiàn)不行，才老老實(shí)實(shí)寫遞歸，這個(gè)問題我們需要把我們遞歸的數(shù)記錄下來，因?yàn)轭}目說了(n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1)

所以我們用a數(shù)組來記錄，每次判斷這個(gè)數(shù)行不行時(shí)，就與前面的數(shù)進(jìn)行判斷，比大小，本人給這個(gè)遞歸函數(shù)取了一個(gè)沒有技術(shù)含量的名字叫solve(int n)，我們用循環(huán)從1到n(兩端取到，不必從0~n，因?yàn)?可以一直遞歸下去，而且判斷n時(shí)，就相當(dāng)于在判斷0)。

OK，那么我們這個(gè)邊界值就是n==0，就cnt++;

最后輸出。

提醒一下，數(shù)據(jù)最大為50，會超時(shí)，所以我們保險(xiǎn)起見，先把40~50的結(jié)果打出來，直接復(fù)制給a，然后輸出。

我是把1~40的先算出來，40-50的直接復(fù)制。然后再輸入n，直接輸出。

好了，看代碼。

#include

using namespace std;

long long int n,a[1000],cnt,b[70];

void solve(int m,int death)

{

bool flag=1;

if(m==0)

{

cnt++;

}

else

{

for(int i=1;i<=m;i++)

{

flag=1;

++death;

for(int j=1;j

if(a[j]>i)

{

flag=0;

break;

}

if(flag)

{

a[death]=i;

solve(m-i,death);

}

--death;

}

}

}

int main()

{

for(int i=1;i<=39;i++)

{

solve(i,0);

memset(a,0,sizeof(a));

b[i]=cnt;

cnt=0;

}

b[40]=37338;

b[41]=44583;

b[42]=53174;

b[43]=63261;

b[44]=75175;

b[45]=89134;

b[46]=105558;

b[47]=124754;

b[48]=147273;

b[49]=173525;

b[50]=204226;

while(cin>>n)

{

cout<

}

}

標(biāo)簽：cnt,death,正整數(shù),遞歸,int,flag,50,整數(shù),劃分

來源： https://blog.csdn.net/cxoi9010/article/details/116381931

總結(jié)

以上是生活随笔為你收集整理的整数划分问题的递归算法-c语言,简单的整数划分问题（递归）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。