<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 
例如正整数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。
</blockquote>
 
<h2 id="input">Input</h2>
<blockquote>
多组输入EOF结束，每组输入包含一个数字n表示要拆分的数字(1&lt;=n&lt;=50)
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
对于每组输入，输出所有的拆分，每个拆分一行。对于每个拆分，先输出大的数字，再输出小的数字。对于所有拆分，先输出拆分中最大数较大的，最大数相等时先输出次大数较大的....这样的顺序，具体见样例
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
5 
6
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
5 
4+1 
3+2 
3+1+1 
2+2+1 
2+1+1+1 
1+1+1+1+1 
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
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
对于一个整数a我们对其进行拆分，可以从a里面分出小于a的所有自然数Ni。 
这时，我们还需要分解a-Ni，并且以后再分解出的数不能够超过Ni 
根据这个可以写出递归的函数 
每加深一层递归，就把当前选择的数记录下来，当递归到最后时输出即可
如果使用<code>int</code>数组记录，则会导致超时 
而显然算法上已经很难在优化了。 
应该使用<code>char</code>数组来记录数据，因为直接输出字符串，比循环拼接一群<code>int</code>要快`
要特别注意，如果当前要记录的数<code>i</code>满足<code>i&gt;=10</code>,那么我们将其转换成<code>char</code>时，需要逐位进行转换。
递归的终点是需要分解的数小于等于0 
当递归到需要分解的数为0时，输出
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
 
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
using namespace std;
 
const int maxn = 55*2*2;
char flag[maxn];
 
 
void DFS(int a,int max,int pos) {
 if(a &lt; 0)
 return;
 if(a == 0) {
 /*for(int i = 0;i &lt; pos;i++) {
 if(i)
 printf(&#34;+&#34;);
 printf(&#34;%d&#34;,flag[i]);
 }
 printf(&#34;\n&#34;);*/
 flag[pos - 1] = &#39;\0&#39;;
 printf(&#34;%s\n&#34;,flag);
 return;
 }
 
 for(int i = max;i &gt;= 1;i--) {
 //将整数i转化成char
 int pos2 = pos;
 int bit = 1;
 int j = i;
 while(j) {
 j /= 10;
 bit *= 10;
 }
 bit /= 10;
 j = i;
 while(bit) {
 flag[pos2++] = (j / bit) + &#39;0&#39;;
 j %= bit;
 bit /= 10;
 }
 //flag[pos] = i+&#39;0&#39;;
 flag[pos2++] = &#39;+&#39;;
 DFS(a - i,i,pos2);
 //flag[pos] = -1;
 }
}
 
bool Do() {
 int n;
 if(scanf(&#34;%d&#34;,&amp;n) == EOF)
 return false;
 DFS(n,n,0);
 return true;
}
 
int main() {
 while(Do());
 /*for(int i = 5;i &lt;=6;i++)
 DFS(i,i,0);*/
 return 0;
}
</pre>

AOJ 808.算法期末考试D(整数拆分)