我中意的描述计算机科学的办法是把它看作是算法的学问.docVIP

我中意的描述计算机科学的办法是把它看作是算法的学问。算法是精确定义的一系列规则：指出怎样从给定的输入信息经过有限步骤产生所求的输出信息。 ——图灵奖获得者 唐纳德(克努斯（Donald Knuth） 一、算法的概念 “算法”即演算法的大陆中文名称出自《周髀算经》；而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为algorism[?lɡ?riz?m]，意思是阿拉伯数字的运算法则，在18世纪演变为algorithm。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。 电子计算机的出现，开创了算法研究的新时代。人们可以将算法编写成程序提交给计算机执行。从而迅速获得解题结果。著名计算机科学家高纳德(D．E．Knuth)认为：计算机科学是算法的科学。程序按照算法运行，程序是算法的实现。 事实上，在日常生活中解决问题经常要用算法，只是通常不用算法这个词罢了。例如，乐谱是乐队指挥和演奏的算法；菜谱是厨师做菜的算法等等。在漫长的岁月中，人们发现了很多算法。例如，欧几里得提出的求两个自然数的最大公约数算法，早期希腊学者埃拉多塞尼(Eratosthenes)发现的寻找素数的筛法等都是著名的算法例子。 算法是指对问题求解方法准确而完整的描述。算法与程序不同，程序是算法的一种描述，同一个算法可以用不同的编程语言来编写，编写程序时要考虑计算机系统运行环境等细节问题，但设计算法可以摆脱这些束缚。（1）有穷性：算法必须在合理的有限时间内，执行有限次数后结束。 （）确定性：算法中每一条指令的执行必须有唯一的结果，不允许有二义性 （）可行性：算法中描述的操作可以通过已经实现的基本运算有限次地执行来完成。（）算法有两个基本要素：一是算法中对数据的运算和操作，二是算法的控制结构。 （1）算法中对数据的运算和操作 在一般的计算机系统中，基本的功能操作有： ①算术运算：加、减、乘、除等。 ②逻辑运算：或、与、非等。 ③关系运算：大于、小于、等于、不等于等。 ④数据传输：输入、输出、赋值。 （2）算法的控制结构 各种运算和操作之间的执行顺序称为算法的控制结构。算法的基本控制结构有三种：顺序、选择、循环。通常用流程图、N-S结构化流程图、算法描述语言等来描述算法 3.欧几里德算法举例 公元前300年左右，欧几里德在其著作几何原本（Elements）第七卷中阐述了关于求解两个数最大公因子的过程。这就是著名的欧几里德算法：给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。 步骤如下： ①以n除m并令所得余数为r，r必小于n。 ②若r=0算法结束，输出结果为n，否则继续步骤③。 ③将n置换为m，r置换为n，并返回步骤①继续进行。 例如，设m=56,n=32,求m,n的最大公因子。 求解过程如下： ①32除56余数为24。 ②24除32余数为8。 ③8除24余数为0，算法结束，输出结果为8。 二、算法的表示 描述算法的工具，可以是自然语言，也可以是非自然语言。一般可以使用下面几种类型的工具描述算法。 1. 自然语言 自然语言即人们日常生活中使用的语言，如汉语、英语等。例如：求三个数中（a,b,c）最大数的问题，可以描述为： ①比较前两个数； ②将①中较大的数与第三个数进行比较； ③步骤②中较大的数即为所求的数。 用自然语言描述算法通俗易懂，但它存在着难以克服的缺陷： 易产生歧义性。自然语言的语义往往根据上下文的不同容易产生对不同的理解，会产生歧义，不够严格，无法准确表示为计算机语言。 语句比较繁琐冗长。自然语言的描述难于清楚地表达算法的逻辑流程。如果算法中包括判断、循环等结构时，自然语言描述其流程就很难表达清楚且不够直观。 2. 程序设计语言 可直接用程序设计语言来表示算法，例如：求三个数中的最大数的算法用VB语言表示为： a = InputBox(请输入第一个数:) b = InputBox(请输入第二个数:) c = InputBox(请输入第三个数:) If a b Then Max = a Else Max = b If Max c Then Print 最大数为; Max Else Print 最大数为