一.问题描述
在古埃及，人们使用单位分数的和(形如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都大。
二.算法描述
1 //按照贪心输出其中的一种 2 #include<iostream> 3 using namespace std; 4 int main() 5 { 6 int A,B,C,D; 7 cin>>A>>B; 8 if(A>=B) 9 cout<<"error"; 10 cout<<A<<"/"<<B<<"="; 11 while(A!=1) 12 { 13 C=B/A+1; 14 cout<<"1/"<<C<<"+"; 15 16 //下两步骤类似通分 17 A=A*C-B; 18 B=B*C; 19 if(B%A==0) 20 { 21 22 cout<<"1/"<<B/A<<endl; 23 A=1; 24 } 25 } 26 //while(1); 27 return 0; 28 }
等有时间了研究下迭代加深的A*算法……
