分治算法在信息学奥赛中的应用

张成棋　洪院花

摘 要：随着计算机的发展，算法在信息学奥赛的地位日益突出。分治算法在信息学奥赛中的应用也越来越广泛。本文主要介绍分治算法的基本思想与分治算法两种形式在信息学奥赛中是通过划分子问题的方法，由小尺寸问题的解决导致原问题的解决。初步分析和探讨了分治算法在信息学奥赛中的适用场合。

关键词：算法信息学奥赛分治算法

一、算法概述

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.