分治算法在信息學(xué)奧賽中的應(yīng)用

（云南省保山市實(shí)驗(yàn)小學(xué) 云南保山 678000）

一、算法概述

1.算法背景

“算法”的中文名稱出自周髀算經(jīng)；而英文名稱 Algorithm 來(lái)自于9世紀(jì)波斯數(shù)學(xué)家比阿勒·霍瓦里松的名字al-Khwarizmi，因?yàn)楸劝⒗铡せ敉呃锼稍跀?shù)學(xué)上提出了算法這個(gè)概念?！八惴ā痹瓰椤盿lgorism”，意思是阿拉伯?dāng)?shù)字的運(yùn)算法則，在18世紀(jì)演變?yōu)椤盿lgorithm”。 第一次編寫算法是Ada Byron于1842年為巴貝奇分析機(jī)編寫求解解伯努利方程的程序，因此Ada Byron被大多數(shù)人認(rèn)為是世界上第一位程序員。因?yàn)椴闋査埂ぐ拓惼妫–harles Babbage）未能完成他的巴貝奇分析機(jī)，這個(gè)算法未能在巴貝奇分析機(jī)上執(zhí)行。因?yàn)椤眞ell-defined procedure”缺少數(shù)學(xué)上精確的定義，19世紀(jì)和20世紀(jì)早期的數(shù)學(xué)家、邏輯學(xué)家在定義算法上出現(xiàn)了困難。20世紀(jì)的英國(guó)數(shù)學(xué)家圖靈提出了著名的圖靈論題，并提出一種假想的計(jì)算機(jī)的抽象模型，這個(gè)模型被稱為圖靈機(jī)。圖靈機(jī)的出現(xiàn)解決了算法定義的難題，圖靈的思想對(duì)算法的發(fā)展起到了重要的作用。[1]

2.什么是算法

算法（algorithm）一詞源于算術(shù)（algorism），算術(shù)方法的原義是一個(gè)由已知推求未知的運(yùn)算過(guò)程。后來(lái)，人們把它推廣到一般，指算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則，甚至把把進(jìn)行某一工作的方法和步驟也稱為算法。

3.算法的一般特征

（1）能行性（effectiveness）

算法的能行性包括兩個(gè)方面：一是算法中的每一個(gè)步驟必須是能實(shí)現(xiàn)的。二是算法執(zhí)行的結(jié)果要能達(dá)到預(yù)期的目的。[2]

（2）確定性（definiteness）

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

（3） 有窮性（finiteness）

算法的有窮性是指算法必須能在有限的時(shí)間內(nèi)執(zhí)行完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。

（4） 有0個(gè)或多個(gè)輸入項(xiàng)，至少有一個(gè)輸出項(xiàng)（算法必須擁有足夠的情報(bào)）

一個(gè)算法是否有效，還取決于為算法的執(zhí)行所提供的情報(bào)是否足夠。一般來(lái)說(shuō)，只有當(dāng)算法擁有足夠的情報(bào)時(shí)，該算法才是有效的；而如果提供的情報(bào)不夠，則算法并不是有效的。

二、算法與信息學(xué)奧賽

1.信息學(xué)奧賽簡(jiǎn)介

全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽（NOI）是由國(guó)家教育部、中國(guó)科協(xié)批準(zhǔn)，中國(guó)計(jì)算機(jī)學(xué)會(huì)主辦的一項(xiàng)面向全國(guó)青少年的信息學(xué)競(jìng)賽和普及活動(dòng)。也是與聯(lián)合國(guó)教科文組織提倡的國(guó)際信息學(xué)奧林匹克競(jìng)賽，同步進(jìn)行的一項(xiàng)競(jìng)賽活動(dòng)。旨在向那些在中學(xué)階段學(xué)習(xí)的青少年普及計(jì)算機(jī)科學(xué)知識(shí)；給學(xué)校的信息技術(shù)教育課程提供動(dòng)力和新的思路；給那些有才華的學(xué)生提供相互交流和學(xué)習(xí)的機(jī)會(huì)；通過(guò)競(jìng)賽和相關(guān)的活動(dòng)培養(yǎng)和選拔優(yōu)秀計(jì)算機(jī)人才。而算法卻在信息學(xué)奧賽中占有重要地位。

2.信息學(xué)奧賽與算法

（1）算法在信息學(xué)奧賽中有利于培養(yǎng)思維能力

算法一方面具有具體化、程序化、機(jī)械化的特點(diǎn)，同時(shí)又有抽象性、概括性和精確性。對(duì)于一個(gè)具體算法而言，從算法分析到算法語(yǔ)言的實(shí)現(xiàn)，任何一個(gè)疏漏或錯(cuò)誤都將導(dǎo)致算法的失敗。算法是思維的條理化、邏輯化。算法所體現(xiàn)出來(lái)的邏輯化特點(diǎn)被有些學(xué)者看成是邏輯學(xué)繼形式邏輯和數(shù)理邏輯之后發(fā)展的第三個(gè)階段。因此，算法可以培養(yǎng)邏輯思維能力

（2）算法在信息學(xué)奧賽中有利于培養(yǎng)理性精神和實(shí)踐能力

算法既重視“算則”，更重視“算理”。對(duì)于算法而言，一步一步的程序化步驟，即“算則”固然重要，但這些步驟的依據(jù)，即“算理”有著更基本的作用。“算理”是“算則”的基礎(chǔ)，“算則”是“算理”的表現(xiàn)。中國(guó)古代數(shù)學(xué)以算法為主要特征，取得了舉世公認(rèn)的偉大成就?，F(xiàn)代信息技術(shù)的發(fā)展使算法煥發(fā)了前所未有的生機(jī)和活力，算法也進(jìn)入信息學(xué)奧賽中。[3]

3. 信息學(xué)奧賽中常用到的算法

信息學(xué)奧賽中常用到的算法有迭代法、窮舉搜索法、遞推法、貪婪法、回溯法、分治法、動(dòng)態(tài)規(guī)劃法等算法。分治算法在信息學(xué)奧賽中應(yīng)用廣泛，在一些題中使用分治算法能使算法變得更簡(jiǎn)單，容易理解。還可以在算法技巧上設(shè)計(jì)的更巧妙，更合理。使最終的程序算法在時(shí)間和空間上達(dá)到最佳的平衡。[4]

三、分治算法在中學(xué)信息學(xué)奧賽中的應(yīng)用

1.分治法的基本思想

任何一個(gè)可以用計(jì)算機(jī)求解的問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問(wèn)題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。例如，對(duì)于n個(gè)元素的排序問(wèn)題，當(dāng)n=1時(shí)，不需任何計(jì)算。n=2時(shí)，只要作一次比較即可排好序。n=3時(shí)只要作3次比較即可，而當(dāng)n較大時(shí)，問(wèn)題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問(wèn)題，有時(shí)是相當(dāng)困難的。分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分治者，分而治之。分治策略是：對(duì)于一個(gè)規(guī)模為n的問(wèn)題，若該問(wèn)題可以容易地解決（比如說(shuō)規(guī)模n較?。﹦t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。這種算法設(shè)計(jì)策略叫做分治法。如果原問(wèn)題可分割成k個(gè)子問(wèn)題，1＜k≤n ，且這些子問(wèn)題都可解，并可利用這些子問(wèn)題的解求出原問(wèn)題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。分治算法有基于“聚合”的底向上的分治算法和基于“分解”的頂向下的分治方法兩種。

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

1.分解（Divide）：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；

2.解決（Resolve）：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；

3.合并（Merge）：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解；

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

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

結(jié)語(yǔ)

隨著信息學(xué)奧賽的發(fā)展，算法在信息學(xué)奧賽中的地位日益突出。分治算法在信息學(xué)奧賽中的應(yīng)用也越來(lái)越廣泛。在一些題中使用分治算法可以得到預(yù)想不到的效果。分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：[5]

1.該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；

2.該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；

3.利用該問(wèn)題分解出的子問(wèn)題的解，可以合并為該問(wèn)題的解；

4.該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題；

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

參考文獻(xiàn)：

[1]呂國(guó)英，任瑞征，錢宇華.算法設(shè)計(jì)與分析[M]（2006年版）.北京：清華大學(xué)出版社，2006.3，128～140.

[2]晉良穎.數(shù)據(jù)結(jié)構(gòu)[M]（2003年版）.北京：人民郵電出版社，2003，1～76，251～256.

[3]譚浩強(qiáng).C程序設(shè)計(jì)[M]（1999年第二版）.北京：清華大學(xué)出版社，1999，13～18，260～266.

[4]余祥宣，崔國(guó)華，鄒海明.計(jì)算機(jī)算法基礎(chǔ)[M](2000年第二版).武漢：華中科技大學(xué)出版社，2000，1～7，37～63.

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