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

数的拆分(1)

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

【题目描述】

任何一个大于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;
}


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

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

分享给朋友：
返回列表

上一篇：奶牛的耳语

下一篇：八皇后问题

相关文章

【题解】选班委

【题目描述】小 T 和他的小伙伴们到 CZ 中学的创新实验班报到后的第一件事就是选班委，班主任 R 老师走上讲台宣布了选举办法，首先让全班 40 位同学依次上讲台做自我介绍，然后按照 职位一个一个依次...

【题解】流感传染

【题目描述】有一批易感人群住在网格状的宿舍区内，宿舍区为n\*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已...

猴子吃桃

【题目描述】猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。 第二天早上又将剩下的桃子吃掉一半，又多吃一个。以后每天早上都吃了前一天剩下的一半零一个。到第N天早上想再吃时...

【题解】走出迷宫的最少步数

【题目描述】一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜...

【题解】Ride to Office

【题目描述】起点与终点相隔4500米。现Charley 需要从起点骑车到终点。但是，他有个习惯，沿途需要有人陪伴，即以相同的速度， 与另外一个人一起骑。而当他遇到以更快的速度骑车的人时，他会以相应的速...

【题解】阶乘的末尾

【题目描述】n的阶乘定义为n!=1*2*3*……*n  如3!=6   n!通常最后会有很多0，如5!=120  最后有一个0，现在统计n!去除末尾的0后，最后k位是多少...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.