前n項大數(shù)求和的算法分析與設計

【摘 要】基于等距抽樣法，討論了運用雙向鏈表實現(xiàn)求和運算問題，給出了算法思想、程序流程。通過運用Turbo c語言編程實現(xiàn)并對相關(guān)數(shù)據(jù)進行測試，驗證了算法的正確性和有效性。

【關(guān)鍵詞】等距抽樣 大數(shù)求和 雙向鏈表 算法

在教育技術(shù)研究中運用調(diào)查研究時，當研究對象是一個范圍極為廣大的總體時，要直接研究總體的情況根本無法實現(xiàn)，故人們常使用系統(tǒng)抽樣（等距抽樣）法，從一個大的總體中抽取部分單位作為研究的樣本，再從樣本的情況來推斷總體的情況，并且能夠極大地降低調(diào)查的費用。等距抽樣法，是把總體中所有個體按一定順序編號，然后依固定間隔取樣，間隔的大小視所需樣本容量與總體中個體數(shù)目的比率而定，起始數(shù)字必須是隨機決定的。等距抽樣的步驟如下：

⑴設總體共有N個單位，現(xiàn)需要從中抽出n個單位作為樣本。先將總體的N個單位按與總體特征標志無關(guān)的標志進行排隊。

⑵確定取樣間隔，將N 劃分為n個單位相等的部分，每部分間隔為：K = N/n；

⑶決定起點。通常是在第一部分順序為1，2，3，…，i，…，K個單位中隨機取一個單位i作為抽樣的起點。

⑷在第一部分中，隨機以i為起點抽出第一個樣本后，繼續(xù)在第二部分中抽出第i+k單位為樣本；如此類推，在第n部分則抽出第i+（n-1）K單位為樣本。

這樣一共抽出了n個單位組成樣本，而且每個樣本的間隔都是K。

但是，當總體很大時，樣本號單位會逐漸增大到很大，那么在用Turbo c 語言編寫程序過程中可能會遇到?jīng)]有適當?shù)臄?shù)據(jù)類型變量能夠存儲這樣的大數(shù)，這使等距抽樣法的應用受到極大的限制。為此，筆者編寫了一個前n項大數(shù)求和的算法，可以根本上解決此類求和的算法問題。

一、算法分析及設計

用Turbo c語言進行運算時，c語言中沒有適當?shù)臄?shù)據(jù)類型變量能夠存儲足夠大的值，同樣前n項和Sum的值也無法利用已有的數(shù)據(jù)類型通過定義變量來存儲這樣大的值。開辟動態(tài)存儲單元雖可以用數(shù)組，但是用數(shù)組往往要求開辟存儲單元之前就必須確定要開辟存儲單元的字節(jié)數(shù)，若n值是不確定時，從而Sum值也是不確定的，可見用開辟動態(tài)數(shù)組的方法并不能徹底解決這一求解問題，因此筆者嘗試采用雙向鏈表來建立動態(tài)存儲單元接受輸入n值及前n項和Sum值的數(shù)據(jù)。

（一）數(shù)據(jù)接受

采用雙向鏈表建立存儲單元來接受用戶從鍵盤輸入的n值。

1.建立的雙向鏈表[1]，指針n_head指向其頭結(jié)點，如圖1所示：（例如輸入n值為512，其他值有類似圖1樣式，其中每一格代表一個字節(jié) ）

圖1 存放鍵盤輸入n值及標志的雙向鏈表

說明：將n值從高位到低位分別存放在鏈表各個結(jié)點的數(shù)據(jù)域中，并將n值最低位的標志域置1（為下一步讓鏈表里的數(shù)據(jù)自減做準備），其他位的標志域置0。

2.程序流程圖（函數(shù)名為build（無參數(shù)），函數(shù)返回值為頭結(jié)點的地址）如圖2所示：

圖2 存放鍵盤輸入n值的算法流程圖

（二）新建雙向鏈表存放累加前n項和i的值，即。

1.（1）首先存放第n項的值（此時新鏈表里的初始值為512）。即拷貝n_head指針指向的鏈表的數(shù)據(jù)域，并使s_head指針指向這個新建的雙向鏈表，注意并不拷貝n_head指向鏈表的標志域，而是使新建鏈表的標志域值均為零。指針s指向鏈表尾結(jié)點。

圖3 向新建雙向鏈表累加第n項的值

（2）流程圖[2]（函數(shù)名為copy （參數(shù)為結(jié)構(gòu)體指針head） ，該函數(shù)返回其頭結(jié)點地址）如圖4所示：

圖4 向新建雙向鏈表累加第n項的值算法流程圖

2.（1）將存放n值鏈表里的值自減1（即n_head指向鏈表里的值變?yōu)?11）。q指針指向鏈表的最后一個結(jié)點。

圖5 存放n值鏈表里的值自減

（2）流程圖如圖6所示（函數(shù)名為dec_n（參數(shù)為指針q ））：

圖6 存放n值鏈表里的值自減

3. （1）將s_head鏈表里的值和n_head鏈表里的值按位相加（由低位到高位），若有進位則存放到s_head鏈表的標志域里。

圖7 第n-1按位相加到存放Sum的鏈表中

在按位相加時可分為兩大部分：

第一部分：只進行除了最高位以外的其他位的按位相加。流程圖（屬主函數(shù)部分）如圖8所示：

圖8 除高位外各位的按位相加

第二部分：指針q和指針s移到高位時，進行相加時有兩種情況。

一種情況是s指針指向結(jié)點沒有前驅(qū)結(jié)點。在這種情況下，如果有進位，需要重新開辟存儲單元（新結(jié)點）來存放進位值，并使該新結(jié)點成為存放累加和Sum鏈表的頭結(jié)點連接到鏈表中。以n值減到511而Sum值為512進行按位相加為例來說明。

圖9 高位處無前驅(qū)結(jié)點的按位相加

另一種情況是s指針指向結(jié)點有前驅(qū)結(jié)點。在這種情況下，如果有進位，需要判斷其前驅(qū)結(jié)點加1是否有進位，若無則將進位累加到前驅(qū)結(jié)點數(shù)據(jù)域中，若有進位，則還應繼續(xù)開辟新結(jié)點存放進位，依次進行，直到?jīng)]有進位為止。

先以n值減到509從而Sum值累加到1533為例來說明前驅(qū)結(jié)點加1無進位的處理。

圖10 高位處有前驅(qū)結(jié)點無進位的按位相加

再以n值減到493從而Sum值累加到9557為例來說明前驅(qū)結(jié)點加1有進位的處理。

圖11 高位處有前驅(qū)結(jié)點有進位的按位相加

開辟新結(jié)點并連接到鏈表中的流程圖如下（函數(shù)名為start（指針s為參數(shù)））：

圖12 開辟新結(jié)點為存放高位的進位算法流程

向結(jié)點中累加進位的流程圖如下（函數(shù)名為kpjw（r參數(shù)），函數(shù)返回值為r結(jié)點的地址）：

圖13 高位處的按位相加算法流程圖

第二部分算法總的流程圖（屬于主函數(shù)部分，其中調(diào)用以上圖12和圖13的函數(shù)）如下：

圖14 高位處進行相加

（三）結(jié)果輸出

用指針指向存放Sum值的鏈表的頭結(jié)點從而將每個結(jié)點里的值即Sum值的每一位由高位到低位全部輸出。

二、結(jié)束語

依據(jù)上述累加和算法，用Turbo C語言編寫程序，并選取大量數(shù)據(jù)對程序進行了測試和驗證，結(jié)果表明，程序輸出結(jié)果正確。在算法設計中是將求和大數(shù)當作字符串進行處理，亦即將大數(shù)用十進制字符鏈表加以表示， 然后模擬人們手工進行“豎式計算”的過程編寫其加減函數(shù)。應該看到，這一算法效率不是很高， 因為1024位的大數(shù)其十進制數(shù)字個數(shù)就有數(shù)百個，對于任何一種運算，都需要在兩個有數(shù)百個元素的鏈表空間上做多重循環(huán)，另還需要許多額外的空間存放計算的進位退位標志。當然其優(yōu)點是算法符合人們熟知的算術(shù)求和規(guī)則，易于表述理解，能從根本上解決大數(shù)求和問題?？梢酝贫ǎ诓煌臋C型和語言環(huán)境中，這個算法的程序編寫語句會有所不同，但算法思想是通用的或可借鑒的。不難推定，求和算法可以推廣到類似的求和問題中，例如，…等等。只要逐次累加值的變化規(guī)律明晰可循，就不難編寫出其相應的求和程序來。

參考文獻：

[1] 嚴蔚敏. 數(shù)據(jù)結(jié)構(gòu)（C語言版） [M]. 北京：清華大學出版社，2003.

[2] 譚浩強. C程序設計（第二版） [M]. 北京：清華大學出版社，1999.

[3]田振清，葉曉玲. 匯編語言中求解任意十進制整數(shù)除法的一個算法[J]. 內(nèi)蒙古師范大學學報：自然科學漢文版，2006年12月第35卷第4期.

作者簡介：

殷文輝（1981—），女，滿，講師，內(nèi)蒙古科左后旗人。