第3章
程序控制结构








流程图


3.1流程图及程序控制结构简介
3.1.1流程图


关于什么是程序，计算机科学家沃思曾给出如下定义： 
程序=数据结构+算法
其中，算法是为了解决特定问题而规定的一个有限长的操作序列。
算法可以采用自然语言、流程图、伪代码、计算机语言等表示方法描述。
采用流程图描述算法的优点是直观形象、易于理解。流程图包括传统流程图、结构化流程图等，本书仅介绍传统流程图。
一个传统流程图包括表示相应操作的框； 带箭头的流程线； 框内外必要的文字说明。
传统流程图的基本要素包括起止框、输入/输出框、处理框、判断框、流程线、连接点等，具体框图如图31所示。



图31传统流程图基本要素框图



其中，起止框表示算法的开始与结束； 输入/输出框表示输入与输出； 处理框表示处理； 判断框表示条件判断； 流程线表示算法的流程； 连接点用于连接不同页内的同一算法。



例3.1.1“统计闰年”算法的流程图表达
请用传统流程图描述“统计并输出年份区间［ s,t ］中有几个闰年”的算法。
闰年的条件： 闰年是能被4整除，但不能被100整除的年份或者能被400整除的年份。
统计闰年的算法主体部分主要包含输入、处理、输出三部分，具体流程图如图32所示。其中，虚框标注的是处理部分。



图32“统计闰年”的传统流程图表达


采用流程图描述算法是非常重要的一项程序设计技能，本书中以此例说明算法的流程图表示方法。作为入门练习，读者可以尝试用传统流程图表达以下问题的算法。
（1） 输入三角形的三边长，用海伦公式求其面积。
（2） 输入三个人的身高，找出其中的高个。
（3） 输入n及n个人的身高，找出n个人中身高的最大值。
此后，读者可以针对以后的例题、习题画出流程图，进一步熟悉和巩固采用传统流程图表达算法的方法。


3.1.2程序控制结构简介
程序控制结构主要包括顺序结构、选择结构、循环结构。
顺序结构是按语句的书写顺序执行的程序结构。
选择结构是根据特定的条件决定执行哪个语句的程序结构，常用if语句和switch语句。

循环结构是在满足特定的条件时重复执行某些语句的程序结构，常用for、while和do…while等语句。


图33顺序结构流程图

顺序结构的流程图如图33所示。

例如，下面的代码先输入a、b，再输出它们的和。

int a, b;                 //定义变量

cin>>a>>b;                //输入

cout << a+b << endl;    //输出 


上面代码定义变量、输入及输出三个基本语句按顺序依次执行下来。
在C/C++源程序中，基本语句以分号“;”作为结束标记； 仅由单个分号“;”构成的语句称为空语句； 复合语句则以大括号“{}”括起来，例如： 

{

a=a+b;

cout<<a<<endl;

}


3.2选 择 结 构
3.2.1if语句及其使用




例3.2.1

例3.2.1两者中的大者
输入两个整数a，b，找出其中的大者并输出。
思路1： 先假设第一个数大，然后与后一个数比较，若后一个数大，则大者为后一个。可用单分支if语句实现，具体代码如下。

//C++风格，单分支选择结构

#include<iostream>

using namespace std;

int main() {

int a,b,c;

cin>>a>>b;

c=a;                  　　//假设第一个数大，并放到c中

if (b>c)c=b;        　　//若第二个数大于假设的最大数c，则把第二个数放到c中

cout<<c<<endl;

return 0;

}

/*C风格，单分支选择结构*/

#include<stdio.h>

int main() {

int a,b,c;

scanf("%d%d",&a,&b);

c=a;                  　　/*假设第一个数最大，并放到c中*/

if (b>c) c=b;      　　/*如果第二个数大于假设的最大数c，则把第二个数放到c中*/

printf("%d＼n",c);

return 0;

}


思路2： 直接比较两个数，若前一个数大，则把它作为结果输出，否则输出后一个数。可用双分支if语句实现，具体代码如下。

//C++风格，双分支选择结构

#include<iostream>

using namespace std;

int main() {

int a,b;

cin>>a>>b;

if (a>=b)           　　//若第一个数大于等于第二个数

cout<<a<<endl; 　　//则输出第一个数

else

cout<<b<<endl;　　//否则输出第二个数

return 0;

}

/*C风格，双分支选择结构*/

#include<stdio.h>

int main() {

int a,b;

scanf("%d%d",&a,&b);

if (a>=b)   				　　//若第一个数大于等于第二个数

printf("%d＼n",a);    　　//则输出第一个数

else

printf("%d＼n",b);    　　//否则输出第二个数

return 0;

}


本题两种思路的代码中分别使用了单分支、双分支if语句。
1. 基本的if语句
基本if 语句格式如下。
if (条件) 语句1 ［ else 语句2 ］
描述语法时，［ ］表示其中的内容是可选项，即if语句可以是单分支if语句，如下。
if (条件) 语句1
此if语句在满足条件时执行语句1，否则不执行任何语句，其流程图如图34所示。

或者是双分支if语句，如下。
if (条件) 语句1 else 语句2
此if语句在满足条件时执行语句1，否则执行语句2，其流程图如图35所示。




图34单分支if语句流程图




图35双分支if语句流程图




可见，if语句可带else子句（双分支选择结构），也可以不带（单分支选择结构）。
if语句的条件需用小括号括起来，该条件一般是一个逻辑表达式或关系表达式等值为true(或1)或false(或0)的表达式，否则一切0值转换为false，一切非0值转换为true。
语句1和语句2可以是基本语句，也可以是复合语句。例如： 

if(x)                               //x相当于x!=0

printf("x is non-zero＼n"); //基本语句

else

printf("x is zero＼n");

if(x==1) {                         //复合语句   

a=1;

b=2;

}

else {

a=-1;

b=-2;

} 


2. 嵌套的if 语句
嵌套的if语句是指在if语句中又使用if语句。if语句可以嵌套在if子句中，也可以嵌套在else子句中。
从第一个else开始，else总与离它最近的且未被匹配的if配对（最近匹配原则）。
观察如下代码，思考能否达到“当n小于等于0时把z赋值为b，否则当a大于b时，把z赋值为a”的目的。

if(n>0)

if(a>b) z=a; 

else 

z=b;


上面的else虽然在缩排上与if(n>0)对齐，但根据最近匹配原则，这个else与if(a>b)匹配，达到的效果是“当n大于0且a小于等于b时把z赋值为b”。为避免类似问题，建议在else子句中嵌套if语句。
思考： 如何才能使得else与if(n>0)匹配？
可以把第2个if语句用{}括起来： 

if(n>0) {

if(a>b) z=a;

}

else 

z=b;


或者，把if语句嵌套到else子句中： 

if(n<=0)

z=b;

else if(a>b)

z=a;    


3. if 选择结构示例


例3.2.2

例3.2.2三者的最大值
输入三个整数，找出其中最大的一个并显示出来。
思路： 假设第一个数最大并放到结果d中，若后面的数大于d，则把d变为该数。可用单分支语句实现，代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int a, b, c, d;

cin>>a>>b>>c;

d=a;                          //假设第一个数最大，把其存放在d中

if (b>d) d=b;               //若第二个数大于假设的最大数d，则把d改为该数

if (c>d) d=c;               //若第三个数大于假设的最大数d，则把d改为该数

cout<<d<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int a, b, c, d;

scanf("%d%d%d",&a,&b,&c);

d=a;                          /*假设第一个数最大，把其存放在d中*/

if (b>d) d=b;               /*若第二个数大于假设的最大数d，则把d改为该数*/

if (c>d) d=c;               /*若第三个数大于假设的最大数d，则把d改为该数*/

printf("%d＼n",d);



例3.2.3

return 0;

}


这种思路比较简单，而且容易扩展到多个数的情况（结合循环结构）。读者可以思考本题还有哪些其他实现方法，并自行编写代码实现。

例3.2.3三数排序
输入三个整数，然后按从大到小的顺序把它们显示出来。
这个问题该如何实现呢？仔细思考，可以想到多种方法。下面给出两种方法，分别用到选择排序和冒泡排序的思想。
思路1： 采用选出当前最大者放到当前最前面位置（选择排序）的思想。实现代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int a,b,c,d;

cin>>a>>b>>c;

if (a<b)     			   //前两个数比较，若位置不对则交换，使得a>=b

d=a,a=b,b=d;

if (a<c)   				   //前两个数的大者与c比较，若位置不对则交换，a为最大者

d=a,a=c,c=d;

if (b<c)  				   //后两个数的位置若不对，则交换

d=b,b=c,c=d;

cout<<a<<" "<<b<<" "<<c<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int a,b,c,d;

scanf("%d%d%d",&a,&b,&c);

if (a<b)     			　　/*前两个数比较，若位置不对则交换，使得a>=b*/

d=a,a=b,b=d;

if (a<c)     			　　/*前两个数的大者与c比较，若位置不对则交换，a为最大者*/

d=a,a=c,c=d;

if (b<c)   				　　/*后两个数的位置若不对，则交换*/

d=b,b=c,c=d;

printf("%d %d %d＼n",a,b,c);

return 0;

}


思路2： 采用把当前最小者放到当前最后面位置（冒泡排序）的思想。实现代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int a,b,c,d;

cin>>a>>b>>c;

if (a<b)                       　　//前两个数比较，若位置不对则交换，使得a>=b

d=a,a=b,b=d;

if (b<c)                     　　//后两数比较，若位置不对则交换，c为最小者

d=b,b=c,c=d;

if (a<b) {                   　　//前两个数的位置若不对，则交换

d=a,a=b,b=d;

cout<<a<<" "<<b<<" "<<c<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int a,b,c,d;

scanf("%d%d%d",&a,&b,&c);

if (a<b)                       　　/*前两个数比较，若位置不对则交换，使得a>=b*/ 

d=a,a=b,b=d;

if (b<c)                      　　/*后两数比较，若位置不对则交换，c为最小者*/ 

d=b,b=c,c=d;

if (a<b)                      　　/*前两个数的位置若不对，则交换*/ 

d=a,a=b,b=d;

printf("%d %d %d＼n",a,b,c);

return 0;

}



例3.2.4（1）

例3.2.4成绩转换
百分制成绩转换为五级计分制时，90~100分以上等级为A，80～89分等级为B，70～79分等级为C，60～69分等级为D，0～59分等级为E。输入一个百分制成绩，输出等级。
本例是多分支结构，可以用嵌套if语句实现，这里使用if嵌套在else子句中的方法，实现代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int score;

char rank;

cin>>score;

if (score>=90) rank='A'; 

else if (score>=80) rank='B';

else if (score>=70) rank='C';

else if (score>=60) rank='D';

else rank='E';

cout<<rank<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int score;

char rank;

scanf("%d",&score);

if (score>=90) rank='A'; 

else if (score>=80) rank='B';

else if (score>=70) rank='C';

else if (score>=60) rank='D';

else rank='E';

printf("%c＼n",rank);

return 0;

}


3.2.2switch语句及其使用


例3.2.4（2）

例3.2.4是多分支选择结构，也可以使用switch语句实现。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int score;

char rank;

cin>>score;

switch(score/10) {              //对百分制成绩作除以10的运算，减少常量个数

case 9:

case 10:

rank='A'; break;

case 8:

rank='B'; break;

case 7:

rank='C'; break;

case 6:

rank='D'; break;

default:

rank='E';

}

cout<<rank<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int score;

char rank;

scanf("%d",&score);

switch(score/10) {              /*对百分制成绩作除以10的运算，减少常量个数*/

case 9:

case 10:

rank='A'; break;

case 8:

rank='B'; break;

case 7:

rank='C'; break;

case 6:

rank='D'; break;

default:

rank='E';

}

printf("%c＼n",rank);

return 0;

}


上面的程序根据表达式score/10的值去匹配case后面的常量值，匹配成功则执行其后的语句，执行到break时则跳出switch语句； 若都匹配不上，则执行default（对应0、1、2、3、4、5等常量）后的语句。另外，case标号后的多条语句不需要用{}括起来； 多个case标号可以共有一组语句。
switch语句常用于实现多分支选择结构，其语句格式如下。
switch(表达式) {
case常量表达式1:语句序列1
case常量表达式2:语句序列2
…
case常量表达式n:语句序列n
 ［ default:语句序列n+1 ］
}
switch语句中的表达式及常量表达式一般应为整型或字符型。执行时，按表达式的值与case后的常量表达式相匹配，若匹配成功则执行相应语句序列，否则执行default后的语句序列，流程图如图36所示。



图36switch语句流程图



各个case块（含default块）的顺序可以交换。一般每个语句序列（处于最后面的除外）都是由包含break的多条语句构成，但不需要用{}括起来。
如果各case块的语句序列中没有用break语句跳出switch语句，则语句序列将顺序执行下去（不再考虑表达式是否匹配常量值）。例如： 

int n;

cin>>n;                    		　　//scanf("%d",&n);

switch(n) {  

case 10:

cout<<'A'<<endl;		　　//printf("A＼n");

case 11:

cout<<'B'<<endl;		　　//printf("B＼n");

case 12:

cout<<'C'<<endl;		　　//printf("C＼n");

}


若输入10，则运行结果如下。



A

B

C





如上面的代码所示，switch语句可以省略default子句。
若各case语句序列中含有break语句，即： 

int n;

cin>>n;                               　　//scanf("%d",&n);

switch(n) {

case 10:

cout<<'A'<<endl; break;  　　//printf("A＼n"); break;

case 11:

cout<<'B'<<endl; break;  　　//printf("B＼n"); break;

case 12:

cout<<'C'<<endl; break;  　　//printf("A＼n"); break;

}

若输入10，则运行结果如下。



A






例3.2.5

例3.2.5某月的天数
输入年份year、月份month，判断该月的天数。
已知大月有31天，小月有30天，2月有28天或29天（闰年）。大月有1、3、5、7、8、10、12，共7个月； 小月有4、6、9、11，共4个月。
本题需要根据不同的情况（大月、小月、2月）确定该月的天数，用if或switch语句都可以完成。下面给出使用switch语句的代码。

//C++风格

#include<iostream>

using namespace std;

int main() {

int year,month,days;

cin>>year>>month;

switch(month) {

case 2:

if (year%4==0&&year%100!=0||year%400==0)

days=29;

else

days=28;

break;

case 4:	case 6:	case 9:	case 11:

days=30;

break;

default:

days=31;

break;

}

cout<<days<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int year,month,days;

scanf("%d%d",&year,&month);

switch(month) {

case 2:

if (year%4==0&&year%100!=0||year%400==0)

days=29;

else

days=28;

break;

case 4:	case 6:	case 9:	case 11:

days=30;

break;

default:

days=31;

break;

}

printf("%d＼n",days);

return 0;

}

3.3循 环 结 构
3.3.1引例与三种循环语句
1. 引例


例3.3.1

例3.3.1n个整数中的最大值
首先输入一个整数n，然后输入n个整数，请输出这n个整数中的最大值。
在例3.2.2中，使用两条类似的单分支if语句可求得3个数的最大值。现在要求n个数中最大值，若程序运行前已知n的值，则也可以写n-1个单分支语句完成，但n是一个变量，在程序运行中输入后才能确定其值，因此无法在程序运行前写好n-1个if语句。由于n-1个if语句是重复的，可以写一条if语句并使其执行n-1次，这可以使用循环结构完成。循环结构中的for语句常用于实现次数固定且重复执行的要求。求n个整数中的最大值的代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int n,t,max;

cin>>n;                      //先输入数据个数 

cin>>t;                      //先输入第1个数

max=t;                       //假设第1个数最大，并放到max中

for(int i=1; i<n; i++) { //控制输入n-1个数并做比较

cin>>t; 

if (t>max)             //若后面的数大于当前的最大数

max=t;             //则把当前的最大数赋值为后面的数

}

cout<<max<<endl; 

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int i,n,t,max;

scanf("%d",&n);            /*先输入数据个数*/

scanf("%d",&t);            /*先输入第1个数*/

max=t;                       /*假设第1个数最大，并放到max中*/

for(i=1; i<n; i++) {      /*控制输入n-1个数并做比较*/

scanf("%d",&t); 

if (t>max)             /*若后面的数大于当前的最大数*/

max=t;             /*则把当前的最大数赋值为后面的数*/

}

printf("%d＼n",max); 

return 0;

}


上面的代码中，for语句中循环变量i从1到n-1进行循环，共执行n-1次循环体（输入t，再比较max和t，把大者保存在max中）。
2. 三种循环语句
思考： 如何求1+2+…+n的累加和（结果保证在int类型的范围内）？
一种常见的方法是直接采用循环逐项累加，下面给出使用for、while和do…while语句的C风格代码。

/*C风格*/

#include<stdio.h>

int main() {

int sum1=0,sum2=0,sum3=0,n,i;

scanf("%d",&n);

for(i=1; i<=n; i++) sum1 += i;

printf("%d＼n",sum1);

i=1;

while(i<=n) {

sum2 += i;

i++;

}

printf("%d＼n",sum2);

i=1;

do {

sum3 += i;

i++;

} while(i<=n);

printf("%d＼n",sum3);

return 0;

}


运行结果： 



10 

55

55

55





可见，三种循环语句的运行结果相同。实际上，三种循环语句可以相互转换，例3.3.1也可以使用另外两种循环语句实现。若循环体有多条语句，则必须以{}括起来构成复合语句。建议： 循环体只有一条语句也要用{}括起来。
3.3.2for语句及其使用
1. for语句基本格式
for循环语句的基本格式如下。
for(表达式1; 表达式2; 表达式3)
循环体
例如，在线做题时，对于T组测试数据，可用如下代码控制。

int i, T;

cin>>T;                     //C风格： scanf("%d",&T);

for(i=1;i<=T;i++) {

//一组测试的代码

}


for后()中两个分号必不可少，三个表达式可以根据具体情况省略。其中，表达式1通常是循环变量初始化或给循环变量赋值，可以逗号表达形式给多个变量赋值； 表达式2是循环条件，在满足循环条件时反复执行循环体，否则结束循环； 表达式3通常是循环变量调整，可以从小往大调整也可以从大往小调整，如果调整多个循环变量则构成逗号表达式。for循环的流程图如图37所示。



图37for 循环流程图


注意： 在标准编译器下，循环变量初始化中的变量仅在该for语句中有效。若希望循环变量在for语句中及其后都能使用，则把该循环变量定义在for语句之前。另外，纯粹C语言的for语句中不能定义循环变量。
最简单的for语句形式如下。
for(  ;  ;  )
循环体
即三个表达式同时省略，此时循环体中一般要有结束循环的语句，例如，跳出循环的break语句，否则将成为无限循环（死循环），因为表达式2省略时表示循环条件为true，是永真条件。
2. for语句的使用


例3.3.2

例3.3.2数据统计
首先输入一个整数n，然后输入n个整数，请统计其中负数、零和正数的个数。
本例可以设置3个计数器（统计个数的变量，初值为0），每输入一个数就判断其是正、负或0的哪一种，再把对应计数器加1。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int n,d;

cin>>n;

int zero=0,positive=0,negative=0;      //计数器清0 

for(int i=0; i<n; i++) {

cin>>d;

if (d>0) positive++;

else if (d<0) negative++;

else zero++;

}

cout<<negative<<" "<<zero<<" "<<positive<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int d,i,n;

int zero=0,positive=0,negative=0;      /*计数器清0*/ 

scanf("%d",&n);

for(i=0; i<n; i++) {

scanf("%d",&d);

if (d>0) positive++;

else if (d<0) negative++;

else zero++;

}

printf("%d %d %d＼n",negative,zero,positive);

return 0;

}




例3.3.3

例3.3.3亲和数判断
古希腊数学家毕达哥拉斯在自然数研究中发现，220的所有真约数（即不是自身的约数）之和为： 1+2+4+5+10+11+20+22+44+55+110＝284。而284的所有真约数为1、2、4、71、142，加起来恰好为220。人们称这样的数对为亲和数。也就是说，若两个数中任何一个数都是另一个数的真约数之和，则它们就是亲和数。请判断输入的两个整数是否是亲和数，是则输出“YES”，否则输出“NO”。引号不必输出。
本题根据亲和数的定义把两个整数的真约数之和各自求出，再判断各自是否等于另一个数即可。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int a,b,i,sumA=0,sumB=0;

cin>>a>>b;

for(i=1;i<a;i++) {

if(a%i==0) sumA+=i;

}

for(i=1;i<b;i++) {

if(b%i==0) sumB+=i;

}

if(sumA==b&&sumB==a) cout<<"YES"<<endl; 

else cout<<"NO"<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int a,b,i,sumA=0,sumB=0;

scanf("%d%d",&a,&b);

for(i=1;i<a;i++) {

if(a%i==0) sumA+=i;

}

for(i=1;i<b;i++) {

if(b%i==0) sumB+=i;

}

if(sumA==b&&sumB==a) printf("YES＼n"); 

else printf("NO＼n");

return 0;

}



例3.3.4

例3.3.4星号三角形
输入整数n，显示星号*构成的三角形。例如，n=6时，显示输出的三角形如下。



*

***

*****

*******

*********

***********






二维图形的输出，一般在观察图形得到规律后用二重循环实现。对于本题，若输入n，则输出n行，且第i行有n-i个空格和2i-1个*。故采用二重循环，第一重循环（外循环）控制行数，第二重循环（内循环）控制每行的空格数和*的个数。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int n, j;

cin>>n;

for(int i=1; i<=n; i++) {        //外循环，控制共输出n行

for(j=1; j<=n-i; j++) {      //内循环，输出每行前面的空格

cout<<' '; 

}

for(j=1; j<=2*i-1; j++) {   //内循环，输出每行的*

cout<<'*'; 

}

cout<<endl;  

}

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int i, j, n;

scanf("%d",&n);

for(i=1; i<=n; i++) {             /*外循环，控制共输出n行*/

for(j=1; j<=n-i; j++) {      /*内循环，输出每行前面的空格*/

printf(" "); 

}

for(j=1; j<=2*i-1; j++) {   /*内循环，输出每行的"*" */

printf("%c", '*'); 

}

printf("＼n");  

}

return 0;

}


多重循环的执行过程： 外循环变量每取一个值，内循环完整执行一遍。上面的程序当外循环变量i为1时，内循环中第一个循环控制输出n-1个空格，内循环中第二个循环控制输出1个*； 外循环变量i为2时，内循环中第一个循环控制输出n-2个空格，内循环中第二个循环控制输出3个*，……，外循环变量i为n时，内循环中第一个循环条件不成立，该循环不执行，没有空格输出，内循环中第二个循环控制输出2n-1个*。作为二维图形输出练习，读者可以尝试输入整数n，再输出类似n=5时如例1.6.2 中所示的漏斗图形。


例3.3.5

例3.3.5百钱百鸡问题
100元钱买100只鸡，公鸡5元1只，母鸡3元1只，小鸡1元3只。问公鸡、母鸡、小鸡三种鸡各多少只（某种鸡可以为0只）？ 
分别设三种鸡的只数为x、y、z，然后利用总数量、总金额两个条件，可以列出两个方程： 
（1） x+y+z=100
（2） 5x+3y+z3=100
两个方程共有三个未知数，不能直接求出结果。可以使用穷举法（也称枚举法，对待求解问题的所有可能情况逐一检查是否为该问题的解）对x（0~20）、y（0~33）、z（0~100）的各种取值逐一检查是否满足这两个方程，如果满足，则得出一组结果。
另外，还要注意到一个隐含的条件，就是小鸡的数量是3的倍数，即z%3==0。
根据以上分析，可以用三重循环求解本题，具体实现代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int x,y,z;

for (x=0; x<=20; x++) {

for (y=0; y<=33; y++) {

for (z=0; z<=100; z++) {

if ( x+y+z==100 && 5*x+3*y+z/3==100 && z%3==0 ) {

cout<<x<<" "<<y<<" "<<z<<endl;					

}

}

}

}

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int x,y,z;

for (x=0; x<=20; x++) {

for (y=0; y<=33; y++) {

for (z=0; z<=100; z++) {

if ( x+y+z==100 && 5*x+3*y+z/3==100 && z%3==0 ) {

printf("%d %d %d＼n",x,y,z);

}

}

}

}

return 0;

}


实际上，当公鸡和母鸡的只数分别为x、y时，可以直接得到小鸡的只数z=100-x-y，因此小鸡只数不需要从0到100去穷举，如此只需要用二重循环就能求解本题，具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int x,y,z;

for (x=0; x<=20; x++) {

for (y=0; y<=33; y++) {

z=100-x-y;

if (5*x+3*y+z/3==100 && z%3==0) {

cout<<x<<" "<<y<<" "<<z<<endl;

}

}

}

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int x,y,z;

for (x=0; x<=20; x++) {

for (y=0; y<=33; y++) {

z=100-x-y;

if (5*x+3*y+z/3==100 && z%3==0) {

printf("%d %d %d＼n",x,y,z);

}

}

}

return 0;

}


3.3.3while语句及其使用
1. while语句基本格式
while循环语句的格式如下。
while(循环条件)
循环体 
while语句在满足循环条件时反复执行循环体，否则结束循环，流程图如图38所示。



图38while 循环流程图


循环体中一般需要有改变循环变量使循环趋于结束或跳出循环的语句，以避免死循环。若循环体有多条语句，则必须以{}括起来构成复合语句。
在线做题时，对于T组测试的题目，可用如下代码控制。

int T;

cin>>T;        	　　//C风格： scanf("%d",&T);

while(T--) {

//一组测试的代码

}


其中，while(T) 当T≥1时，非0值转换为逻辑值true，执行循环体； 当T==1时，先取T的值1转换为true，最后执行一次循环，之后T变为0，再取T的值0，转换为false，循环结束。


例3.3.6

2. while语句的使用

例3.3.6奇数的和
输入一个整数n，用while循环求［1，n］中所有奇数的和。
可从1开始，当奇数在n的范围内就逐个累加，超出n则不再累加，循环结束。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int n,sum;

cin>>n;

sum=0;                　　//累加单元清0

int i=1;              //循环变量赋初值

while(i<=n) {        //满足循环条件则执行循环体

sum += i;

i+=2;             //改变循环变量使循环趋于结束

}

cout<<sum<<endl; 

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int i,n,sum;

scanf("%d",&n);

sum=0;                /*累加单元清0*/

i=1;                  /*循环变量赋初值*/

while(i<=n) {       /*满足循环条件则执行循环体*/

sum += i;

i+=2;            /*改变循环变量使循环趋于结束*/

}

printf("%d＼n",sum); 

return 0;

}


这个例子使用了while语句来实现循环，当满足i<=n条件时，反复执行循环体； 当i不断增加使得i<=n条件不成立，即i>n时，结束循环。


例3.3.7

例3.3.7数位之和
输入一个正整数，求其各个数位上的数字之和。例如，输入12345，输出15。
本题需要数位分离，即把一个整数的个位、十位、百位等数位分离出来。可以不断地取得个位相加，再把个位去掉，直到该数等于0为止。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int n, t, sum;

cin>>n;

sum=0;

while(n>0) {          //当n>0进行循环

t=n%10;           //取得个位

n=n/10;           //去掉个位

sum=sum+t;

}

cout<<sum<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int n, t, sum;

scanf("%d",&n);

sum=0;

while(n>0) {          	　　/*当n>0进行循环*/

t=n%10;           	　　/*取得个位*/

n=n/10;           	　　/*去掉个位*/

sum=sum+t;

}

printf("%d＼n",sum);

return 0;

}




例3.3.8

例3.3.8数列求和

求下面数列的所有大于等于0.000 001的数据项之和，显示输出计算的结果（四舍五入保留6位小数）。
12、34、58、716、932、…
观察上面的数列，发现有什么规律？
规律1： 分子为从1开始的奇数、分母为2的幂次； 即第i项的通项公式为(2i-1)/2i。
规律2： 第一项分子为1，分母为2，后一项与前一项相比，分子值增加2，分母值增加1倍。
这里采用按规律2，逐项累加。另外，0.000 001可以表示为1e6。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

double sum=0,t;

int a=1,b=2;

t=(double)a/b;           	　　//强制转换，避免类似1/2结果为0

while(t>=1e-6) {

sum+=t;

a+=2;

b*=2;

t=a*1.0/b;           	　　//a*1.0,向double类型自动转换，避免类似3/4结果为0

}

printf("%.6lf＼n", sum);	　　//结果保留6位小数用C语言写法更方便，自动四舍五入

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

double sum=0,t;

int a=1,b=2;

t=(double)a/b;           	　　/*强制转换，避免类似1/2结果为0*/

while(t>=1e-6) {

sum+=t;

a+=2;

b*=2;

t=a*1.0/b;           	　　/*a*1.0,向double类型自动转换，避免类似3/4结果为0*/

}

printf("%.6lf＼n", sum);	　　/*结果保留6位小数，自动四舍五入*/

return 0;

}



例3.3.9

例3.3.9计算sinx的近似值
按下面的计算公式，设计一个程序，输入弧度 x，通过累加所有绝对值大于等于0.000 001的项来计算sinx 的近似值，显示输出计算的结果。结果保留6位小数。
sinx=x1-x33！+x55！-x77！+…

观察计算公式，发现有什么规律？
规律1： 第n项的分子为x的2n-1次幂（与前一项相差-x2）、分母为(2n-1)!。
规律2： 第一项为x，第n项的通项为x2n-1/(2n-1)!，后一项与前一项相比，相差一个因子-x2/((2n-1)(2n-2))。
根据规律2，逐项累加。0.000 001可以表示为1e6。代码如下。

//C++风格

#include<iostream>

using namespace std;

#include<cmath>

int main() {

double sum=0,t,x;

cin>>x;

t=x;                       	　　//t表示某一项，首项为x

int n=1;

while(fabs(t)>=1e-6) { 	　　//fabs(t)求实数t的绝对值

sum+=t;

n++;

t*=-x*x/(2*n-1)/(2*n-2);

}

printf("%.6lf＼n",sum); 	　　//结果保留6位小数用C语言写法更方便

return 0;

}

/*C风格*/

#include<math.h>

#include<stdio.h>

int main() {

double sum=0,t,x;

int n=1;

scanf("%lf",&x);

t=x;                       	　　/*t表示某一项，首项为x*/

while(fabs(t)>=1e-6) { 	　　/*fabs(t)求实数t的绝对值*/

sum+=t;

n++;

t*=-x*x/(2*n-1)/(2*n-2);


}

printf("%.6lf＼n",sum); 	　　/*结果保留6位小数*/

return 0;

}


其中，用到数学函数fabs(double)求实数绝对值，故须包含头文件cmath或math.h。
也可以采用规律1实现，具体代码如下。

//C++风格

#include<iostream>

using namespace std;

#include<cmath>

int main() {

double sum=0,t,x,r=1;

cin>>x;

t=x;

int n=2;

while(fabs(t/r)>=1e-6) {

sum+=t/r;

t*=-x*x;

r=1;

for(int i=1;i<=2*n-1;i++) r*=i;

n++;

}

printf("%.6lf＼n",sum);

return 0;

}

/*C风格*/

#include<math.h>

#include<stdio.h>

int main() {

double sum=0,t,x,r=1;

int i,n=2;

scanf("%lf",&x);

t=x;	

while(fabs(t/r)>=1e-6) {

sum+=t/r,t*=-x*x,r=1;

for(i=1;i<=2*n-1;i++) r*=i;

n++;

}

printf("%.6lf＼n",sum);

return 0;

}


此代码在while循环中嵌套了for循环求阶乘，是二重循环的实现方式。注意，由于阶乘的速度增长很快，为避免溢出，保存阶乘结果的变量r定义为double类型。另外，本题中阶乘是除数，也可以考虑不计算阶乘而在for循环中用“t/=i;”求得各项，具体代码留给读者自行实现。
3.3.4do…while语句及其使用
1. do…while语句基本格式
do…while 循环语句格式如下。


图39do…while循环流程图

do
循环体 
while(循环条件);
do…while循环体中需要有改变循环变量使循环趋于结束或跳出循环的语句，以避免死循环。若循环体有多条语句，则必须以{}括起来构成复合语句。do…while语句先做一次循环体，再判断循环条件，在满足循环条件时反复执行循环体，否则结束循环，流程图如图39所示。


2. do…while语句的使用
思考： 如何保证输入的数据一定在［1，10］范围内？
显然，当不在［1，10］范围内时需要重新输入，用do…while语句可以方便实现。具体代码如下。

do {

cin>>n;              //C风格： scanf("%d",&n);

} while(n<1 || n>10); 　　//当满足此条件时执行循环体



例3.3.10

例3.3.10偶数之和
输入n，求［1，n］范围内的所有偶数之和。
本例的循环变量i可以从0开始，每次增2，逐个把i加到求和单元中，具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int n,sum=0;

cin>>n;

int i=0;                 　　//循环变量赋初值

do {                      　　//循环体		

sum += i;

i+=2;               　　//改变循环变量使循环趋于结束

}while(i<=n);           　　//满足循环条件则执行循环体

cout<<sum<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int i,n,sum=0;

scanf("%d",&n);

i=0;                     　　/*循环变量赋初值*/

do {                      　　/*循环体*/		

sum += i;

i+=2;                 　　/*改变循环变量使循环趋于结束*/

}while(i<=n);           　　/*满足循环条件则执行循环体*/

printf("%d＼n",sum);

return 0;

}


do…while语句与while语句的区别在于： 
若一开始循环条件就不成立时，do…while语句执行1次循环体，while语句执行0次循环体。
3.3.5continue、break语句及其使用
在C/C++语言中，continue语句用于提前结束本轮循环的执行，即本轮循环不执行continue之后的语句，而是继续进行下一次循环的准备与条件判断； break语句用来跳出其所在的循环，接着执行该循环之后的语句。
对于例3.3.10，循环变量也可以从1开始，依次递增1，但在循环体中增加判断语句，跳过奇数。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int n,sum=0;

cin>>n;

for(int i=1;i<=n;i++) {

if (i%2==1)        	　　//i为奇数

continue;      	　　//跳过本次循环continue之后的语句

sum+=i;

}

cout<<sum<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int i,n,sum=0;

scanf("%d",&n);

for(i=1;i<=n;i++) {

if (i%2==1)        	　　/*i为奇数*/

continue;      	　　/*跳过本次循环continue之后的语句*/

sum+=i;

}

printf("%d＼n",sum);



例3.3.11

return 0;

}


例3.3.11素数判定
输入一个正整数m（m>1），判断该数是否为素数。如果m为素数则输出“yes”； 反之输出“no”。
根据素数的定义，除了1和本身之外没有其他因子的自然数是素数。因此可以从2到该数的前一个数去看有没有因子，只要这个范围内有任意一个因子就可以确定该数不是素数，不必再看是否有其他因子。根据这个思路，实现代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int m;

cin>>m; 

bool isPrime=true;           //标记变量，一开始假设是素数

for (int i=2;i<m;i++) {

if (m%i==0) {             //有其他因子

isPrime=false;       //更改标记，表示不是素数

break;                 //跳出其所在的循环

}

}

if(isPrime==true)             //标记变量保留原值，说明没有其他因子

cout<<"yes"<<endl;

else

cout<<"no"<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int i,m;

int isPrime=1;            /*标记变量，一开始假设是素数*/

scanf("%d",&m);

for (i=2;i<m;i++) {

if (m%i==0) {             /*有其他因子*/

isPrime=0;       /*更改标记，表示不是素数*/

break;                 /*跳出其所在的循环*/

}

}

if(isPrime==1)             /*标记变量保留原值，说明没有其他因子*/

printf("yes＼n");

else

printf("no＼n");

return 0;

}


上面的代码中，for循环有两个出口，一个是循环条件不成立，即!(i<m)（实际上i==m时结束循环）； 另一个是break语句，执行该语句时程序流程直接从循环中跳出（此时循环条件i<m依然成立）。
注意，一个break语句只能跳出一个循环。如果要用break跳出二重循环，可以在内、外循环中都使用break，也可以设置一个标记变量（初值设为true用&&运算符）添加到两个循环条件中，当需要结束循环时把标记变量改为false，从而构成“短路”表达式。
注意，如果本题没有说明m>1，则需要对1做特殊处理，因为根据上面的代码，输入1将得到“yes”，而实际上1不是素数。
对于2 147 483 647这个素数而言，上面判断是否有因子的循环需要执行2 147 483 646次。显然效率很低，能否改进代码，提高效率呢？在效率提高方面，因为m除了本身之外的最大因子是m/2，循环条件可以改为i<=m/2，这样对于一个素数的判断循环次数少了约一半，效率得到提高。实际上，效率可以进一步提高，因为若m是合数（不是素数），则可以分解为两个因子（设为a，b，且a≤b）之积，即
m＝a×b 
则 a2≤a×b≤b2
即 a2≤m≤b2
即 a≤m≤b
可见，a这个因子不大于m，因此可以判断到m，因为m之前没有因子的话，m之后也不会有因子。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

#include<cmath>

int main() {

int m;

cin>>m; 

bool isPrime=true;

int sqm=(int)sqrt(m*1.0);

for (int i=2;i<=sqm;i++) {

if (m%i==0) {

isPrime=false;

break;

}

}

if (isPrime==true)

cout<<"yes"<<endl;

else

cout<<"no"<<endl;

return 0;

}

/*C风格*/

#include<math.h>

#include<stdio.h>

int main() {

int i,m,sqm;

int isPrime=1;

scanf("%d",&m);	

sqm=(int)sqrt(m*1.0);

for (i=2;i<=sqm;i++) {

if (m%i==0) {

isPrime=0;

break;

}

}

if (isPrime==1)

printf("yes＼n");

else

printf("no＼n");

return 0;

}


对于2 147 483 647而言，上面判断是否有因子的循环需要执行46 339次，效率远高于前一种方法。另外，调用sqrt函数（头文件cmath）时，建议实际参数用double类型，以避免在线提交时出现编译错误。


例3.3.12

例3.3.12最大公约数
求两个正整数m，n的最大公约数（Greatest Common Divisor，GCD）。
本题的一种解法是直接利用数学性质求解，即从m，n两个数中的小者到1逐个尝试（穷举法），找第一个能同时整除m，n的因子（找到则直接用break跳出循环），实现代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int m,n,gcd;

cin>>m>>n;

int k=m;

if (n<k) k=n;

for (int i=k;i>=1;i--) {

if (m%i==0&&n%i==0) {

gcd=i;

break;

}

}

cout<<gcd<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int i,k,m,n,gcd;

scanf("%d%d",&m,&n);

k=m;

if (n<k) k=n;

for (i=k;i>=1;i--) {

if (m%i==0&&n%i==0) {

gcd=i;

break;

}

}

printf("%d＼n",gcd);

return 0;

}


另一种方法是利用欧几里得（Euclid）算法。欧几里得算法又称辗转相除法，用于计算两个整数m，n的最大公约数。其计算原理依赖于下面的定理： gcd(m，n)=gcd(n，m%n)。
例如，求m=70和n=16的最大公约数，计算过程如表31所示。


表31求最大公约数计算过程



轮次
m
n
t=m%n
1
70
16
6
2
16
6
4
3
6
4
2
4
4
2
0
5
2
0


计算时，m、n不断用新值代替旧值（迭代法），直到n为0时，m为最大公约数。因此，实现代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int m,n,gcd;

cin>>m>>n;

while(n>0) {

int t=m%n;

m=n;

n=t;

}

gcd=m;

cout<<gcd<<endl;

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int m,n,t,gcd;

scanf("%d%d",&m,&n);

while(n>0) {

t=m%n;

m=n;

n=t;

}

gcd=m;

printf("%d＼n",gcd);

return 0;

}


思考： 怎么求m，n的最小公倍数（Least Common Multiple，LCM）lcm？
一种思路是从m、n中的大者出发，逐个检查该数的1倍、2倍、…是否是另一个数的倍数。另一种思路是基于求得的最大公约数gcd。设原来的m、n已经分别保存在a、b中，则最小公倍数lcm=a*b/gcd。考虑到a*b可能产生溢出，可以先除后乘（这也是程序设计竞赛中要注意的一个小技巧），即lcm=a/gcd*b，因为最大公约数gcd肯定能整除a、b中的任何一个数。
思考： 如何求n个正整数的最小公倍数？
可以在求解两个数的最小公倍数的基础上进行，设最小公倍数lcm的初值为1，在执行n次的循环中每输入一个整数t，就求lcm与t的最小公倍数并保存在lcm中，则最终的lcm为结果。具体代码留给读者自行实现。
3.4OJ题目求解


例3.4.1

例3.4.1求绝对值（HLOJ 1948） 
Problem Description
输入一个实数，求其绝对值。
Input
测试数据有多组，处理到文件尾。每组测试数据输入一个实数。
Output
对于每组测试数据，在一行上输出该实数的绝对值，结果保留两位小数。



Sample Input


-456.01








Sample Output


456.01






取绝对值时，对于非负数，可以直接输出，而对于负数，可用负号-把该数转换为正数再输出。对于处理到文件尾，可用循环while(cin>>d)的方式。具体代码如下。

//C++风格

#include <iostream>

using namespace std;

int main() {

double d;

while(cin>>d) {              	 //控制处理到文件尾(此时cin得到NULL，循环结束)

if (d<0) d=-d;

printf("%.2lf＼n",d);

}

return 0;

}


当然，求实数的绝对值也可以直接调用数学库函数fabs，例如，fabs(-1.23)的结果等于1.23。注意fabs函数的参数类型为double，头文件为cmath或math.h。

/*C风格*/

#include<stdio.h>

#include<math.h>

int main() {

double d;

while(scanf("%lf",&d)!=EOF) /*控制处理到文件尾(此时scanf得到EOF，循环结束)*/

printf("%.2lf＼n",fabs(d));

}

return 0;

}




例3.4.2


例3.4.2求和（HLOJ 1001） 
Problem Description
输入一个数n，求出由1加至n的总和。测试数据保证结果在int范围内。
Input
测试数据有多组，处理到文件尾。每组测试输入一个正整数n。
Output
对于每组测试，输出1+2+3…+n的结果。



Sample Input


4








Sample Output


10






在前面的章节中，曾使用逐个累加的方法求1+2+3…+n。但在程序设计竞赛中或在线做题时，可能经常出现n较大且数据量很大的情况。这种情况下，逐个累加将得到超时反馈。为避免超时，需要考虑更高效的方法。因为1，2，…，n等各项构成等差数列，可以直接使用求和公式n(n+1)/2。需要注意的是，比赛时测试数据一般都比较完善，若n较大，例如50 000，则50 000×50 001=2 500 050 000超出int能表示的最大值2 147 483 647，即产生溢出，解决办法： 一是使用更长的类型，例如long long int； 二是判断n的奇偶性，先用偶数除以2再乘另一个数。具体代码如下。

//C++风格

#include <iostream>

using namespace std;

int main() {

int n;

while(cin>>n) {                 //控制处理到文件尾(此时cin得到NULL，循环结束)

int sum;

if(n%2==0) sum=n/2*(n+1);

else sum=(n+1)/2*n;

cout<<sum<<endl;

}

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int n,sum;

while(scanf("%d",&n)!=EOF) { /*scanf得不到数据时返回EOF(-1)*/ 

if(n%2==0) sum=n/2*(n+1);

else sum=(n+1)/2*n;

printf("%d＼n",sum);

}

return 0;

}




例3.4.3

例3.4.3求n!（HLOJ 1909）
Problem Description

n!=1,n=0,1

1×2×…×n,n≥2


Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据输入一个正整数n（n≤12）。
Output
对于每组测试，输出整数n的阶乘。



Sample Input


1

5








Sample Output


120






实现思想： 外循环控制测试组数，内循环从1连乘到n。连乘单元初值置为1。

//C++风格

#include <iostream>

using namespace std;

int main() {

int T;

cin>>T;

for(int i=0;i<T;i++) {

int n;

cin>>n; 

int res=1;

for(int j=2;j<=n;j++) res*=j;

cout<<res<<endl;

}

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int T,i,j,n,res;

scanf("%d",&T);

for(i=0;i<T;i++) {

scanf("%d",&n); 

res=1;

for(j=2;j<=n;j++) res*=j;

printf("%d＼n",res);

}

return 0;

}


需要注意的是阶乘的增长速度很快，13!已经超出int范围，若要求稍大的n的阶乘，可以用long long int类型，对于更大的n，则需要考虑使用数组或字符串处理。


例3.4.4

例3.4.4闰年判断（HLOJ 1910） 
Problem Description
闰年是能被4整除但不能被100整除或者能被400整除的年份。请判断给定年份是否闰年。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据输入一个年份y。
Output
对于每组测试，若y是闰年输出“YES”，否则输出“NO”。引号不必输出。



Sample Input

2

2008

1900








Sample Output

YES

NO





实现思想： 在循环中逐个判断闰年条件是否成立，具体代码如下。

//C++风格

#include <iostream>

using namespace std;

int main() {

int n;

cin>>n; 

for(int i=0; i<n; i++) {

int y;

cin>>y; 

if (y%4==0&&y%100!=0||y%400==0) cout<<"YES"<<endl;

else cout<<"NO"<<endl;

}

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int i,n,y;

scanf("%d",&n); 

for(i=0; i<n; i++) {

scanf("%d",&y); 

if (y%4==0&&y%100!=0||y%400==0) printf("YES＼n");

else printf("NO＼n");

}

return 0;

}




例3.4.5

例3.4.5统计数字（HLOJ 1950）
Problem Description
输入一个字符串，统计其中数字字符的个数。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入一个仅由字母和数字组成的字符串（长度不超过80）。
Output
对于每组测试，在一行上输出该字符串中数字字符的个数。



Sample Input

2

ac520ac520

a1c2m3sdf








Sample Output

6

3






实现思想： 外循环控制测试组数，内循环中输入字符串后逐个扫描字符串的每个字符，若是数字字符，则计数器增1。具体代码如下。

//C++风格

#include <iostream>

#include <string>

using namespace std;

int main() {

int n;

cin>>n;

for(int j=0; j<n; j++) {

string s;

cin>>s;

int cnt=0;

for(int i=0;i<s.size();i++) {

if (s［i］>='0'&&s［i］<='9') cnt++;

}

cout<<cnt<<endl;

}

return 0;

}


本题使用STL之string。处理字符串时，使用string比使用char类型的数组要简单、方便。但对于大量字符串的输入的比赛题目，用cin输入到string类型变量可能导致超时，此时可以使用字符数组作为缓冲避免超时。具体代码如下。

//C++风格

#include <iostream>

#include <string>

using namespace std;

int main() {

int n;

scanf("%d",&n);

for(int j=0; j<n; j++) {

string s;

char ts［81］;     //定义一个字符数组，长度为81 

scanf("%s",ts); //缓冲输入，若输入的字符串包含空格，则用gets(ts); 

s=ts;             //可以把char数组赋值给string类型变量 

int cnt=0;

for(int i=0;i<s.size();i++) {

if (s［i］>='0'&&s［i］<='9') cnt++;

}

cout<<cnt<<endl;

}

return 0;

}


上面的代码使用了字符数组，用scanf输入时格式字符是s。下面再给出C风格代码，也使用字符数组，读者可以先行了解相关知识，或暂时跳过此内容，待学完字符数组的知识后再回头掌握。
本题的C风格代码具体如下。

/*C风格*/ 

#include <stdio.h>

#include <string.h>                        /*char数组处理函数的头文件*/ 

int main() {

int i,j,n,cnt;

char s［81］;                            /*定义一个字符数组s，长度为81*/  

scanf("%d",&n);

for(j=0; j<n; j++) {

scanf("%s",s);                    /*输入，格式字符为s*/ 

cnt=0;

for(i=0;i<strlen(s);i++) {     /*strlen(s)求s的长度*/ 

if (s［i］>='0'&&s［i］<='9') cnt++;

}

printf("%d＼n",cnt);

}

return 0;

}



例3.4.6

例3.4.6查找最大元素（HDOJ 2025）
Problem Description
对于输入的每个字符串（由大小写英文字母构成），查找其中的最大字母，在该字母后面插入字符串“(max)”。
Input
测试数据有多组，处理到文件尾。每组测试输入一个字符串（仅由大小写字母构成，且长度不超过100）。
Output
对于每组测试，输出插入字符串“(max)”后的结果，如果存在多个最大的字母，就在每一个最大字母后面都插入“(max)”。



Sample Input


abcgfcba

zzzzz








Sample Output


abcg(max)fcba

z(max)z(max)z(max)z(max)z(max)





OJ通常按测试数据比对来判断程序对错，故本题可以采用直接输出的方法。本题的实现思想： 外循环控制到文件尾，内循环先找到最大字符，然后逐个输出字符，若该字符是最大字符，则再输出字符串"(max)"。

//C++风格

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

while(cin>>s) {                //控制处理到文件尾(此时cin得到NULL，循环结束)

int i,n=s.size();

char maxCh=s［0］;          //假设第一个字符最大

for(i=1; i<n; i++) {     //找最大字符

if (maxCh<s［i］) maxCh=s［i］;

}

for(i=0;i<n;i++) {       //逐个输出字符，若是最大字符，则再输出(max)

cout<<s［i］;

if(maxCh==s［i］) cout<<"(max)";

}

cout<<endl;

}

return 0;

}


相应的C风格代码如下。

/*C风格*/

#include<stdio.h>

#include<string.h>

int main() {

char s［101］,maxCh;

int i,n;

while(scanf("%s",s)!=EOF) {  /*控制处理到文件尾*/

n=strlen(s);

maxCh=s［0］;                /*假设第一个字符最大*/

for(i=1;i<n;i++) {        /*找最大字符*/

if(maxCh<s［i］) maxCh=s［i］;

}

for(i=0;i<n;i++) {        /*逐个输出字符，若是最大字符，则再输出(max)*/

printf("%c",s［i］);

if(maxCh==s［i］) printf("(max)");

}

printf("＼n");

}

return 0;

}


若本题确实要把(max)插入到字符串中，则可以最大字符位置为界分别取得string类型字符串的左子串（含最大字符）和右子串，然后用连接符+把"(max)"连接到左、右子串之间。另外需要注意插入(max)之后的串长度发生了变化，下次比较的起始位置也要偏移"(max)"的长度，即5。具体代码如下。

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

while(cin>>s) {                   //控制处理到文件尾

int i,n=s.size();

char maxCh=s［0］;             //假设第一个字符最大

for(i=1;i<n;i++) {           //找最大字符

if(maxCh<s［i］) maxCh=s［i］;

}

for(i=0;i<s.size();i++) { //因为s不断变长，串长应为s.size()

if(maxCh==s［i］) {      //若是最大字符，则在其后插入(max)

s=s.substr(0,i+1)+"(max)"+s.substr(i+1);

i+=5;                //跳过刚插入的(max)

}

}

cout<<s<<endl;

}

return 0;

}


其中，s.substr(0,i+1)取s从0开始长度为i+1的子串，s.substr(i+1)取s从i+1开始的剩余子串。
使用char数组时，插入(max)需要频繁移动数组元素，处理起来没有string类型变量方便，读者可以在掌握了char数组的相关知识后再自行尝试。


例3.4.7

例3.4.7 单词首字母大写（HDOJ 2026）
Problem Description
输入一个英文句子，要求将每个单词的首字母改成大写字母。
Input
测试数据有多组，处理到文件尾。每组测试输入一行，包含一个长度不超过100的英文句子（仅包含大小写英文字母和空格），单词之间以一个空格分隔。
Output
对于每组测试，输出按照要求改写后的英文句子。



Sample Input


i like acm

i want to get accepted








Sample Output


I Like Acm

I Want To Get Accepted






实现思想： 根据空格取单词，每次把空格之前的子串作为一个单词从句子中截取下来，存放到临时串t中，使用cnt统计单词个数。方便处理起见，在输入串的最后添加一个空格。具体代码如下。

//C++风格

#include<iostream>

#include<string>

using namespace std;

int main() {

string s;

while(getline(cin,s)) {		              

s=s+" ";                //按空格取单词，方便处理起见，在最后加一个空格

int i,n=s.size(),cnt=0;

string t="";           //临时保存一个单词

for(i=0;i<n;i++) {

if (s［i］==' ') { //遇到空格，表示其前面的一个单词结束

if (t［0］>='a'&&t［0］<='z') t［0］+='A'-'a';

cnt++;        //单词数增1

if(cnt>1) cout<< " ";

cout<<t;

t="";

continue;

}

t=t+s［i］;         //把字符连接到临时串t中

}

cout<<endl;

}

return 0;

}


上面的代码能逐个单词取出放到临时字符串t中，可以对单词做更多的处理，例如，单词逆置、求最长单词等。实际上，本题还有其他一些求解方法，例如，用字符串的成员函数find找空格，再用成员函数substr取子串来完成，具体留给读者自行实现。本程序对于单词之间有多个空格的情况也能正确处理，请读者自行分析。
由于C语言使用字符数组处理字符串时不如string类型变量方便，推荐使用C++的string处理字符串。为方便读者体会字符数组的使用，给出本题的C风格代码如下。

#include<stdio.h>

#include<string.h>

int main() {

char s［101］;                      /*定义字符数组*/ 

int i,n;

while(gets(s)) {                 /*有空格，故用gets函数，遇文件尾返回NULL*/

n=strlen(s);                 /*求串长*/ 

if (s［0］>='a'&&s［0］<='z') /*处理首字符*/

putchar(s［0］+('A'-'a')); 

for(i=1;i<n;i++) {

if (s［i-1］==' ')    	   /*遇到空格，表示一个单词开始，把其后字母大写*/ 

if (s［i］>='a'&&s［i］<='z') putchar(s［i］+('A'-'a'));

else putchar(s［i］);

}

putchar('＼n');

}

return 0;

}


其中，gets函数用于输入包含空格的字符串，得不到数据时返回空指针NULL。由于使用字符串操作函数，需包含头文件string.h。这里使用putchar函数输出一个字符。需要注意的是，此代码与前面C++截取单词的思路有所不同。本程序把每个空格之后的字符作为一个新单词的开始，若前一个字符是空格则判断其后字符是否大写，否则改为大写。


例3.4.8


例3.4.8列出完数（HLOJ 1911）


Problem Description
输入一个整数n，要求输出［1，n］范围内的所有完数。完数是一个正整数，该数恰好等于其所有不同真因子之和。例如，6、28是完数，因为6=1+2+3，28=1+2+4+7+14； 而24不是完数，因为24≠1+2+3+4+6+8+12＝36。
Input
测试数据有多组，处理到文件尾。每组测试数据输入一个整数n（1≤n≤10 000）。
Output
对于每组测试，首先输出n和一个冒号“:”； 然后输出所有不大于n的完数（每个数据之前留一个空格）； 若［1，n］范围内不存在完数，则输出“NULL”。引号不必输出。具体输出格式参考Sample Output。



Sample Input

100

5000

5








Sample Output

100: 6 28

5000: 6 28 496

5: NULL






对于本题，一个很自然的思路是从1到n逐个检查数据，判断一个数的所有真因子之和是否等于该数，是则输出。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int n;

while(cin>>n) {

cout<<n<<":"; 

int cnt=0;                    //计数器清0

for(int k=1;k<=n;k++) {

int sum=0;               //存放k的真因子之和

for(int i=1;i<=k/2;i++) {

if(k%i==0) {

sum=sum+i;

}

}

if(sum==k) {            //k是完数

cout<<" "<<k;      //输出完数 

cnt++;	            //计数器加1

}

}

if(cnt==0)                  //若计数器等于初值0，则表示没有完数

cout<<" NULL";  

cout<<endl; 

}

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int i,k,n,cnt,sum;

while(scanf("%d",&n)!=EOF) { 

printf("%d:",n); 

cnt=0;                         /*计数器清0*/

for(k=1;k<=n;k++) {

sum=0;                    /*存放k的真因子之和*/

for(i=1;i<=k/2;i++) {

if(k%i==0) {

sum=sum+i;

}

}

if(sum==k) {            /*k是完数*/

printf(" %d",k); 

cnt++;	            /*计数器加1*/

}

}

if(cnt==0)                  /*若计数器等于初值0，则表示没有完数*/

printf(" NULL");  

printf("＼n"); 

}

return 0;

}


运行结果： 



10000 

10000: 6 28 496 8128

5↙

5: NULL





上面的代码用计数器控制没有完数时输出NULL，这是一种常用的方法，希望读者熟练掌握。当然，也可以用标记变量（设为flag）的方法，flag初值设为false，若有完数时则把flag的值改为true，最后检查flag的值，若其值为false则输出NULL。另外，若已知6是最小的完数，则可以在n小于6时直接输出NULL。
上面的代码在本地（自己使用的计算机）运行无误。但细心的读者会注意到在输入10 000时，程序运行后需要稍作等待才能得到结果，即程序运行耗时较多。若在线题目的测试数据接近10 000的较多，则提交代码后将得到超时反馈。此时，可以用空间换时间的方法避免超时，即把完数先保存起来，输入数据后再从保存的结果中把答案取出来。从上面代码的运行结果可见，10 000以内的完数仅有4个，即6、28、496、8128，如此相当于结果已经保存，则在输入n时，可以判断n与这4个完数的大小关系输出相应的完数。具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int n;

while(cin>>n) {

cout<<n<<":"; 

if(n<6) cout<<" NULL";  

else if (n<28) cout<<" 6"; 

else if (n<496) cout<<" 6 28"; 

else if (n<8128) cout<<" 6 28 496"; 

else if (n<=10000) cout<<" 6 28 496 8128"; 

cout<<endl;

}

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int n;

while(scanf("%d",&n)!=EOF) { 

printf("%d:",n); 

if(n<6) printf(" NULL");  

else if (n<28) printf(" 6"); 

else if (n<496) printf(" 6 28"); 

else if (n<8128) printf(" 6 28 496"); 

else if (n<=10000) printf(" 6 28 496 8128"); 

printf("＼n");

}

return 0;

}


实际上，空间换时间的方法经常需要使用数组。即一次性先把所有结果保存在数组中，输入数据时再从数组中把相应结果取出来并输出（可能在输出前要稍做处理）。


例3.4.9

例3.4.9组合数（HLOJ 1953）
Problem Description
输入两个正整数n、m，要求输出组合数Cmn。
例如，当n=5、m=2时，组合数C25=(5×4)/(2×1)=10。
Input
测试数据有多组，处理到文件尾。每组测试输入两个整数n，m（0 <m≤n≤20）。
Output
对于每组测试，输出组合数Cmn。



Sample Input


53

20 12








Sample Output

10

125970





本题如果直接使用组合数的公式，分别把分子、分母求出来再相除则需要用unsigned int或long long int类型，否则会产生数据溢出问题。若仅使用int类型，则可以采用程序设计竞赛可能用到的一个小技巧： 循环变量i从1到m进行循环，每次先乘以一个数（n-i+1）再除以一个数（i），具体代码如下。

//C++风格

#include<iostream>

using namespace std;

int main() {

int m,n;

while(cin>>n>>m) {

int c=1;

for(int i=1;i<=m;i++) {

c=c*(n-i+1)/i;

}

cout<<c<<endl; 

}

return 0;

}

/*C风格*/

#include<stdio.h>

int main() {

int c,i,m,n;

while(scanf("%d%d",&n,&m)!=EOF)  {  

c=1;

for(i=1;i<=m;i++) {

c=c*(n-i+1)/i;

}

printf("%d＼n",c); 

}

return 0;

}



例3.4.10

例3.4.10*平均值（HLOJ 1912）
Problem Description
在一行上输入若干整数，每个整数以一个空格分开，求这些整数的平均值。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入一个字符串（仅包含数字字符和空格）。
Output
对于每组测试，输出以空格分隔的所有整数的平均值，结果保留一位小数。



Sample Input

1

1 2 3 4 5 6 7 8 9 10








Sample Output


5.5





由于本题未明确一行上输入几个整数，可以直接用getline输入一个字符串，再根据空格把各个整数字符串分离出来。一种方法是类似于单词分离（参看例3.4.7）的方法取得各整数串再把其转换为整数，这种方法的代码由读者自行实现。另一种方法是使用C++ STL中的串流stringstream（需要包含头文件sstream），用这种方法可以很容易得到各个整数，具体代码如下。

//C++风格

#include<iostream>

#include<string>

#include<sstream>           //串流的头文件 

using namespace std;

int main() {

int T;

cin>>T;

cin.get();              //吸收测试组数后的换行符

while(T--) {

string s;

getline(cin,s);   //输入包含空格的串

stringstream ss;  //定义串流ss

ss<<s;              //把串插入到串流，此处ss类似cout

int t;

int sum=0, cnt=0;

while(ss>>t) {    //从串流中提取以空格分隔的数据，此处ss类似cin

sum+=t;

cnt++;

}

printf("%.1lf＼n",sum*1.0/cnt);

}

return 0;

}


可见，使用stringstream可以方便地取得输入的字符串中以空格分隔的各个数据，方法是先把输入的数据“输出”到串流中，再从串流中“输入”到变量中。另外，可以发现，代码中没有做把数字串转换为整数的工作，因为ss>>t中的t是整型变量，所以得到的结果就是整数。如果要把整数转换为数字串，也可以用串流完成，例如，以下代码把整数123456转换为数字串"123456"。

stringstream ss;

ss<<123456;

string s;

ss>>s;


在线做题时或程序设计竞赛中使用串流有些情况下可以简化编程； 但需要注意的是，串流的执行效率较低。本题也能用C语言处理，有兴趣的读者可以自行完成。
本书前三章的大部分代码同时提供了C风格和C++风格的写法，其目的在于使读者体会在过程化程序设计中C++风格和C风格代码的区别不大，并为读者在需要把后续章节中的C++风格代码转换为C风格代码时提供参考。除了动态内存分配、字符数组等个别章节，本书后续章节不再特意提供C风格的写法，需要的读者可以参考前三章把后续章节的C++代码转换为C风格的写法。在不同的C语言标准下，C风格的代码可能有所不同。若读者拟编写纯粹的C风格代码，为避免在线提交时选择C编译器而导致编译错，建议如下。
（1） 函数中的所有变量都定义在可执行语句之前。
（2） for语句的()中不定义循环变量。
（3） 不使用“//”注释符。
习题
一、 选择题
1. C/C++过程化程序设计的三种基本程序控制结构是()。

A. 顺序结构、选择结构、循环结构
B. 输入、处理、输出
C. for、while、do…while
D. 复合语句、基本语句、空语句
2. 在C/C++语言中，if语句中的else子句总是与()尚无else匹配的if相配对。
A. 缩排位置相同B. 其之前最近C. 其之后最近D. 同一行上
3. 以下代码段的输出结果是（）。

int i=1, j=2;

if (--i && --j)	cout<<i<<" ";

else cout<<j<<" ";

if (++i || ++j) cout<<i<<endl;

else cout<<j<<endl;

A. 1 1B. 1 2C. 2 3 D. 2 1
4. 执行以下代码段后，变量i 的值为（）。

int i=1;

switch (i) {

case 1: i+=10;

case 2: i+=20;

case 3: i++; break;

default: i++; break;

}

A. 11B. 31C. 33D. 32
5. 下面有关for循环的正确描述是()。
A. for循环只能用于循环次数确定的情况
B. for循环先执行循环体语句，后判断循环条件
C. 在for循环中，不能用break语句跳出循环体
D. for循环的循环体可以包含多条语句，但多条语句必须构成复合语句
6. 执行语句“for(s=0,k=0;s<=20||k<=10;k+=2) s+=k;”后，k、s的值为()。
A. 30、12B. 12、30 C. 20、10D. 10、20
7. k、s的当前值为5、0，执行语句“while(k)s+=k;”后，k、s值分别为()。
A. 15、0B. 0、15C. 10、0D. 0、10
8. 关于do…while 循环，以下说法中正确的是()。
A. 循环体语句只能有一条基本语句
B. 在while(循环条件)后面不能写分号
C. 当while后面循环条件的值为false时结束循环
D. 根据情况可以省略while

9. 以下不是无限循环的语句为()。
A. for(y=10,x=1;x<++y;x++);
B. for( ; ; );
C. while(1){x++;}
D. for(i=10;true ;i) sum+=i;
10. 下列代码段中循环体执行的次数为（）。


int k=10; 

while (k=1) k=k-1;


A. 循环体语句一次都不执行B. 循环体语句执行无数次
C. 循环体语句执行一次D. 循环体语句执行9次
二、 OJ编程题
1. 输入输出练习（1）（HLOJ 2096） 
Problem Description
共有T组测试数据，每组测试求n个整数之和。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试先输入数据个数n，然后再输入n个整数，数据之间以一个空格分隔。
Output
对于每组测试，在一行上输出n个整数之和。



Sample Input

2

4 1 2 3 4

5 1 8 3 4 5








Sample Output

10

21






2. 输入输出练习（2）（HLOJ 2097） 
Problem Description
测试数据有多组，处理到文件尾。每组测试求n个整数之和。
Input
测试数据有多组，处理到文件尾。每组测试先输入数据个数n，然后再输入n个整数，数据之间以一个空格分隔。
Output
对于每组测试，在一行上输出n个整数之和。



Sample Input


5 1 8 3 4 5








Sample Output


21





3. 输入输出练习（3）（HLOJ 2098） 
Problem Description
测试数据有多组，每组测试求n个整数之和，处理到输入的n为0为止。
Input
测试数据有多组。每组测试先输入数据个数n，然后再输入n个整数，数据之间以一个空格间隔，当n为0时，输入结束。
Output
对于每组测试，在一行上输出n个整数之和。



Sample Input


5 1 8 3 4 5

0









Sample Output


21






4. 输入输出练习（4）（HLOJ 2099）
Problem Description
求n个整数之和。T组测试，且要求每两组输出之间空一行。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试先输入数据个数n，然后再输入n个整数，数据之间以一个空格分隔。
Output
对于每组测试，在一行上输出n个整数之和，每两组输出结果之间留一个空行。



Sample Input


2

4 1 2 3 4

5 1 8 3 4 5








Sample Output


10



21





5. 电费（HLOJ 2092） 
Problem Description
某电价规定： 月用电量在150kW·h及以下部分按每千瓦时0.4463元收费，月用电量在151~400kW·h的部分按每千瓦时0.4663元收费，月用电量在401kW·h及以上部分按每千瓦时0.5663元收费。
请编写一个程序，根据输入的月用电量（单位kW·h），按该电价规定计算出应缴的电费（单位以元计）。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。对于每组测试，输入一个整数n（0≤n≤10 000），表示月用电量。

Output
对于每组测试，输出一行，包含一个实数，表示应缴的电费。结果保留两位小数。



Sample Input


1

267








Sample Output


121.50





6. 小游戏（HLOJ 2011） 
Problem Description
有一个小游戏，6个人上台去算手中扑克牌点数之和是否5的倍数，据说是小学生玩的。这里稍微修改一下玩法，n个人上台，算手中数字之和是否同时是5，7，3的倍数。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试先输入1个整数n（1≤n≤15），再输入n个整数，每个都小于1000。
Output
对于每组测试，若n个整数之和同时是5，7，3的倍数则输出“YES”，否则输出“NO”。引号不必输出。



Sample Input

2

3 123 27 60

3 2327 6








Sample Output

YES

NO





7. 购物（HLOJ 2012） 
Problem Description
小明购物之后搞不清最贵的物品价格和所有物品的平均价格，请帮他编写一个程序实现。
Input
测试数据有多组，处理到文件尾。每组测试先输入1个整数n（1≤n≤100），接下来的n行中每行输入1个英文字母表示的物品名及该物品的价格。测试数据保证最贵的物品只有1个。
Output
对于每组测试，在一行上输出最贵的物品名和所有物品的平均价格，两者之间留一个空格，平均价格保留1位小数。



Sample Input

3

a 1.8

b 2.5

c 1.5








Sample Output

b 1.9




8. 等边三角形面积（HLOJ 2013） 
Problem Description
数学基础对于程序设计能力而言很重要。对于等边三角形面积，请选择合适的方法计算之。
Input
测试数据有多组，处理到文件尾。每组测试输入1个实数表示等边三角形的边长。
Output
对于每组测试，在一行上输出等边三角形的面积，结果保留两位小数。



Sample Input

1.0

2.0








Sample Output

0.43

1.73





9. 三七二十一（HLOJ 2017） 
Problem Description
某天，诺诺看到三七二十一（3721）数，觉得很神奇，这种数除以3余2，而除以7则余1。例如，8是一个3721数，因为8除以3余2，8除以7余1。现在给出两个整数a、b，求区间［a，b］中的所有3721数，若区间内不存在3721数则输出“none”。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入两个整数a，b（1≤a<b<2000）。
Output
对于每组测试，在一行上输出区间［a，b］中所有的3721数，每两个数据之间留一个空格。如果给定区间不存在3721数，则输出“none”（引号不必输出）。



Sample Input

2

1 7

1 100








Sample Output

none

8 29 50 71 92





10. 胜者（HLOJ 2014） 
Problem Description
Sg和Gs进行乒乓球比赛，进行若干局之后，想确定最后是谁胜（赢的局数多者胜）。
Input
测试数据有多组，处理到文件尾。每组测试先输入一个整数n，接下来的n行中每行输入两个整数a，b（0≤a，b≤20），表示Sg与Gs的比分是a比b。
Output
对于每组测试数据，若还不能确定胜负则输出“CONTINUE”，否则在一行上输出胜者“Sg”或“Gs”。引号不必输出。



Sample Input

3

311

13 11

11 9








Sample Output

Sg




11. 加密（HLOJ 2015） 
Problem Description
信息安全很重要，特别是密码。给定一个5位的正整数n和一个长度为5的字母构成的字符串s，加密规则很简单，字符串s的每个字符变为它后面的第k个字符，其中，k是n的每一个数位上的数字。第一个字符对应n的万位上的数字，最后一个字符对应n的个位上的数字。简单起见，s中的每个字符为ABCDE中的一个。
Input
测试数据有多组，处理到文件尾。每组测试数据在一行上输入非负的整数n和字符串s。
Output
对于每组测试数据，在一行上输出加密后的字符串。



Sample Input

12345 ABCDE







Sample Output

BDFHJ




12. 比例（HLOJ 2016） 
Problem Description
某班同学在操场上排好队，请确定男、女同学的比例。
Input
测试数据有多组，处理到文件尾。每组测试数据输入一个以“.”结束的字符串，串中每个字符可能是“MmFf”中的一个，“m”或“M”表示男生，“f”或“F”表示女生。
Output
对于每组测试数据，在一行上输出男、女生的百分比，结果四舍五入到1位小数。输出形式参照Sample Output。



Sample Input

FFfm.

MfF.








Sample Output

25.0 75.0

33.3 66.7





13. 某校几人（HLOJ 2018） 
Problem Description
某学校教职工人数不足n人，在操场排队，7个一排剩5人，5个一排剩3人，3个一排剩2人； 请问该校人数有多少种可能？最多可能有几人？
Input
测试数据有多组，处理到文件尾。每组测试输入一个整数n（1≤n≤10 000）。
Output
对于每组测试，输出一行，包含两个以一个空格间隔的整数，分别表示该校教职工人数的可能种数和最多可能的人数。



Sample Input

1000







Sample Output

9 908




14. 昨天（HLOJ 2019） 
Problem Description
小明喜欢上了日期的计算。这次他要做的是日期的减1天操作，即求在输入日期的基础上减去1天后的结果日期。
例如，日期为20191001，减去1天，则结果日期为20190930。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入1个日期，日期形式为“yyyymmdd”。保证输入的日期合法，而且输入的日期和计算结果都在［10000101，99991231］范围内。
Output
对于每组测试，在一行上以“yyyymmdd”的形式输出结果。



Sample Input

1

20191001








Sample Output

20190930




15. 直角三角形面积（HLOJ 2020） 
Problem Description
已知直角三角形的三边长，求该直角三角形的面积。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组数据输入3个整数a，b，c，代表直角三角形的三边长。
Output
对于每组测试输出一行，包含一个整数，表示直角三角形面积。



Sample Input

2

3 4 5

3 5 4








Sample Output

6

6






16. 转向三角形（HLOJ 2021） 
Problem Description
输入一个整数n，要求用数字1~n排列出一个转向三角形。例如，n=5时，转向三角形如Sample Output所示。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据输入1个整数n（1≤n≤9）。
Output
对于每组测试数据，输出一个有2n-1行的，由数字1…n…1组成的转向三角形（参看Sample Output）。



Sample Input

1

5








Sample Output

1

22

333

4444

55555

4444

333

22

1





17. 求累加和（HLOJ 2024） 
Problem Description
输入两个整数n和a，求累加和S=a+aa+aaa+…+aa…a（n个a）之值。
例如，当n=5，a=2时，S=2+22+222+2222+22 222=24 690。
Input
测试数据有多组，处理到文件尾。每组测试输入两个整数n和a（1≤n，a<10）。
Output
对于每组测试，输出a+aa+aaa+…+aa…a（n个a）之值。



Sample Input

5 3

8 6








Sample Output

37035

74074068





18. 字符梯形（HLOJ 2022） 
Problem Description
用从m到n的数字字符排列出一个字符梯形。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据输入两个整数m、n（1≤m≤n≤9）。
Output
对于每组测试数据，输出一个有n-m+1行的，由数字m…n排列而成的梯形，每行的长度依次为： m，m+1，m+2，…，n，每行的数字依次是m，m+1，m+2，…，n。



Sample Input

1

3 6








Sample Output

333

4444

55555

666666





19. 菱形（HLOJ 2023） 
Problem Description
输入一个整数n，输出2n-1行构成的菱形，例如，n=5时的菱形如Sample Output所示。
Input
测试数据有多组，处理到文件尾。每组测试输入一个整数n（3≤n≤20）。
Output
对于每组测试数据，输出一个共2n-1行的菱形，具体参看Sample Output。



Sample Input

5







Sample Output


*

***

*****

*******

*********


*******

*****

***

*





20. 水仙花数（HLOJ 2025）
Problem Description
输入两个3位的正整数m，n，输出［m，n］区间内所有的“水仙花数”。所谓“水仙花数”是指一个3位数，其各位数字的立方和等于该数本身。
例如，153是一水仙花数，因为153=1×1×1+5×5×5+3×3×3。
Input
测试数据有多组，处理到文件尾。每组测试输入两个3位的正整数m，n（100≤m<n≤999）。
Output
对于每组测试，若［m，n］区间内没有水仙花数则输出“none”（引号不必输出），否则逐行输出区间内所有的水仙花数，每行输出的格式为： n=a*a*a+b*b*b+c*c*c，其中，n是水仙花数，a、b、c分别是n的百、十、个位上的数字，具体参看Sample Output。



Sample Input

100 150

100 200








Sample Output

none

153=1*1*1+5*5*5+3*3*3





21. 猴子吃桃（HLOJ 2026） 
Problem Description
猴子第一天摘下若干个桃子，当即吃了2/3，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉2/3，又多吃了一个。以后每天早上都吃了前一天剩下的2/3再多吃一个。到第n天早上想再吃时，发现只剩下k个桃子了。求第一天共摘了多少桃子。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组数据输入两个正整数n，k（1≤n，k≤15）。
Output
对于每组测试数据，在一行上输出第一天共摘了多少个桃子。



Sample Input

2

2 1

4 2








Sample Output

6

93





22. 最小回文数（HLOJ 2027） 
Problem Description
若一个数正向看和反向看等价，则称作回文数。例如，6，2552，12321均是回文数。
给出一个正整数n，求比n大的最小的回文数。（n和运算结果均不会超出int类型范围。）
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入1个正整数n。
Output
对于每组测试数据，输出比n大的最小回文数。



Sample Input

2

12

123456








Sample Output

22

124421





23. 分解素因子（HLOJ 2028） 
Problem Description
假设n是一个正整数，它的值不超过1 000 000，请编写一个程序，将n分解为若干个素数的乘积。
Input
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据输入一个正整数n（1< n≤1 000 000）。
Output
每组测试对应一行输出，输出n的素数乘积表示式，式中的素数从小到大排列，两个素数之间用一个“*”表示乘法。若输入的是素数，则直接输出该数。



Sample Input

2

9828

88883








Sample Output

2*2*3*3*3*7*13

88883





24. Fibonacci分数序列（HLOJ 2029） 
Problem Description
求Fibonacci分数序列的前n项之和。Fibonacci分数序列的首项为2/1，后面依次是3/2，5/3，8/5，13/8，21/13…
Input
测试数据有多组，处理到文件尾。每组测试输入一个正整数n（2≤n≤20）。
Output
对于每组测试，输出Fibonacci分数序列的前n项之和。结果保留6位小数。



Sample Input

3

8

15








Sample Output

5.166667

13.243746

24.570091





25. n马n担问题（HLOJ 2030） 
Problem Description
有n匹马，驮n担货，大马驮3担，中马驮2担，两匹小马驮1担，问有大、中、小马各多少匹?（某种马的数量可以为0。）
Input
测试数据有多组，处理到文件尾。每组测试输入一个正整数n（8≤n≤1000）。
Output
对于每组测试，逐行输出所有符合要求的大、中、小马的匹数。要求按大马数从小到大的顺序输出，每两个数字之间留一个空格。



Sample Input

20







Sample Output

1 5 14

4 0 16