7-54 整数分解为若干项之和_dfs深度优先搜索
程序员文章站
2022-03-13 15:49:53
...
知识点
此题是深度优先搜索算法的变形,除去了访问标志。我们先来回顾下什么是深度优先搜索,以此题为背景,以N=3为例,则从1开始一直搜索,搜索到11,再搜索1,即状态为1 1 1,发现满足要求,返回上一层,状态变成1 1,再搜索2,即状态变为1 1 2,发现当前和超过3,返回上一层,状态变为1 1 ,再搜索3,以此类推,直到搜索到N=3,返回上一层变为1 1,因为搜索N个搜索完了,再返回上一层状态变为1。至此,1 1开头,后一位为试探数已经试探完毕,故1 2开头,搜索,直到N=3,1,3开头。。。最后返回到1,1变为2,以2开头。。。依次类推,其本质为对N做一个全排列,总数为N!
这就是所谓的试探回溯法,先逐层试探,满足条件了再逐层回溯。
#include<bits/stdc++.h>
using namespace std;
int N,sum=0,cnt=0;
int result[31],pos=-1;//定义试探数组,存放试探数字
void dfs(int x){
if(sum==N){ //如果试探和等于待匹配数
cnt++; //成功次数+1
cout<<N<<'=';
for(int i=0;i<pos;i++){ //输出试探数
cout<<result[i]<<'+';
}
if(cnt%4==0||result[pos]==N){//判定最后一个试探数的情况
//如果成功次数为4的倍数或者试探数等于待匹配数
cout<<result[pos]<<endl;//输出试探数并换行
} else{
cout<<result[pos]<<';';//否则按格式输出
}
return;
}
else if(sum>N){//如果试探和大于待匹配数,则返回到上一层
return;
}
for(int i=x;i<=N;i++){//范围从输入参数,即上一层传进来的试探数开始到待匹配数
result[++pos]=i; // 指针指向下一位置并保存当前变量为试探数
sum+=i; //试探和累加试探数
dfs(i); //递归试探
sum-=i; //试探完后减去试探数,以待下一循环加上新的试探数来试探
pos--; //指针回复到原来的位置,以待下一次自增并保存新的试探数
// pos=0 result[0]; sum=1; dfs(1); sum=0;
}//注意,sum,pos作为全局变量,在连续递归调用的情况下会一直自增,故无需担心自增后马上被减去
}
int main(){
cin>>N;
dfs(1);
return 0;
}
学长代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
template <class T>
inline void read(T &x) {
x=0;
int f=0;
char c=getchar();
while(!isdigit(c)) {
f|=(c=='-');
c=getchar();
}
while(isdigit(c)) {
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
if(f) x=-x;
}
const int maxn=1e3+5;
ll gcd(ll x,ll y){
return y==0?x:gcd(y,x%y);
}
ll a[1005],cnt=0,nn;
void dfs(ll pos,ll n,ll num){
if(n==0){
cout << nn << "=" ;
rep(j,0,num-1){
if(j!=0) putchar('+');
cout << a[j];
}
cnt++;
if(cnt%4 && num!=1) putchar(';');
else putchar('\n');
return ;
}
rep(i,pos,n){
a[num]=i;
dfs(i,n-i,num+1);
}
}
int main() {
ll n;
read(n);
nn=n;
rep(i,1,n){
a[0]=i;
dfs(i,n-i,1);
}
return 0;
}
上一篇: 习题7-2 求一批整数中出现最多的个位数字 (20分)
下一篇: Java 10进制和16进制互转