4.1.2性质 在4.1.1中我们曾介绍了克努斯给出的算 法定义,其中包括算法成立的五个重要条 件,实际上就是算法的规则序列必须满足 的五个特性。 1958 g
4.1.2 性质 在4.1.1中我们曾介绍了克努斯给出的算 法定义,其中包括算法成立的五个重要条 件,实际上就是算法的规则序列必须满足 的五个特性
例1给定两个整数m和n,试写出它们的最大公因 子的算法。 其算法如下: 1.读入两个正整数m和n(设m>n) 2.求m和n的余数r。 3.用n的值取代m,用r的值取代n 4.判断r的值是否为零,如果r=0,则m为最大公 因子,否则返回2 输出m的值 1958 g
例1 给定两个整数m和n，试写出它们的最大公因 子的算法。 其算法如下： 1． 读入两个正整数m和n（设m>n）。 2． 求m和n的余数r。 3． 用n的值取代m，用r的值取代n。 4. 判断r的值是否为零，如果r=0，则m为最大公 因子，否则返回2 5. 输出m的值
■我们可以看到,无论给出多大的两个数,这个 算法都会在执行一定次数之后结束。这是算法 的有穷性要求:“算法必须总是(对任何合法 的输入值)在执行有穷步之后结束,且每一步 都可在有穷时间内完成”。 1958 g
◼ 我们可以看到，无论给出多大的两个数，这个 算法都会在执行一定次数之后结束。这是算法 的有穷性要求：“算法必须总是（对任何合法 的输入值）在执行有穷步之后结束，且每一步 都可在有穷时间内完成”
■给出的数值必须是确定的,不能出现诸如 “比m大一些或比n小一点儿”之类的无法确 定数值的表达方式。这是算法的确定性要求 算法中每一条指令必须被确切地定义,读者 理解时不会产生二义性。 ■算法一定是可操作的,当我们用笔和纸代替 计算机去完成计算过程时是可以做到的。这 算法的可行性要求:即算法中描述的操作 都是可以通过有限次的基本运算执行来实现 的 1958 g
◼ 给出的数值必须是确定的，不能出现诸如 “比m大一些或比n小一点儿”之类的无法确 定数值的表达方式。这是算法的确定性要求： 算法中每一条指令必须被确切地定义，读者 理解时不会产生二义性。 ◼ 算法一定是可操作的，当我们用笔和纸代替 计算机去完成计算过程时,是可以做到的。这 是算法的可行性要求：即算法中描述的操作 都是可以通过有限次的基本运算执行来实现 的
个算法有零个或多个的输入。在上述的例 子中共有两个已知变量:m和n,否则算法将无 法执行下去,这是算法的输入要求。 算法必须给出结果,在本例中,结果为m和n 的最大公因子。这是算法的输出要求:一个 算法有一个或多个的输出,这些输出是与输 入有着某些特定关系的量。 1958 g
◼ 一个算法有零个或多个的输入。在上述的例 子中共有两个已知变量:m和n,否则算法将无 法执行下去,这是算法的输入要求。 ◼ 算法必须给出结果，在本例中，结果为m和n 的最大公因子。这是算法的输出要求：一个 算法有一个或多个的输出，这些输出是与输 入有着某些特定关系的量