张成棋　洪院花

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

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

一、算法概述

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），算术方法的原义是一个由已知推求未知的运算过程。后来，人们把它推广到一般，指算法是在有限步骤内求解某一问题所使用的一组定义明确的规则，甚至把把进行某一工作的方法和步骤也称为算法。……