第3章选择与迭代

1、计算基础计算基础C+C+语言实现语言实现人类处理问题，都是按照一定的顺序进行的。人们会根据人类处理问题，都是按照一定的顺序进行的。人们会根据所面临的情况的不同，选择不同的处理方法，或者是重复进行所面临的情况的不同，选择不同的处理方法，或者是重复进行同一个处理过程，这些都是在处理问题的过程中可能需要的。同一个处理过程，这些都是在处理问题的过程中可能需要的。本章介绍选择和迭代思想，以及如何使用本章介绍选择和迭代思想，以及如何使用C+C+实现选择和迭代实现选择和迭代。通过本章的学习，读者能够根据自己的问题，判断出是否应。通过本章的学习，读者能够根据自己的问题，判断出是否应该采用选择或迭代处理方法，能

2、够设计出相应的算法，并且能该采用选择或迭代处理方法，能够设计出相应的算法，并且能够使用够使用C+C+提供的相应语句编写程序实现算法。本章还介绍提供的相应语句编写程序实现算法。本章还介绍C+C+中实现程序流程转移的转向语句，并给出部分应用程序实中实现程序流程转移的转向语句，并给出部分应用程序实例，这些实例涉及程序设计时迭代和二分的基本思想，给读者例，这些实例涉及程序设计时迭代和二分的基本思想，给读者以启发，激发读者利用计算思维解决更多、更复杂的问题的兴以启发，激发读者利用计算思维解决更多、更复杂的问题的兴趣。趣。2在解决一些问题时，人们都是按照一定的顺序进行的。有时，处理过程中的一些步骤需要根据

3、不同的情况进行不同的处理，这种情况就是选择。例如，我国著名数学家华罗庚在推广应用统筹学时举的一个鲜活的例子。当需要烧开水喝茶时，喝茶的基本过程可以是下面的任何一种，但花费的时间却是完全不同的: 烧开水取茶和洗茶杯将茶放入茶杯里将开水倒入茶杯喝茶。 取茶和洗茶杯烧开水将茶放入茶杯里将开水倒入茶杯喝茶。显然，第一个过程花费的时间更少，由于在“烧开水”的同时可以“取茶和洗茶杯”，体现了并行处理的思想。3.1 3.1 选择选择3u 3.1.1 3.1.1 单单路选择问题路选择问题单路选择问题是如果某种情况发生，就进行相应的处理，否则不需要做任何处理。例如，天黑了，如果房间里的灯是关着的就将灯打开。 1

4、. 1. 单路选择问题实例单路选择问题实例【例3-1】求一个实数的绝对值问题。问题求解问题求解思路思路: : 变量x是用户输入的实数值，如果x=0时，x的值就是其绝对值，不需要做任何处理。解决该问题需要3个步骤，其中，第2步需要根据x的值选择进行处理或不进行处理。解决该问题的算法如下表所示。3.1 3.1 选择选择4【例3-2】下表是2011最新个人所得税税率表（表中的全月应纳税所得额是指以每月收入额减除费用3500元后的余额），需要解决的问题是计算工资和薪金总额应缴纳的个人所得税。步骤步骤处处 理理1输入x的值2如果x0 且 income1500 且 income4500 且 income9

5、000 且 income35000 且 income55000 且 income80000tax=income*0.45-13505;3输出tax的计算结果3.1 3.1 选择选择62 2. . 用用C+C+提供的提供的ifif语句编程解决单路选择问题语句编程解决单路选择问题对于需要进行单路选择处理的问题，C+提供了相应的if语句，用户可以使用该语句编写程序，让计算机完成问题的求解。if语句的语法格式为: if (if () ifif语句的执行过程是语句的执行过程是: : 首先计算的值，如果其值为true（非0），表示满足某种条件，执行；否则，表示不满足某种条件，不执行而直接执行分支语句后面的

6、语句。If语句的流程图见下页。if语句中的不能缺少，它可以是任意类型的表达式。3.1 3.1 选择选择73.1 3.1 选择选择8【例3-3】根据表3-1给出的算法，编写程序，用C+提供的if语句实现求一个实数的绝对值问题。# #includeinclude using namespace std;using namespace std;intint main() main() double x;double x;coutcout请输入请输入1 1个实数个实数:x;x;ifif(x0(x0) )/当当x x是负数时，需要进行处理是负数时，需要进行处理x=-x;x=-x;coutcoutxx的绝

7、对值是的绝对值是:x:xendlendl; ;return 0;return 0; 请思考：请思考：例3-3中if语句的条件表达式是哪个？例3-3中if语句的分支语句是哪个？例3-3中共有多少条语句？3.1 3.1 选择选择9【例3-4】根据表3-3给出的算法，编写程序，用C+提供的if语句实现求个人所得税问题。int main()int main() double income, tax; double income, tax; coutcout请输入工资总额：请输入工资总额：endl;income;cinincome;income=income-3500;income=income-350

8、0;/计算应纳税所得额计算应纳税所得额ifif (income0 & income0 & income1500 & income1500 & income80000 (income80000) ) taxtax=income=income* *0.45-13505;0.45-13505;coutincome+3500coutincome+3500元收入，应该上税：元收入，应该上税：taxtax元元endl;0&a!=0c0&a!=0步骤处 理1输入一元二次方程，即输入系数a，b，c2如果该方程有两个不相等的实根： 计算这两个实根并输出否则 输出“

9、此方程无两个不相等的实根”3.1 3.1 选择选择142. 2. 用用C+C+提供的提供的ifelseifelse语句编程解决双路选择问题语句编程解决双路选择问题对于需要进行双路选择处理的问题，C+提供了相应的ifelse语句，用户可以使用该语句编写程序，让计算机完成问题的求解。ifelse语句的语法格式为: if(if() elseelse 2 3.1 3.1 选择选择15ifelseifelse语句的执行过程是语句的执行过程是: : 首先计算的值，如果其值为“真”（非0），表示满足测试条件，执行;否则,执行。下图是ifelse语句的流程图3.1 3.1 选择选择16【例3-7】根据表3-4

10、给出的算法，编写程序，用C+提供的ifelse语句实现判断用户输入的年份是否为闰年的问题。int main()int main() int year;int year;bool isLeapYear;bool isLeapYear;coutcout请输入一个年数：请输入一个年数：endl;year;cinyear;isLeapYear=isLeapYear=(year % 4 = 0 & (year % 4 = 0 & year%100 year%100 != 0!= 0)|(year%400 )|(year%400 =0);=0);ifif(isLeapYear)(isLea

11、pYear)coutyearcoutyear年是闰年！年是闰年！endl;endl;elseelsecoutyearcoutyear年不是闰年！年不是闰年！endl;endl;return 0;return 0; 3.1 3.1 选择选择17【例3-8】根据表3-5给出的算法，编写程序，用C+提供的ifelse语句实现“求解一元二次方程ax2+bx+c=0的两个不相等的实根”问题。int main()int main() int a,b,cint a,b,c; ; double double x1,x2;x1,x2;coutcout请输入一元二次方程的系数：请输入一元二次方程的系数：endl;

12、abc;cinabc;ifif (b (b* *b-4b-4* *a a* *c c00&a!=0)&a!=0) x1=(-b+sqrt(bx1=(-b+sqrt(b* *b-4.0b-4.0* *a a* *c)/(2c)/(2* *a);a);x2=(-b-sqrt(bx2=(-b-sqrt(b* *b-4.0b-4.0* *a a* *c)/(2c)/(2* *a);a);coutcout方程的两个实数根分别是：方程的两个实数根分别是：x1x1和和x2endl;x2endl; elseelse coutcout此方程无两个不相等的实根此方程无两个不相等的实根endl;en

13、dl;return 0return 0;3.1 3.1 选择选择18u 3.1.3 3.1.3 嵌套嵌套选择选择问题问题在根据某种情况选择了一种处理后，在进行该处理时，还需要根据情况进行选择，这就构成了选择的嵌套，这样的问题就是嵌套选择问题。【例3-9】找出3个人中年龄最小的那个人。要求给出寻找过程。问题求解思路问题求解思路: : 假设3个人的年龄分别是age1、age2、age3，首先比较age1和age2，找出第1和第2个人中年龄较小的那个人；然后再用这个人的年龄与第3个人的年龄age3进行比较，根据比较结果，找出年龄最小的那个人。由于第一次的比较结果决定第二次哪两个年龄进行比较，第二次的

14、比较结果决定最后是谁最小，所以，这样的问题就是嵌套选择问题。解决该问题的算法如下表所示。3.1 3.1 选择选择19步骤步骤处处 理理1输入三个人的年龄，分别放到age1、age2和age3中2输出“现在开始比较第1个人和第2个人的年龄”的信息3如果age1小于age2 输出“前两个人中第1个人较年轻，下面比较第1个人和第3个人的年龄”的信息如果age1小于age3则找到了年龄最小的人是第1个人，输出“第1个人年龄最小”的信息否则则找到了年龄最小的人是第3个人，输出“第3个人年龄最小”的信息否则 输出“前两个人中第2个人较年轻，下面比较第2个人和第3个人的年龄”的信息如果age2小于age3则

15、找到了年龄最小的人是第2个人，输出“第2个人年龄最小”的信息否则则找到了年龄最小的人是第3个人，输出“第3个人年龄最小”的信息3.1 3.1 选择选择20用C+提供的if或ifelse语句，就能够解决嵌套的问题。根据表3-6对算法的描述发现，第一次（即外层）选择是一个双路选择，使用ifelse语句即可解决。对于外层选择后的进一步处理也是一个双路选择，所以继续使用ifelse语句来解决内层选择问题。3.1 3.1 选择选择21int main()int main() int age1, age2, age3;int age1, age2, age3;coutcout请分别输入请分别输入3 3个人

16、的年龄：个人的年龄：endl;age1age2age3;cinage1age2age3;if(age1age2)if(age1age2)/外层外层ifif coutcout前两个人中第前两个人中第1 1个人较年轻个人较年轻endlendl下面比较第下面比较第1 1个人和第个人和第3 3个人的年龄个人的年龄endl;endl;if(age1age3)if(age1age3)/内层内层ififcoutcout第第1 1个人年龄最小个人年龄最小endl;endl;elseelse/内层内层elseelsecoutcout第第3 3个人年龄最小个人年龄最小endl;endl; 3.1 3.1 选择选择

17、22elseelse/外层外层elseelse coutcout前两个人中第前两个人中第2 2个人较年轻：个人较年轻：endlendl下面比较第下面比较第2 2个人和第个人和第3 3个人的年龄个人的年龄endl;endl;if(age2age3if(age2age3) )/内层内层ififcoutcout第第2 2个人年龄最小个人年龄最小endl;endl;elseelse/内层内层elseelsecoutcout第第3 3个人年龄最小个人年龄最小endl;endl; return 0;return 0; 3.1 3.1 选择选择23u 3.1.4 3.1.4 多多路选择问题路选择问题多路选择

18、问题也是根据不同的情况进行不同的处理。双路选择问题是多路选择问题中可能出现两种情况的一类问题。实际上，有的问题存在的情况会超过两种，这类问题就是多路选择问题。对于多路选择问题，可以直接使用C+提供的if或ifelse语句，通过多次判断来完成问题的求解。C+还提供了一个专门处理多路选择的switch语句，感兴趣和有需要的读者可参考3.3.1节和其他相关资料。3.1 3.1 选择选择24很多计算问题需要重复一组特殊的计算步骤，直到达到某一状态才停止。例如，设计一种计算15的累加和的算法。简单的算法可以是: 第1步: 将总和sum清0；第2步: 将1累加到sum中；第3步: 将2累加到sum中；第4

19、步: 将3累加到sum中；第5步: 将4累加到sum中；第6步: 将5累加到sum中；第12步: 输出15的累加和sum。这个算法很简单。如果如果问题变成设计一种计算问题变成设计一种计算1 1100000100000的累的累加和的算法，则需要加和的算法，则需要100000100000行类似行类似“将将1 1累加到累加到sumsum中中”的操作，依的操作，依此类推。显然，这种算法在处理大规模问题时是不可行的。此类推。显然，这种算法在处理大规模问题时是不可行的。3.2 3.2 迭代迭代25u 3.2.1 3.2.1 迭代迭代算法算法使用计算思维中经常使用的迭代思想，设计出迭代算法，可以将算法中重复

20、步骤简要、清楚地描述出来，使算法变短因而增加其可读性。设计迭代算法，首先要确定需要重复的操作或操作集合，然后确定需要进行多少次这样的循环。对于上面的问题，可设计一个非常短的迭代算法: 第1步: 将总和sum清0;第2步: i的取值范围是15，将i累加到sum中;第3步: 输出15的累加和sum。如果问题变为“设计一种计算1100000的累加和的算法”时，仅需将上面迭代算法的第2步“i的取值范围是15”修改为“i的取值范围是1100000”即可。3.2 3.2 迭代迭代26【例3-10】设计“计算1+2+3+n”的迭代算法。问题求解思路问题求解思路: : 可以发现该问题需要重复的操作是将一个整数

21、累加，这个操作需要重复n次。所以，解决该问题的迭代算法如下表所示。3.2 3.2 迭代迭代步骤步骤处处 理理1输入用户要累加的最大整数n2将存放累加和的sum清03i的取值范围是1到n，进行如下操作： 将i累加到sum中4输出结果27【例3-11】设计“计算2n”的迭代算法。问题求解思路问题求解思路: : 可以发现该问题需要重复的操作是乘2，这个操作需要重复n次。所以，解决该问题的迭代算法如下表所示。3.2 3.2 迭代迭代步骤步骤处处 理理1输入2的幂次n2将存放结果的power置为13重复n次下面的操作： power=power24输出结果28u 3.2.2 3.2.2 用用C+C+提供的

22、循环语句实现迭代算法提供的循环语句实现迭代算法几乎所有的程序设计语言都有实现迭代算法的循环语句。所以，可以使用这些循环语句来实现一个语句（或一组语句）的重复处理，直到某个条件满足才停止。1. 1. 用用C+C+提供的提供的forfor语句实现迭代语句实现迭代算法算法C+提供了专门用于循环的for语句。for语句的语法格式为:for for ( ( ; ; ; ; ) 3 ) 3.2 3.2 迭代迭代29forfor语句的执行过程是语句的执行过程是：首先执行，然后执行。当的值为“真”（非0），执行。每执行完后，执行，再执行，当的值为“真”（非0）则重复执行循环体，再执行重复上述过程，直到等于“假

23、”（0）为止。for语句中的的主要作用是初始化循环变量；的主要作用是控制循环；的主要作用是修改循环变量。3.2 3.2 迭代迭代30【例3-12】根据表3-7给出的迭代算法，编写程序，用C+提供的for语句实现“计算1+2+3+n”的问题。int int main()main() int int n,sum;n,sum;coutcout请输入要累加的最大整数：请输入要累加的最大整数：endl;n;n;sumsum=0;=0;forfor(int i=1; i=n; i+)(int i=1; i=n; i+)sum=sum+i;sum=sum+i;coutcout1+2+31+2+3+n n的结

24、果为：的结果为：sumendl;sumendl;return return 0;0; 3.2 3.2 迭代迭代312. 2. 用用C+C+提供的提供的whilewhile语句实现迭代算法语句实现迭代算法C+提供了专门用于循环的while语句。while语句的语法格式为: while (while () ) 3.2 3.2 迭代迭代whilewhile语句的执行过程是：语句的执行过程是：首先计算的值，如果其值为“真”（非0），表示满足循环条件，则执行；如果其值为“假”（0），则结束循环每执行完一次循环体后再次计算的值，如果其值为“真”（非0），则继续执行；如果其值为“假”（0），则结束循环。右侧

25、是while语句流程图。32【例3-13】根据表3-8给出的迭代算法，编写程序，用C+提供的while语句实现“计算2n”的问题。intint main()main() int i,n,power;int i,n,power;coutcout请输入幂次：请输入幂次：endl;n;n;power=1power=1; ;i i=1=1; ;while while (i=n)(i=n) power=powerpower=power* *2;2;i+;i+; coutcout22的的n n次幂为：次幂为：powerendl;power0 income0 并且并且 income=1500 income1

26、500 income1500 并且并且 income=4500 income4500 income4500 并且并且 income=9000 income9000 income9000 并且并且 income=35000 income35000 income35000 并且并且 income=55000 income55000 income55000 并且并且 income=80000 income80000income80000 tax=income tax=income* *0.45-135050.45-13505; ; 输出输出taxtax的计算结果的计算结果 输入输入下一个工资总额下一

27、个工资总额incomeincome35int int main()main() double income, tax; double income, tax; coutcout请输入工资总额（输入请输入工资总额（输入0 0结束程序）：结束程序）：endl;income;cinincome;while (income!=0)while (income!=0) tax=0;tax=0;income=income-3500;income=income-3500;/计算应纳税所得额计算应纳税所得额if (income0 & income0 & income1500 & income1500 & income=4500)tax=incometax=income* *0.1-1050.1-105; ;coutcoutincome+3500income+3500元收入，应该上税：元收入，应该上税：taxtax元元endl;endl;coutcout请输入下一个工资总额（输入请输入下一个工资总额（输入0 0结束程序）：结束程序）：endl;income;cinincome;/输入输入 return 0;return 0; 36u 3.2.4 3.2.4 迭代嵌套迭代嵌套在一个迭代算法，重复处理的每一步还是一个迭代算法，这就构成了迭代嵌套。使