1.2.2 算法举例

例1.6 设计一个求解一元二次方程ax2+bx+c=0的算法。

算法分析：我们知道，根据判别式Δ=b2−4ac的符号，一元二次方程ax2+bx+c=0的解有三种情况，所以，在求解方程前要先判断判别式的符号，然后执行不同的计算。

第一步：输入三个系数a、b、c；

第二步：计算Δ=b2−4ac的值；

第三步：判断是否成立Δ≥0，若是，则计算，进入第四步；若否，输出“方程没有实数根”。

第四步：判断Δ=0，若是，则输出x= p；若否，计算x1= p+q,x2= p−q，并输出x1、x2，结束。

例1.6的N-S图如图1.7（a）所示，流程图如图1.7（b）所示。

例1.7 中国农历60年一大轮回，按天干（甲、乙、丙、丁、戊、己、庚、辛、壬、癸）和地支（子、丑、寅、卯、辰、巳、午、未、申、酉、戍、亥）循环排列而成。天干共10个，公元纪年也是10年一周期，公元纪年除以10的余数（就是公元纪年的尾数）与天干之间有一种关联，即余数与天干一一对应（见表1.2）。

地支共12个，地支12年一轮回，用公元纪年除以12，余数与地支也有一一对应关联（如表1.3所示）。

根据以上对应关系，设计一个算法并输出字符串农历纪年的算法，然后画出N-S图。

解：N-S图如图1.8（a）所示，流程图如图1.8（b）所示。

例1.8 设计一个求10！的算法，画出N-S图。

算法分析：求10!，要先计算1×2，然后将1×2的结果乘以3，前3个数的乘积再乘以4，以此方式进行一个累乘循环的计算过程。所以，需要设定一个存放每次乘积的变量t和一个循环计数变量i，将累乘变量的初值设为1，计数变量在1≤i≤10范围。

第一步：赋初值t=1,i=1。

第二步：判断i≤10，若是，计数变量i增加1，即i=i+1，累乘变量t乘以计数变量，即t=t×i；若否，输出t，结束。

例1.8的N-S图如图1.9（a）所示，流程图如图1.9（b）所示。

例1.9 用“二分法”设计一个求方程x2−2=0的近似根的算法。

二分法是基于“根的存在定理”，求方程根的近似值的一种算法。二分法思想为：将函数的零点所在区间不断地一分为二，使所得的新区间不断变窄，两个端点逐步逼近零点，达到精度要求为止。

根的存在定理：设函数f（x）在闭区间[a,b]上连续，且f（a）×f（b）＜0，则（a,b）内至少有一点c，使得f（c）=0。c称为函数f（x）的零点，这个定理可以帮助我们确定方程根的大致范围，或判断方程在某一范围内是否有解。

算法分析：根据“二分法”步骤，需要的已知条件有方程、有且只有一个根的区间、近似根的精度。

第一步：输入 f（x）=x2−2，误差精度ε,a、b（a、b为有根区间的端点）。

第二步：令，判断f（m）是否为0，若是，则m为方程的根；若否，进入第三步。

第三步：判断 f（a）×f（m）＜0，若是，则令b=m；若否，令a=m。

第四步：判断，若是，则输出x=m；若否，则返回第二步。

例1.9的N-S图如图1.10（a）所示，流程图如图1.10（b）所示。

课堂练习1.2

1.判断下列说法是否正确。

A　算法的三种基本逻辑结构流程图都只有一个入口、一个出口。（　　）

B　循环结构有选择性和重复性，选择结构具有选择性但不重复。（　　）

2.填空。

（1）算法的基本逻辑结构有（　　）。

（2）表示算法的图有（　　）。

（3）求10！的算法里循环结构的三个要素（　　）。

（4）表达交换a、b的值的语句是（　　）。

3.已知华氏温度和摄氏温度的转换公式是：

设计一个将华氏温度转换成摄氏温度的算法，并画出其流程图或N-S图。

4.设计一个算法，求方程ax+b=0的根，并画出其流程图或N-S图。

5.设计一个算法，求1+2+4+...+249，并画出其流程图或N-S图。