传智播客旗下高端IT在线教育平台|咨询热线:010-56288220

返回顶部 返回列表
142 1

[大数据专区] 古寒飞:《从数瓜子浅谈计算机算法的特性》

[复制链接]

5

主题

8

帖子

37

积分

新手上路

古寒飞

Rank: 1

积分
37
1421 古寒飞 发表于 2018-6-14 21:21:18
本帖最后由 18516187075 于 2018-6-14 22:54 编辑

和大仙下楼买东西,然后我买了8个小橘子共计4元,他买了一包散称的瓜子共计6元,最后付款总金额10元,我们一人付了一半,在上楼梯的时候我们谈到了分配问题,我的8个小橘子可以直接分配给他4个,那么他手里提着的瓜子分配给我多少颗呢,我们打算搞清楚这个问题。



身为一个遵守计算机编程标准的理工男,数清楚瓜子数量这种问题,自然是要应用上计算机算法的。在随意的讨论中,我们诞生了三个计算方式,分别如下:



方案一:
直接数清楚所有瓜子的数量,除以2后,再数出其中一个人的数量,剩下的数量归属另一人所有。


方案二:
每数出100粒瓜子后单独作为一堆存放,然后把总堆数处以2,最后一堆不足100粒时,从另一人的其中一堆中拿出差额的二分之一即可(这句话要好好理解哦!)。


方案三:
分奇数堆瓜子和偶数堆瓜子,然后按照每一粒瓜子的序号快速遍历所有瓜子,第一颗瓜子放在奇数堆,第二颗瓜子放在偶数堆,第三颗放在奇数堆,第四课放在偶数堆,以此类推,当快速遍历完所有的瓜子后,两堆瓜子将会顺利的一分为二。




这是我们谈论出来的三种对瓜子平均分配的解决方案,暂时没有想到其它的分法了,那么就根据这三种方法转化为算法吧。

方案1:假设瓜子有5000颗,那么计算机总共要运算次数如下:
5000次(遍历总数)
1次(总数处以2)
2500次(遍历一半的数量)
合计:7251次计算可以完成
总次数:5000+1+2500=7251(次)


方案2:假设瓜子有5000颗,那么计算机总共要运算次数如下:
5000次(遍历总数)
50次(遍历时,并行累加总堆数)
1次(判断最后一堆是否满足100颗)
1次(计算最后一堆不满足100颗时的差额)
1次(差额结果除以2)
1次(不满100颗的那一堆加上二分之一的差额数量)
1次(总堆数除以2,一人25堆)
合计:5055次计算可以完成。
总次数:5000+50+1+1+1+1+1=5055(次)


方案3:假设瓜子有5000颗,那么计算机总共要运算次数如下:
5000次(为每颗瓜子编号,从第1颗~5000颗,每次都用编号除以2来判断编号是奇数还是偶数,编号整除2时放入偶数堆,编号不整除2时放入奇数堆,总共5000次判断就能完成统计和分类的全部工作)
合计:5000次计算可以完成
总次数:5000次


显然第三种算法是最优的,可以显著的提升计算性能,而节省下来的时间和计算资源就可以另作他用。不知道大家还有没有其它更优化的算法?




最后奉上瓜子总数,计算后实际总数共计1041颗,总价6元,平均每1元可以购买173.5颗瓜子,数据真实有效,便于小伙伴们购买时做个参考。



我们买的瓜子,很好吃的!

我们买的瓜子,很好吃的!
回复

5

主题

8

帖子

37

积分

新手上路

古寒飞

Rank: 1

积分
37
 楼主| 古寒飞 发表于 2018-6-14 21:56:00
作者是:第十五期的神秘蛋小挞
回复

您需要登录后才可以回帖 登录 | 立即注册