【基础练习】【IDA*】codevs1288 埃及分数题解

深藏阁楼爱情的钟 2022-08-09 12:46 252阅读 0赞

题目描述 Description

在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。 如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种，但是哪种最好呢？ 首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越 好。 如： 19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30, 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18. 最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。 给出a,b(0<a<b<1000),编程计算最好的表达方式。

输入描述 Input Description

a b

输出描述 Output Description

若干个数，自小到大排列，依次是单位分数的分母。

样例输入 Sample Input

19 45

样例输出 Sample Output

5 6 18

这道题目，显然搜索规模会很大，关键在枚举每一次可能搜索的分数时限制上下界的范围，这样能有效减少搜索量。

关于这个，其实网上的题解非常多了 我在这里简单说一下我枚举上下界的依据

限制范围的核心代码如下

ll low=max(v[dep-1]+1,bb/aa);
    	ll high=bb*(k-dep+1)/aa;
    	if (high>oo) high=oo;
    	if(k&&bb/aa+k-dep+1>best[k])return;//¿ÉÄÜÒªÈ¥µô

对于下界，首先分母要比上一个分母v\[dep-1\]大，而且要满足当前分数小于剩下应该分解的分数，在两者中取较大的

对于上界，如果剩下的全部都取一样的分母，那么最后应当是(k-dep+1)\*(1/x)==aa/bb 可推得上述式子

我们这里之所以开long long 是因为在bb/aa的时候可能会超过int的范围 但实质上真正枚举的分母不会超过几十万的范围，因此如果超过int范围我们就把上界定为maxint

最后一行是勉勉强强可以称作“A\*”的东西，如果当前最小分母加上其他所有位置分母取1，得到的最小值仍然大于目前最优解，直接退出。

那么代码如下

//°£¼°·ÖÊý aijifenshu
    //copyright by ametake
    #include
       
         
    #include
        
         
    #include
         
          
    #define ll long long
    #define oo 2147483647
    using namespace std;
    
    const int maxn=12;
    ll v[maxn],best[maxn];
    ll a,b,k;
    bool ok;
    
    ll gcd(ll a,ll b)
    {
    	return b?gcd(b,a%b):a;
    }
    
    bool yue(ll &x,ll &y)
    {
    	ll g=gcd(x,y);
    	x/=g;
    	y/=g;
    	if (x==1) return true;
    	return false;
    }
    
    void dfs(int dep,ll aa,ll bb)
    {
    	//printf("*%lld %lld\n",aa,bb);
    	if (dep==k)
    	{
    		if (bb%aa!=0) return;
    		v[k]=bb/aa;
    		if (v[k]!=v[k-1]&&v[k]
          
           oo) high=oo;
    	if(k&&bb/aa+k-dep+1>best[k])return;//¿ÉÄÜÒªÈ¥µô 
    	for (ll i=low;i<=high;i++)//Ã¶¾ÙÃ¿Ò»ÖÖ¿ÉÄÜ£¬Í¬Ê±´¦Àí 
    	{
    		if (i==v[dep-1]) continue;
    		v[dep]=i;
    		ll xa=aa*i-bb,ya=bb*i;
    		if (xa<0||ya<0) continue;
    		//printf("*%d %d\n",xa,ya);
    		yue(xa,ya);
    		dfs(dep+1,xa,ya);
    	}
    }
    
    void outit()
    {
    	for (int i=1;i

`AC这个题特别有成就感，这是老题了，以前也做过，一直望而生畏，总算是了结一块心病 今天暂时搬家，希望在这个屋子里也能好好的学。 ——楚塞三湘接，荆门九派通`