驗(yàn)證古埃及分?jǐn)?shù)猜想

說在前面

有一個(gè)著名的分馬問題：老財(cái)主臨終前把三個(gè)兒子叫到身邊說，家里有17匹馬可當(dāng)遺產(chǎn)分，大兒子分得1/2，二兒子分得1/3，三兒子分得1/9。不許殺馬，不許流血，必須按老父親的遺囑分配馬匹。

三個(gè)兒子百思不得其解，于是請(qǐng)來村里的智伯幫助解決難題。智伯想了又想，終于找出了答案。

智伯是怎么解決這個(gè)難題的呢？

他從自己家里牽來了一匹馬，湊成18匹。大兒子得1/2是9匹，二兒子分1/3是6匹，三兒子分1/9是2匹。9+6+2等于17匹，還剩下一匹，是智伯從自家牽來的，牽回去就可以了。

分馬問題中有17/18 = 1/2 + 1/3 + 1/9。

其中的訣竅是把有理數(shù)17/18分解成了3個(gè)分子為1的分?jǐn)?shù)，且其分母均為18的因數(shù)。古代埃及人在進(jìn)行分?jǐn)?shù)運(yùn)算時(shí)，只使用分子是1的分?jǐn)?shù)。因此這種分?jǐn)?shù)也叫做埃及分?jǐn)?shù)，或者叫單分子分?jǐn)?shù)。

古埃及分?jǐn)?shù)猜想：將大于1的整數(shù)任意分成有限個(gè)子集，必然有一個(gè)子集中的部分整數(shù)倒數(shù)加起來為1。

例如只要有一個(gè)子集中有2、3、6，就有1 = 1/2 + 1/3 + 1/6。

對(duì)于任意有理數(shù)，我們都可以用簡(jiǎn)單的算法找到古埃及分?jǐn)?shù)表示。

現(xiàn)在請(qǐng)你編寫一個(gè)自定義函數(shù)，將任意一個(gè)有理數(shù)展開成古埃及分?jǐn)?shù)的表示形式。函數(shù)頭說明如下：

#!/usr/bin/python3# 文件名:驗(yàn)證古埃及分?jǐn)?shù)猜想# 作者：巧若拙@Python算法之旅# 時(shí)間：2022-3-16'''函數(shù)功能：使用古埃及分?jǐn)?shù)表示任意有理數(shù)函數(shù)名：egyptian_fraction(nr, dr)參數(shù)表：nr -- 分子（numerator）；        dr -- 分母（denominator）。返回值：返回存儲(chǔ)了古埃及分?jǐn)?shù)中分母序列的列表。例1，當(dāng)nr=17,dr=18時(shí)，返回[2, 3, 9]。例2，當(dāng)nr=11,dr=12時(shí)，返回[2, 3, 12]。'''def egyptian_fraction(nr, dr):    import math    ans = [] #用來存儲(chǔ)古埃及分?jǐn)?shù)中分母序列的列表    while nr != 0:        x = math.ceil(dr / nr)        ans.append(x)        nr = x * nr - dr        dr = dr * x    return ans#主函數(shù)nr, dr = 17, 18#nr, dr = 11, 12nr, dr = 9, 10ans = egyptian_fraction(nr, dr)print(ans)print(f'{nr}/{dr} = ', end='')for d in ans[:-1]:    print(f'1/13ixwwoc3 + ', end='')print(f'1/{ans[-1]}')

課后練習(xí)

篇頭的分馬問題總共馬匹數(shù)為17，三個(gè)兒子所占比例分別為1/2，1/3和1/9，我們可以分別用變量表示為a=17，b=2，c=3，d=9。除了這一組取值，還有a=11，b=2，c=3，d=12組合，即11/12 = 1/2 + 1/3 + 1/12。

除此之外，你還知道哪些數(shù)據(jù)組合可以代入到分馬問題中嗎？請(qǐng)編程實(shí)現(xiàn)之。

需要本文PPT、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關(guān)優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學(xué)習(xí)方式

Python算法之旅文章分類