【编程珠现】-算法设计技术

        【编程珠玑】第一部分的基础知识已经看完，比较有感触的有以下几点：
            1）、数据决定程序结构：对不同的程序，选用最合适的数据结构，必要是可以借助数据库来解决问题
            2）、学会写伪代码：伪代码是思想的结晶，抛开算法的细节，抓住算法的本质思想。

          第二部分是关于程序性能的讲解。在算法设计技术章节讲到了以下几个重要的技术：
            1）、保存状态，避免重要计算：这也是动态规划所采用的思想，别浪费中间结果，它们很宝贵
            2）、将信息预处理至数据结构中：保存中间结果的一种方法
            3）、分治算法：算法课上第一个学习的算法，如：二分查找、Strassen矩阵乘法等等。核心思想在于把问题分解成简单的子问题，然后对子
                        问题进行合并，经常和递归一起使用
            4）、扫描算法
            5）、累积：通常用于求前i个值的和
            6）、下界：许多问题要证明它的下界是多少


            下面是习题14的解答思想：
             描述：给定整数m、n和整数（实）数向量x[n]，请找到出现使总和x[i]+……+x[i+m]最接近0的整数i( 0<=i<n-m)
             解决思路：从i+1开始的长度为m+1的子向量等当前子向量减去x[i-1],再加上x[i+m]

              
         原题中的向量为实数，核心算法还是一样的，只是浮点数比较的时候要注意下
         有兴趣的朋友欢迎一起讨论 ：）

posted on 2011-01-14 11:20 XXXXXX 阅读(252) 评论(0)  编辑  收藏 所属分类: Algorithm