现在的位置: 首页 > 综合 > 正文

编程之美第一章游戏之乐学习总结

2014年01月16日 ⁄ 综合 ⁄ 共 688字 ⁄ 字号 评论关闭

    第一种游戏之乐中有18个游戏问题,从不同角度让我们学习使用计算机解决问题的能力,例如第一个问题“让cpu占用率曲线听你指挥”,让我们了解到怎样使cpu工作或者忙碌,怎样得到cpu的占用率等参数,以便我们选择是否让cpu工作或者睡眠来达到控制cpu曲线的目的。

    第一章中介绍最多的还是怎样利用递归遍历的方式找到问题的解答,这也是计算机的最基本也是最重要的能力,递归遍历查找问题的解答,(1)最重要的是要能够将问题分解为可以递归的子问题。例如它的第三个问题“一摞烙饼的排序问题”,它的解答:对于数量为N的一摞烙饼,将他的每一次翻转做为一个子问题,我们只需要关心当前这一步如何翻转烙饼,剩下的问题就留给下一次递归解决。例如我们当前的翻转就有N-1种情况,每一种情况对第一个烙饼到第x(x为1到N)个烙饼这一子摞进行翻转。(2)递归中另一个非常重要的问题就是:如何找出递归终止的条件。这个条件的找的好可以减少递归遍历的搜索空间,可以大大的提高解题的效率。例如问题中我们发现:一摞烙饼排序中最坏的情况就是每个烙饼都先翻着到最上面,然后在翻转到它对应有序队列中的位置,也就是说每个烙饼都要翻转两次(最后一个不用翻转),所以递归最多需要翻转2*(n-1)次,这最为它的终止条件的上界;然后我们在找下界,就是最少要翻转多少次,假设有序的子列可以作为一个烙饼看待(有一部分是),我们假设这一摞烙饼中总共有m个有序的序列,他们总共占有sum(m)个烙饼,所以递归翻转的下界就是N+m-sum(m)。这个上下界越小遍历时间越短效率越高,所以递归问题中我们要尽量的缩小搜索的范围,提高算法效率。


抱歉!评论已关闭.