首页 > 其他分享 >洛谷2404 自然数的拆分问题 【搜索】

洛谷2404 自然数的拆分问题 【搜索】

时间:2024-07-03 18:29:34浏览次数:25  
标签:输出 洛谷 int 自然数 样例 dfs 2404 拆分

自然数的拆分问题

题目描述

任何一个大于 1 1 1 的自然数 n n n,总可以拆分成若干个小于 n n n 的自然数之和。现在给你一个自然数 n n n,要求你求出 n n n 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列,其中字典序小的序列需要优先输出。

输入格式

输入:待拆分的自然数 n n n。

输出格式

输出:若干数的加法式子。

样例 #1

样例输入 #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

提示

数据保证, 2 ≤ n ≤ 8 2\leq n\le 8 2≤n≤8。

#include<cstdio>
using namespace std;
int n;
int a[10];
void dfs(int k,int s)
{
	if(s==0)
	{		
		if(k>2)
		{
			for(int i=1;i<k-1;++i)
		  		printf("%d+",a[i]);
			printf("%d\n",a[k-1]);
		}

	}	
	for(int i=a[k-1];i<=s;++i)
	{
		a[k]=i;
		dfs(k+1,s-i);
		a[k]=0;
	}
	
}
int main()
{
	scanf("%d",&n);
	a[0]=1;
	dfs(1,n);
	return 0;	 
}
 

标签:输出,洛谷,int,自然数,样例,dfs,2404,拆分
From: https://blog.csdn.net/tonman7797/article/details/140144603

相关文章

  • 洛谷 P5723 【深基4.例13】质数口袋 题解
    题面传送门观察题目,我们可以看到这是一道朴素的,判断质数的一道题目。何为质数?质数就是除了111和这个本身,没有其他因数的数。特别的,......
  • C++题解(1) 信息学奥赛一本通 1003:对齐输出 洛谷 B2004:对齐输出 土豆编程 T1003:对
    【题目描述】读入三个整数,按每个整数占8个字符的宽度,右对齐输出它们,按照格式要求依次输出三个整数,之间以一个空格分开。【输入】只有一行,包含三个整数,整数之间以一个空格分开。【输出】只有一行,按照格式要求依次输出三个整数,之间以一个空格分开。【输入样例】......
  • 洛谷 U285997 松鼠没有家
    https://www.luogu.com.cn/problem/U285997#submit题目描述星斗大森林里有一棵参天巨树,树上有 nn 个结点,我们给它们编号 11~nn。松鼠每天从树的这头窜到那头,因为它不认真写信息学作业只想划树叶子(树上没办法划水啊),被妈妈给批评了,于是回不了家。现在松鼠想要知道,它从......
  • P2404 自然数的拆分问题
    #include<bits/stdc++.h>#include<math.h>#include<cmath>usingnamespacestd;intmain(){   intn;   cin>>n;   if(n==2)cout<<"1+1";   elseif(n==3){      cout<<"1+1+1"<<endl;     ......
  • 洛谷 P1030 [NOIP2001 普及组] 求先序排列
    因为题目求先序,意味着要不断找根。那么我们来看这道题方法:(示例)中序ACGDBHZKX,后序CDGAHXKZB,首先可找到主根B;那么我们找到中序遍历中的B,由这种遍历的性质,可将中序遍历分为ACGD和HZKX两棵子树,那么对应可找到后序遍历CDGA和HXKZ(从头找即可)从而问题就变成求1.中序遍历ACGD,后序......
  • 洛谷
    题目链接:思路    代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=1e4+10;llx,y,dx,dy,n;boolvis[N];intmp[1010][1010];structpoint{intx,y;booloperator<(conststructpointa)const{......
  • 洛谷P1304 哥德巴赫猜想 (质数题) (内含埃氏筛和欧拉筛等一些小总结解释)
    题目题目解析题目意思很简单,对于每一组数据来说,就是找这个偶数的两个质数相加的那两个质数,并且要满足加法中的第一个质数要是最小的质数,满足第一个质数是最小的质数的情况下也要保证第二个数也是质数代码#include<bits/stdc++.h>usingnamespacestd;boolis_prime(in......
  • 洛谷 P1020 导弹拦截
    题目链接:导弹拦截思路    代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;inta[N],x,l,dp[N],maxn;intg[N],cnt;intmain(){while(cin>>x)a[++l]=x;for(inti=1;i<=l;i++){intk=1......
  • P1255洛谷
    #include<bits/stdc++.h>#include<math.h>#include<cmath>usingnamespacestd;constintmaxn=5050;structBigInt{  inta[maxn];  intlen;  BigInt(){len=1;memset(a,0,sizeofa);}  BigInt(char*s){    len=strlen(s);  ......
  • 洛谷 B3867 [GESP202309 三级] 小杨的储蓄 题解
     题目题目-[GESP202309三级]小杨的储蓄-洛谷题目描述小杨共有 ......