ITEEDU

2.8 构造算法：实例研究1(计数器控制重复)

要演示如何开发算法，我们要解决几个全班平均成绩的问题。考虑下列问题：

班里有10个学生参加测验，可以提供考试成绩(0到100的整数值)，以确定全班平均成绩。

全班平均成绩等于全班成绩总和除以班里人数。计算机上解决这个问题的算法是辅人每人的成绩，进行平均计算，然后打印结果。

注意算法中引用了总数(total)和计数器。总数变量用于累计一系列数值的和。计数器变量用于计数，这里计算输人的成绩数。存放总数的变量通常应先初始化为0之后再在程序中使用，否则总和会包括总数的内存地址中存放的原有数值。

  Set total to zero
   Set grade counter to one
      While grade counter is less than or equal to ten
              Input the next grade
              Add the grade i.to the total
              Add one to the grade counter
      Set the class average to the total divided by ten
      Print the class average

图2.6 用计数器控制重复解决全班平均成绩问题的伪代码算法

// Fig. 2.7: fig0207.cpp
// Class average program with counter-controlled repetition
#include <iostream.h>
int main()
{
	int total,          // sum of grades
	gradeCounter,  // number of grades entered
	grade,        // one grade
	average;      // average of grades
	// initialization phase
	total = 0;                           // clear total
	gradeCounter = 1;                     // prepare to loop
	// processing phase
	while ( gradeCounter <= 10 ) {          // loop 10 times
		cout << "Enter grade: ";          // prompt for input
		cin >> grade;                   // input grade
		total = total + grade;            // add grade to total
		gradeCounter = gradeCounter + 1;    // increment counter
	}
	// termination phase
	average - total / 10;             // integer division
	cout << "Class average is "<< average << endl;
	return 0;  // indicate program ended successfully
}

输出结果：

    Enter grade: 98
    Enter grade: 76
    Enter grade: 71
    Enter grade: 87
    Enter grade: 83
    Enter grade: 90
    Enter grade: 57
    Enter grade: 79
    Enter grade: 82
    Enter grade: 94
    Class average is 81

图2.7 用计数器控制重复解决全班平均成绩问题的C++程序和示例输出

根据使用情况，计数器变量通常应先初始化为0或1(下面会分别举例说明)。未初始化变量会包含垃圾值“garbage”value)，也称为未定义值(undefined

value)，为该变量保存内存地址中最后存放的值。

常见编程错误2.6

编程技巧2.7

编程技巧2.8

每个变量在单独一行中声明。注意程序中的平均计算产生一个整数结果。实际上，本例中的成绩总和是817，除以10时应得到81.7，是个带小数点的数，下节将介绍如何处理这种值(称为浮点数)。

常见编程错误2.7

在计数器控制循环中，由于循环计数器(每人循环加1时)比最大合法值多1(例如，从1算到10时为11)．因此在循环之后用计数器值进行计算通常会出现差1的错误。

图2.7中，如果第21行用gradeCounter而不是10进行计算，则这个程序的输出显示数值74。

2.9构造算法与自上而下逐步完善：实例研究2(标记控制重复)

下面将全班平均成绩问题一般化，考虑如下问题：

开发一个计算全班平均成绩的程序，在每次程序运行时处理任意个成绩数。

在第一个全班平均成绩例子中，成绩个数(10)是事先预置的。而本例中，则不知道要输入多少个成绩，程序要处理任意个成绩数。程序怎么确定何时停止输入成绩呢?何时计算和打印全班平均成绩呢?

显然，标记值不能与可接受的输入值混淆起来。由于考试成绩通常是非负整数，因此可以用-1作标记值。这样，全班平均成绩程序可以处理95、96、75、74、89和-l之类的输人流。程序计算并打印成绩95、96、75、74和89的全班平均成绩(不计入-1，因为它是标记值)。

常见编程错误2.8

将选择的标记值与可接受的输入值混淆时会造成逻辑错误。

refinement)的方法开发计算全班平均成绩的程序，这是开发结构化程序的重要方法。我们首先生成上层伪代码表示：

  Determine  the  class  avcraqe  for  the quiz

上层伪代码只是一个语句，表示程序的总体功能。这样．上层等于是程序的完整表达式。但上层通常无法提供编写C++程序所需的足够细节。因此要开始完善过程。我们将上层伪代码分解为一系列的小任务，按其需要完成的顺序列出。这个结果就是下列第一步完善(first，refinement)：

Initialize variables
    Input,sum,and count the quiz grades
    Calculate and print the class average

这里只用了顺序结构，所有步骤按顺序逐步执行。

软件工程视点2.4

上层伪代码及每一步完善都是算法的完整定义，只是详细程度不同而已。

软件工程视点2.5

许多程序可以在逻辑上分为三个阶段：初初化阶段将程序变量初始化，处理阶段输入数据值和相应调整程序变量，结束阶段计算和打印最后结果。

refinement)，我们要指定特定变量，要取得数字的动态和以及计算机处理的数值个数，用一个变量接收每个输入的成绩值，一个变量保存计算平均值。下列伪代码语句：

      Initialize variables

可以细化成：

 Initialize total to zero
    Initialize counter to zero

注意，只有total和counter变量要先初始化再使用，average和grade变量(分别计算平均值和用户输入)不需要初始化．因为它们的值会在计算或输入时重定义。

下列伪代码语句：

Input, sum, and count the quiz grades

需要用重复结构(即循环)连续输入每个成绩。由于我们事先不知道要处理多少个成绩，因此使用标记控制重复。用户一次一项地输入合法成绩。输入最后一个合法成绩后，用户输人标记值。程序在每个成绩输入之后测试其是否为标记值．如果用户输入标记值，则顺序循环终止。上述伪代码语句的第二步完善如下：

   Input the first grade (possibly the sentinel)
    While the user has not as yet entered the sentinel
   Add this grade into the running total
    Add one to the grade counter
    Input the next grade (possibly the sentinel)

注意，在这个伪代码中，我们没有在while结构体中使用花括号，只是在while下面将这些语句缩排表示它们属于while。伪代码只是非正式的程序开发辅助工具。

下列伪代码语句可以完善如下：

 If the counter is not equal to zero
     Set the average to the total divided by the counter
     Print the average
    else
      Print "No grades were entered"

常见编程错误2.9

除数为0是个致命逻辑错误。

编程技巧2.9

进行除法时，要测试除数为0的可能性，并在程序中进行相应处理(如打印一个错误消息)．而不是让致命逻辑错误发生。

图2.6和图2.8的伪代码中增加了一些空行，使伪代码更易读。空行将程序分成不同阶段。

图2.8所示的伪代码算法解决更一般的全班平均成绩问题，这个算法只进行了第二步完善，还需要进一步完善。

 Initialize total to zero
    Initialize counter to zero

    Input the first grade (possibly the sentinel)
    While the user has not as yet entered the sentinel
       Add this grade into the running total
       Add one to the grade counter
       Input the next grade (possibly the sentinel)

    if the counter is not rqual to zero
       Set the average to the total divided by the counter
       Print the average
    else
       Print "No grades were entered"

图2．8 用标记符控制重复解决全班平均成绩问题的伪代码算法

软件工程视点2.6

伪代码算法的细节足以将伪代码变为C++代码时，程序员即可停止自上而下逐步完善的过程，然后就可方便地实现C++程序。

图2.9显示了C++程序和示例执行结果。尽管只输入整数成绩，但结果仍然可能产生带小数点的平均成绩，即实数。int类型无法表示实数，程序中引入float数据类型处理带小数点的数(也称为浮点数，floatingpoint number)，并引入特殊的强制类型转换运算符(cast operator)处理平均值计算。这些特性将在程序之后详细介绍。

// Fig. 2.9: fig02_09.cpp
// Class average program with sentinel-controlled repetition.
#include <iostream.h>
#include <iomanip.h>
int main()
{
	int total,    // sum of grades
	gradeCounter, // number of grades entered
	grade;      // one grade
	float average;  // number with decimal point for average
	// initialization phase
	total = 0;
	gradeCounter = 0;
	// processing phase
	cout << "Enter grade, -1 to end: ";
	cin >> grade;
	while ( grade !=-1 ) {
		total = total + grade;
		gradeCounter = gradeCounter + 1;
		cout << "Enter grade, -1 to end: ";
		cin >> grade;
	}
	// termination phase
if ( gradeCounter != 0 } {
	average - static_cast< float >( total ) / gradeCounter;
	cout << "Class average is "<< setprecision{ 2 )
		<< setiosflags( ios::fixed | ios::showpoint )
			<< average << endl;
		}
		else
			cout << "NO grades were entered" << endl;
			return 0;        // indicate program ended successfully
		}

输出结果：

   Enter grade, -1 to end: 75
    Enter grade, -1 to end: 94
    Enter grade, -1 to end: 97
    Enter grade,-1 to end: 88
    Enter grade, -1 to end: 70
    Enter grade, -1 to end: 64
    Enter grade, -1 to end: 83
    Enter grade, -1 to end: 89
    Enter grade, -1 to end: -1
    Class average is 82.50

图2.9 用标记符控制重复解决全班平均成绩问题的C++程序和示例执行结果

注意图2.9中while循环中的复合语句。如果没有花括号，则循环体中的最后三条语句会放到循环以外，使计算机错误地理解如下代码：

   while { grade ! = -1 )
       total - total + grade;
    gradeCounter = gradeCounter + 1;
    cout << "Enter grade, -1 to end:";
    cin >> grade;

如果用户输入的第一个成绩不是-l，则会造成无限循环。

注意下列语句：

   cin >>grade;

前面用一个输出语句提示用户输入。

编程技巧2.10

提示用户进行每个键盘输入。提示应表示输入形式和任何特殊输入值(如用户终止循环时输入的标记值)。

编程技巧2.11

在标记控制循环中，提示请求输入数据项目时应显式指定标记值是什么值。

division)，小数部分丢失(即截尾，truncated)。由于先要进行计算，因此小数部分在将结果赋给average之前已经丢失。要用整数值进行浮点数计算，就要先生成用于计算的临时浮点数值。

C++提供了一元强制类型转换运算符(unary cast operator)。下列语句：

average = static cast< float >(total) /gradeCounter;

图2.9中格式化功能将在第11章详细介绍，这里先做一简要介绍。下列输出语句中调用

 setpreclslon(2)：
        cout<<"Class average is" << setprecision(2)
        << Setiosflaqs(iOS::fixed |iOS::showpoint)
        << averaqe<< endl；

        #include<iomanip.h>

常见编程错误2.10

如莱在使用浮点敷时认为其精确地表示了敷值．则全得到不正确的蛄柬。浮点敷雇大多数计算机上都采用近似表示。

编程技巧2.12

不要比较浮点数值的相等和不等性，而要测试差值绝对值是否小于指定的值。

尽管浮点数算不总是100％精确，但其用途很广。例如，我们说正常体温98.6(华氏温度)时，并不需要精确地表示，如果温度计上显示98.6度．实际上可能是98.5999473210643度。这里显示98.6对大多数应用已经足够了。

另一种得到浮点数的方法是通过除法。10除以3得到3.333333……，是无限循环小敷。计算机只分配固定空间保存这种值，因此只能保存浮点值的近似值。

2.10构造算法与自上而下逐步完善：实例研究3(嵌套控制结构)

下面介绍另一个问题。这里还是用伪代码和自上而下逐步完善的方法构造算法，然后编写相应的C++程序。我们介绍过按顺序堆叠的控制结构，就像小孩堆积木一样。这里显示C++中控制结构的另一种方法，称为嵌套控制结构。

考虑下列问题：

的名单，每个姓名后面写1时表示考试通过，写2时表示没有通过。

程序应分析考试结果，如下所示：

2．计算每种类型的考试成绩数。

3．显示总成绩，表示及格人数和不及格人数。

认真分析上述问题后，我们做出下列结论：

1．程序要处理10个考试成绩，用计数器控制循环。

2．每个考试成绩为数字l或2，每次程序读取考试成绩时，程序要确定成绩是否为数字1或2。

我们的算法中测试1，如果不是l，则我们假设其为2(本章末尾的练习会考虑这个假设的结果)。

3，使用两个计数器，分别计算及格人数和不及格人数。

4．程序处理所有结果之后，要确定是否有超过8个学生及格。

下面进行自上而下逐步完善的过程。首先是上层的伪代码表示：

    Analyze exam results and decide if tuition should be raised

我们再次强调，顶层是程序的完整表达，但通常要先进行几次完善之后才能将伪代码自然演变成C++程序。我们的第一步完善为：

Initialize variables
    lnput the ten quiz qrades and COU~t passes and failures
    Print a sugary Of the cxam results and decide if tuition should be raised

这里虽然有整个程序的完整表达式，但还需要进一步完善。我们要提供特定变量。要用两个计数器分别计算，用一个计数器控制循环过程，用一个变量保存用户输入。伪代码语句：

        Initialize variables

可以细分如下：

Initialize passes to zero
    lnitialize failules to  zero
Inltiallze student  counter to  One

注意．这里只初始化计数器和总和。伪代码语句：

  Input the ten quiz grades and count Passes and faiLures

要求循环输入每个考试成绩。我们事先知道共有10个成绩，因此可以用计数器控制循环。在循环中(即嵌套在循环中)，用一个双项选择结构确定考试成绩为数字1或2，并递增相应的计数器。上述伪代码语句细化如下：

Initialize passes to zero
    lnitialize failules to  zero
Inltiallze student  counter to  One

注意这里用空行分开if/else控制结构，以提高程序可读性。伪代码语句：

Print a sugary Of the exam results and declde if tuition should be raised

可以细化如下：

  Print the number of passes
    Print the number of filuies
    if more than eight students Passed
    Priht "Raise tuition"

图2.10显示了完整的第2步完善结果。注意这里用空行分开while结构，以提高程序可读性。

    Initlalize passes to zero
    Init±a1ize failures to zero
    lnitlallze student counter to one
    while student counter is less than or equal to ten
    Input the next exam result
    if the student Passed
    Add one to passes
    else
    Add one to failures
    Add one to student  counter
    Priht the number of passes
    Prirt the number of filures
    if more than eight students passed
    Print”Raise tuition'’

图2.10检查考试成绩的伪代码

这个伪代码语句已经足以转换为C++程序。图2.11显示了C++程序及示例的执行结果。注意，

我们利用C++的一个特性，可以在声明中进行变量初始化。循环程序可能在每次循环开头要求初始

化，这种初始化通常在赋值语句中进行。

// Fig. 2.11: fig02_ll.cpp
#include <iostream.h>
int main()
{
	// initialize variables in declarations
	int passes = 0,      // number of passes
	Passes = v;   // number or passes
	failures = 0,       // number of failures
	studentCounter = 1,  // student counter
	result;            // oue exam result
	// process 10 students; counter-controlled loop
	while ( studentCounter <= 10 ) {
		cout << "Enter result (1=pass,2=fail): ";
		cin >> result;
		if { result == 1 }      // if/else nested in while
			passes = passes + 1;
			else
				failures = failures + 1;
				studentcounter = studentCounter + 1;
				)
				// termination phase
				cout << "Failed" << failures << endl;
				if ( passes > 8 )
					cout << "Raise tuition "<< endl;
					return 0;  // successful termination

输出结果：

    Enter result (l=pass,2=fail}: 1
    Enter result (l=pass,2=fail): 2
    Enter result (l=pass,2=fail): 1
    Enter result (l=pass,2=fail): 1
    Enter result (l=pass,2=fail): 1
    Enter result (l=pass,2=fail)  1
    Enter result (l=pass,2=fail): 2
    Enter result {l=pass,2=fail): 1
    Enter result (l=pass,2=fail): 1
    Enter result )1=pass,2=fail): 2
    Passed 6
    Failed 4

    Enter result (a=pass,2=Fail): 1
    Enter result (l=pass,2=fail): 1
    Enter result (l=pass,2=fail)  1
    Enter result (1-pass,2=fail): 2
    Enter result {l=pass,2=fail): 1
    Enter result (l=pass,2=fail): 1
    Enter result {1=Pass,2=fail)：1
    Enter result(1=pass，2=fail)：1
    Enter result(1=pass，2=fail)：1
    Enter result(1=pass，2=fail)：1
    Passed 9
    Failed 1
    Raise tuition

图2.11 检查考试成绩的C++程序及示例执行结果

编程技巧2.13

在声明中进行变量初初化可以帮助程序员避免数据表初始化问题。

软件工程视点2.7

经验表明，计算机问题最难解决的部分是开发解决方案的算法。一旦确定正确算法后，从算法生成C++程序的过程通常是相当简单的。

软件工程视点2.8