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

数的拆分(1)

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

【题目描述】

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


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

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

    分享给朋友：
    返回列表

    上一篇：奶牛的耳语

    下一篇：八皇后问题

    相关文章

    【题解】开关灯（2）

    1.开关灯（light.cpp）【题目描述】某实验室共有n盏灯，灯的编号为1~n,每盏灯的初始状态是关闭的。现在有m位学生，每位学生可以前去抽取一张带数字的卡片，其数字为Ai，然后依次将自己手中的数字...

    【题解】母牛的故事

    【题解】母牛的故事

    【题目描述】有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？【输入描述】输入数据由多个测试实例组成，每个测试实例占一行...

    【题解】吃糖果

    【题解】吃糖果

    【题目描述】小明终于从小红手里赢走了所有的糖果，小明转变吃掉所有糖果，但是小明吃糖果有个特殊癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另外一种。试问小明是否存在一种吃糖果的顺序使得...

    【题解】合唱队形

    【题目描写】N位同学站成一排，音乐老师要请其中的(N−K)位同学出列，使得剩下的KK位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1,T...

    2021年市南区程序设计竞赛（小学组）

    1.建设病房（build.cpp）【题目描述】2020年1月23日下午，武汉市建设局紧急召集中建三局等单位举行专题会议，要求参照2003年抗击非典期间北京小汤山医院模式，在武汉职工疗养院建设火神山医院...

    线段

    题目描述在一个数轴上有n条线段，现选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少?输入格式第一行为一个正整数n，下面n行每行2个数字ai，bi，描述每条线段。输出格式输出文件仅包括1...

    鲁ICP备20008475号

    Powered By Z-BlogPHP. Theme by TOYEAN.