循环结构
使用循环结构的程序可以解决一些按一定规则重复执行的问题而无须重复书写源代码，这是程序设计中最能发挥计算机特长的程序结构。首先介绍while语句。
while语句是用来实现“当型”循环结构，其一般形式如下：
while(表达式成立)
执行一条语句;或者是：
while(表达式成立)
{
语句1；
语句2；
...
}
即当表达式的值为真时，执行while语句中的内嵌语句。
例如，求1+2+3+…+100的值的程序可以这样写：
1 //计算1+2+3+…+100的值
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int i=1,sum=0;
8 while(i<=100) //当i<=100时，则执行循环体内的语句
9 {
10 sum=sum+i;
11 i++;
12 }
13 cout<<sum<<endl;
14 system("pause");
15 return 0;
16 }
【上机实践】 计算15的阶乘
试计算1×2×3×4×…×15的值。
【例题描述】 电文保密
魔法世界电报局的电文保密的规律是将每个英文字母变成其后的第4个字母，如A变成E，a变成e。最后的4个大写字母W、X、Y、Z分别变为A、B、C、D。非字母字符不变。输入一行字符，要求输出相应的密码。
1 //电文保密
2 #include <iostream>
3 #include <math.h>
4 using namespace std;
5
6 int main()
7 {
8 char c;
9 while((c=getchar())!='＼n')
10 {
11 if((c>='a' && c<='z') || (c>='A' && c<='Z')) //当字符为英文字母时
12 {
13 c=c+4;
14 if(c>'Z' && c<='Z'+4 || c>'z')
15 c=c-26;
16 }
17 cout<<c;
18 }
19 system("pause");
20 return 0;
21 }
第9行的语句并不是从终端敲入一个字符马上输出一个字符。而是直到按Enter键后将所有字符送入内存缓冲区，然后每次从缓冲区读一个字符，再输出该字符。
【例题描述】 求魔法力
每个魔法学徒的魔法力是不同的，试编写一个程序，从键盘读入每个学徒的魔法力，求全部魔法学徒的魔法力总和。当用户输入0时，程序结束。
1 //求魔法力
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int sum=0,n;〖BHDG1*4〗
8 while(true) //表示永远为真，即永远循环，也可以用while(1)
9 {
10 cout<<"输入一个整数(0表示结束)";
11 cin>>n;
12 if(n==0)
13 break;//跳出该层循环
14 sum+=n;
15 }
16 cout<<"总和为： "<<sum<<endl;
17 system("pause");
18 return 0;
19 }
【上机实践】 火柴游戏
魔法学院流行一种火柴游戏，即21根火柴，两人轮流取，每人可取1~4根，不可多取，也不可不取，谁取最后一根谁输，假设楚继光先取，张琪曼后取，如何编程让张琪曼赢。
这是一道简单的博弈题，取胜策略：只需让后方取火柴的数量与前方取火柴数量之和等于5即可。
1 设变量num=21，即火柴数
2 设变量man表示楚继光，可设另一个变量表示张琪曼，也可以不设
3 当火柴未取完时
4 {
5 屏幕输出现在的火柴数
6 输入这一次楚继光取的火柴数即变量man
7 如果楚继光取的火柴数违反规定
8 coutinue; //无效重取，即本次循环无效，继续下轮循环
9 否则输出张琪曼取的火柴数(即5-man)和剩余的火柴数(即num-5)
10 更新现在的火柴数即num=num-5
11 }
12 屏幕输出"你输了! "
【上机实践】 整数猜想
魔法世界的魔法师们相信“万法归一”的说法，即天下所有的学问，到了最后都是相通的。令人惊讶的是，居然有魔法师宣称从数学角度证明了该说法的正确性，这就是所谓的整数猜想：即对于任意给定的大于1的一个正整数，如果它是一个偶数请将其除以2，若是奇数就将其乘以3加1，对其运算结果，如果它不是1，则重复上述操作经过。经过若干步操作后，总会得到结果1。
对于这道题，由于事先无法知道要经过多少步才能得到结果1。所以用while是比较合适的。剩下的就简单了，模拟运算即可。
伪代码如下所示：
1 输入任一大于1的正整数i
2 当(i>1)时
3 {
4 如果i为偶数时
5 i=i/2
6 否则
7 i=i*3+1
8 输出更新后的i值
9 }
【上机实践】 求圆周率
圆周率，一般以π来表示，是一个在数学及物理学普遍存在的数学常数。它定义为圆形之周长与直径之比。如图2.5所示，早在远古时代的中国，有一位叫祖冲之的数学家第一次将圆周率（π）值计算到小数点后七位，即3.1415926到3.1415927之间。而魔法世界的魔法师对于圆周率的精确度相求是相当高的，例如用35位精度的圆周率值来计算一个能把太阳系包起来的一个圆的周长，误差还不到质子直径的百万分之一。
图2.5
现用π/4=1-1/3+1/5-1/7+…公式求π的近似值，直到某一项的绝对值小于10-6为止。
由公式π/4=1-1/3+1/5-1/7+…可推出π=（1-1/3+1/5-1/7+…）×4，问题是（1-1/3+1/5-1/7+…）的值怎么算呢？
设变量ans为最终结果，初始值0，使用while（）循环进行逐项累加直到某一项的绝对值小于10-6为止。
但是累加每一项的时候，分母在不断地递增（每次多2），所以需要定义一个变量来保存分母的值，此外每一项的正负号也在不断变换，这可能也需要一个变量来表示，例如x=-x即可完成正负号的转变。
伪代码如下所示：
1 float n=1.0 //n表示分母，初始为1
2 float t=1,ans=0 //t为循环中要加的每一项
3
4 则当(t的绝对值>1e-6)时 //1e-6即1乘以10的-6次方
5 {
6 ans=ans+t//累加
7 更新分母的值
8 改变正负号
9 更新t的值
10 }
11 输出ans*4的值
【上机实践】 求最大公约数和最小公倍数
输入两个正整数a和b，求其最大公约数和最小公倍数。
我们使用辗转相除法（欧几里得算法）来求最大公约数，即将大的数a除以小的数b，得余数c，a=b，b=c，如此反复直到余数为0，此时的b为最大公约数。
例如a=24，b=10，则c=24%10＝4，
由a=b，b=c得a=10，b=4，则c=10%4=2
由a=b，b=c得a=4，b=2，则c=4%2=0，故最大公约数为b=2。
最小公倍数公式为初始数a×初始数b/最大公约数。
伪代码如下所示：
1 输入a,b的值
2 如果a<b
3 交换a和b的值
4 当(b!=0)
5 {
6 c=a%b
7 a=b
8 b=c
9 }
10 输出最大公约数
11 输出最小公倍数
【上机实践】 求Sn的值
光明系魔法的魔法力增长值遵循Sn=a+aa+aaa+aaaa+…的公式，其中a是一个数字。例如某学徒初始魔法力为3，则4年后的魔法力为3+33+333+3333，试求n年后该学徒的魔法力Sn，其中a，n由键盘输入。
因为年数n是键盘输入的，所以我们必须控制while结构循环n次后就结束，这可以用一个变量充当计数器，每循环一次，计数器+1，直到计数器>n退出循环即可。
难点是循环中如果更改需累加的项数，即项数由a变为aa，由aa变为aaa…，一个想法是使用a=a×10+a，将a的值扩大10倍后再加上a，当然这可能需要其他变量的辅助完成才行。
【例题描述】 埃及分数
魔法学院院长将家中11匹马分给3个儿子，老大1/2，老二1/4，老三1/6。3个儿子正在无奈之际，邻居把自己家的马牵来，老大二分之一，牵走了6匹；老二四分之一，牵走了3匹；老三六分之一，牵走了2匹。一共11匹，分完后，邻居把自己的马牵了回去。即11/12=1/2+1/4+1/6。这种分子是1的分数，叫作埃及分数，因为古代埃及人在进行分数运算时，只使用分子是1的分数。
现输入一个真分数，请将该分数分解为埃及分数。例如，8/11=1/2+1/5+1/55+1/110。
若真分数a/b中的分子a能整除分母b，则真分数经过化简直接就可以得到埃及分数，否则若真分数的分子不能整除分母，则可以从原来的分数中分解出一个分母c=b/a+1的埃及分数。
分解后剩下的部分形成一个新的a/b，即a=a×c-b，b=b×c。继续用这种方法将剩余部分反复分解，最后可得到结果。
1 //埃及分数
2 #include<iostream>
3 using namespace std;
4
5 int main()
6 {
7 long int a,b,c;
8 cin>>a>>b; //输入分子a和分母b
9 while(1)
10 {
11 if(b%a!=0) //若分子不能整除分母
12 c=b/a+1; //则分解出一个分母为b/a+1的埃及分数
13 else //否则，输出化简后的真分数(埃及分数)
14 {
15 c=b/a;
16 a=1;
17 }
18
19 if(a==1) //若分子已经为1了
20 {
21 cout<<"1/"<<c;
22 break; //则结束
23 }
24 else
25 cout<<"1/"<<c<<"+";
26
27 a=a*c-b; //求出余数的分子
28 b=b*c; //求出余数的分母
29
30 if(a==3) //若余数为3，输出最后两个埃及分数如3/14=1/7+1/14
31 {
32 cout<<"1/"<<b/2<<"+"<<"1/"<<b;
33 break;
34 }
35 }
36 system("pause");
37 return 0;
38 }
do~while语句的特点是先执行循环体，然后判断循环条件是否成立。其一般形式为
do
循环体语句
while(表达式);
例如，求1+2+3+…+100的值的程序我们可以这样写：
1 //计算1+2+3+…+100的值
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int i=1,sum=0;
8 do
9 {
10 sum=sum+i;
11 i++;
12 } while(i<=100);
13 cout<<sum<<endl;
14 system("pause");
15 return 0;
16 }
while与do~while循环的比较是while先判断表达式是否为真，如果为真才执行循环，如果为假则不执行循环。而do~while是先不管表达式的值为何值，先执行循环体内的语句一遍，然后再进行表达式的判断以决定是否继续执行该循环。
注意不要忘了do~while语句结束后的分号。
【例题描述】 菜单程序的实现
如图2.6所示，张琪曼要编写一个小学生算术练习系统，该系统的菜单项包括1．加法；2．减法；3．乘法；4．除法；5．退出。编程实现进入系统后显示菜单，等待用户选择，然后执行相应的功能（设每个子功能暂设置为一个输出结果的功能），执行完毕后返回主菜单，直至选择退出。
图2.6
1 //菜单程序的实现
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int c;
8 int a,b;
9 do
10 {
11 system("cls"); //清屏
12 cout<<"小学生算术练习系统＼n";
13 cout<<" 1.加法＼n";
14 cout<<" 2.减法＼n";
15 cout<<" 3.乘法＼n";
16 cout<<" 4.除法＼n";
17 cout<<" 5.退出＼n";
18 cout<<"请选择(1~5): ";
19 cin>>c;
20 if(c!=5)
21 {
22 cout<<"请输入两个数，以空格间隔";
23 cin>>a>>b;
24 switch(c)
25 {
26 case 1:cout<<a<<"+"<<b<<"="<<a+b<<endl;break;
27 case 2:cout<<a<<"-"<<b<<"="<<a-b<<endl;break;
28 case 3:cout<<a<<"*"<<b<<"="<<a*b<<endl;break;
29 case 4:if(b!=0)
30 cout<<a<<"/"<<b<<"="<<a/b<<endl;
31 else
32 cout<<"除数不能为0！";
33 break;
34 default:cout<<"错误的输入，请重新选择＼n"<<endl;
35 }
36 system("pause");
37 }
38 else
39 {
40 cout<<"练习结束!＼n";
41 break;
42 }
43 }while(1);
44 system("pause");
45 return 0;
46 }
for语句是C++语言里使用最为灵活的语句，它完全可以代替while语句。一般形式如下：
for(循环变量赋初值；循环条件;循环变量增值)
表达式1 表达式2 表达式3
它的执行过程如下：
（1）先求解表达式1。
（2）求解表达式2，若其值为真，则执行for语句的内嵌语句，然后执行下面第（3）步。若为假，则结束循环，转到第（5）步。
（3）求解表达式3。
（4）转回上面第（2）步骤继续执行。
（5）循环结束，执行for语句下面的一个语句。
例如求1+2+3+…+100的值的程序我们可以这样写：
1 //计算1+2+3+…+100的值
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int sum=0,i; //定义循环变量i
8 for(i=1;i<=100;i++) //i赋初值； 循环条件;i每次自增1
9 {
10 sum+=i; //即sum=sum+i
11 }
12 cout<<sum<<endl;
13 system("pause");
14 return 0;
15 }
for语句是很简单和方便的，使用该语句完全可以替代其他的循环语句。
表达式1、2、3可以根据实际情况省略（注意不可省略分号）。但程序设计者应另外设法保证循环能正常结束。以下几个程序和上面的程序结果是一样的。
程序一：
1 //计算1+2+3+…+100的值
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int sum=0,i=1; //此处赋初值
8 for(;i<=100;i++)
9 {
10 sum+=i;//即sum=sum+i
11 }
12 cout<<sum<<endl;
13 system("pause");
14 return 0;
15 }
程序二：
1 //计算1+2+3+…+100的值
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int sum=0,i=1; //此处赋初值
8 for(;i<=100;)
9 {
10 sum+=i; //即sum=sum+i
11 i++; //循环变量递增写在此处
12 }
13 cout<<sum<<endl;
14 system("pause");
15 return 0;
16 }
程序三：
1 //计算1+2+3+…+100的值
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int sum=0,i=1; //此处赋初值
8 for(;;)
9 {
10 if(i>100) //此处进行判断
11 break;
12 sum+=i; //即sum=sum+i
13 i++; //循环变量递增写在此处
14 }
15 cout<<sum<<endl;
16 system("pause");
17 return 0;
18 }
【上机实践】 计算数列和
墨老师在黑板上写了一行字：“试编程计算12+22+32+…+502的和。”然后说：“同学们是不是看到这种题目就很头痛啊？我告诉大家，其实解决这种问题很简单的，吃一片止痛药就好啦。”
可以用for循环语句循环50次累加每一项，用循环变量表示当前计算的项数，求和的每一项为项数的平方。
【例题描述】 显示ASCII码
目前计算机中用得最广泛的字符集及其编码，是由美国国家标准局（ANSI）制定的ASCII码（American Standard Code for Information Interchange，美国标准信息交换码），它已被国际标准化组织（ISO）定为国际标准，称为ISO 646标准。请编写一个程序，显示ASCII码为15~127的字符。
参考程序如下所示：
1 //显示ASCII码
2 #include <iostream>
3 #include <iomanip>
4 using namespace std;
5
6 int main()
7 {
8 int i,n=0;
9 for(i=15;i<128;i++)
10 {
11 if (n%10==0 && n>0)
12 cout<<endl; //每显示十个换一行
13 cout <<setw(4)<<i<<":"<<(char)i<<" ";
14 n++;
15 }
16 cout<<endl;
17 system("pause");
18 return 0;
19 }
【上机实践】 同构数
张琪曼很喜欢研究数字规律。她发现有一些数值平方后会有一种奇怪的现象，她把会出现这种现象的数叫“同构数”。“同构数”是指这样的一种数，会出现在它的平方数的右端的数。例如，5是25右边的数，25是625右边的数，5和25都是同构数。张琪曼觉得这些数并不止一两个，请帮她找出2~10000之间全部同构数。
伪代码为：
1 for循环穷举从2~10000的每一个数i
2 {
3 计算该数的平方数即j
4 依次从后向前比较i和j的位数是否相等
5 {
6 如果i的所有位数比较完毕仍然相等
7 则输出该数i
8 否则
9 跳出进行下一个数的穷举
10 }
11 }
【上机实践】 求e的近似值
e（指自然底数e）与圆周率π被认为是数学中最重要的两个超越数（不满足任何整系数代数方程的数，称超越数）。而且e、π与虚数i三者之间有一个相当有名的关系式：e（iπ）=-1。通常我们可以通过公式e=1+1/1!+1/2!+1/3!+…计算到它前n项或到某一项小于规定值作为近似值。试计算e的值计算到前一百项。
计算阶乘时无须一遍遍地反复算，完全可以利用前一项已算法的值递推出下一项的值，例如当计算出5！后，计算6！即为6×5！。
例如某项值为t=1/n!，则下一项即为t/（n+1）。
伪代码如下所示：
1 定义浮点数ans=1,t=1
2 for(循环一百次)
3 {
4 递推出下一项值t
5 ans+=t //累加
6 }
7 输出ans的值
【例题描述】 兔子永生
修罗王在恐怖的冥域中找到了传说中的不死秘术，为了安全起见，他对一对刚出生的小兔子施展了此秘术，现在假设秘术使得所有的兔子都不死，而兔子在出生两个月后，就有繁殖能力，那么40个月后可以繁殖多少对兔子？
如图2.7所示：
图2.7
第一个月小兔子没有繁殖能力，所以还是一对；
两个月后，生下一对小兔后总数共有两对；
三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对；
……
这就是有名的斐波那契数列（Fibonacci），这个数列有如下特点：第1、2两个数为1、1。从第3个数开始，该数是其前面两个数之和。即：1、1、2、3、5、8、13…
1 //兔子永生
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int f1=1,f2=1,i;
8 for(i=1;i<=20;i++)
9 {
10 cout<<f1<<''<<f2;
11 if(i%2==0) //当一行输出两次f1和f2(即4个数字)的值后另起一行
12 cout<<'＼n';
13 f1=f1+f2;
14 f2=f2+f1;
15 }
16 system("pause");
17 return 0;
18 }
【上机实践】 求分子序列和
有一分子序列：2/1，3/2，5/3，8/5，13/8，21/13，…，求出这个数列的前20项之和。
伪代码为：
1 定义浮点数a=2,b=1,ans=0;//其中a为分子，b为分母
2 for(循环20次)
3 {
4 ans=ans+a/b;
5 更新分子a和分母b的值;
6 }
7 输出ans的值;
【例题描述】 计算圆面积
如图2.8所示，魔法学院计划建设一个圆形广场，试依次计算半径r=1到r=10时的圆面积，直到面积area大于100为止。
图2.8
1 //计算r=1到r=10时的圆面积，直到面积area大于100为止
2 # include <iostream>
3 using namespace std;
4 int main()
5 {
6 float area;int r;
7 for(r=1;r<=10;r++)
8 {
9 area=3.14*r*r;
10 if(area>100)
11 break; //跳出当前循环体，执行循环体下面的语句
12 cout<<r<<":area="<<area<<endl;
13 }
14 system("pause");
15 return 0;
16 }
【例题描述】 不能被3整除的数
与世界上的多数古代文明相同，魔法世界也认为3是一个神圣的数字，所有能被3整除的数字也是神圣的数字，试将100~200之间不能被3整除的数输出。
1 //把100~200之间不能被3整除的数输出
2 #include <iostream>
3 using namespace std;
4 int main()
5 {
6 int n;
7 for(n=100;n<=200;n++)
8 {
9 if(n%3==0)
10 continue; //跳出当前循环体，执行循环体下面的语句
11 cout<<n<<' ';
12 }
13 system("pause");
14 return 0;
15 }
break可以用来从循环体内跳出循环体，即提前结束循环，接着执行循环下面的语句。break语句不能用于循环语句和switch语句之外的任何其他语句中。
continue语句与break语句的区别是：continue语句只结束本次循环，而不是终止整个循环的执行。而break语句则是结束整个循环过程，不再判断执行循环的条件是否成立。
【例题描述】 九九乘法表
九九乘法表又称九九乘法歌诀，在《荀子》、《管子》、《淮南子》、《战国策》等中国古书中就能找到“三九二十七”“六八四十八”“四八三十二”“六六三十六”等句子。试编程输出九九乘法表。
这道题需要两层for循环语句嵌套完成，即：
for(i=1;i<=9;i++) for(j=1;j<=9;j++) cout<<i<<"*"<<j<<"="<<i*j<<' ';
注意两层for循环的循环变量应分别定义，即定义i和j。其运行顺序是执行外循环到内循环时，要先把内循环的所有循环执行完后再跳到外循环。
1 //九九乘法表
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int i,j;
8 for(i=1;i<=9;i++)
9 for(j=1;j<=9;j++)
10 cout<<i<<'*'<<j<<"="<<i*j<<endl;
11 system("pause");
12 return 0;
13 }
【例题描述】 执行任务
魔法学院要在A、B、C、D、E、F六个学员中尽可能多地挑若干人去执行一项任务，但有以下限制条件：
（1）A和B两人中至少去一人；
（2）A和D不能一起去；
（3）A、E和F三人中要派两人去；
（4）B和C都去或都不去；
（5）C和D两人中去一个；
（6）若D不去，则E也不去。
问应当让哪几个人去？
用a、b、c、d、e、f六个变量表示六个人是否去执行任务的状态，变量的值为1，则表示该人去；变量的值为0，则表示该人不参加执行任务，根据题意可写出表达式：
a+b>=1 A和B两人中至少去一人；
a+d!=2 A和D不能一起去；
a+e+f==2 A、E、F三人中要派两人去；
b+c==0或b+c==2 B和C都去或都不去；
c+d==1 C和D两人中去一个；
d+e==0或d==1 若D不去，则E也不去（都不去；或D去E随便）。
上述各表达式之间的关系为“与”关系。穷举每个人去或不去的各种可能情况，代入上述表达式中进行推理运算，使上述表达式均为“真”的情况就是正确的结果。
1 //执行任务
2 #include<iostream>
3 using namespace std;
4
5 int main()
6 {
7 int a,b,c,d,e,f;
8 for(a=1;a>=0;a--)/ /穷举每个人是否去的所有情况
9 for(b=1;b>=0;b--) //1:去 0:不去
10 for(c=1;c>=0;c--)
11 for(d=1;d>=0;d--)
12 for(e=1;e>=0;e--)
13 for(f=1;f>=0;f--)
14 if(a+b>=1&&a+d!=2&&a+e+f==2&&
15 (b+c==0||b+c==2)&&c+d==1&&(d+e==0||d==1))
16 {
17 cout<<"a:"<<a<<endl;
18 cout<<"b:"<<b<<endl;
19 cout<<"c:"<<c<<endl;
20 cout<<"d:"<<d<<endl;
21 cout<<"e:"<<e<<endl;
22 cout<<"f:"<<f<<endl;
23 }
24 system("pause");
25 return 0;
26 }
【例题描述】 打印三角形
使用循环结构打印如下图形：
*
***
*****
*******
参考程序如下所示：
1 //打印三角形
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 for(int i=1;i<=4;i++) //输出行数
8 {
9 for(int j=1;j<=4-i;j++) //控制每行输出的空格数
10 cout<<' ';
11 for(int j=1;j<=2*i-1;j++) //控制每行输出的*的个数
12 cout<<'*';
13 cout<<endl;
14 }
15 system("pause");
16 return 0;
17 }
【上机实践】 打印菱形
使用循环结构打印如下图形：
*
***
*****
*******
*****
***
*
请完善下面的程序：
1 //打印菱形
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 for(int i=-3;i<=3;i++) //输出行数
8 {
9 int k=abs(i);
10 for(_____) //控制输出每行空格数
11 cout<<' ';
12 for(_____) //控制输出每行*号数
13 cout<<'*';
14 cout<<endl;
15 }
16 system("pause");
17 return 0;
18 }
【上机实践】 打印数字菱形1
使用循环结构打印如下图形：
4
333
22222
1111111
22222
333
4
请完善下面的程序：
1 //打印数字菱形1
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 for(int i=-3;i<=3;i++) //控制输出行数
8 {
9 int k=abs(i);
10 for(_____) //控制输出每行的空格数
11 cout<<' ';
12 for(_____) //控制输出的数字
13 cout<<k+1;
14 cout<<endl;
15 }
16 system("pause");
17 return 0;
18 }
【上机实践】 打印数字菱形2
使用循环结构打印如下图形：
1
212
32123
4321234
32123
212
1
参考程序如下所示：
1 //打印数字菱形2
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 for(int i=-3;i<=3;i++) //控制输出的行数
8 {
9 int k=abs(i);
10 for(_____) //控制输出的空格数
11 cout<<' ';
12 for(_____) //控制输出的数字
13 cout<<_____;
14 cout<<endl;
15 }
16 system("pause");
17 return 0;
18 }
【例题描述】 判断质数
素数又称质数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的。所以，质数是合数的基础，没有质数就没有合数。所有的合数都可由若干个质数相乘而得到。
从键盘输入一个数，并判断该数是否是质数。
1 //判断质数
2 # include <iostream>
3 # include <math.h>
4 using namespace std;
5
6 int main()
7 {
8 int number,i,k;
9 cin>>number;
10 k=sqrt(number); //k为输入数的平方根,想一下为什么？
11 for(i=2;i<=k;i++) //将输入数用从2~k的一个一个数进行整除
12 if(number%i==0)
13 break; //只要能被整除，即跳出for循环
14 if(i>k)
15 cout<<number<<"是一个素数＼n";
16 else
17 cout<<number<<"不是一个素数＼n";
18 system("pause");
19 return 0;
20 }
【上机实践】 求素数
编程求10~500之间的全部素数。
这个很简单了，使用一个for循环枚举10~500之间的每一个数，再使用上面的判断质数的程序判断即可。
我能想到的两个优化是：
（1）判断一个数number是不是质数，只需要从2依次试除到
，看能否被这些数整除即可。
（2）因为偶数肯定不是素数，所以在for循环时，可以直接跳过，这样可提高一倍的速度。
数学家欧几里得最早在《几何原本》中证明了素数有无穷多个：
假设只有有限个素数P1，P2，P3，…，Pn。令N=P1×P2×P3×…×Pn。那么，N+1是素数或者不是素数。
如果N+1为素数，则N+1要大于P1，P2，P3，…，Pn，所以它不在那些假设的素数集合中。
如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以N+1不可能被P1，P2，P3，…，Pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。
因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。
对任何有限个素数的集合来说，用上述的方法永远可以得到有一个素数不在假设的素数集合中的结论。
所以原先的假设不成立。也就是说，素数有无穷多个。
【例题描述】 防护罩
魔法世界的所有街区均为边长为1公里的正方形，如图2.9所示整齐地排列，为了防止黑暗势力的魔法攻击，魔法学校欲建立一个以中心四个街区的交点为圆心，半径为r（r≥
）公里的圆形魔法防护罩，试计算防护罩所能保护的完整街区数N。
图2.9
由于圆的对称性，所以只需要计算四分之一圆中所包含的完整的街区数N，将其中所包含的完整街区数以纵列划分为组，设K为四分之一圆中共有K组街区，显然K为不超过r的最大整数，如图2.10所示。
图2.10
则N=4×（第一组内街区数+第二组内街区数+…+第K组内街区数），问题是每组内的街区数如何计算呢？
现以第四组为例，作一直角三角形如图2.11所示，可知斜边为r，底边为组数，根据勾股定理，当组数为a，则第a组街区数
的最大取整数。
图2.11
C++语言提供的取整函数有：
1．floor函数
floor（x）返回的是x的整数部分，方法是向负无穷大方向舍入。例如：
floor(2.5)= 2
floor(-2.5)= -3
2．ceil函数
ceil（x）返回的是不大于x的最小整数，方法是向正无穷大方向舍入。例如：
ceil(2.5)= 3
ceil(-2.5)= -2
参考代码如下所示：
1 //防护罩
2 #include <iostream>
3 #include <math.h> //须加此头文件
4 using namespace std;
5
6 int main()
7 {
8 int N=0,i,temp;
9 double r,l;
10 cin>>r;
11 l=floor(r); //获得组数
12 for(i=1;i<=l;i++)
13 {
14 temp=sqrt(r*r-i*i);
15 N=N+temp;
16 }
17 cout<<N*4;
18 system("pause");
19 return 0;
20 }
【例题描述】 完美数
魔法世界有一个毕达哥拉斯学派，他们将一个数如果恰好等于它的因子之和的数称为“完美数”。并且认为完美数具有神奇的魔力。例如6的因子为1、2、3，而6=1+2+3，因此6是“完美数”。创始人毕达哥拉斯说：“6象征着完满的婚姻以及健康和美丽，因为它的部分是完整的，并且其和等于自身。”
请编程序找出1000之内的所有完美数。
1 //求完美数
2 #include <iostream>
3 using namespace std;
4 #define M 1000 //定义寻找范围
5
6 int main()
7 {
8 int k0,k1,k2,k3,k4,k5,k6,k7,k8,k9; //保存因子，因子数一定不超过10个
9 int i,j,n,s;
10 for(j=2;j<=M;j++) //枚举每一个数
11 {
12 n=0; //n指向因子保存的位置
13 s=j;
14 for(i=1;i<j;i++)
15 {
16 if((j%i)==0)
17 {
18 n++;
19 s=s-i;
20 switch(n) //判断因子存在何处
21 {
22 case 1:k0=i;break;
23 case 2:k1=i;break;
24 case 3:k2=i;break;
25 case 4:k3=i;break;
26 case 5:k4=i;break;
27 case 6:k5=i;break;
28 case 7:k6=i;break;
29 case 8:k7=i;break;
30 case 9:k8=i;break;
31 case 10:k9=i;break;
32 }
33 }
34 }
35 if(s==0) //若减去所有因子后恰巧为0,则是完美数
36 {
37 cout<<j<<"是一个完美数,它的因子是:";
38 if(n>1)
39 cout<<k0<<''<<k1<<' ';
40 if(n>2)
41 cout<<k2<<' ';
42 if(n>3)
43 cout<<k3<<' ';
44 if(n>4)
45 cout<<k4<<' ';
46 if(n>5)
47 cout<<k5<<' ';
48 if(n>6)
49 cout<<k6<<' ';
50 if(n>7)
51 cout<<k7<<' ';
52 if(n>8)
53 cout<<k8<<' ';
54 if(n>9)
55 cout<<k9<<' ';
56 cout<<"＼n";
57 }
58 }
59 system("pause");
60 return 0;
61 }
后世的大数学家欧拉曾推算出完美数的获得公式：
如果p是质数，且2p-1也是质数，那么（2p-1）×2p-1便是一个完美数。
例如p=2是一个质数，2p-1=3也是质数，则（2p-1）×2p-1=3×2=6是完美数。
例如p=3是一个质数，2p-1=7也是质数，则（2p-1）×2p-1=7×4=28是完美数。
但是2p-1什么条件下才是质数呢?事实上，当2p-1是质数的时候，称其为梅森素数。至今，人类只发现了47个梅森素数，也就是只发现了47个完全数。
【例题描述】 除式还原1
魔法学院的后山出现一块神秘石碑，石碑上有一个除式如图2.12所示，据说解开此除式可以解开一个重大秘密。
图2.12
由除式本身尽可能多地推出已知条件：
1．被除数的范围是10000到99999，除数的范围是10~99，且可以整除；
2．商为100~999之间，且十位数字为7；
3．商的第一位与除数的积为三位数，且后两位为77；
4．被除数的第三位一定为4；
5．7乘以除数的积为一个三位数，且第二位为7；
6．商的最后一位不能为0，且与除数的积为一个两位数。
由已知条件就可以采用穷举的方法找出结果。
参考代码如下所示：
1 //除式还原1
2 #include<iostream>
3 using namespace std;
4 int main()
5 {
6 long int i;
7 int j,l;
8 for(i=10000;i<=99999;i++) //条件1. i为被除数
9 //if(i%1000-i%100==400) //条件4.被除数的第三位一定为4
10 for(j=10;j<=99;j++) //条件1. j为除数
11 if(i%j==0 && (l=i/j)%100>=70 && l%100<80 //条件1.可整除，商的十位数为7
12 &&l%10!=0&&l>100&&l<=999) //商的个数不能为0,商l在100~999之间
13 if((j*(l%10))<100&&j*(l%10)>10) //条件6.商的个数与除数的积为两位数
14 if(j*7%100>=70&&j*7%100<80) //条件5.7乘以除数的积的第二位为7
15 if(j*(l/100)%100==77&&j*(l/100)>100) //商的第1位×除数的后两位为77
16 cout<<i<<"/"<<j<<"="<<l;
17 system("pause");
18 return 0;
19 }
【例题描述】 换零钱1
楚继光想把100元钱换成10元、5元、1元这样的零钱，在这三种零钱中每种零钱都至少各有一张的情况下，共有多少种兑换方案？
设100元可以换10元x张、5元y张，1元z张，则：
100=10x+5y+z（x≥1，y≥1，z≥1）
分析上面的等式可以发现，1≤x≤9，1≤y≤19，1≤z≤99。
因为x≥1，所以5y的取值范围变成5≤5y≤100-10×1，解得1≤y≤18；同理，z的取值范围为1≤z≤100-10×1-5×1，解得1≤z≤85，这样使得内层循环体执行的次数由原来的9×19×99=16929次缩小到9×18×85=13770次，循环次数减少了3159次。另外，由于1元的零钱必为5的倍数，所以还可再做优化。
1 //换零钱基本算法
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int i,j,k,count=0;
8 for(i=1;i<=9;i++)
9 for(j=1;j<=18;j++)
10 for(k=1;k<=85;k++)
11 if((i*10+j*5+k*1)==100)
12 count++;
13 cout<<count<<endl;
14 system("pause");
15 return 0;
16 }
用不等式减少循环套数量：
对于不定方程100=10x+5y+z，做如下变形：z=100-10x-5y。由于z是大于等于1的整数，所以不定方程100=10x+5y+z解的个数就等于不等式100-10x-5y>0的解的个数，易得1≤x≤9，1≤y≤18。故而可用二重循环求解。此时，只需9×18=162次循环体，效率提高了105倍。
1 //利用不等式优化算法
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int i,j,k,count=0;
8 for(i=1;i<=9;i++)
9 for(j=1;j<=18;j++)
10 if(i*10+j*5<100)
11 count++;
12 cout<<count<<endl;
13 system("pause");
14 return 0;
15 }
取1张10元的，则剩下的90元可以用1~17张5元和若干1元的相加得到，故共有17种方案；
取2张10元的，则剩下的80元可以用1~15张5元和若干1元的相加得到，故共有15种方案；
…
取8张10元的，则剩下的20元可以用1~3张5元和若干张1元的相加得到，故共有3种方案；
取9张10元的，则剩下的10元可以用1张5元和5张1元的相加得到，故共有1种方案。
综上可得，总方案数为1+3+5+…+17=81种，则问题就变成了求9个数的和。用单重循环运算9次即可。此时程序效率提升了共1881倍。
1 //利用排列组合优化
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int i,count=0;
8 for(i=1;i<=9;i++)
9 count+=2*i-1;
10 cout<<count<<endl;
11 system("pause");
12 return 0;
13 }
观察数字序列1 3 5 7 9 11…，可以发现相邻两个数的差恒为2，这显然是“等差数列”，记第一项为a1，相邻两个数之间的差为公差，记为d，记第n项为an，容易推导出：an=a1+（n-1）d，如上面第3个数为1+（3-1）×2=5。对于等差数列，我们有如下的公式来求出其前n项的和：
公式（1）用于求知道首项、末项和项数的等差数列的前n项和；
公式（2）用于求知道首项，公差和项数的等差数列的前n项和；
公式（3）用于求知道末项，公差和项数的等差数列的前n项和。
则无须循环，直接用任何一个公式就可求出和为81。
1 //换零钱1——利用数学公式
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 cout<<(1+17)*9/2<<endl;
8 system("pause");
9 return 0;
10 }
【上机实践】 换零钱2
楚继光想把N元钱换成10元、5元、1元这样的零钱，在这三种零钱中每种零钱都至少各有一张的情况下，共有多少种兑换方案（16≤N≤105）
由于钱的数字变成了任意数N，问题变得复杂起来，如果用两重循环，105的数据量肯定超时（1秒）。有什么好的办法吗？
设N元可以换10元x张，5元y张，1元z张，x、y、z均不小于1。则题目的解为不等式N-10x-5y>0解的个数。
等差数列的项数为：可以换10元的最大张数；等差数列的最末项为：当有1张10元时，可以换5元的最大张数。由于是换成10元、5元和1元三种，每增加一张10元必定减少2张5元，所以等差数列的公差为2。
N元钱，当有1张10元时，可以换5元的最大张数b为：
等差数列的公差为2，项数为a，最末项为b，使用等差数列的求和公式（3）得
Sum=a×b-（a×（a-1））/2×2=a×b-a×（a-1）=a×（b-a+1）
参考程序如下所示：
1 定义变量n,a,b,c,sum，其中sum为最终答案，a,b,c分别为10元，5元，1元的张数 2 输入变量n的值 3 计算a的值 4 计算c的值 5 如果剩下的钱不够一张5元和一张1元 6 则a-- 7 计算b的值 8 计算c的值 9 如果c的值不足一元钱 10 则b-- 11 计算sum的值 12 输出sum的值
或者对于输入的钱数x，必定需要一张10元、一张5元和一张1元的。为了简化，可以将这16元钱从x中减去，剩下的钱所需要的钱的张数均为大于等于0。当10元的张数为0（减去后）时，5元张数的最大值为（x-16）/5（整数相除自动去尾）。然后可以一张5元的换成5张1元的，即有（x-16）/5+1种换法。当10元的张数为1时，5元张数的最大值少2，方法数也少2。一直到5元的张数为1或2时，10元张数达到最大（若10元张数更大，5元张数为-1或0）。若为奇数，例如输入x=100，方法的总和为17+15+13+11+9+…+1，运用等差数列求和，count=（x+1）×（x+1）/4。若为偶数，由于整数相除时自动去尾，count仍可以用原来的式子表示。
参考程序如下所示：
1 //换零钱2优化
2 #include<iostream>
3 using namespace std;
4 int main()
5 {
6 int count=0,x,i;
7 cin>>x;
8 x=(x-16)/5+1; //求5元面值张数的最大值，即10元张数=0时的方法数量
9 count=(x+1)*(x+1)/4; //等差求和
10 cout<<count<<endl;
11 system("pause");
12 return 0;
13 }