驗(yàn)證古埃及分?jǐn)?shù)猜想
說(shuō)在前面
有一個(gè)著名的分馬問(wèn)題：老財(cái)主臨終前把三個(gè)兒子叫到身邊說(shuō)，家里有17匹馬可當(dāng)遺產(chǎn)分，大兒子分得1/2，二兒子分得1/3，三兒子分得1/9。不許殺馬，不許流血，必須按老父親的遺囑分配馬匹。
三個(gè)兒子百思不得其解，于是請(qǐng)來(lái)村里的智伯幫助解決難題。智伯想了又想，終于找出了答案。
智伯是怎么解決這個(gè)難題的呢？
他從自己家里牽來(lái)了一匹馬，湊成18匹。大兒子得1/2是9匹，二兒子分1/3是6匹，三兒子分1/9是2匹。9+6+2等于17匹，還剩下一匹，是智伯從自家牽來(lái)的，牽回去就可以了。
分馬問(wèn)題中有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ù)加起來(lái)為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ù)展開(kāi)成古埃及分?jǐn)?shù)的表示形式。函數(shù)頭說(shuō)明如下：
#!/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 mathans = [] #用來(lái)存儲(chǔ)古埃及分?jǐn)?shù)中分母序列的列表while nr != 0:x = math.ceil(dr / nr)ans.append(x)nr = x * nr - drdr = dr * xreturn 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/go7utgvlrp + ', end='')print(f'1/{ans[-1]}')
課后練習(xí)
篇頭的分馬問(wèn)題總共馬匹數(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ù)組合可以代入到分馬問(wèn)題中嗎？請(qǐng)編程實(shí)現(xiàn)之。
需要本文PPT、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來(lái)！
相關(guān)優(yōu)秀文章：