欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基础编程题目集 7-37 整数分解为若干项之和

程序员文章站 2022-03-13 15:50:05
...

7-37 整数分解为若干项之和

题目链接-7-37 整数分解为若干项之和
基础编程题目集 7-37 整数分解为若干项之和
解题思路
dfs递归思想

  • 因为因子要递增出现,所有循环内要判断当前要分解的因子是不是比上一个大。
  • 具体操作见代码

附上代码

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=1e5+5;
typedef long long ll;
typedef pair<int,int> PII;
int cnt,n;
int a[35]={1};
void print(int pos){
	cnt++;//计数
	cout<<n<<"=";
	for(int i=1;i<=pos-1;i++)
		cout<<a[i]<<"+";
	if(cnt%4==0||a[pos]==n)
		cout<<a[pos]<<endl;
	else
		cout<<a[pos]<<";";
}
void dfs(int x,int pos){//x是每一步需要拆分的数 
	for(int i=a[pos-1];i<=x;i++){
		if(i<=n){//当前数i要大于等于前1位数,且不超过n
			a[pos]=i;//保留当前拆分的数i
			x-=i;//拆分后的x
			if(x==0)
				print(pos);//拆分结束,输出结果
			else
				dfs(x,pos+1);//否则继续递归
			x+=i;//回溯,加上拆分的数,以便产生所有可能产生的拆分
		} 
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>n;
	dfs(n,1);
	return 0;
}
相关标签: dfs PTA