第3章 计算机算法初步

第3章

计算机算法初步

3.1 算法的概念

3.2 穷举法

3.3 递推与迭代法

3.1

算法的概念

利用计算机求解问题的一般过程 (1)问题分析阶段(2)数据结构设计阶段 (3)算法设计阶段 (4)编码与调试阶段

算法描述

在计算机科学的发展过程中，人们已经提出了很多 种类的算法描述方法。

一种是自然语言的描述方法。鉴于自然语言本身过 于灵活且又缺乏严谨性，所以容易产生理解上的歧 义。

还有一种算法的图形描述方式——流程图。它采用 一些标准的图形符号描述算法的操作过程，从而避 免了人们对非形式化语言的理解差异。

常用流程图符号起止框

调用框

I/O框 连接框 处理框 有向边 判断框

例1:求解一元二次方程 问题分析

假设一元二次方程可以书写成ax2+bx+c=0。可以看 出，任何一个一元二次方程都由三个系数a、b、c惟

一确定，所以，首先需要用户输入三个系数，然后再根据一元二次方程的求解规则计算最终的结果， 并将结果显示输出。

算法描述开始

输入 a,b,c

b2-4ac t

t<0 N N t=0 Y 输出两个解 输出一个解

Y

输出“无解”

结束

程序代码#include <stdio.h> #include <math.h> main( ) { int a, b, c,t; printf( “Input a,b,c: ” ); scanf( “%d%d%d”, &a, &b, &c ); t = b*b – 4*a*c; if (t<0) printf( “No solution\n” ); else if ( t==0 ) printf( “X = %lf\n”, -b/(2.0*a) ); else { double t0; t0 = sqrt( (double)t ); printf( “X1 = %lf, X2= %lf\n”, (-b+t0)/(2*a), (-b-t0)/(2*a) ); } }

3.2 概述

穷举法

穷举法，又称为枚举法，是人们日常生活中常用的 一种求解问题的方法。例如，从某个班中找出所有 班干部，需要逐一对每个同学进行查看，判断是否 是班干部。这种方法的基本思路就是一一列举每个

可能性，逐个进行排查。因此，穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个 进行判断，最终找出正确问题的答案。

穷举法应用实例1:素数的判断

所谓素数是指仅能被1和自身整除，且大于等于2的 数值。判断一个给定的数值是否是素数是穷举法的 典型实例。

例2:判断给定整数是否是素数 。 问题分析

为了检查一个整数是不是素数，可以采用穷举法。 假设给定的整数用x表示，则判断过程就是确认x不 能整除以2~x-1之间的任何整数。这就需要一一列举 出2~x-1之间的每个整数进行排查。

算法描述开始

输入x

2 t

N t<x Y Y x%t==0 N t 加1 N t == x Y

输出“不是素数”

输出“是素数”

结束

程序代码#include <stdio.h> main( ) { int x, t; printf( “Enter an integer: ” ); scanf( “%d”, &x ); for (t = 2; t<x; t++ ) /* 列举小于x大于1的所有

整数 */ if ( x%t == 0 ) break; if ( t == x ) /* 是否通过循环条件出口 */ printf( “%d is prime\n”, x ); else printf( “%d isn’t prime\n”, x ); }

穷举法应用实例2:百钱买百鸡

“百钱买百鸡”是我国古代数学家张丘建提出的一 个著名的数学问题。假设某人有钱百枚，希望买一 百只鸡；不同的鸡价格不同，公鸡5枚钱一只，母 鸡3枚钱一只，而小鸡3只1枚钱。试问：如果用百 枚钱买百只鸡，可以包含几只公鸡、几只母鸡和几 只小鸡。

例3:百钱买百鸡。 问题分析

从题目要求可知：公鸡、母鸡和小鸡的数量是有限的，都不会超过100。通过对不同数量的公鸡、母 鸡和小鸡进行组合，可以计算出购买这些鸡所用的 花费，但这个题目要求找出那些花费正好100枚且 鸡的总数也为100只的情况。因此，可以采用穷举 法，将不同的公鸡、母鸡和小鸡的数量枚举一遍， 找出那些符合题目要求的解。

算法描述开始 0 x

N x <= 100/5 x 加1 Y 0 y

结束

N y <= 100/3 x Y 0 z y 加1

N z<=100 z 加1 Y 条件判断 Y N

输出 x, y, z

程序代码#include <stdio.h> #include <math.h> main( ) { int x, y, z;for( x=0; x<=100/5; x++ ) for( y=0; y<=100/3; y++ ) for( z=0; z<=100; z++ ) { if (x+y+z ==100 &&15*x+9*y+z==300) printf( “x=%d, y=%d, z=%d\n”, x, y, z ); } }