当前位置：首页 > 题解目录 > 正文内容

数的拆分(1)

亿万年的星光5年前 (2021-01-28)题解目录8419

【题目描述】

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。例如：当n=7时

7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14

【输入描述】

一个数N

【输出描述】

一个数，表示多少种拆分的方式

【样例输入】

3

【样例输出】

3=1+1+1
3=1+2
total=2

【题目分析】

【参考代码1】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int a[100000]={1};int n,tot;
void dfs(int,int);
void print(int);
int main()
{
   cin>>n;
   dfs(n,1);
   cout<<"total="<<tot;
   return 0;
}
void dfs(int p,int q)
{
   int i;
   for(i=a[q-1];i<=p;i++)
   {
       if(i<n)
       {
           a[q]=i;
           p-=i;
           if(p==0)print(q);
           else dfs(p,q+1);
           p+=i;
       }
   }
}
void print(int j)
{
   tot++;
   cout<<n<<"=";
   for(int i=1;i<=j;i++)
   {
       if(i!=j)
       cout<<a[i]<<"+";
       else cout<<a[i];
   }
   cout<<endl;
}


扫描二维码推送至手机访问。

版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。

分享给朋友：
返回列表

上一篇：奶牛的耳语

下一篇：八皇后问题

相关文章

【题解】黑色联通块

【题解】黑色联通块

【题目描述】输入一个n×n的黑白图像（1表示黑色，0表示白色），任务是统计其中黑色连通块的个数。如果两个黑格子有公共边或者公共顶点，就说它们属于同一个联通块。如下图所示的图形有3个联通块。【输入描述】...

【题解】滑翔翼

【题目描述】小T和小K都是OIER，入选省队后有幸去苏州参加JSOI集训，训练之余，他们相约一起去苏州乐园玩。苏州乐园里有一个非常热门的游乐项目叫双人滑翔翼。小T想和小K一起乘双人滑翔翼，但是排在他们...

【题解】连通块

【题目描述】一个n × m的方格图，一些格子被涂成了黑色，在方格图中被标为1，白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子...

家庭作业

题目描述老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10，要求在6天内交，那么要想拿到这10学分，就...

奶牛的耳语

【题目描述】在你的养牛场，所有的奶牛都养在一排呈直线的牛栏中。一共有 n头奶牛，其中第 ii头牛在直线上所处的位置可以用一个整数坐标 pi(0<pi<10^8...

【题解】区间合并

【题目描述】给定n个闭区间[ai,bi]，其中i=1,2,...n。任意两个相邻或相交或相邻的闭区间可以合并为一个闭区间。例如，[1,2]和[2,3]可以合并为[1,3]。[1,3]和[2,4]可以合...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.