埃及分数 [复制链接]

埃及分数之和


例：
      设计一个程序，把一个真分数表示为埃及分数之和的形式。
问题分析：
    所谓埃及分数，是指分子为1的形式。古代埃及有一个非常奇怪的习惯，他们喜欢把一个分数表示为若干个分子为1的分数之和的形式。如，7/8=1/2+1/3+1/24。
  下面介绍其中一种算法――贪心算法。贪心算法是由数学家菲波那契提出的，基本思想是：
设某个真分数的分子为A，分母为B；
把B除以A的商的整数部分加1后的值作为埃及分数的某一个分母；
将A乘以C减去B作为新的A；
将B乘以C作为新的B；
如果A大于1且能整除B，则最后一个分母为B/A；
如果A＝1，则最后一个分母为B；
否则转步骤（2）。

var s,t:string;
  m,a,b:longint;
  i:integer;
function zy(x,y:longint):longint;
var r:integer;
begin
repeat r:=x mod y;x:=y;y:=r;until r=0;
zy:=x;
end;
begin
readln(s);write(s,'=');
for i:=1 to length(s) do
if s<>'/' then t:=t+s else begin val(t,a);t:='';end;
val(t,b);i:=1;
repeat
inc(i);
m:=i*b div zy(i,b);
a:=a*(m div b);
b:=b*(m div b);
if (a-m div i>0) then begin write('1/',i,'+');a:=a-m div i;end;
if a=1 then begin write('1/',m);exit;end;
if (a-m div i=0) then begin write('1/',i);exit;end;
until a-m div i=0;
end.