整數(shù)劃分

時(shí)間限制：3000?ms ?|? 內(nèi)存限制：65535?KB 描述

將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，?
其中n1≥n2≥…≥nk≥1，k≥1。?
正整數(shù)n的這種表示稱(chēng)為正整數(shù)n的劃分。求正整數(shù)n的不?
同劃分個(gè)數(shù)。?
例如正整數(shù)6有如下11種不同的劃分：?
6；?
5+1；?
4+2，4+1+1；?
3+3，3+2+1，3+1+1+1；?
2+2+2，2+2+1+1，2+1+1+1+1；?
1+1+1+1+1+1。?

輸入

第一行是測(cè)試數(shù)據(jù)的數(shù)目M（1<=M<=10）。以下每行均包含一個(gè)整數(shù)n（1<=n<=10）。

輸出

輸出每組測(cè)試數(shù)據(jù)有多少種分法。

樣例輸入

1
6

樣例輸出

11

下面轉(zhuǎn)自博客：http://www.cnblogs.com/hoodlum1980/archive/2008/10/11/1308493.html

　　所謂整數(shù)劃分，是指把一個(gè)正整數(shù)n寫(xiě)成如下形式：

　　　　n=m₁+m₂+...+m_i; （其中m_i為正整數(shù)，并且1 <= m_i <= n），則：{m₁,m₂,...,m_i}為n的一個(gè)劃分。

　　如果{m₁,m₂,...,m_i}中的最大值不超過(guò)m，即max(m1,m2,...,mi)≤m，則稱(chēng)它屬于n的一個(gè)m劃分。這里我們記n的m劃分的個(gè)數(shù)為f(n,m);

　　例如：當(dāng)n=4時(shí)，共有5個(gè)劃分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};

　　注意4=1+3 和 4=3+1被認(rèn)為是同一個(gè)劃分。

　　該問(wèn)題是求出n的所有劃分個(gè)數(shù)，即f(n, n)。

　　通用的遞推公式如下：

　　?　　?f(n, m) ? ?= ? ?1;????????? ????????????????????????????? ( n = 1 or m = 1 )

???????????????????????????　　 f(n, n);???????????????????????????????? ( n < m )

??????????????????????????? 　　1+ f(n, m - 1);?????????? ? ? ?? ??? ( n = m )

??????????????????????????? 　　f(n - m, m) + f(n, m - 1); ? ? ? ( n > m )

1）自頂向下實(shí)現(xiàn)的版本：

#include <cstdio>
#include <iostream>using namespace std;int f(int i, int j)
{if(i==1 || j==1)    return 1;if(i<j)    return f(i, i);if(i==j)    return f(i, i-1) + 1;return f(i, j-1) + f(i-j, j);    
}int main ()
{int T, n;scanf("%d", &T);while(T--) {scanf("%d", &n);printf("%d\n", f(n, n));    }return 0;
}

?

2）自底向上實(shí)現(xiàn)的版本：

#include <cstdio>
#include <iostream>using namespace std;const int MAXN = 15;int dp[MAXN][MAXN];void init()
{for(int i=1; i<MAXN; i++) {for(int j=1; j<MAXN; j++) {if(j>i)    dp[i][j] = dp[i][i];else if(j == i)    dp[i][j] = dp[i][j-1] + 1;else    dp[i][j] = dp[i][j-1] + dp[i-j][j];}}
}int main ()
{init();int T, n;scanf("%d", &T);while(T--) {scanf("%d", &n);printf("%d\n", dp[n][n]);}return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/AcIsFun/p/5346053.html

總結(jié)

以上是生活随笔為你收集整理的NYOJ 90 —— 求正整数n划分为若干个正整数的划分个数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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