龙空技术网

一道经典的小学数学题,和它背后的贪心算法(35)

和猫妹学Python 123

前言:

眼前小伙伴们对“举个算法的例子”大概比较关怀,小伙伴们都想要了解一些“举个算法的例子”的相关知识。那么小编在网上网罗了一些对于“举个算法的例子””的相关内容,希望咱们能喜欢,兄弟们快快来学习一下吧!

小朋友们好,大朋友们好!

我是猫妹,一名爱上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。

这时要怎么做呢?

这要用动态规划啦

好了,我们今天就学到这里吧!

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

我是猫妹,咱们下次见!

标签: #举个算法的例子