找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法与人生(四)

admin 2019-4-13 05:25 100人围观 C++相关

前话——今天下午刚进健身房,发现音响里放的是SOS,瞬间对某维姓健身房好感加倍。

中午从计算机学院走出来的时候,看到漫天飞舞的柳絮,竟像是降雪了一般。我想到了谢道韫所作的“未若柳絮因风起”,本是描述雪花,私以为放在这里偏有点说柳絮神似雪花的样子。本以为整个校园都是一样的风景,却发现归途并没有一丝异样,可能是天降祥瑞吧。不过还是得提醒各位看官老爷柳絮虽美,但很容易引起呼吸道疾病,所以还是戴上防护性口罩吧。



(图片来自网络,侵删)

今天我想与大家分享的是DP算法。什么是DP?DP是著名deadgame Dota里的游戏人物——死亡先知,法坦,伤害还不低,DP的大......咳咳,跑题了。DP是Dynamic Programming的首字母简称,翻译过来是动态规划。什么是动态规划?我看《算法图解》里的例子举得很“合适”:假如你是一个小偷,去音像店偷东西,你带了一个能承受重量为4磅的袋子,其中吉他1500刀,占1磅;电脑2000刀,占3磅;音响3000刀,占4磅。问你应该怎么去偷能将利益最大化呢。

为了便于理解,他分了3种情况,第一种是只能偷吉他,第二种是能偷吉他和音响,最后一种是三种都能偷。并且对于每种情况又分四个袋子,从一磅到四磅。第一种,因为每只能偷吉他,所以四个袋子都是吉他;第二种,从4磅开始可以偷音响,所以前三个袋子是吉他,第四个袋子是音响;最后一种,从第三磅开始可以偷电脑,第四磅开始可以偷音响,但是电脑+吉他价格大于音响,所以前两个袋子是吉他,第三个袋子是电脑,第四个袋子是电脑+音响。如下图所示:



(图片来自《算法图解》)

可以看出动态规划里的事例是与前面有交集的,因此上例可归纳出:



(图片来自《算法图解》)

动态规划其实是递归的过程。

我想大家应该比较清楚什么是动态规划了。今天我想分享动态规划里的一小部分——斐波那契数列。斐波那契举了一个经典的例子:在第一个月有一对刚出生的小兔子,在第二个月小兔子变成大兔子并开始怀孕,第三个月大兔子会生下一对小兔子,并且以后每个月都会生下一对小兔子。 如果每对兔子都经历这样的出生、成熟、生育的过程,并且兔子永远不死,那么兔子的总数是如何变化的?

首先,第一个月只有1对兔子,且只有1对小兔子,0对大兔子;

其次,第二个月只有1对兔子,有0对小兔子,1对大兔子;

然后,第三个月有两对兔子,有1对小兔子,1对大兔子;

。。。。。。

我们可以归纳出这个表:



我们分析数据,可归纳出第三个月兔子总数是第一、二月之和,第四月份兔子总数是第二、三月之和,以此类推。我们可归纳出一个公式:



斐波那契数列最基础的代码如下:
    defFibonacci(n):if n == 1:return1    if n == 2:        return 1    if n >= 3:     return Fibonacci(n - 1) + Fibonacci(n - 2)
    可以看到这个方法的时间复杂度是(n^n)。

    究其原因,在于每次算f(n)的时候,多次调用了f(1),f(2)等等。为了简化,我们可以化简:

      def fib(n):    if n <= 1:        return n    l_1 = 0    l_2 = 1    l = 1    for i inrange(2,n):        l_i = l_i_1 + l_i_2        l_i_2 = l_i_1        l_i_1 = l_i    return l_i

      上述方法避免了递归的过程,从而节省了时间。

      分享一道《剑指offer》里的经典题目:“我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?”留给大家思考。

      提示:

      第一次摆放一块1 x 2的小矩阵,一共f(n-1)种摆放方法



      第一次摆放一块1 x 2的小矩阵,则一共f(n-2)种摆放方法。



      碰巧昨天看某位我非常尊敬的老师发的一条动态关于辩证贝叶斯。有个问题想问问各位看官老爷们:你觉得人脑的计算是一种递归的过程吗?

      在我看来只有在极少数情况下你可能存在着递归。比如说问你2*3等于几,在你刚学初等数学时,可能会去递归的调用99乘法表。在这种情况下,请允许我下个定义,叫萌新卡洛斯态(瞎编的

      鲜花

      握手

      雷人

      路过

      鸡蛋

      yafeilinux和他的朋友们微信公众号二维码

      微信公众号

      专注于Qt嵌入式Linux开发等。扫一扫立即关注。

      Qt开源社区官方QQ群二维码

      QQ交流群

      欢迎加入QQ群大家庭,一起讨论学习!

      我有话说......

      
      关于进行手机实名认证的紧急通知!
      按照有关部门要求,论坛类网站必须完成手机实名认证才可以进行发帖等操作。希望大家积极配合,为创建一个和谐文明的社区而贡献自己的力量。我们会对会员的隐私进行严格保密,对大家造成的不便深表歉意! 我知道了