分治算法在信息學奧賽中的應用

張成棋　洪院花

摘 要：隨著計算機的發展，算法在信息學奧賽的地位日益突出。分治算法在信息學奧賽中的應用也越來越廣泛。本文主要介紹分治算法的基本思想與分治算法兩種形式在信息學奧賽中是通過劃分子問題的方法，由小尺寸問題的解決導致原問題的解決。初步分析和探討了分治算法在信息學奧賽中的適用場合。

關鍵詞：算法信息學奧賽分治算法

一、算法概述

1.算法背景

“算法”的中文名稱出自周髀算經；而英文名稱 Algorithm 來自于9世紀波斯數學家比阿勒·霍瓦里松的名字al-Khwarizmi，因為比阿勒·霍瓦里松在數學上提出了算法這個概念。“算法”原為”algorism”，意思是阿拉伯數字的運算法則，在18世紀演變為”algorithm”。 第一次編寫算法是Ada Byron于1842年為巴貝奇分析機編寫求解解伯努利方程的程序，因此Ada Byron被大多數人認為是世界上第一位程序員。因為查爾斯·巴貝奇（Charles Babbage）未能完成他的巴貝奇分析機，這個算法未能在巴貝奇分析機上執行。 因為”well-defined procedure”缺少數學上精確的定義，19世紀和20世紀早期的數學家、邏輯學家在定義算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了算法定義的難題，圖靈的思想對算法的發展起到了重要的作用。[1]

2.什么是算法

算法（algorithm）一詞源于算術（algorism），算術方法的原義是一個由已知推求未知的運算過程。后來，人們把它推廣到一般，指算法是在有限步驟內求解某一問題所使用的一組定義明確的規則，甚至把把進行某一工作的方法和步驟也稱為算法。

3.算法的一般特征

（1）能行性（effectiveness）

算法的能行性包括兩個方面：一是算法中的每一個步驟必須是能實現的。二是算法執行的結果要能達到預期的目的。[2]

（2）確定性（definiteness）

算法的確定性，是指算法中的每一個步驟都必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。這一特征也反映了算法與數學公式的明顯差異。

（3） 有窮性（finiteness）

算法的有窮性是指算法必須能在有限的時間內執行完，即算法必須能在執行有限個步驟之后終止。

（4） 有0個或多個輸入項，至少有一個輸出項（算法必須擁有足夠的情報）

一個算法是否有效，還取決于為算法的執行所提供的情報是否足夠。一般來說，只有當算法擁有足夠的情報時，該算法才是有效的；而如果提供的情報不夠，則算法并不是有效的。

二、算法與信息學奧賽

1.信息學奧賽簡介

全國青少年信息學奧林匹克競賽（NOI）是由國家教育部、中國科協批準，中國計算機學會主辦的一項面向全國青少年的信息學競賽和普及活動。也是與聯合國教科文組織提倡的國際信息學奧林匹克競賽，同步進行的一項競賽活動。旨在向那些在中學階段學習的青少年普及計算機科學知識；給學校的信息技術教育課程提供動力和新的思路；給那些有才華的學生提供相互交流和學習的機會；通過競賽和相關的活動培養和選拔優秀計算機人才。而算法卻在信息學奧賽中占有重要地位。

2.信息學奧賽與算法

（1）算法在信息學奧賽中有利于培養思維能力

算法一方面具有具體化、程序化、機械化的特點，同時又有抽象性、概括性和精確性。對于一個具體算法而言，從算法分析到算法語言的實現，任何一個疏漏或錯誤都將導致算法的失敗。算法是思維的條理化、邏輯化。算法所體現出來的邏輯化特點被有些學者看成是邏輯學繼形式邏輯和數理邏輯之后發展的第三個階段。因此，算法可以培養邏輯思維能力

（2）算法在信息學奧賽中有利于培養理性精神和實踐能力

算法既重視“算則”，更重視“算理”。對于算法而言，一步一步的程序化步驟，即“算則”固然重要，但這些步驟的依據，即“算理”有著更基本的作用。“算理”是“算則”的基礎，“算則”是“算理”的表現。中國古代數學以算法為主要特征，取得了舉世公認的偉大成就。現代信息技術的發展使算法煥發了前所未有的生機和活力，算法也進入信息學奧賽中。[3]

3. 信息學奧賽中常用到的算法

信息學奧賽中常用到的算法有迭代法、窮舉搜索法、遞推法、貪婪法、回溯法、分治法、動態規劃法等算法。分治算法在信息學奧賽中應用廣泛，在一些題中使用分治算法能使算法變得更簡單，容易理解。還可以在算法技巧上設計的更巧妙，更合理。使最終的程序算法在時間和空間上達到最佳的平衡。[4]

三、分治算法在中學信息學奧賽中的應用

1.分治法的基本思想

任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，而當n較大時，問題就不那么容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分治者，分而治之。分治策略是：對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設計策略叫做分治法。如果原問題可分割成k個子問題，1

2.分治法的基本步驟（分治法在每一層遞歸上都有三個步驟）

1.分解（Divide）：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；

2.解決（Resolve）：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；

3.合并（Merge）：將各個子問題的解合并為原問題的解；

四、基于“聚合”的底向上的分治算法

如果知道了最終直接可解的原子問題的全部情況，那么可采用由原子問題出發，向上遞推的方法，由已有結論的小尺寸問題的解決，導出比它高一層次的同類問題的解決，最終使原問題徹底解決。這就是和遞歸向下方法對應的由底向上的分治方法的基本思路。

結語

隨著信息學奧賽的發展，算法在信息學奧賽中的地位日益突出。分治算法在信息學奧賽中的應用也越來越廣泛。在一些題中使用分治算法可以得到預想不到的效果。分治法所能解決的問題一般具有以下幾個特征：[5]

1.該問題的規模縮小到一定的程度就可以容易地解決；

2.該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；

3.利用該問題分解出的子問題的解，可以合并為該問題的解；

4.該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題；

上述的第一條特征是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增加而增加；第二條特征是應用分治法的前提，它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用；第三條特征是關鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動態規劃法。第四條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。

參考文獻：

[1]呂國英，任瑞征，錢宇華.算法設計與分析[M]（2006年版）.北京：清華大學出版社，2006.3，128～140.

[2]晉良穎.數據結構[M]（2003年版）.北京：人民郵電出版社，2003，1～76，251～256.

[3]譚浩強.C程序設計[M]（1999年第二版）.北京：清華大學出版社，1999，13～18，260～266.

[4]余祥宣，崔國華，鄒海明.計算機算法基礎[M]（2000年第二版）.武漢：華中科技大學出版社，2000，1～7，37～63.

[5]王紅梅.算法設計與分析[M]（2006年版）.北京：清華大學出版社，2006，1～8，73～74，85～87.