由幾個問題看搜索中內存的使用

1、由幾個問題看搜索中內存的使用暢明Cs03-21程序中內存的大小及分配總內存的限制：1000K or Higher程序自身：100200K；普通變量：less than 1K；系統(tǒng)棧：單參數(shù)無變量函數(shù)遞歸到 11K層但每一次調用使用較大內存(至少 10B)臨時狀態(tài)區(qū)：搜索中占內存較多 2Q1：超級素數(shù)一個至少二位的素數(shù)，如果每次去掉最高位后還是一個素數(shù)，直到一個一位數(shù)，則稱其為超級素數(shù)。例如：223-23-3；求出所有小于 N 的超級素數(shù)。3解法：1：直接搜索：11max ，窮舉2：直接構造：2-23-2233：構造素數(shù)表檢索：常規(guī)；動態(tài)規(guī)劃；4構造素數(shù)表檢索：動態(tài)規(guī)劃常規(guī)過程：構造素數(shù)表；從最

2、小數(shù)檢索；折半搜索一個數(shù)去最高位后是否還在表中，直至只有一位。動態(tài)規(guī)劃：任何一個三位或更高階超級素數(shù)去掉最高位后還是一超級素數(shù) (有點像構造了)。5Q1總結直接搜索：最慢，內存占用為零；構造：時間短，但需要考慮清構造方法，防止結果不全；素數(shù)表搜索：時間短，速度較快，結果全，但搜索范圍受素數(shù)數(shù)組的牽制(在第二題中討論)，且制備素數(shù)數(shù)組要花時間(由于范圍要盡可能的大，數(shù)組要利用好，常規(guī)篩法顯然不行；但常規(guī)方法優(yōu)化后速度也不錯 )6var I , j , sqrti: integer;s MAX of integer;ok : boolean;s1:=2;s2:=3;count:=2; i:=5;w

3、hile i=max-1 doj:=2;ok:=true; sqrti= trunc ( sqrt(i) );while s j= sqrti doif i mod s j=0 then goto 1;inc (j) else goto 1;inc (count);s count:=i;1:inc(i,2);7局部篩法常規(guī)篩法不行時，可以分部分使用篩法，然后存在另一個數(shù)組里。8Q2：完全數(shù)及類似問題完全數(shù)：一個正數(shù)所有因子的和等于自身(包括1，不包括自身)，就是一個完全數(shù)。求小于 N 的完全數(shù)6=1+2+328=1+2+4+7+149解法：1：直接搜索：2：構造數(shù)表檢索：選一數(shù)組，全置為一，然

4、后 I 由 2 到 max/2 循環(huán)，每次給 I 的整數(shù)倍加上 I，直到此整數(shù)倍超過 max；檢查以上數(shù)組，如果一個位置上的結果等于位置，此數(shù)為完全數(shù)。10派生題：Q2-1：兩個數(shù)的因數(shù)之和分別等于對方，求這樣的完全數(shù)對；Q2-2：五個數(shù)排成一隊，每個數(shù)的因數(shù)和各等于下一個數(shù)，最后一個的等于第一個數(shù)，求這樣的數(shù)列；這兩題用此方法可大大減小時間復雜度，特別是 Q2-2。11Q2 解法 2 的缺陷與解決解法二的時間復雜度極低(ms級算到30K)，但對空間要求極高，若要求算到 231 (2G)，顯然不行；這時我們要用時間換空間：設立數(shù)組max_len，及其偏移量 shift，每次用此數(shù)組計算從 shift 到 shift + max_len 之間的完全數(shù)。12注意：max_len 要盡可能的大：Shift 變大后，從一加一遍的代價也較高，max_len較大可以減少加的次數(shù)；這里的時間可以換空間，但不能過頭，因為最開始搜索時是用空間換的時間；最好是整片的數(shù)(e.g.: