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

340

题目


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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论