程序设计基础

4.1 用格雷戈里公式求$\pi$的近似值

例4-1. 使用格雷戈里公式求$\pi$的近似值

要求精确到最后一项的绝对值小于给定精度eps $$ \frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\ldots $$

4.1.1 程序解析

循环结束条件: |item|<eps
循环条件: |item|>=eps --> fabs(item)>=eps

参照例2-8. 求1-1/3+1/5-...的前n项和

                        
flag=1;
denominator=1;
item=1;
sum=0;

for(i=1;i<=n;i++) /* 替换为while(fabs(item)>=eps) */
{
    sum=sum+item;
    flag=-flag;
    denominator=denominator+2;
    item=flag*1.0/denominator;
}
                        
                    

格雷戈里公式求$\pi$源程序

                        
#include<stdio.h>
#include<math.h>
int main()
{
    int denominator, flag;
    double item, pi;
    flag=1; denominator=1; item=1.0; pi=0;
    while(fabs(item)>=eps)
    {
        pi=pi+item;
        flag=-flag;
        denominator=denominator+2;
        item=flag*1.0/denominator;
    }
    pi=pi+item;
    pi=pi*4;
    printf("pi=%.4f\n", pi);
    return 0;
}
                        
                    

从第1项到倒数第2项，fabs(item)>eps，最后一项fabs(item)<eps

4.1.2 while语句

while(条件)
    循环体语句; /* 一条语句或者多条复合语句 */

注意区分循环体和循环条件

while语句说明

• while和for语句都是在循环前先判断条件
• 将for语句改写成while语句

for(表达式1; 表达式2; 表达式3)
    循环体语句





表达式1;
while(表达式2){
    for的循环体语句;
    表达式3;
}

• 改写的前提是，for的循环体语句中没有使用continue语句

while和for的比较

                            
sum=0;
for(i=1;i<=10;i++)
{
    sum=sum+i;
}
                            
                        

                            
sum=0;
i=1;         /* 循环变量赋初值 */
while(i<=10) /* 循环条件 */
{
    sum=sum+i;
    i++;     /* 循环变量改变值 */
}
                            
                        

统计学生的成绩

例4-2. 从键盘输入一批学生的成绩，计算平均成绩，并统计不及格学生的人数

比较：例3-3. 输入一个正整数n，再输入n个学生的成绩，计算平均分，并统计不及格成绩的个数

                        
total=0;
count=0;
for(i=1;i<=n;i++)
{
    scanf("%lf", &score);
    total=total+score;
    if(score<60)
    {
        count++;
    }
}
                        
                    

如何确定循环条件?

解题分析--统计成绩

确定循环条遥

• 不知道输入数据的个数，无法事先确定循环次数
• 可以用一个特殊的数据作为正常输入数据的结束，比如选用一个负数作为结束标志，比如循环条件是score>=0，可使用score<0作为循环结束条件

程序段设计

从for循环到while循环

                            
total=0;
count=0;
for(i=1;i<=n;i++)
{
    scanf("%lf", &score);
    total=total+score;

    if(score<60)
    {
        count++;
    }
}
                            
                        

                            
num=0;
total=0;
count=0;
scanf("%lf", &score);
while(score>=0)
{
    total=total+score;
    num++;
    if(score<60)
    {
        count++;
    }
    scanf("%lf", &score);
}
                            
                        

统计成绩源程序

                        
#include<stdio.h>
int main()
{
    int count, num;
    double score, total;
    num=0; total=0; count=0;
    printf("Enter score:\n");
    scanf("%lf", &score); /* 输入第1个数 */
    while(score>=0)       /* 输入负数，循环结束 */
    {
        total=total+score;
        num++;
        if(total<60)
        {
            count++;
        }
        scanf("%lf", &score);
    }
    if(num!=0)
    {
        printf("Average: %.2f\n", total/num);
        printf("Number of failures is %d\n", count);
    }else
    {
        printf("Average is 0\n");
    }
    return 0;
}
                        
                    

常见循环控制小结

• 计数控制循环(2.4)

sum=0
for(i=1;i <=n;i++)
    sum=sum+i;

• 计算值控制的循环(例4-1)

item=1.0;
while(fabs(item)>=eps){
    ......
    item=flag*1.0/denominator;
}

• 输入值控制的循环(伪数据)(例4-2)

scanf("%lf", &score);
while(score>=0){
    ......
    scanf("%lf", &score);
}

4.2 统计一个整数的位数

例4-3. 统计一个整数的位数

从键盘读入一个整数，统计该数的位数

4.2.1 程序解析

分析：以495为例，从低位往高位(右向左)，一位一位地数

• 从个位数开始: 第1次数出5(495%10=5)
• 数好一位，就划掉该数字，得到一个新数字49: 495。
  舍去5，得到新数49(495/10=49)
• 继续从新数的个位数开始数：第2次数出9(49%10=9)
• 数好一位，就划掉该数字，再得到一个新数4: 495。
  舍去9，得到新数4(49/10=4)
• 继续从新数的个位数开始数：第3次数出4(4%10=4)
• 数好一位，就划掉该数字，再得到一个新数0: 495。
  舍去4，得到新数0(4/10=0)
• 全部数好，全部划去，遇零结束。共重复3次，得到3位数

算法解析

循环体

                            
count=0;
do{
    digit=number%10;
    number=number/10;
    count++;
}while(number!=0);
                            
                        

                            
count=0;
while(number!=0)
{
    digit=number%10;
    number=number/10;
    count++;
}
                            
                        

思考: 两种循环的区别是什么？

统计位数源程序

while循环

do-while循环

统计位数源程序(1)

                        
#include<stdio.h>
int main()
{
    int count, number;
    printf("Enter a number:");
    scanf("%d", &number);
    if(number<0)
    {
        number=-number;
    }
    count=0;
    do{
        number=number/10;
        count++;
    }while(number!=0);
    printf("It contains %d digits.\n");
    return 0;
}
                        
                    

统计位数源程序(2)

                        
#include<stdio.h>
int main()
{
    int count, number, t_number;
    printf("Enter a number:");
    scanf("%d", &number);
    t_number=number;
    if(t_number<0)      /* 保护输入的数number */
    {
        t_number=-t_number;
    }
    count=0;
    do{
        t_number=t_number/10;
        count++;
    }while(t_number!=0);
    printf("It contains %d digits.\n", count);
    return 0;
}
                        
                    

do-while语句

                        
do{
    循环体语句;
}while(表达式);
                        
                    

while和do-while的比较

while: 先判别条件，再决定是否循环

do-while: 先至少循环一次，然后再根据条件决定是否继续循环

将一个整数逆序输出

例4-4. 将一个整数逆序输出

确定循环条件和循环体(循环不变体)，取12345为例，需得到5 4 3 2 1

循环不变式:
  digit=number%10;
  number=number/10;
循环结束条件:
  number==0;

整数逆序输出源程序

#include<stdio.h>
int main()
{
    int number;
    printf("Enter a number:");
    scanf("%d", &number);
    do{
        printf("%d ", number%10);
        number=number/10;
    }while(number!=0);
    return 0;
}
                    

4.3 判断素数

例4-5. 判断素数

输入一个正整数m，判断它是否为素数。素数指的是只能被1和自身整除的正整数，1不是素数，2是素数

4.3.1 程序解析

判断素数的依据：除了1和m，不能被其它数整除
设i取值范围在[2, m-1]之间，有

• 如果m不能被该区间上的任何一个整数整除，即对每个i，m%i都不为0，则m是素数
• 只要能找到一个i，有m%i=0，则m必不是素数

m不可能被大于m/2的整数整除
i的取值可能有
[2,m-1], [2, m/2], [2, $\sqrt{m}$], [2, $\sqrt{m}+1$]

4.3.1 程序解析

                        
limit=sqrt(m)+1; /* 考虑浮点数运算误差 */
for(i=2; i<=limit; i++)
{
    if(m%i==0)
        break;
}
if(i>m/2)
    printf("yes\n");
else
    printf("no\n");
                        
                    

判断素数源程序

                        
#include<stdio.h>
#include<math.h>
int main()
{
    int m, limit, i;
    printf("Enter a number:");
    scanf("%d", &m);
    if(m<=1)
        printf("no\n");
    else if(m==2)
        printf("yes\n");
    else
    {
        limit=sqrt(m)+1;
        for(i=2; i<=limit; i++)
        {
            if(m%i==0)
                break;
        }
        if(i>limit)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}
                        
                    

4.3.2 break语句

                            
while(expa){
    语句1;
    if(expb)
        break;
    语句2;
}
                            
                        

                                
for(i=2; i<=limit; i++)
    if(m%i==0) break;
if(i>limit) print("yes\n");
else printf("no\n");
                                
                            

练习--输出结果是什么

                        
for(i=2; i<=limit; i++)
  if(m%i==0) break;
if(i>limit) print("yes\n");
else printf("no\n");
                        
                    

Enter a number: 9
no

                            
for(i=2; i<=limit; i++)
if(m%i==0){
    printf("no\n");
    break;
}
printf("yes\n");
                            
                        

                            
for(i=2; i<=limit; i++)
{
    if(m%i==0) printf("no\n");
    else printf("yes\n");
}
                            
                        

continue语句

                            
while(expa)
{
    语句1;
    if(expb)
        continue;
    语句2;
}
                            
                        

break和continue

下述代码的输出结果是什么?

                        
#include<stdio.h>
int main()
{
    char c;
    int i;
    for(i=0; i<10; i++)
    {
        c=getchar();
        if(c=='\n')
            continue;
        putchar(c);
    }
}
                        
                    

输入: abc<Enter>efgh<Enter>123<Enter>
输出的字符: abcefgh1

for和while的差异--continue

输出100~200之间所有能被3整除的数

                            
for(i=100; i<=200; i++)
{
    if(i%3==0)
        printf("%d ", i);
}
                            
                        

                            
for(i=100; i<=200; i++)
{
    if(i%3!=0)
        continue;
    printf("%d ", i);
}
                            
                        

                            
i=100;
while(i<=200)
{
    if(i%3!=0)
        continue;
    printf("%d ", i);
    i++;
}
                            
                        

for和while等价的前提是, for的循环语句中没有使用continue

改写猜数游戏

例4-6. 改写例3-1的简单猜数游戏，输入你所猜的整数(规定为1~100)，与计算机产生的被猜数比较，若相等，显示猜中；若不等，显示与被猜数的大小关系，最多允许猜7次

改写猜数游戏--版本(!)

                        
#include<stdio.h>
int main()
{
    int count=0, flag, mynumber, yournumber;
    mynumber=38;  /* 计算机指定被猜的数 */
    flag=0;       /* flag为0表示没猜中，1表示猜中 */
    while(count<7)
    {
        printf("Enter your number:");
        scanf("%d", yournumber);
        count++;
        if(yournumber==mynumber)  /* 若相等，显示猜中 */
        {
            printf("Lucky you!\n");
            flag=1;
            break;      /* 已猜中，终止循环 */
        }else if(yournumber>mynumber)
        {
            printf("Too big!\n");
        }else
        {
            print("Too small\n");
        }
    }
    if(flag==0)    /* 超过7次还没猜中，提示游戏结束 */
        printf("Game Over!\n");
    return 0;
}
                        
                    

改写判断素数程序

                        
#include<stdio.h>
#include<math.h>
int main()
{
    int m, limit, i, flag;
    printf("Enter a number:");
    scanf("%d", &m);
    if(m<=1)
        flag=0;
    else if(m==2)
        flag=1;
    else
    {
        flag=1;
        limit=sqrt(m)+1;
        for(i=2; i<=limit; i++)
        {
            if(m%i==0)
            {
                flag=0;
                break;
            }
        }
        if(flag==1)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}
                        
                    

改写猜数游戏--版本(2)

                        
#include<stdio.h>
#include<time.h>
int main()
{
    int count=0, flag=0, mynumber, yournumber;
    srand(time(0));
    mynumber=rand()%100+1; /* 随机产生一个1~100之间的被猜数 */
    while(count<7)
    {
        printf("Enter your number:");
        scanf("%d", yournumber);
        count++;
        if(yournumber==mynumber)  /* 若相等，显示猜中 */
        {
            printf("Lucky you!\n");
            flag=1;
            break;      /* 已猜中，终止循环 */
        }else if(yournumber>mynumber)
        {
            printf("Too big!\n");
        }else
        {
            print("Too small\n");
        }
    }
    if(flag==0)    /* 超过7次还没猜中，提示游戏结束 */
        printf("Game Over!\n");
    return 0;
}
                        
                    

4.4 求1!+2!+...+n!

例4-7. 使用函数求阶乘和

输入一个正整数n(n≤16)，计算1!+2!+3!+...+n!。要求定义和调用函数fact(n)计算n的阶乘，如果n是非负数，则该函数返回n的阶乘，否则返回0

4.4.1 程序解析

                        
#include<stdio.h>
double fact(int n);
int main()
{
    int i, n;
    double sum;
    printf("Enter n:");
    scanf("%d", &n);
    sum=0;
    for(i=1; i<=n; i++)
        sum=sum+fact(i);
    printf("sum=%.0f\n", sum);
    return 0;
}
double fact(int n)
{
    int i;
    double result;

    if(n<0)
        return 0;
    result=1;
    for(i=1; i<=n; i++)
        result=result*i;
    return result;
}
                        
                    

嵌套循环

求阶乘的循环:

                        
item=1;
for(i=1; i<=n; i++)
    item=item*i;
                        
                    

循环求阶乘加和

                        
sum=0;
for(i=1; i<=n; i++)
{
    item=1;              /* 每次求阶乘都从1开始乘 */
    for(j=1; j<=i; j++)  /* 内层循环算出item=i! */
    {                    /* 注意内外层循环用不同的变量控制 */
        item=item*j;
    }
    sum=sum+item;
}
                        
                    

讨论--内层循环的初始化

求1!+2!+3!+...+n!

                            
sum=0;
for(i=1; i<=n; i++)
{
    item=1;
    for(j=1; j<=i; j++)
    {
        item=item*j;
    }
    sum=sum+item;
}
                            
                        

                            
sum=0;
item=1;
for(i=1; i<=n; i++)
{
    for(j=1; j<=i; j++)
    {
        item=item*j;
    }
    sum=sum+item;
}
                            
                        

分析嵌套循环的执行过程

                        
sum=0;
for(i=1; i<=n; i++)
{
    item=1;
    for(j=1; j<=i; j++)
    {
        item=item*j;
    }
    sum=sum+item;
}
                        
                    

第2-10行，外层循环变量i的每个值，内层循环变量第5-8行都要变化一个完整的轮次
内外层循环变量的名字不能相同，分别用i和j

练习

以下代码片段运行结果是什么?内层循环总共执行了多少次?

                        
for(i=1; i<=100; i++)
{
    for(j=1; j<=i; j++)
    {
        printf("%d %d\n", i, j);
    }
}
                        
                    

4.5 循环结构程序设计

• 循环程序的实现要点
• 归纳出哪些操作需要反复执行? 执行体
• 这些操作在哪些情况下重复执行? 循环条件
• 常见的循环控制方式
• 计数控制、计算值控制、输入值控制
• 多重控制(计数控制+计算值控制, ......)

常见的循环控制方式

• 计数控制：2.4，例4-6, 4-7, 4-9, 4-11, 4-12

sum=0;
for(i=1; i <=n; i++){
    sum=sum+fact(i);
}

• 计算值控制：例4-1, 4-3, 4-4

item=1.0;
while(fabs(item)>=0.0001){
    item=flag*1.0/denominator;
    ......
}

• 输入值控制为主：例4-2, 4-8

scanf("%lf", &score);
while(score>=0){
    ......
    scanf("%lf", &score);
}

• 计数控制+计算值控制：例4-5, 4-6, 4-10

循环语句的控制

• 主要考虑因素：循环控制方式
• 事先给定循环次数，首选for
• 通过其它条件控制循环，考虑while或do-while
• 如果循环条件在进入循环时明确，可选用while循环
• 如果循环条件需要在循环体中明确，则使用do-while语句

求学生成绩最高分

例4-8. 求最值问题

输入一批学生的成绩，找出最高分

求学生成绩最高分(for实现)

                        
#include<stdio.h>
int main()
{
    int i, mark, max, n;
    printf("Enter n:");
    scanf("%d", &n);
    printf("Enter %d marks:", n);
    scanf("%d", &mark);    /* 读入第一个成绩 */
    max=mark;      /* 假设第一个成绩是最高分 */
    for(i=1; i<=n; i++)
    {
        scanf("%d", &mark);
        if(mark>max)
            max=mark;
    }
    printf("max=%d\n", max);
    return 0;
}
                        
                    

求学生成绩最高分(while实现)

以"-1"作为成绩输入的结束

                        
#include<stdio.h>
int main()
{
    int mark, max;
    printf("Enter marks:");
    scanf("%d", &mark);    /* 读入第一个成绩 */
    max=mark;      /* 假设第一个成绩是最高分 */
    while(mark>=0)
    {
        if(mark>max)
            max=mark;
        scanf("%d", &mark);
    }
    printf("max=%d\n", max);
    return 0;
}
                        
                    

求学生成绩最高分(do-while实现)

                        
#include<stdio.h>
int main()
{
    int mark, max;
    max=-1; /* 给max赋一个小初值 */
    printf("Enter marks:", n);
    do{
        scanf("%d", &mark);
        if(mark>max)
            max=mark;
    }while(mark>=0);
    printf("max=%d\n", max);
    return 0;
}
                        
                    

Fibonacci数列问题

例4-9. 斐波那契问题

输入正整数n(1≤n≤46)，输出斐波那契(Fibonacci)数列的前n项：1, 1, 2, 3, 5, 8, 13, ..., 每行输出5个。Fibonacci数列就是满足任一项数字是前两项的和(最开始的两项均定义为1)的数列

                        
x1=x2=1;
x=x1+x2;
x1=x2;
x2=x;
                        
                    

Fibonacci数列问题源程序

                        
#include<stdio.h>
int main()
{
    int i, n, x1, x2, x;  /* x1和x2分别代表前两项，x是其后一项 */
    printf("Enter n:");
    scanf("%d", &n);
    if(n<1 || n>46)
    {
        printf("Invalid.\n");
    }
    else if(n==1)
    {
        printf("%10d", 1);    /* 输出第1项 */
    }
    else
    {
        x1=1; x2=1;
        printf("%10d%10d", x1, x2);  /* 先输出前两项 */
        for(i=3; i<=n; i++)      /* 循环输出后n-2项 */
        {
            x=x1+x2;             /* 计算新项 */
            printf("%10d", x);
            if(i%5==0)
                printf("\n");
            x1=x2;
            x2=x;
        }
    }
    return 0;
}
                        
                    

素数问题

例4-10. 素数问题

输入2个正整数m和n(1≤m≤n≤500)，输出m到n之间的全部素数，每行输出10个。素数就是只能被1和自身整除的正整数，1不是素数，2是素数

                        
for(k=m; k<=n; k++)
    if(k是素数)
        printf("%d", k);
                        
                    

素数问题解析

判断k是否为素数

                        
if(k<=1)
    flag=0;
else if(k==2)
    flag=1;
else{
    flag=1;
    limit=sqrt(k)+1;
    for(i=2; i<=limit; i++){
        if(k%i==0){
            flag=0;
            break;
        }
    }
}
if(flag==1)
    printf("%d", k);
                        
                    

素数问题源程序

                        
#include<stdio.h>
#include<math.h>
int main()
{
    int count, i, k, flag, limit, m, n;
    printf("Enter m, n");
    scanf("%d%d", &m, &n);
    count=0;
    if(m<1 || n>500 || m<n)
        printf("Invalid\n");
    else{
        for(k=m; k<=n; k++){
            if(k<=1)
                flag=0;
            else if(k==2)
                flag=1;
            else{
                flag=1;
                limit=sqrt(k)+1;
                for(i=2; i<limit; i++){
                    if(k%i==0){
                        flag=1;
                        break;
                    }
                }
            }
            if(flag==1){
                printf("%d", k);
                count++;
                if(count%10==0)
                    printf("\n");
            }
        }
    }
    return 0;
}
                        
                    

搬砖问题

例4-11. 搬砖问题

某工地需要搬运砖块，书籍男人一人搬3块，女人一人搬2块，小孩两人搬一块。如果想用n人正好搬n块砖，问有哪些搬法?

搬砖问题源程序(1)

                        
#include<stdio.h>
int main()
{
    int children, men, women, cnt, n;
    printf("Enter n:");
    scanf("%d", &n);
    cnt=0;
    for(men=0; men<=n; men++){
        for(women=0; women<=n; women++){
            for(children=0; children<=n; children++){
                if(men+women+children==n && men*3+women*2+children*0.5==n){
                    printf("men=%d, women=%d, children=%d", men, women, children);
                    cnt++;
                }

            }
        }
    }
    if(cnt==0){
        printf("None\n");
    }
    return 0;
}
                        
                    

搬砖问题源程序(2)

                        
#include<stdio.h>
int main()
{
    int children, men, women, cnt, n;
    int men_limit, women_limit;
    printf("Enter n:");
    scanf("%d", &n);
    cnt=0;
    men_limit=n/3;
    women_limit=n/2;
    for(men=0; men<=men_limit; men++){
        for(women=0; women<=women_limit; women++){
            children=n-men-women;
            if(men+women+children==n && men*3+women*2+children*0.5==n){
                printf("men=%d, women=%d, children=%d", men, women, children);
                cnt++;
            }
        }
    }
    if(cnt==0){
        printf("None\n");
    }
    return 0;
}
                        
                    

找零钱问题

例4-12. 找零钱问题

有足够数量的5分、2分和1分硬币，现在要用这些硬币来支付一笔小于1元的零钱money，问至少要用多少个硬币？输入零钱，输出硬币的总数量和相应面额的硬币数量

硬币总数最小，优先考虑使用面值大的硬币
采用三重循环嵌套，按照5分、2分和1分的顺序，从上限(money/币值)到下限(0)

找零钱问题源程序

                        
#include<stdio.h>
int main()
{
    int flag, money, n1, n2, n5; /* n1, n2, n5分别表示5分、2分和1分硬币的数量 */

    flag=1;  /* 表示是否中止嵌套循环 */
    printf("Enter money:");
    scanf("%d", &money);
    for(n5=money/5; (n5>=0)&&(flag==1); n5--){
        for(n2=(money-n5*5)/2; (n2>=0)&&(flag==1); n2--){
            for(n1=money-n5*5-n2*2;(n1>=0)&&(flag==1); n1--){
                if(n5*5+n2*2+n1==money){
                    printf("n5: %d, n2: %d, n1: %d\n, total: %d", n5, n2, n1, n1+n2+n5);
                    flag=0;
                }
            }
        }
    }
    return 0;
}