2.2 课后习题详解
1什么是算法？试从日常生活中找3个例子，描述它们的算法。
答：为解决一个问题而采取的方法和步骤，就称为“算法”。
例1，从上海去北京：先要预定车票、然后去车站乘车、抵达目的地后下车；
例2，喝茶：先准备好茶叶、再烧一壶开水、然后将茶叶放入杯中、倒入开水、等待茶叶泡好；
例3，开车：先要打开车门、驾驶员坐好、插上车钥匙、发动汽车。
2什么叫结构化的算法？为什么要提倡结构化的算法？
答：结构化算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本的结构范围内。一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变。跟结构化算法比较起来，非结构化算法有以下缺点：流程不受限制的随意转来转去，使流程图毫无规律，使人在阅读的时候难以理解算法的逻辑，难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。
3试述3种基本结构的特点，请另外设计两种基本结构（要符合基本结构的特点）。
答：3种基本结构的特点：
①只有一个入口。
②只有一个出口。
③结构内的每一部分都有机会被执行到。即对每一个框来说，都应当有一条从入口到出口的路径通过它。
④结构内不存在“死循环”。
另外两种基本结构如图2-13所示。
图2-13 另外两种基本结构图
4用传统流程图表示求解以下问题的算法。
（1）有两个瓶子A和B，分别盛放醋和酱油，要求将它们互换（即A瓶原来盛醋，现改盛酱油，B瓶则相反）。
答：显然，如果只有两个瓶子，肯定不能完成此任务，必须有一个空瓶C作为过渡，A瓶与B瓶互换的流程图如图2-14。
图2-14 A瓶与B瓶互换流程图
（2）依次将10个数输入，要求输出其中最大的数。
答：求解10个数中最大数的流程图如图2-15所示。
图2-15 求解10个数中最大数的流程图
（3）有3个数a，b，c，要求按大小顺序把它们输出。
答：将3个数大小输出的流程图如图2-16所示。
图2-16 3个数大小输出的流程图
（4）求1＋2＋3＋…＋100。
答：求1＋2＋3＋…＋100的流程图如图2-17所示。
图2-17 1到100累加的流程图
（5）判断一个数n能否同时被3和5整除。
答：判断一个数n能否同时被3和5整除的流程图如图2-18所示。
图2-18 判断一个数能否被3和5整除的两种流程图
（6）将100～200之间的素数输出。
答：输出100～200之间素数的流程图如图2-19所示。
图2-19 找出100～200之间素数的流程图
（7）求两个数m和n的最大公约数。
答：求两个数m和n最大公约数的流程图如图2-20所示。
图2-20 求两个数最大公约数的流程图
（8）求方程式ax2＋bx＋c＝0的根。分别考虑：
①有两个不等的实根；
②有两个相等的实根。
答：求方程式ax2＋bx＋c＝0根的流程图如图2-21所示。
图2-21 求一元二次方程根的流程图
5用N-S图表示第4题中各题的算法。
答：（1）A瓶与B瓶互换的N-S流程图如图2-22所示。
图2-22 A瓶与B瓶互换的N-S流程图
（2）求解10个数中最大数的N-S流程图如图2-23所示。
图2-23 求解10个数中最大数的N-S流程图
（3）将3个数大小输出的N-S流程图如图2-24。
图2-24 将3个数大小输出的N-S流程图
（4）求1＋2＋3＋…＋100的N-S流程图如图2-25所示。
图2-25 求1＋2＋3＋…＋100的N-S流程图
（5）判断一个数n能否同时被3和5整除的N-S流程图如图2-26所示。
图2-26 判断一个数n能否同时被3和5整除的N-S流程图
（6）输出100～200之间素数的流程图如图2-27所示。
图2-27 输出100～200之间素数的N-S流程图
（7）求两个数m和n最大公约数的流程图如图2-28所示。
图2-28 求两个数m和n最大公约数的N-S流程图
（8）求方程式ax2＋bx＋c＝0根的流程图如图2-29所示。
图2-29 求一元二次方程根的N-S流程图
6用伪代码表示第4题中各题的算法。
答：（1）A瓶与B瓶互换的伪代码为：
c=a
a=b
b=c
（2）求解10个数中最大数的伪代码为：
n=1
input max
while n<10 do
input a
if a>max then max=a
n=n+1
end do
print max
（3）将3个数大小输出的伪代码为：
input a,b,c
if a<b then swap a,b
if a<c then
print c,a,b
else
if c>b then
print a,c,b
else
print a,b,c
end if
end if
（4）求1＋2＋3＋…＋100的伪代码为：
sum=0
n=1
while n<=100 do
sum=sum+n
n=n+1
end do
print sum
（5）判断一个数n能否同时被3和5整除的伪代码为：
input n
flag=0
if mod(n,3)≠0 then flag=-1
if mod(n,5)≠0 then flag=-1
if flag=0 then
print n "能被3和5整除"
else
print n "不能被3和5整除"
end if
（6）输出100～200之间素数的伪代码为：
n=100
while n<=200 do
i=2
while i<=sqrt(n)
if mod(n,i)=0 then
i=n
else
i=i+1
end if
end do
if i<sqrt(n) then print n
n=m+1
end do
（7）求两个数m和n最大公约数的伪代码为：
input m,n
if m<n then swap m,n
t=mod(m,n)
while r≠0 do
m=n
n=r
r=mod(m,n)
end do
print n
（8）求方程式ax2＋bx＋c＝0根的伪代码为：
int a,b,c
disc=b^2-4ac
if disc>=0 then
if disc=0 then
x1,x2=-b/(2a)
else
x1=(-b+sqrt(disc))/(2a)
x2=(-b-sqrt(disc))/(2a)
end if
print x1,x2
else
p=-b/(2a)
q= sqrt(disc)/(2a)
print p+q,"+","i"
end if
7什么叫结构化程序设计？它的主要内容是什么？
答：结构化程序设计的概念最早由E.W.Dijikstra在1965年提出的，是软件发展的一个重要的里程碑。它的主要观点是采用自顶向下、逐步求精及模块化的程序设计方法；使用三种基本控制结构构造程序，任何程序都可由顺序、选择、循环三种基本控制结构构造。结构化程序设计主要强调的是程序的易读性。
8用自顶向下、逐步细化的方法进行以下算法的设计：
（1）输出1900～2000年中是闰年的年份，符合下面两个条件之一的年份是闰年：
①能被4整除但不能被100整除；
②能被100整除且能被400整除。
答：先画出图2-30（a），对它细化得图2-30（b）；对图2-30（b）中的S1.1细化得图2-30（c）。
图2-30 输出1900～2000中闰年的流程图
（2）求ax2＋bx＋c＝0的根。分别考虑d＝b2－4ac大于0、等于0和小于0这3种情况。
答：先画出图2-31（a），对其中的S3细化为图2-31（b）；对图2-31（b）中的S3.1细化为图2-31（c）；对图2-31（c）中的S3.1.1细化为图2-31（d）；对图2-31（c）中的S3.1.2细化为2-31（e），对图2-31（b）中S3.2细化为图2-31（f）。
图2-31 求ax2＋bx＋c＝0根的流程图
（3）输入10个数，输出其中最大的一个数。
答：先初步画出图2-32（a），考虑到还没有学习数组的知识，因而不能做到将10个数全部输入给数组中各个元素，然后再从中找到最大者。由于不采用数组这种数据结构，算法也应与采用数组时有所不同，现在只用普通变量，逐个读入数据，将当时各数中的最大者保留下来存放在max中，以便再与后面读入的数比较。将图2-32（a）细化为图2-32（b），再细化为图2-32（c）。
图2-32 求解输入10个数中最大数的流程图