埃及分数问题java代码,埃及分数是什么

分子为1的分数称为埃及分数，现输入一个真分数，使用循环方法将该分数分解为埃及分数用C语言解答

子为1 的分数称为埃及分数，现输入一个真分数，请将该分数分解为埃及分数。

成都创新互联公司是一家专注于成都网站制作、网站设计与策划设计,工布江达网站建设哪家好?成都创新互联公司做网站,专注于网站建设10多年,网设计领域的专业建站公司;建站业务涵盖:工布江达等地区。工布江达做网站价格咨询:18982081108

如：8/11=1/2+1/5+1/55+1/110。

*问题分析与算法设计

若真分数的分子a能整除分母b，则真分数经过化简就可以得到埃及分数，若真分数的分子不能整除分母，则可以从原来的分数中分解出一个分母为b/a+1的埃及分数。用这种方法将剩余部分反复分解，最后可得到结果。

*程序说明与注释

/*注：对源程序作稍许修改，主要是添加了一个外循环，可以直接计算多个真分数的埃及分数，按Ctrl-C退出。具体的算法我没有认真看，有问题请提出，谢谢*/

#include

int main(void)

{

long int a,b,c;

while(true)

{

printf("Please enter a optional fraction(a/b):");

scanf("%ld/%ld",a,b); /*输入分子a和分母b*/

printf("It can be decomposed to:");

while(true)

{

if(b%a) /*若分子不能整除分母*/

c=b/a+1; /*则分解出一个分母为b/a+1的埃及分数*/

else{ c=b/a; a=1;} /*否则，输出化简后的真分数(埃及分数)*/

if(a==1)

{

printf("1/%ld\n",c);

break; /*a为1标志结束*/

}

else

printf("1/%ld + ",c);

a=a*c-b; /*求出余数的分子*/

b=b*c; /*求出余数的分母*/

if(a==3) /*若余数为3，输出最后两个埃及分数*/

{ printf("1/%ld + 1/%ld\n",b/2,b); break;}

}

return 0;

}

*运行结果

Please enter a optional fraction (a/b): 1/6

It can be decomposed to: 1/6

Please enter a optional fraction (a/b): 20/33

It can be decomposed to: 1/2+1/10+1/165

Please enter a optional fraction (a/b): 10/89

It can be decomposed to: 1/9+1/801

Please enter a optional fraction (a/b): 19/99

It can be decomposed to: 1/6+1/40+1/3960

Please enter a optional fraction (a/b): 8/87

It can be decomposed to: 1/11+1/957

……（按ctrl-c退出）

四个分数分子为1加起来怎么得1？

这是典型的埃及分数问题。如果限定分解的个数为四个，则只能通过枚举。

一共有14组解。

算法关键在于确定循环搜索的范围。下限是前一个分母的数值，上限则通过等式计算来判断。通过三重循环来搜索，第四个分母通过计算来获取，验证其是否正确。计算时间在1毫秒内。

附：计算结果和fortran代码

埃及分数

埃及分数是指分子是1的分数，也叫单位分数。古代埃及人在进行分数运算时，只使用分子是1的分数。因此这种分数也叫做埃及分数，或者叫单分子分数。

中文名

埃及分数

发明地

埃及

快速

导航

相关发现

两千多年后的数学家终于发现：2/n=1/[(n+1)/2]+1/[(n+1)n/2]； 1/n=1/(n+1)+1/[n(n+1)]；1=1/2+1/3+1/6。此时才大梦初醒。埃及分数以旺盛的生命力屹立在世界数坛，使三千年后的数学家也自叹弗如。例如，分马问题，能否设计出（n-1)/n=1/x+1/y+1/z .。经过2000多年的努力，终于揭开其中的奥秘：有6种可能，共7种分法。7/8=1/2+1/4+1/8；11/12=1/2+1/4+1/6=1/2+1/3+1/12；17/18=1/2+1/3+1/9；19/20=1/2+1/4+1/5；23/24=1/2+1/3+1/8；41/42=1/2+1/3+1/7。原先人们以为，这样的情况大概有无穷多个，可是，继续追击却一无所获，真是难以预料。黑龙江的关春河发现共有43种情况。这是正确的。

求解过程

当限定分母为奇数时，把“1”分解为埃及分数，项数限定为9项，共有5组解：

1=1/3+1/5+1/7+1/9+1/11+1/15+1/35+1/45+1/231。

1=1/3+1/5+1/7+1/9+1/11+1/15+1/21+1/135+1/10395。

1=1/3+1/5+1/7+1/9+1/11+1/15+1/21+1/165+1/693。

1=1/3+1/5+1/7+1/9+1/11+1/15+1/21+1/231+1/315。

1=1/3+1/5+1/7+1/9+1/11+1/15+1/33+1/45+1/385。

以上5组解是在1976年才找到。限定为11项时，发现了1组解最小分母是105。若大于105则有很多的解。

1/n型分数还可以表示成为级数分解式：

1/n=1/(n+1)+1/(n+1)^2+1/(n+1)^3+1/(n+1)^4+....+1/(n+1)^k+1/n(n+1)^k.

埃及分数成为不定方程中一颗耀眼的明珠。

埃及分数最著名的猜想是Erods猜想：1950年Erods猜想，对于n〉1的正整数，

总有：

4/n=1/x+1/y+1/z. （1）

其中，x，y，z。都是正整数。

Stralss进一步猜想，当n≥2时，方程的解x，y，z满足x≠y，y≠z，z≠x。x〈y〈z。

1963年柯召，孙奇，张先觉证明了Erods猜想stralss猜想等价。几年后yamanot又把结果发展到10的7次方。以后一些数学家又把结果推向前去，始终未获根本解决。对于4/n=1/x+1/y+1/z，只需要考虑n=p为素数的情况，因为若（1）式成立，则对于任何整数m，m1，

4/pm=1/xm+1/ym+1/zm，（2）

也成立。

一切奇素数都可以表示为4R+1与4R+3型。对于p=4R+3型，（参见《单位分数》人民教育出版社1962年）：（1）式是显然的。

2002年王晓明提出：

如果设X=AB,Y=AC,Z=ABCP,

即：

4/P=1/AB+1/AC+1/ABCP.（3）

对于p=4R+3型，（3）式是显然的。

因为这时A=(p+1)/4 ，B=1。C=P+1.。

即：

4 /P = { 1/ [(P+1)/4] } + { 1 / [(P+1)(p+1)/4] } + { 1/ [p(p+1)(p+1)/4] }。 (4)

例如：4/7=1/2+1/16+1/112

对于p=4R+1 型的素数，把（3)式整理成：

4ABC=PC+PB+1 (5)

A = (PC+PB+1)/4BC (6)

-PC+TB=1 (7)

SC+(-P)B=1 (8)

例如p=17时，A=3，B=2，C=5，T=43，S=7，k=2 。

4 /17=[1/(2×3)]+[1/(3×5)]+[1/(3×2×5×17 )]

即4/17=1/6+1 /15+1/510.

等价于下面的式子:

（-17）×5+43×2=1

7×5+（-17）×2=1

注意：P=(4ABC-1)/(B+C). (9)

由于4ABC-1是4R+3型，所以，当P=4R+1型时，B+C=4K-1型；P=4R+3,B+C=4K+1型。.

因为对于二元一次不定方程组，我们有得是办法。根据《代数学辞典》上海教育出版社1985年（376页）：“

方程组:ax+by=c

a'x+b'y=c'

公共解（整数解）x,y的充分必要条件是(ab'-a'b)不等于0，并且 (ab'-a'b) | (bc'-b'c) 和 (ab'-a'b) | (ca'-c'a)。”

我们把（7）（8）式的C与B当成上面的x,y. 在（7）式中，只要（P,T）=1；就有无穷多组B和C整数解;在（7）中，只要（P,S）=1，就有B和C的整数解。根据已知的定理（柯召，孙奇《谈谈不定方程》）13 至17页，联立二元一次不定方程，就知道（7）（8）式必然有公共整数解（用到矩阵，单位模变换等知识）。即ST-P×P≠0，(ST-P×P) | (P+T)； (ST-P×P) | (P+S)。为什么说是必然有解，只要有一个素数有解，其它素数必然有解。在中国象棋中，“马”从起点可以跳到所有的点，那么，马在任何一个点就可以跳到任何点。因为马可以从任何一个点退回的起点。

下面是一些p值的解：

--p---|---A---|---B---|----C-----|------T-----|------S-------|-------K-----|

------------------------------------------------------------------------------|

--5---|--2----|---1----|---2------|-----11-----|----3---------|------1------|

-29--|---2----|---4----|---39----|----283----|----3---------|------11-----|

-37--|---2----|---5----|--62-----|---459-----|----3---------|-------17----|

-53--|---2----|---7----|--124----|---939-----|----3--------|-------33----|

-61--|---2----|---8----|--163----|---1243----|----3--------|-------43----|

-173-|--2----|----22--|--1269---|--9979----|----3--------|------323----|

-----------------------------------------------------------------------------------------

以上是P=4R+1，R为奇数时的解，此时，A=2；S=3。

---------------------------------------------------------------------------------

-17--|--3-----|---2----|-----5------|----43-----|-----7--------|-----2-------|

-41--|--12----|---1----|----6-------|---247----|----7---------|-----2-------|

-41--|--6------|---3----|----4-------|---55-----|-----31-------|-----2-------|

-73--|---10----|---2----|---21------|----767--|-----7---------|-----6-------|

- 97--|---17---|---2----|----5-------|---243---|----39--------|-----2-------|

-113-|--5------|---6----|---97------|--1827---|----7---------|----26-------|

-409-|--59-----|---2---|----13------|--2659---|----63-------|----4--------|

-409-|--22-----|---5---|-----66-----|--5399---|----31-------|-----18-----|

-409-|--11-----|---11--|----60-----|---2231--|----75-------|-----18-----|

---------------------------------------------------------------------------------------

以上是p=4R+1，R是偶数时的解。

41有两组解；409有三组解。就是说4/41=1/（12×1）+1/（12×6）+1/（12×1×6×41）=1/12+1/72+1/2952

4/41=1/（6×3）+1/（6×4）+1/（6×3×4×41）=1/18+1/24+1/2952。

-41×6+247×1=1

7×6+（-41）×1=1

和第二组解；

-41×4+55×3=1

31×4+（-41×3）=1

（2）式是对于所有的p值都有解，但不是全部解。(例如，4/41有7组解，而（2）式只求证4/p=1/AB+1/AC+1/ABCP

的形式解。请注意普遍解与全部解的区别。

在七十年代，人们又提出了5/P的情况，所有的素数P都可以表示成5R+1；5R+2；5R+3；5R+4形。

对于P= 5R+4形，5/（5R+4）=1/（R+1）+1/[（5R+4）（R+1）]

其中任何一个：1/N=1/（N+1）+1/[N（N+1）]。

例如，5/9=1/2+1/18，而1/2=1/3+1/6；或者1/18=1/19+1/（18×19）。

对于P=5R+3形，5/（5R+3）=1/（R+1）+2/[（5R+3）（R+1）]

其中任何一个：2/N=1/[（N+1）/2]+1/[N（N+1）/2]

例如，5/13=1/3+2/39，而2/39=1/[（39+1）/2]+1/[39×（39+1）/2]。

对于P=5R+2形，5/（5R+2）=1/（R+1）+3/[（5R+2）（R+1）]

R必然是奇数，（R+1）必然是偶数。

而：3/[（5R+2）（R+1）]=1/[（5R+2）（R+1）]+1/[（5R+2）（R+1）/2]

例如，5/37=1/8+3/（37×8）；而3/（37×8）=1/（37×8）+1/（37×4）。

对于P=5R+1形，

设5/P=1/AB+1/AC+1/ABCP （8）。

5ABC=PC+PB+1 （9）

A=（PC+PB+1）/5BC （10）。

同样可以整理成（6）（7）式，同样有解。B+C=5K-1形。

下面是一些p=5R+1形的素数的解。

5/11=1/3+1/9+1/99，A=3，B=1，C=3，T=34，S=4；

5/31=1/7+1/56+1/1736，A=7，B=1，C=8，T=248，S=4；

5/41=1/9+1/93+1/11439，A=3，B=3，C=31，T=424，S=4；

5/61=1/14+1/95+1/81130，A=1，B=14，C=95，T=414，S=9；

5/71=1/15+1/267+1/94785，A=3，B=5，C=89，T=1264，S=4；

5/101=1/21+1/531+1/375417，A=3，B=7，C=177，T=2554，S=4；

5/131=1/27+1/885+1/1043415，A=3，B=9，C=295，T=4294，S=4；

方法同4/P一样。请读者自己完成。

为什么（6）（7）式可以必然有解？

两联二元一次不定方程：

a1x+b1y=1

a2x+b2y=1.

有解的充分条件是(a1b2-a2b1)|(a1-a2);(a1b2-a2b1)|(b2-b1).

我们考察一联二元一次不定方程：

ax+by=1.(14)

根据已知定理，只要（a,b)=1,(14)式就有整数x,y的解。并且是有无穷多组解。

例如，5x-2y=1.

x; y

-----------------

1, 2;

3, 7;

5, 12;

7, 17;

9, 22;

11，27；

13，32；

15，37；

17, 42;

19, 47;

...........

换句话说，（14）式中，x与y也互素。这就是联立方程组有公共解的基础。我们把a,b与x,y互换，

以上例为例子，5x-2y=1换成5a-2b=1,x=5,y=2.

3x-7y=1

17x-42y=1

形成二联二元一次不定方程。

5x-12y=1

19x-47y=1

7x-17y=1

形成三联二元一次不定方程。

（4）式可以表示成一个素数的式子：

p=(4ABC-1)/(C+B)。例如p=41时，41=（4x6x3x4-1）/（4+3）；41=（5x3x3x31-1）/（31+3）；

41=(6x1x8x47-1)/(8+47)；41=(7x1x7x36-1)/(7+36)；41=(8x6x1x6-1)/(1+6)；41=(9x1x6x19-1)/(6+19)；

41=(10x1x6x13-1)/(6+13)；41=(11x1x4x55-1)/(4+55);；41=(12x4x1x6-1)/(1+6);；41=(13x1x4x15-1)/(4+15)；

41=(14x1x3x124-1)/(3+124).。到n=15就没有了：41= (nABC-1)/(B+C)都有效。

人们于是问：是否一切np/3,对于任何一个素数p都有：

p=(nABC-1)/(B+C).

有三个未知变量的素数公式，可以求得一切素数：

P=(4ABC-1)/(B+C).(15)。

（15）式对于一切p=4r+1形式的素数都可以。

例如，17.：17=（4x3x2x5-1)/(2+5)。

（15）式对于一切p=4r+3形式的素数，A=(P+1)/4，,B=1,，C=P+1。例如11=（4x3x1x12-1)/(1+12).。

对于合数n=4r+3形式。n=（4xBXC－1）/（B+C）．

例如51=（4x13x664－1）/（13+664）。B=（P+1）/4，C=n（n+1）/4+1．

算法解决

题目

埃及分数

在古埃及，人们使用单位分数的和（形如 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 gcd(a,b:longint):int64;

begin

if b=0 then exit(a);

exit(gcd(b,a mod b));

end;

function lcm(a,b:longint):int64;

var

t:longint;

begin

if ab then

begin

t:=a;a:=b;b:=t;

end;

exit(a div gcd(a,b)*b);

end;

procedure sum(var s1,s2:int64;m:longint);

var

t:int64;

begin

t:=lcm(s2,m);

if t100000 then

begin

s1:=10000;

s2:=1;

exit;

end;

s1:=t div s2*s1+t div m;

s2:=t;

t:=gcd(s1,s2);

s1:=s1 div t;

s2:=s2 div t;

end;

procedure 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;

procedure dfs(s:extended;s1,s2,m,i:int64);

var

j:longint;

up,down,t1,t2:int64;

begin

if s1/s2aim then exit;

if imaxd then begin fc(s1,s2); exit;end;

up:=trunc(1/(aim-s));

if upm 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;

procedure 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:=gcd(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(a1)

then write('1/',b div a);

if a=1 then write('1/',b);

readln;

end.

未来发展

实际上这个问题还远远没有解决。但是已经给出了前进的方向。

.埃及分数，一个曾被人瞧不起的，古老的课题，它隐含了何等丰富的内容，许多新奇的谜等待人们去揭开

埃及分数的算法解决

题目

埃及分数

在古埃及，人们使用单位分数的和（形如 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 gcd(a,b:longint):int64;

begin

if b=0 then exit(a);

exit(gcd(b,a mod b));

end;

function lcm(a,b:longint):int64;

var

t:longint;

begin

if ab then

begin

t:=a;a:=b;b:=t;

end;

exit(a div gcd(a,b)*b);

end;

procedure sum(var s1,s2:int64;m:longint);

var

t:int64;

begin

t:=lcm(s2,m);

if t100000 then

begin

s1:=10000;

s2:=1;

exit;

end;

s1:=t div s2*s1+t div m;

s2:=t;

t:=gcd(s1,s2);

s1:=s1 div t;

s2:=s2 div t;

end;

procedure 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;

procedure dfs(s:extended;s1,s2,m,i:int64);

var

j:longint;

up,down,t1,t2:int64;

begin

if s1/s2aim then exit;

if imaxd then begin fc(s1,s2); exit;end;

up:=trunc(1/(aim-s));

if upm 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;

procedure 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:=gcd(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(a1)

then write('1/',b div a);

if a=1 then write('1/',b);

readln;

end.

网站栏目：埃及分数问题java代码,埃及分数是什么
分享网址：http://6mz.cn/article/hcccdh.html

网站建设知识

埃及分数问题java代码,埃及分数是什么

分子为1的分数称为埃及分数，现输入一个真分数，使用循环方法将该分数分解为埃及分数用C语言解答

四个分数分子为1加起来怎么得1？

埃及分数

埃及分数的算法解决

其他资讯