埃及分数
有一个困扰我很多天的问题，哪位高手能将此程序注释一下，或大体讲一下思路，谢谢！Problem
在古埃及，人们使用单位分数的和(形如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
第一行:N 表示有N组测试数据，每组测试数据为一行包含a,b(0〈a〈b〈1000)。
Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。
Sample Input
1
19 45
Sample Output
5 6 18
Source
oibh
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>
using namespace std;
const double zero=1e-20;
const double maxn=1e20;
int num;
bool bb;
double tempa[1000],tempb[1000],best[1000],v[1000];
int g_cd(int a,int b)
{
int ta,tb;
ta=a;tb=b;
if(ta<tb)swap(ta,tb);
if(!(ta%tb))return tb;
else return g_cd(tb,ta%tb);
}
void solve(int x)
{
int i,next,temp,prev;
if(x>num)
{
if(fabs(tempa[num])<zero)
{
bb=1;
if(v[num]<best[num])
for(i=1;i<=num;i++)
best[i]=v[i];
}
}else
{
prev=(int(tempb[x-1]/tempa[x-1])>int(v[x-1]+1))?int(tempb[x-1]/tempa[x-1]):int(v[x-1]+1);
next=int((num-x+1)*tempb[x-1]/tempa[x-1]+zero);
if(tempb[x-1]/tempa[x-1]+num-x+1>best[num])return;
for(i=prev;i<=next;i++)
{
v[x]=i;
tempa[x]=tempa[x-1]*i-tempb[x-1];
if(tempa[x]<0)continue;
tempb[x]=tempb[x-1]*i;
if(tempa[x]>-zero && int(tempa[x]*v[x]/tempb[x])<=num-x)
solve(x+1);
}
}
}
int main(int argc, char *argv[])
{
int i,j,n,temp,a,b;
cin>>n;
for(j=0;j<n;j++)
{
cin>>a>>b;
temp=g_cd(a,b);
a/=temp;b/=temp;
if(a==1)
cout<<b<<endl;
else
{
v[0]=b/a;num=1;
bb=0;best[1]=maxn;
while(1)
{
num++;
best[num]=maxn;
tempa[0]=a;tempb[0]=b;
solve(1);
if(bb)break;
}
for(i=1;i<num;i++)
cout<<setiosflags(ios::fixed)<<setprecision(0)<<best[i]<<' ';
cout<<best[num]<<endl;
}
}
//system("PAUSE");
return 0;
}
