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

数的拆分(1)

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

【题目描述】

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


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

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

分享给朋友：
返回列表

上一篇：奶牛的耳语

下一篇：八皇后问题

相关文章

【题解】AC

4．AC(ac.cpp) 【问题描述】 小明获得了一行字符串，他想知道在不改变字符顺序的情况下，从前到后最多能组合出多少个ac？ （a和c的位置可以不连续）比如：字符串为addca...

【题解】01背包

【题目描述】一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。【输入描述】第一...

【题解】踩方格

【题目描述】有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b、走过的格子立即塌陷无法再走第二次；c、只能向北、东、西三个方向走；请问...

【题解】老王赛马

【题目描述】赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。 赛马是当时最受...

【题解】真分数（2019青岛市程序设计竞赛）

【描述】真分数，指的是分子比分母小的分数，真分数的分数值小于1。给出n个正整数，任取两个数分别作为分子和分母组成真分数。求能组成多少不同值的真分数。【输入】第一行是一个正整数n。第二行是n个不同的正整...

【题解】相关数

【题目描述】一个数与另一个数如果含有相同数字和个数的字符，则称两数相关。现有一堆乱七八糟的整数，里面可能充满了彼此相关的数，请你用一下手段，自动地将其剔除。【输入描述】每组数据前有一个N(<10...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.