埃及分数

本文主要是介绍埃及分数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

link

搜索中迭代加深的技巧。迭代加深是解决一类答案深度不大、但搜索树可能很深（甚至无限深）、用广搜还不是很好解决的问题。方法是枚举答案的深度，通过限制搜索树深度的方法达到解决问题的目的。

比如这道题。分解得到的分数数量可能非常多，但答案的数量不会太大，就可以通过迭代加深加剪枝的方法进行。

#include<bits/stdc++.h>
//#define zczc
#define int long long
using namespace std;
const int N=2010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}

inline int gcd(int s1,int s2){
	return s2==0?s1:gcd(s2,s1%s2);
}
inline void check(int &s1,int &s2){
	int g=gcd(s1,s2);
	s1/=g,s2/=g;
}
inline int max(int s1,int s2){
	return s1<s2?s2:s1;
}

int m,now[N],an[N];
bool ok=false;
void dfs(int wh,int a,int b,int last){
	//还剩多少个分数，当前还剩的值a/b，上次的分母
	check(a,b);
	if(wh==1){
		if(a!=1)return;now[wh]=b;
		if(ok&&an[1]<now[1])return;
		for(int i=1;i<=m;i++)an[i]=now[i];
		ok=true;return;
	}
	for(int i=max(last+1,b/a);i*a<wh*b;i++){
		if(a*i<=b)continue;
		now[wh]=i;
		dfs(wh-1,a*i-b,b*i,i);
	}
}

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	int a,b;read(a);read(b);
	while(ok==false){
		m++;
		dfs(m,a,b,0);
		if(ok){
			for(int i=m;i;i--)printf("%lld ",an[i]);
		}
	}
	
	return 0;
}

这篇关于埃及分数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！