整数拆分

2013年11月28日4,2770

来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1261

题目描述

一个正整数N(N<=20)可以划分成若干个正整数的和的形式，例如5可以划分成以下几种形式：
5＝1＋1＋1＋1＋1
5＝1＋1＋1＋2
5＝1＋1＋3
5＝1＋2＋2
5＝1＋4
5＝2＋3
5＝5

编写一个程序，输入任意一个不大于20的整数N，按以上格式输出它的所有拆分。

输入

只有一行，包含一个整数N（N不超过20）。

输出

按样例中格式，输出对N的所有拆分。

样例输入

样例输出

5=1+1+1+1+1 5=1+1+1+2 5=1+1+3 5=1+2+2 5=1+4 5=2+3 5=5

提示

#include<iostream>
using namespace std;
int a[10001]={1},n,total;
int search(int,int);
int print(int);
int main()
{
cin>>n;
search(n,1);
cout<<n<<'='<<n;
return 0;
} 
int search(int s,int t)
{
    int i;
    for(i=a[t-1];i<=s;i++)
    if(i<n)
    {
        a[t]=i;
        s-=i;
        if(s==0)print(t);
        else search(s,t+1);
        s+=i; 
    }
}
int print(int t)
{
    cout<<n<<"=";
    for(int i=1;i<=t-1;i++)
    cout<<a[i]<<"+";
    cout<<a[t]<<endl; 
}

#include<iostream>

using namespace std;

int a[10001]={1},n,total;

int search(int,int);

int print(int);

int main()

{

cin>>n;

search(n,1);

cout<<n<<'='<<n;

return 0;

}

int search(int s,int t)

{

int i;

for(i=a[t-1];i<=s;i++)

if(i<n)

{

a[t]=i;

s-=i;

if(s==0)print(t);

else search(s,t+1);

s+=i;

}

int print(int t)

{

cout<<n<<"=";

for(int i=1;i<=t-1;i++)

cout<<a[i]<<"+";

cout<<a[t]<<endl;

}

« 「CODEVS2080」特殊的质数肋骨 NOIP2002选数 »

hzwer.com _ Home | http://hzwer.com

整数拆分

题目描述

输入

输出

样例输入

样例输出

提示

分类目录

热门文章

Myfriends

近期评论