P2404 自然数的拆分问题

admin · 发表于 2018-5-12 23:15:14

https://www.luogu.org/problemnew/show/P2404

题目背景
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

题目描述
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

输入输出格式
输入格式：
输入：待拆分的自然数n。

输出格式：
输出：若干数的加法式子。

输入输出样例
输入样例#1：
7
输出样例#1：
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
说明
用回溯做。。。。

n≤8

黄煦喆 · 发表于 2018-9-2 12:13:20

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

复制代码

universehyf · 发表于 2018-9-1 21:09:56

#include<iostream>
using namespace std;
int s[9];
int n,c,t;
void dfs(int x)
{
for(int i=s[x-1];i<n;i++)
if(c+i<=n)
{
c+=i;s[x]=i;
if(c==n)
{
cout<<s[1];
for(int j=2;j<=x;j++)
cout<<"+"<<s[j];
cout<<endl;
}
else dfs(x+1);
c-=i;
}
else return;
}
int main()
{
cin>>n;s[0]=1;
dfs(1);return 0;
}

复制代码

倚窗倾听风吹雨 · 发表于 2018-7-12 16:39:38

#include<iostream>
using namespace std;
int n,a[10001]={1},t=1;
void dfs(int x,int y)
{
int i,k;
if(y==0)
{
for(k=1; k<x-1; k++)
cout<<a[k]<<"+";
cout<<a[x-1]<<endl;
return;
}
else
for(i=a[x-1]; i<=y; i++)
{
if(i<n)
{
a[x]=i;y-=i;
dfs(x+1,y);
y+=i;
}
}
}
int main()
{
cin>>n;
dfs(1,n);
return 0;
}

复制代码

t20020125 · 发表于 2018-7-5 09:15:13

#include<iostream>
#include<cstdio>
using namespace std;
const int mm=100;
int n;
int a[mm];
void dfs(int f,int m,int l)
{
if(l==0&&f!=2)
{
      //cout<<f<<"====";
      for(int i=1;i<=f-2;i++)
      {
         cout<<a[i]<<'+';
      }
      cout<<a[f-1];
      cout<<endl;
}
else if(l<m)return;
else
{
      for(int i=m;i<=l;i++)
      {
         a[f]=i;
         dfs(f+1,i,l-i);
      }
}
}
int main()
{
cin>>n;
dfs(1,1,n);
return 0;
}

Scorpio · 发表于 2018-6-28 20:17:16

#include<iostream>
using namespace std;
int a[9];
int n;
void hhh(int i,int s)
{
int j,k;
if(s>=n)
{
for(j=1;j<=i-1;j++)
if(j==1)
cout<<a[j];
else
cout<<"+"<<a[j];
cout<<endl;
}
else for(k=1;k<=n-s;k++)
{
if(k>=a[i-1]&&k!=n)
{
a[i]=k;
hhh(i+1,s+a[i]);
}
}
}
int main()
{
cin>>n;
hhh(1,0);
return 0;
}

复制代码

冯文韬 · 发表于 2018-6-26 20:45:26

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

复制代码

吴语林 · 发表于 2018-6-25 21:26:08

#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n,a[20];
void dfs(int left,int last,int w)
{
if(left==0&&w!=1)
{
for(int i=1;i<w;i++)
printf("%d+",a[i]);
printf("%d\n",a[w]);
return ;
}
for(int i=last;i<=left;i++)
a[w+1]=i,dfs(left-i,i,w+1);
}
int main()
{
scanf("%d",&n);
dfs(n,1,0);
return 0;
}

复制代码

admin · 发表于 2018-6-4 17:04:07

李思旷同学的那个string out真是别出心裁！

李思矿 · 发表于 2018-6-4 13:52:21

#include<iostream>
#include<algorithm>
using namespace std;
int n;
void dfs(int last,int now,int tot,string out)
{
if(now==tot)
{
cout<<out<<endl;
return ;
}
for(int i=last;i<=tot-now;i++)
{
string str=out;
str+='+';
str+=i+'0';
dfs(i,now+i,tot,str);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n/2;i++)
{
string str="";
str+=i+'0';
dfs(i,i,n,str);
}
return 0;
}

复制代码

		自动登录	找回密码
密码			立即注册