【編程珠現】-算法設計技術

        【編程珠璣】第一部分的基礎知識已經看完，比較有感觸的有以下幾點：
            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 閱讀(279) 評論(0)  編輯  收藏 所屬分類: Algorithm