本文主要是介绍拆分自然数(c++题解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。
输入格式
输入只有1行,包含1个整数n,表示待拆分的数字。
输出格式
对于每组输入输出n的拆分方法,每种拆分方法占1行,最后输出一共有多少种拆分方案。
样例
样例输入
复制4
样例输出
复制4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
4
数据范围与提示
n在45以内
#include <bits/stdc++.h>
using namespace std;
int a[100005],n,ans;
void f(int x,int y){if(n==x){int z=0;for(int i=1;i<=n;i++){if(a[i]!=0){z=i;break;}}if(z==n){return;}ans++;cout<<n<<"=";cout<<z;for(int i=1;i<a[z];i++){cout<<"+"<<z; }for(int i=z+1;i<=n;i++){for(int j=1;j<=a[i];j++){cout<<"+"<<i; }}cout<<endl; return;}for(int i=y;i<=n-x;i++){a[i]++;f(i+x,i);a[i]--;}
}
int main(){cin>>n;f(0,1);cout<<ans;
}
_____________________________________________________________________________
写作不易,点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________________________________________________
这篇关于拆分自然数(c++题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!