埃及分数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

#include"stdio.h"
void tran(int a,int b)
{
 int c;
 if(b%a==0) printf("1/%d\n",b/a);
 else
 {
  c=b/a+1;
  printf("1/%d+",c);
  a=a*c-b;
  b=b*c;
  if(a==1)  printf("1/%d\n",b);
  else tran(a,b);
 }
}
void main()
{
  int a,b;
  while(1)
  {
 printf("请输入分子与分母:");
   scanf("%d%d",&a,&b);
   tran(a,b);
  }
}

收到的鲜花

• xiaomiking 于 2009-09-01 11:18 送鲜花  2朵  

似乎不是最优的！等有时间了再想想

这是个竞赛题目

难在于如何判断最优，上面的算法只是一种分解方式！

IDA*

参考了沙发的思路，我感觉有门路了。似乎可以用回溯法，递归实现！当确定要分解出的个数时，每一个埃及分数都是有上下限的。

好难~！

顶起来，大家一起思考~

看来没人做得出来，好失望~~~