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

201

题目


Description  


将正整数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。


Input  


多组输入EOF结束,每组输入包含一个数字n表示要拆分的数字(1<=n<=50)


Output  


对于每组输入,输出所有的拆分,每个拆分一行。对于每个拆分,先输出大的数字,再输出小的数字。对于所有拆分,先输出拆分中最大数较大的,最大数相等时先输出次大数较大的....这样的顺序,具体见样例


Sample Input  


5
6


Sample Output  


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


题解



对于一个整数a我们对其进行拆分,可以从a里面分出小于a的所有自然数Ni
这时,我们还需要分解a-Ni,并且以后再分解出的数不能够超过Ni
根据这个可以写出递归的函数
每加深一层递归,就把当前选择的数记录下来,当递归到最后时输出即可

如果使用int数组记录,则会导致超时
而显然算法上已经很难在优化了。
应该使用char数组来记录数据,因为直接输出字符串,比循环拼接一群int要快`

要特别注意,如果当前要记录的数i满足i>=10,那么我们将其转换成char时,需要逐位进行转换。


递归的终点是需要分解的数小于等于0
当递归到需要分解的数为0时,输出



代码


/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn = 55*2*2;
char flag[maxn];


void DFS(int a,int max,int pos) {
if(a < 0)
return;
if(a == 0) {
/*for(int i = 0;i < pos;i++) {
if(i)
printf("+");
printf("%d",flag[i]);
}
printf("\n");*/
flag[pos - 1] = '\0';
printf("%s\n",flag);
return;
}

for(int i = max;i >= 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) + '0';
j %= bit;
bit /= 10;
}
//flag[pos] = i+'0';
flag[pos2++] = '+';
DFS(a - i,i,pos2);
//flag[pos] = -1;
}
}

bool Do() {
int n;
if(scanf("%d",&n) == EOF)
return false;
DFS(n,n,0);
return true;
}

int main() {
while(Do());
/*for(int i = 5;i <=6;i++)
DFS(i,i,0);*/
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论