前言:
眼前小伙伴们对“举个算法的例子”大概比较关怀,小伙伴们都想要了解一些“举个算法的例子”的相关知识。那么小编在网上网罗了一些对于“举个算法的例子””的相关内容,希望咱们能喜欢,兄弟们快快来学习一下吧!小朋友们好,大朋友们好!
我是猫妹,一名爱上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。
这时要怎么做呢?
这要用动态规划啦
好了,我们今天就学到这里吧!
如果遇到什么问题,咱们多多交流,共同解决。
我是猫妹,咱们下次见!
标签: #举个算法的例子