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

数的拆分(1)

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

【题目描述】

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


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

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

    分享给朋友：
    返回列表

    上一篇：奶牛的耳语

    下一篇：八皇后问题

    相关文章

    【题解】小x与队列

    【题目描述】小X正和同学们做列队的练习。有n名同学排成一路纵队，编号为i的同学排在从前往后数第i个位置上，即：初始时的队列为1, 2, 3, ..., n。接下来小X会发出若干条指令，每条指令形如“请...

    【题解】公路乘车(动态规划)

    【题目描述】一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。   没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<...

    【题解】最大配对

    题目描述      给出2个序列A={a[1]，a[2]，…，a[n]}，B={b[1]，b[2]，…，b[n]}，从A、B中各选出n个元素进行一一配对（可以不按照原来在...

    【题解】合并有序表

    【题目描述】k路归并问题把k个有序表合并成一个有序表。元素共有n个。【输入描述】读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数，表示第i个序列。总数小于100000。【输出描述】输...

    【题解】流感传染

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

    【题解】阶乘的末尾

    【题目描述】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.