埃及分数(迭代搜索(按层数剪枝))


//在古埃及,人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数 
//x/y=1/a+1/b+....+1/x+1/y+1/z+....
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5;
const int INF=0x3f3f3f3f;
bool flag;
LL best,limt;
LL way[N],ans[N];//way:临时数组 
void dfs(LL x , LL y , LL dep)
{
    LL l1,l2,xx,yy;
    //当前分母必须比上次的分母大 
    l1 = max(way[dep-1]+1,y/x); //寻找当前层数分母的最小值 
    //至少为:(1/i)*(limt-dep+1)>=a/b
    l2 = min(y*(limt-dep+1)/x,best-1);//寻找当前层数分母的最大值 
    for(LL i=l1;i<=l2;i++)
    {//x/y=1/i+....<---->....=x/y-1/i=(x*i-y)/(y*i)
        xx=x,yy=y,way[dep]=i;
        xx=xx*i-yy;//计算剩余的分子 
        if(xx<0) continue;
        yy=yy*i;//计算剩余的分母 
        if(dep<limt) dfs(xx,yy,dep+1);
        if(i<best&&xx==0)//dep==limt--xx=0说明limt个数累加等于a/b 
        {
            flag=true,best=i;
            for(int j=1;j<=limt;j++)
				ans[j]=way[j]; //更新答案
        }
    } 
}
int main()
{
    LL a,b;
    scanf("%lld %lld",&a,&b);
    flag=false,way[0]=1,best=INF;
    while(!flag){
        limt++; // 枚举当前深搜的层数 
        dfs(a,b,1);
    }
    printf("%d/%d = ",a,b);
    for(LL i = 1; i < limt ; i ++)
    	printf("1/%d + ",ans[i]);
    printf("1/%d",ans[limt]);
    
    return 0; 
}
上一篇:字节跳动技术整理:mysql8修改默认密码


下一篇:一招教你看懂Netty!mysqlinstaller安装