您现在的位置是：首页 >技术教程 >一道经典的小学数学题，和它背后的贪心算法(35)网站首页技术教程

小朋友们好，大朋友们好！

我是猫妹，一名爱上Python编程的小学生。

欢迎和猫妹一起，趣味学Python。

今日主题

这个五一小长假，你玩得怎么样？

今天，咱们先做一道经典的小学数学题，抛砖引玉，然后了解下贪心算法。

一个地主临终前留下了遗嘱，将自己的11头牛分给三个儿子，老大1/2，老二1/4，老三1/6，请问在不杀牛的情况下，应该怎么分呢？

五一小长假，猫妹去了趟朱家角，烟雨江南、美轮美奂。

咱们先欣赏下朱家角的美景，顺便花几分钟思考下这道题目。

这么分

怎么样？

你得出答案了吗？

一位村民给出了解决方案，他将自己的一头牛拉了进来，然后老大1/2=6，老二1/4=3，老三1/6=2，最后剩下了一头牛，再还回自己。

这是因为1/2+1/4+1/6等于11/12，并不等于1。

这道数学题，实际上就是把有理数n/(n+1)分解成3个单位分数之后。

贪心算法

现代数学家钻研如何把任意有理数m/n写成单位分数的和，还创造出了一种算法——贪心算法。

这里有几个概念，咱们先学习下。

什么是有理数？

• 有理数是整数（正整数、0、负整数）和分数的统称，是整数和分数的集合。

• 无理数，也称为无限不循环小数，不能写作两整数之比。若将它写成小数形式，小数点之后的数字有无限多个，并且不会循环。 常见的无理数有非完全平方数的平方根、π和e（其中后两者均为超越数）等。无理数的另一特征是无限的连分数表达式。无理数最早由毕达哥拉斯学派弟子希伯索斯发现。

什么是单位分数？

分数单位是一个数学学科术语。

把单位“1”平均分成若干份取其中的一份的数，叫做分数单位。

即分子是1，分母是正整数的分数，又叫单位分数，记为1/n 。

单位分数又叫“单分子分数”，它还有一个名称叫“埃及分数”。

什么是贪心算法？

贪心算法（greedy algorithm ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

举个例子

如何将5/22写成单位分数的和？

这个可以用贪心算法来实现。

我们假设m/n<1，贪心算法思路是，先找到最大的、但是不大于m/n的单位分数，把它写下来。

再看看剩下多少，如果剩下的是单位分数，那么搞定，如果不是，就重复之前的。

计算第一个单位分数：

1/k<5/22

k>22/5(4.4)

k=5

计算第一个单位分数后的结果：

1/5=5/22+3/110

计算第二个单位分数(因为3/110不是单位分数，需要将其变为单位分数)：

1/k<3/110

K>110/3(36.666)

k=37

计算第二个单位分数后的结果：

5/22=1/5+1/37+1/4070

代码实现

fraction是Python一个自带库，可以进行分数运算。

我们上面的运算用代码实现如下：

import timefrom fractions import Fraction as fracdef process(fenzi,fenmu):    l1=[]    while True:        c=fenmu%fenzi        if c==0:            d=fenmu//fenzi        else:            d=fenmu//fenzi+1        #print(d)        l1.append(d)        new=frac(fenzi,fenmu)-frac(1,d)        if new==0:            break        #print(new)        fenzi=new.numerator        fenmu=new.denominator        #time.sleep(1)    return l1    if __name__ == '__main__':    a=5    b=22        l1 = process(a,b)    print(l1)        print(frac(a,b))        s=0    for num in l1:        s+=frac(1,num)    print(s)

贪心算法的使用场合

贪心算法不是万能的，有时局部最优解不是整体最优解，这个时候就不能用贪心算法来实现了。

适合贪心算法的例子：

11个数，如果都是正数，比如1~11，取6个数相乘，使其积最大，此时每次都取最大值，此时局部最优解等同于最优解。

不适合贪心算法的例子：

如果11个数，不全是正数，这个策略不一定适用。

比如11个数，5~1,0，-1~-5。

这时要怎么做呢？

这要用动态规划啦

好了，我们今天就学到这里吧！

如果遇到什么问题，咱们多多交流，共同解决。

我是猫妹，咱们下次见！