【編程珠現(xiàn)】-算法設(shè)計技術(shù)

        【編程珠璣】第一部分的基礎(chǔ)知識已經(jīng)看完，比較有感觸的有以下幾點：
            1）、數(shù)據(jù)決定程序結(jié)構(gòu)：對不同的程序，選用最合適的數(shù)據(jù)結(jié)構(gòu)，必要是可以借助數(shù)據(jù)庫來解決問題
            2）、學(xué)會寫偽代碼：偽代碼是思想的結(jié)晶，拋開算法的細(xì)節(jié)，抓住算法的本質(zhì)思想。

          第二部分是關(guān)于程序性能的講解。在算法設(shè)計技術(shù)章節(jié)講到了以下幾個重要的技術(shù)：
            1）、保存狀態(tài)，避免重要計算：這也是動態(tài)規(guī)劃所采用的思想，別浪費(fèi)中間結(jié)果，它們很寶貴
            2）、將信息預(yù)處理至數(shù)據(jù)結(jié)構(gòu)中：保存中間結(jié)果的一種方法
            3）、分治算法：算法課上第一個學(xué)習(xí)的算法，如：二分查找、Strassen矩陣乘法等等。核心思想在于把問題分解成簡單的子問題，然后對子
                        問題進(jìn)行合并，經(jīng)常和遞歸一起使用
            4）、掃描算法
            5）、累積：通常用于求前i個值的和
            6）、下界：許多問題要證明它的下界是多少


            下面是習(xí)題14的解答思想：
             描述：給定整數(shù)m、n和整數(shù)（實）數(shù)向量x[n]，請找到出現(xiàn)使總和x[i]+……+x[i+m]最接近0的整數(shù)i( 0<=i<n-m)
             解決思路：從i+1開始的長度為m+1的子向量等當(dāng)前子向量減去x[i-1],再加上x[i+m]

              
         原題中的向量為實數(shù)，核心算法還是一樣的，只是浮點數(shù)比較的時候要注意下
         有興趣的朋友歡迎一起討論 ：）

posted on 2011-01-14 11:20 XXXXXX 閱讀(277) 評論(0)  編輯  收藏 所屬分類: Algorithm