第1章 算法与程序.ppt

第1章 算法与程序.ppt.ppt,就描述了求解两个整数的最大公因子的解题步骤。要求解的问题描述为:“给定两个正整数m和n,求它们的最大公因子,即能同时整除m和n的最大整数”。欧几里德当时给出的算法如下:⑴以n除m,并令所得余数为r(必有r<n);⑵若r=0,输出结果n,算法结束;否则继续步骤⑶;⑶令m=n和n=r,返回步骤⑴继续进行。什么是算法(续)由此,我们可以得出这样的结论,算法就是求解问题的方法和步骤。这里的方法和步骤是一组严格定义了运算顺序的规则;每一个规则都是有效的,且是明确的;按此顺序将在有限次数下终止。有关算法(Algorithm)一词的定义不少,但其内涵基本上是一致的。《计算机程序的艺术》(puterProgram)第一卷中所做的有关描述。其非形式化的定义是:一个算法,就是一个有穷规则的集合,其中之规则定义了一个解决某一特定类型问题的运算序列。什么是算法(续)算法的形式化定义如下所述:算法是一个四元组,即(Q,I,Ω,F)。其中:Q是一个包含子集I和Ω的集合,它表示计算的状态;I表示计算的输入集合;Ω表示计算的输出集合;F表示计算的规则,它是由Q至它自身的函数,且具有自反性,即对任何一个元素q∈Q,有F(q)=q。什么是算法(续)一个算法是对于任何的输入元素x,都在有穷步骤内终止的一个计算方法。在算法的形式化定义中,对任何一个元素x∈I,x均满足性质x0=x,xk+1=F(xk),(k≥0)该性质表示任何一个输入元素x均为一个计算序列,即x0,x1,x2,…,xk;该序列在第k步结束计算。算法的基本特性输入(Input)输出(Output)确定性(Definiteness)有穷性(Finiteness)有效性(Effectiveness)—