埃及分數演算法

① 分數與分數相乘怎麼算

分數與分數相乘時，分數的分子與分子相乘，分母與分母相乘，能約分的要先約分。

做第一步時，就要想一個數的分子和另一個分母能不能約分。分數與整數相乘就是把多個同樣的數疊加。.

例如：2/8×5/6首先第一個乘數先約分，是1/4，2/8×5/6就是1/4×5/6=5/24。

分數與整數相乘就是把多個同樣的數疊加，如⅔X2，就是指2個⅔相加，⅔X10是指10個⅔相加。若是整數乘分數的話：整數就乘與分子，不能和分母乘（整數和分母可以約分就約分）。

(1)埃及分數演算法擴展閱讀：

分數乘整數的意義與整數乘法的意義相同，就是求幾個相同加數的和的簡便運算。一個數與分數相乘，可以看作是求這個數的幾分之幾是多少。

分數的加減法計算：

1、同分母分數相加減，分母不變，即分數單位不變，分子相加減，能約分的要約分。

2．異分母分數相加減，先通分，即運用分數的基本性質將異分母分數轉化為同分母分數，改變其分數單位而大小不變，再按同分母分數相加減法去計算，最後能約分的要約分。

最早的分數是整數倒數：代表二分之一的古代符號，三分之一，四分之一，等等。埃及人使用埃及分數c。 1000 bc。大約4000年前，埃及人用分數略有不同的方法分開。他們使用最小公倍數與單位分數。他們的方法給出了與現代方法相同的答案。

埃及人對於Akhmim木片和二代數學紙莎草的問題也有不同的表示法。希臘人使用單位分數和（後）持續分數。希臘哲學家畢達哥拉斯（c。530 bc）的追隨者發現，兩個平方根不能表示為整數的一部分。

② 埃及是世界上四大文明古國之一，早在2000多年前，埃及人就發現了分數。他們把分數化為分子是1的分數來計算

等於1/127。
首先你這個題不怎麼對呢。你的題是大概是這樣的，1/16+1/2+1/4+1/8+1/16等於多少。
但是古代埃及人是把分子大於1的正分數表示成單位分數的和。例：1/4+1/4+1/6=2/3
總而言之就是能化簡成分子等於1的正分數就不能講說是埃及分數的和

③ 古埃及人如何進行分數計算

埃及同中國一樣，也是世界上著名的文明古國。人們在考察古埃及歷史時注意到象阿基米德這樣的數學巨匠，居然也研究過埃及分數。本世紀一些最偉大的數學家也研究埃及分數，例如，沃而夫數學獎得主，保羅-歐德斯，他提出了著名的猜想 4/n=1/x+1/y+1/z. 難倒了世界上第一流的數學家。當9個麵包要平均分給 10個人的時候，古埃及人不知道每個人可以取得 9/10，而是說每人1/3+1/4+1/5+1/12+1/30。真叫人難以想像，你連9/10都搞不清楚，怎麼知道9/10=1/3+1/4+1/5+1/12+1/30。所以幾千年來，數學史家一直堅持認為，古埃及人不會使用分數。
1858年，蘇格蘭考古學家萊登買到了一份古埃及草紙文件，經過鑒定這是繁生於尼羅河泛濫形成的池塘和沼澤地里的草製成的紙，成文年代約在公元前1700年。
那麼，古埃及的人們，是怎麼算的呢？首先，把 2 個物品分成 4 個 1/2，先給每個人 1 個 1/2，剩下的 1 個1/2 再分成 3 等分，均分結果，每人分到 1/2 加 1/2 的 1/3，也就是 1/2 + 1/6 = 2/3。這份至今保存在大英博物館的「萊登」草紙，用很大的篇幅記載著將真分數分解成單分子分數，這種運算方式，遭到現代數學家們紛紛責難，認為埃及人之所以未能把算術和代數發展到較高水平，其分數運算之繁雜也是原因之一。

埃及金字塔是舉世聞名的，表明古埃及人具有高超的建築技巧和超凡的智力，難道最簡單的現代分數也不懂？金字塔所蘊含的難道是一篇粗劣的作品？
現代數學已經發展到十分抽象和復雜的程度，而埃及分數卻是這樣粗糙，在人們的記憶里早該煙消雲散了，然而，它產生的問題直到今天仍然引起人們的重視。
四川大學已故老校長柯召寫道：「埃及分數所產生的問題有的已成為至今尚未解決的難題和猜想，他們難住了許多當代數學家」。柯召本人至死都沒有能夠證明這個猜想。
一個古老的傳說是：
老人彌留之際，將家中11匹馬分給3個兒子，老大1/2，老二1/4，老三1/6。二分之一是5匹半馬，總不能把馬殺了吧，正在無奈之際，鄰居把自己家的馬牽來，老大二分之一，牽走了6匹；老二四分之一，牽走了3匹；老三六分之一，牽走了2匹。一共11匹，分完後，鄰居把自己的馬牽了回去。即11/12=1/2+1/4+1/6。
奇妙的埃及分數終於調動自己的潛在難度擊敗了敢於輕視他們的人們。並且給與嘲笑他的人以難堪的回答。

兩千多年後的數學家終於發現：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，m<1，
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)
在（6）式中，若要 B|(PC+PB+1)，需使得B|(PC+1)，設PC+1=TB；若要C|(PC+PB+1)，需使得C|(PB+1)，設PB+1=SC；對於P=4R+1形，若要4|p(C+B)+1],需C+B=4K-1，對於P=4R+3形，若要4|[P（C+B）+1]，需C+B=4K+1。於是，形成一個二元一次不定方程組：
-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)都有效。
人們於是問：是否一切n<p/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．

實際上這個問題還遠遠沒有解決。但是已經給出了前進的方向。
埃及分數，一個曾被人瞧不起的，古老的課題，它隱含了何等豐富的內容，許多新奇的謎等待人們去揭開。

望採納，謝謝。

④ 9/10埃及分數演算法。

你好：
9/10=1/3+1/4+1/5+1/12+1/30

⑤ 這是求埃及分數的演算法，請告訴我第二、三、四步為什麼謝謝！

埃及分數有個特點，所有的分子都是1，要想表現一個分子非1的分數，必須變成多個分子為1的分數之和
所以步驟2是在求第一個分數的分母，第一個分數是接近A/B的大分數
步驟3、4實際是在求A/B-1/C
步驟5、6是在確定第二個分數，如果它仍然不是埃及分數，需要進一步計算

需要指出，上面的步驟有些地方寫的不太准確
（2），這個得數=C
（5），這個貌似寫錯了，應該是B能整除A
最終答案一般是1/C+1/(B/A)或1/C+1/B
我已經用3/4=1/2+1/4 5/6=1/2+1/3 3/8=1/3+1/24 17/100=1/6+1/300試過了

⑥ 埃及分數的演算法解決

題目
埃及分數
在古埃及，人們使用單位分數的和（形如 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 a<b then
begin
t:=a;a:=b;b:=t;
end;
exit(a div gcd(a,b)*b);
end;
procere sum(var s1,s2:int64;m:longint);
var
t:int64;
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:=gcd(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:int64);
var
j:longint;
up,down,t1,t2:int64;
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:=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(Ƈ/',c);
write('+');
until (a=1) or (b mod a=0);
if (b mod a=0)and(a<>1)
then write(Ƈ/',b div a);
if a=1 then write(Ƈ/',b);
readln;
end.

⑦ 貪心演算法的數學應用

如把3/7和13/23分別化為三個單位分數的和
【貪心演算法】
設a、b為互質正整數，a<b 分數a/b 可用以下的步驟分解成若干個單位分數之和：
步驟一： 用b 除以a，得商數q1 及余數r1。（r1=b - a*q1）
步驟二：把a/b 記作：a/b=1/(q1+1）+(a-r1)/b(q1+1）
步驟三：重復步驟2，直到分解完畢
3/7=1/3+2/21=1/3+1/11+1/231
13/23=1/2+3/46=1/2+1/16+1/368
以上其實是數學家斐波那契提出的一種求解埃及分數的貪心演算法，准確的演算法表述應該是這樣的：
設某個真分數的分子為a，分母為b;
把b除以a的商部分加1後的值作為埃及分數的某一個分母c；
將a乘以c再減去b，作為新的a；
將b乘以c，得到新的b；
如果a大於1且能整除b，則最後一個分母為b/a；演算法結束；
或者，如果a等於1，則，最後一個分母為b；演算法結束；
否則重復上面的步驟。
備註：事實上，後面判斷a是否大於1和a是否等於1的兩個判斷可以合在一起，及判斷b%a是否等於0，最後一個分母為b/a，顯然是正確的。
PHP代碼： classtanxin{public$weight;public$price;publicfunction__construct($weight=0,$price=0){$this->weight=$weight;$this->price=$price;}}//生成數據$n=10;for($i=1;$i<=$n;$i++){$weight=rand(1,20);$price=rand(1,10);$x[$i]=newtanxin($weight,$price);}//輸出結果functiondisplay($x){$len=count($x);foreach($xas$val){echo$val->weight,'',$val->price;echo'<br>';}}//按照價格和重量比排序functiontsort(&$x){$len=count($x);for($i=1;$i<=$len;$i++){for($j=1;$j<=$len-$i;$j++){$temp=$x[$j];$res=$x[$j+1]->price/$x[$j+1]->weight;$temres=$temp->price/$temp->weight;if($res>$temres){$x[$j]=$x[$j+1];$x[$j+1]=$temp;}}}}//貪心演算法functiontanxin($x,$totalweight=50){$len=count($x);$allprice=0;for($i=1;$i<=$len;$i++){if($x[$i]->weight>$totalweight)break;else{$allprice+=$x[$i]->price;$totalweight=$totalweight-$x[$i]->weight;}}if($i<$len)$allprice+=$x[$i]->price*($totalweight/$x[$i]->weight);return$allprice;}tsort($x);//按非遞增次序排序display($x);//顯示echo'0-1背包最優解為:';echotanxin($x);java源代碼 packagemain;importjava.util.ArrayList;importjava.util.Collections;importjava.util.Comparator;importjava.util.List;importjava.util.Random;publicclassMain{/***測試*/publicstaticvoidmain(String[]args){//1.隨機構造一批任務List<Pair<Integer>>inputList=newArrayList<Pair<Integer>>();Randomrand=newRandom();for(intn=0;n<20;++n){Integerleft=rand.nextInt(100);Integerright=left+rand.nextInt(100)+1;Pair<Integer>pair=newPair<Integer>(left,right);inputList.add(pair);}//將任務列表按結束時間排序（也就是根據right欄位進行排序）sortByRight(inputList);printPairList(inputList);//執行演算法List<Pair<Integer>>outputList=algorithm(inputList);System.out.println();printPairList(outputList);}/***貪心演算法**@paraminputList*@return使數量最多的任務方案*/publicstatic<TextendsComparable<T>>List<Pair<T>>algorithm(List<Pair<T>>inputList){if(null==inputList||inputList.size()==0||inputList.size()==1){returninputList;}sortByRight(inputList);List<Pair<T>>outputList=newArrayList<Pair<T>>();intlast=0;outputList.add(inputList.get(last));intintputSize=inputList.size();for(intm=1;m<intputSize;++m){Pair<T>nextPair=inputList.get(m);TnextLeft=nextPair.getLeft();Pair<T>lastOutPair=inputList.get(last);TlastRight=lastOutPair.getRight();intflag=nextLeft.compareTo(lastRight);if(flag>=0){outputList.add(nextPair);last=m;}}returnoutputList;}/***對傳入的List<Pair<T>>對象進行排序，使Pair根據right從小到大排序。**@paraminputList*/privatestatic<TextendsComparable<T>>voidsortByRight(List<Pair<T>>inputList){CompareByRight<T>comparator=newCompareByRight<T>();Collections.sort(inputList,comparator);}/***列印一個List<Pair<T>>對象。**@paraminputList*/privatestatic<TextendsComparable<T>>voidprintPairList(List<Pair<T>>inputList){for(Pair<T>pair:inputList){System.out.println(pair.toString());}}}/***根據Pair.right比較兩個Pair。用於Conlections.sort()方法。**@param<T>*/classCompareByRight<TextendsComparable<T>>implementsComparator<Pair<T>>{/*@Override*/publicintcompare(Pair<T>o1,Pair<T>o2){Tr1=o1.getRight();Tr2=o2.getRight();intflag=r1.compareTo(r2);returnflag;}}/***代表一個任務對象。有點裝逼用模板來寫了。left表示開始時間，right表示結束時間。**@param<T>*/classPair<TextendsComparable<T>>{privateTleft;privateTright;publicPair(Tleft,Tright){this.left=left;this.right=right;}@OverridepublicStringtoString(){return[left=+left.toString()+','+right=+right.toString()+']';}publicTgetLeft(){returnleft;}publicvoidsetLeft(Tleft){this.left=left;}publicTgetRight(){returnright;}publicvoidsetRight(Tright){this.right=right;}}

⑧ 什麼是埃及分數計算方法

埃及分數

埃及同中國一樣，也是世界上著名的文明古國。古埃及人約於公元前17世紀

已使用分數，中國《九章算術》中也載有分數的各種運算。古代埃及人處理分數與

眾不同，距今大約三千多年以前的埃及，人們只使用分子是 1 的分數，和我們現在所使用的大不相同。

他們一般只使用分子為1的分數，在我們現今所使用的分數中，當有 2 個物

品要平均分給 3 個人的時候，每個人可以取得 2 個 1/3。你可以算成 2/3 = 1/3 + 1/3。

那麼，古埃及的人們，是怎麼算的呢？首先，把 2 個物品分成 4 個 1/2，先給每個人 1 個 1/2，剩下的 1 個1/2 再分成 3 等分，均分結果，每人分到 1/2 加 1/2 的 1/3，也就是 1/2 + 1/6 = 2/3。

那麼，3/4 和 2/5 又該如何用分子全部為 1 的分數表示呢？結果：

3/4 = 2/4 + 1/4 = 1/2 + 1/4

2/5 = 6/15 = 5/15 + 1/15 = 1/3 + 1/15

又例如：用 表示 ，用 來表示 等等。

所以，像這些分子為1的真分數，就稱為「埃及分數」。將一個分子為1的真

分數分解為兩個或兩個以上分子為1的真分數之和，稱埃及分數的分解。

⑨ 分子為1的分數稱為埃及分數，現輸入一個真分數，使用循環方法將該分數分解為埃及分數用C語言解答

子為1的分數稱為埃及分數，現輸入一個真分數，請將該分數分解為埃及分數。
如：8/11=1/2+1/5+1/55+1/110。
*問題分析與演算法設計
若真分數的分子a能整除分母b，則真分數經過化簡就可以得到埃及分數，若真分數的分子不能整除分母，則可以從原來的分數中分解出一個分母為b/a+1的埃及分數。用這種方法將剩餘部分反復分解，最後可得到結果。
*程序說明與注釋
/*註：對源程序作稍許修改，主要是添加了一個外循環，可以直接計算多個真分數的埃及分數，按Ctrl-C退出。具體的演算法我沒有認真看，有問題請提出，謝謝*/
#include
intmain(void)
{
longinta,b,c;
while(true)
{
printf("Pleaseenteraoptionalfraction(a/b):");
scanf("%ld/%ld",&a,&b);/*輸入分子a和分母b*/
printf("Itcanbedecomposedto:");
while(true)
{
if(b%a)/*若分子不能整除分母*/
c=b/a+1;/*則分解出一個分母為b/a+1的埃及分數*/
else{c=b/a;a=1;}/*否則，輸出化簡後的真分數(埃及分數)*/
if(a==1)
{
printf("1/%ld
",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
",b/2,b);break;}
}
}
return0;
}
*運行結果
Pleaseenteraoptionalfraction(a/b):1/6
Itcanbedecomposedto:1/6
Pleaseenteraoptionalfraction(a/b):20/33
Itcanbedecomposedto:1/2+1/10+1/165
Pleaseenteraoptionalfraction(a/b):10/89
Itcanbedecomposedto:1/9+1/801
Pleaseenteraoptionalfraction(a/b):19/99
Itcanbedecomposedto:1/6+1/40+1/3960
Pleaseenteraoptionalfraction(a/b):8/87
Itcanbedecomposedto:1/11+1/957
……（按ctrl-c退出）

⑩ 兩千多年前，古埃及人總喜歡把分數轉化為分子是1的分數來計算，所以後人常把分子是1的分數稱為「埃及分數

（1）