埃及分数的算法解决
发布网友
发布时间：2022-04-26 21:56
共1个回答
热心网友
时间：2023-11-07 18:08
题目
埃及分数
在古埃及，人们使用单位分数的和（形如 1/a 的，a 是自然数）表示一切有理数。 如：
2/3=1/2+1/6，但不允许 2/3=1/3+1/3，因为加数中有相同的。 对于一个分数 a/b，表示方
法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。 如：
最好的是最后一种，因为 1/18 比 1/180、1/45、1/30、1/180 都大。
【输入文件】
给出两个正整数 a、b（0 < a < b < 1000），编程计算对于分数 a/b 最好的表达方式。
【输出文件】
若干个数，自小到大排列，依次是单位分数的分母。
【样例输入】
19 45
【样例输出】
5 6 18
pascal 代码（迭代加深，有更好的算法）
var
temp,ans:array[1..20]of longint;
flag:boolean;
aim:extended;
a,b,te,maxd:longint;
function *(a,b:longint):int;
begin
if b=0 then exit(a);
exit(*(b,a mod b));
end;
function lcm(a,b:longint):int;
var
t:longint;
begin
if a<b then
begin
t:=a;a:=b;b:=t;
end;
exit(a div *(a,b)*b);
end;
procere sum(var s1,s2:int;m:longint);
var
t:int;
begin
t:=lcm(s2,m);
if t>100000 then
begin
s1:=10000;
s2:=1;
exit;
end;
s1:=t div s2*s1+t div m;
s2:=t;
t:=*(s1,s2);
s1:=s1 div t;
s2:=s2 div t;
end;
procere fc(s1,s2:longint);
var
i:longint;
begin
if (s1=a)and(s2=b) then
begin
flag:=true;
if ans[maxd]>temp[maxd] then
ans:=temp;
end;
end;
procere dfs(s:extended;s1,s2,m,i:int);
var
j:longint;
up,down,t1,t2:int;
begin
if s1/s2>aim then exit;
if i>maxd then begin fc(s1,s2); exit;end;
up:=trunc(1/(aim-s));
if up<m then up:=m;
down:=trunc((maxd-i+1)/(aim-s))+100;
for j:=up to down do
begin
temp[i]:=j;
t1:=s1;t2:=s2;
sum(t1,t2,j);
dfs(s+1/j,t1,t2,j+1,i+1);
end;
end;
procere print;
var
i:longint;
begin
for i:=1 to maxd-1 do
write(ans[i],' ');
writeln(ans[maxd]);
end;
begin
fillchar(ans,sizeof(ans),$3f);
read(a,b);
te:=*(a,b);
a:=a div te;
b:=b div te;
aim:=a/b;
maxd:=1;
flag:=false;
while not flag do
begin
inc(maxd);
dfs(0,0,1,2,1);
end;
print;
end.
还有更基础的解法，初学者可用：
var a,b,c:integer;
begin
write('a,b=');readln(a,b);
write(a,'/',b,'=');
repeat
c:=b div a +1;
a:=a*c-b;
b:=b*c;
write('1/',c);
write('+');
until (a=1) or (b mod a=0);
if (b mod a=0)and(a<>1)
then write('1/',b div a);
if a=1 then write('1/',b);
readln;
end.
热心网友
时间：2023-11-07 18:09
题目
埃及分数
在古埃及，人们使用单位分数的和（形如 1/a 的，a 是自然数）表示一切有理数。 如：
2/3=1/2+1/6，但不允许 2/3=1/3+1/3，因为加数中有相同的。 对于一个分数 a/b，表示方
法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。 如：
最好的是最后一种，因为 1/18 比 1/180、1/45、1/30、1/180 都大。
【输入文件】
给出两个正整数 a、b（0 < a < b < 1000），编程计算对于分数 a/b 最好的表达方式。
【输出文件】
若干个数，自小到大排列，依次是单位分数的分母。
【样例输入】
19 45
【样例输出】
5 6 18
pascal 代码（迭代加深，有更好的算法）
var
temp,ans:array[1..20]of longint;
flag:boolean;
aim:extended;
a,b,te,maxd:longint;
function *(a,b:longint):int;
begin
if b=0 then exit(a);
exit(*(b,a mod b));
end;
function lcm(a,b:longint):int;
var
t:longint;
begin
if a<b then
begin
t:=a;a:=b;b:=t;
end;
exit(a div *(a,b)*b);
end;
procere sum(var s1,s2:int;m:longint);
var
t:int;
begin
t:=lcm(s2,m);
if t>100000 then
begin
s1:=10000;
s2:=1;
exit;
end;
s1:=t div s2*s1+t div m;
s2:=t;
t:=*(s1,s2);
s1:=s1 div t;
s2:=s2 div t;
end;
procere fc(s1,s2:longint);
var
i:longint;
begin
if (s1=a)and(s2=b) then
begin
flag:=true;
if ans[maxd]>temp[maxd] then
ans:=temp;
end;
end;
procere dfs(s:extended;s1,s2,m,i:int);
var
j:longint;
up,down,t1,t2:int;
begin
if s1/s2>aim then exit;
if i>maxd then begin fc(s1,s2); exit;end;
up:=trunc(1/(aim-s));
if up<m then up:=m;
down:=trunc((maxd-i+1)/(aim-s))+100;
for j:=up to down do
begin
temp[i]:=j;
t1:=s1;t2:=s2;
sum(t1,t2,j);
dfs(s+1/j,t1,t2,j+1,i+1);
end;
end;
procere print;
var
i:longint;
begin
for i:=1 to maxd-1 do
write(ans[i],' ');
writeln(ans[maxd]);
end;
begin
fillchar(ans,sizeof(ans),$3f);
read(a,b);
te:=*(a,b);
a:=a div te;
b:=b div te;
aim:=a/b;
maxd:=1;
flag:=false;
while not flag do
begin
inc(maxd);
dfs(0,0,1,2,1);
end;
print;
end.
还有更基础的解法，初学者可用：
var a,b,c:integer;
begin
write('a,b=');readln(a,b);
write(a,'/',b,'=');
repeat
c:=b div a +1;
a:=a*c-b;
b:=b*c;
write('1/',c);
write('+');
until (a=1) or (b mod a=0);
if (b mod a=0)and(a<>1)
then write('1/',b div a);
if a=1 then write('1/',b);
readln;
end.
