作弊是否很有诱惑性? 上堂课已经讲了 作业不一定在两个小时里都能完成 答疑没有一个人？ 作弊是有记录的 心理系很多同学集体作弊，让人震惊 下次再让抓到作弊，就不客气了 作业不一定在两个小时里都能完成 答疑没有一个人？

C语言高级编程（第一部分） 数组与算法 I 北京大学 信息科学技术学院

关于 宏

#define PI 3.14159 形式： 宏名 宏体 作用与意义 1.在源程序中，用简单的宏名 指代 复杂的宏体 2.程序更加直观 （一般用大写， 以区别一般变量） 宏体 （可以是一个复杂的表达式） 作用与意义 1.在源程序中，用简单的宏名 指代 复杂的宏体 2.程序更加直观

#define PI 3.14159 形式： 注意： 1.#define 可出现在程序的任一行 2.宏的作用范围：由 宏定义开始 到 程序末尾 之间的区域 3.宏定义不是C语句，不必在行尾加分号

S的值是多少？ #define PI 3.141593; #include <stdio.h> int main( )｛ double S; S = PI - PI; printf(“%lf\n”, S); return 0; ｝ S的值是多少？

按下build后 … … 源文件 二进制代码 预编译 编译 连接 没有宏的源文件 可执行程序

预编译 把源程序中的所有 PI 替换为 3.141593; 没有宏的 源文件 源文件 #define PI 3.141593; int main( )｛ double S; S = PI - PI; return 0; ｝ int main( )｛ double S; S = 3.141593; - 3.141593;; return 0; ｝

int main( )｛ double S; S = 3.141593; - 3.141593; ; return 0; ｝

✓ ✕ 错误: 使用 宏 定义常量时，在结尾加 ; #define PI 3.14159; #define PI 3.14159 错误: 使用 宏 定义常量时，在结尾加 ; #define PI 3.14159; int main( )｛   return 0; ｝ #define PI 3.14159 int main( )｛   return 0; ｝ ✓ ✕

宏定义其他例子： //整数常量 #define MAX 200

几个 例子

程序填空，要求： 输出的两个数值按照 从小到大 的顺序排列 #include <stdio.h> int main(){ int a, b; int e; scanf("%d", &a); scanf("%d", &b); …… printf("%d %d\n", a, b); return 0; } 程序填空，要求： 输出的两个数值按照 从小到大 的顺序排列

#include <stdio.h> int main(){ int a, b; int e; scanf("%d", &a); scanf("%d", &b); if(a > b){ e = a; a = b; b = e; } printf("%d %d\n", a, b); return 0;

程序填空，要求： 输出的3个数值按照 从小到大 的顺序排列 #include <stdio.h> int main(){ int a, b, c; int e; scanf("%d", &a); scanf("%d", &b); scanf("%d", &c); …… printf("%d %d\n", a, b, c); return 0; } 程序填空，要求： 输出的3个数值按照 从小到大 的顺序排列

#include <stdio.h> int main(){ int a, b, c; int e; scanf("%d", &a); scanf("%d", &b); scanf("%d", &c); if(a > b){ e = a; a = b; b = e; } if(b > c){ e = b; b = c; c = e; if(a > b){ e = a; a = b; b = e; } printf("%d %d %d\n", a, b, c); return 0;

如果要求： 难道需要这样定义10个变量吗？ int a, b, c, d, e, f, g, h, i, j; 如果要输入更多的数值呢？！ 1. 接收用户输入的10个数值 2. 输出的10个数值按照 从小到大 的顺序排列 难道需要这样定义10个变量吗？ int a, b, c, d, e, f, g, h, i, j; 如果要输入更多的数值呢？！ 有没有一种 更简便的方式， 可以一次定义一组变量？

数组

数组 是 什么？ 数组 是 一组变量 数组 是 一组 类型相同 的变量 数组 是 一组 具有编号 的、类型相同 的变量

如何声明 一个数组 必须是一个常量 int sz[10]; 数组的类型 数组名 数组中变量的数目

int sz[10]; 数组 中 变量 的 编号 数组中变量的编号 从 0 开始； 到 数组的长度－1 结束 0 1 2 3 4 5 6 7 8 9 数组中变量的编号 从 0 开始； 到 数组的长度－1 结束

…sz[2]…; 如何访问 数组 中 的 变量 变量编号 数组名 int sz[10]; sz[0] = 1; sz[1] = 3;

数组变量赋值 的 一种特殊方式 声明时赋值 int sz[5] =｛12, 3, 7, 28, -2｝;

int sz[10]; int i; … i =…; sz[i] = … 访问 数组中 变量的一种常见方式 int sz[10]; int i; … i =…; sz[i] = … i 的值可以根据需要变化

; } 程序填空，要求： 1.接收用户输入的10个数字 2.存放在数组sz中 #include <stdio.h> int main(){ int sz[10]; int i; for( ; ; ){ ; } for(i = 0; i < 10; i++){ printf("%d ", sz[i]); return 0; 程序填空，要求： 1.接收用户输入的10个数字 2.存放在数组sz中

for( i=0 ; i < 10 ; i++){ scanf("%d", &(sz[i])); } #include <stdio.h> int main(){ int sz[10]; int i; for( i=0 ; i < 10 ; i++){ scanf("%d", &(sz[i])); } for(i = 0; i < 10; i++){ printf("%d ", sz[i]); return 0;

数组 的 遍历 通过 循环结构

正向 遍历 #define LEN 10 int sz[LEN]; for(int i = 0; i < LEN; i++){ … sz[i] … }

反向 遍历 #define LEN 10 int sz[LEN]; for(int i = LEN-1; i >= 0; i--){ … sz[i] … }

#define LEN 10 int sz[LEN]; 通过遍历 实现 对 数组变量 的 控制台赋值 通过遍历 实现 对 数组变量 的 控制台赋值 #define LEN 10 int sz[LEN]; for(int i = 0; i < LEN; i++){ scanf(“%d”, &(sz[i])); }

#define LEN 10 int sz[LEN]; 通过遍历 实现 对 数组变量 的 控制台输出 通过遍历 实现 对 数组变量 的 控制台输出 #define LEN 10 int sz[LEN]; for(int i = 0; i < LEN; i++){ printf(“%d\n”, sz[i]); }

当程序要处理 一组类型相同、含义类似的数据时， 应该使用数组 数组 的 应用示例 当程序要处理 一组类型相同、含义类似的数据时， 应该使用数组

游戏：过年抽奖 村长邀请我们编写一个程序， 实现村里财政盈余的自动分配 一个村庄，有128个村民 村长对村民说： 游戏规则如下： 今年村里出现了财政盈余M元； M是2000－3000之间的一个整数 准备通过抽奖的方式把钱发给村民 游戏规则如下： 每个村民上报一个在2000－3000元之间的整数 如果有人上报的数字和M相等，就把钱发给这些人 如果只有一个村民猜对，就把M元钱全部发给他 如果有多个人村民猜对，就把M元钱平均分配给这些村民 如果没有人猜对，财政盈余转为下年度开支 村长邀请我们编写一个程序， 实现村里财政盈余的自动分配

编程的基本思路 定义一个数组 存放所有村民上报的数据 定义一个数组 存放获奖者的编号（幸运者数组） 定义一个整数 存放获奖者人数 对村民从0开始编号（最后一个编号是127） 村民按照编号顺序上报数字；程序将村民上报的数字存放在对应编号的数组变量中。 遍历村民上报的数字，若上报数字与幸运数相等，则 将村民编号 按顺序 添加到幸运者数组中； 并将获奖者人数加1 最后，打印出获奖者编号和获得的奖金数额

#define LUCKY_M 2345 //财政盈余 #define POPULATION 128 //村民数量 int main( ){ int people[POPULATION]; //记录所有村民上报数字的数组 int luckyPeople[POPULATION]; //幸运者数组，记录获奖者编号，为什么和村民一样多？ int i, nLucky=0; //循环变量，获奖者人数 for (i=0; i<POPULATION; i++) { scanf(“%d”, &(people[i])); //读入村民报的数字，数组下标就是村民的编号 } if ( people[i] == LUCKY_M ) { luckyPeople[nLucky] = i; nLucky ++; if (nLucky > 0){ for (i=0; i<nLucky; i++){ //输出获奖者编号及所获奖金数额 printf("%d %d\n", luckyPeople[i], LUCKY_M / nLucky); return 0; return -1;

显然，不能采用简单的比较。 需要有更有效的方法。 冒泡排序法 选择排序法 利用 数组， 对一组数据 进行排序 显然，不能采用简单的比较。 需要有更有效的方法。 冒泡排序法 选择排序法

排序的基本方法 如何把大象关在冰箱里? 分3步： 第一步：打开冰箱门; 第二步：把大象推进冰箱; 第三步：关上冰箱门;

int sz[LEN]; //＃define LEN 8 排序的基本方法 7 11 18 分8个步骤进行 第1步：把第1大的数放在变量sz[7]中； 第2步：把第2大的数放在变量sz[6]中； 第3步：把第3大的数放在变量sz[5]中； 第4步：把第4大的数放在变量sz[4]中； 第5步：把第5大的数放在变量sz[3]中； 第6步：把第6大的数放在变量sz[2]中； 第7步：把第7大的数放在变量sz[1]中； 第8步：把第8大的数放在变量sz[0]中； 6 12 17 5 13 16 4 17 15 3 18 14 2 14 13 1 15 12 16 11 编号 排序前 的值 排序后 的值

排序的基本方法 int sz[LEN]; //＃define LEN 8 抽象 分8个步骤进行 LEN个数，分LEN个步骤进行 … 第LEN步：把第LEN大的数放在变量sz[LEN-LEN]中； 抽象

排序的基本方法 LEN个数，分LEN个步骤进行 第1步：把第1大的数放在变量sz[LEN-1]中； … 第LEN步：把第LEN大的数放在变量sz[LEN-LEN]中；

排序的基本方法 （K=1, 2, 3, 4, …, LEN-1, LEN） 对数组 int sz[LEN]进行排序， 第 k 步：把第 k 大的数放在变量 sz[LEN-k] 中； （K=1, 2, 3, 4, …, LEN-1, LEN）

用 冒泡法 作第1步： 把第1大的数放在变量sz[LEN-1]中； int e; for(int i = 0; i < LEN - 1; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 作第2步： 把第2大的数放在变量sz[LEN-2]中； int e; for(int i = 0; i < LEN - 2; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 作第3步： 把第3大的数放在变量sz[LEN-3]中； int e; for(int i = 0; i < LEN - 3; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

把第k大的数放在变量sz[LEN-k]中； int e; for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 对 数组 int sz[LEN] 进行排序 int e; for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 对 数组 int sz[LEN] 进行排序 int e; for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 对 数组 int sz[LEN] 进行排序 int e; for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 对 数组int sz[LEN] 进行排序 int e; for(;;){ for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 对 数组 int sz[LEN] 进行排序 int e; for(int k = ; k <= ; k++){ for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 对 数组 int sz[LEN] 进行排序 int e; for(int k = 1 ; k <= ; k++){ for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 对 数组 int sz[LEN] 进行排序 int e; for(int k = 1 ; k <= LEN ; k++){ for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

用 冒泡法 对 数组 int sz[LEN] 进行排序 int e; for(int k = 1 ; k <= LEN ; k++){ for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; } 对该算法进行测试 编写一个程序： 1.从控制台输入一组 数据，并将其存放 一个数组中； 2.用左侧算法进行排 序； 3.打印出排序结果；

选择 排序法

排序的基本方法 （K=1, 2, 3, 4, …, LEN-1, LEN） 对数组 int sz[LEN]进行排序， 第 k 步：把第 k 大的数放在变量 sz[LEN-k] 中； （K=1, 2, 3, 4, …, LEN-1, LEN）

用 选择法 作 第1步：把第1大的数放在变量sz[LEN-1]中； int maxIndex, e; maxIndex = 0; for(int i = 0; i <= LEN-1; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-1){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-1]; sz[LEN-1] = e;

用 选择法 作 第2步：把第2大的数放在变量sz[LEN-2]中； int maxIndex, e; maxIndex = 0; for(int i = 0; i <= LEN-2; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-2){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-2]; sz[LEN-2] = e;

用 选择法 作 第3步：把第3大的数放在变量sz[LEN-3]中； int maxIndex, e; maxIndex = 0; for(int i = 0; i <= LEN-3; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-3){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-3]; sz[LEN-3] = e;

用 选择法 作 第k步：把第k大的数放在变量sz[LEN-k]中； int maxIndex, e; maxIndex = 0; for(int i = 0; i <= LEN-k; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-k){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-k]; sz[LEN-k] = e;

用 选择法 对 数组 int sz[LEN] 进行排序； int maxIndex, e; maxIndex = 0; for(int i = 0; i <= LEN-k; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-k){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-k]; sz[LEN-k] = e;

用 选择法 对 数组 int sz[LEN] 进行排序； int maxIndex, e; maxIndex = 0; for(int i = 0; i <= LEN-k; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-k){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-k]; sz[LEN-k] = e;

用 选择法 对 数组 int sz[LEN] 进行排序； int maxIndex, e; maxIndex = 0; for(int i = 0; i <= LEN-k; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-k){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-k]; sz[LEN-k] = e;

用 选择法 对 数组 int sz[LEN] 进行排序； int maxIndex, e; for(;;){ maxIndex = 0; for(int i = 0; i <= LEN-k; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-k){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-k]; sz[LEN-k] = e;

用 选择法 对 数组 int sz[LEN] 进行排序； int maxIndex, e; for(int k = ; k <= ; k++){ maxIndex = 0; for(int i = 0; i <= LEN-k; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-k){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-k]; sz[LEN-k] = e;

用 选择法 对 数组 int sz[LEN] 进行排序； int maxIndex, e; for(int k = 1 ; k <= LEN; k++){ maxIndex = 0; for(int i = 0; i <= LEN-k; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-k){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-k]; sz[LEN-k] = e;

用 选择法 对 数组 int sz[LEN] 进行排序； int maxIndex, e; for(int k = 1 ; k <= LEN; k++){ maxIndex = 0; for(int i = 0; i <= LEN-k; i++){ if(sz[i] > sz[maxIndex]){ maxIndex = i; } if(maxIndex != LEN-k){ e = sz[maxIndex]; sz[maxIndex] = sz[LEN-k]; sz[LEN-k] = e; 对该算法进行测试 编写一个程序： 1.从控制台输入一组 数据，并将其存放 一个数组中； 2.用左侧算法进行排 序； 3.打印出排序结果；

一些问题的程序求解

问题1： 判断某一年份是否是闰年

什么是闰年？ 闰年的充分必要条件是： “年份能被400整除” 或者 “年份能被4整除，但不能被100整除”

int main(){ int year; scanf(“%d”, &year); if(year%400 == 0 ||(year%4==0 && year%100!=0)){ printf(“%d is RuiNian.”, year); } else{ printf(“%d not RuiNian.”, year); } return 0;

判断闰年的函数 int isRunNian(int year){ int result; if(year%400 == 0 ||(year%4==0 && year%100!=0)){ result = 1; } else{ result = 0; } return result;

问题2： 给定一个年月日， 判断这一天是这一年的第几天

求解思路 step1: step2： step3： 将该日所在月份之间的所有月份的天数加起来； 并存入一个变量中； 将该日的日期号加入这个变量中； step3： 输出该变量；

int main(){ int year, month, day, total; scanf(“%d %d %d”, &year, &month, &day); total = 0; for(int i = 1; i < month; i++){ //step1 if(i==1||i==3||i==5||i==7||i==8||i==10||i==12){ total += 31; } else if (i == 4 || i ==6 || i == 9 || i==11){ total += 30; } else if(i == 2){ if(isRunNian(year)){ total += 29; } else { total += 28; } total += day; //step2 printf(“%d\n”, total); //step3 return 0;

求解某一日期是当年的第几天的函数 int DiJiTian(int year, int month, int day){ int result = 0; for(int i = 1; i < month; i++){ //step1 if(i==1||i==3||i==5||i==7||i==8||i==10||i==12){ result += 31; } else if (i == 4 || i ==6 || i == 9 || i==11){ result += 30; } else if(i == 2){ if(isRunNian(year)){ result += 29; } else { result += 28; } result += day; //step2 return result;

1. 假设细菌的数量每天成倍增长 2. 给定一个 开始日期 和 细菌数量 3. 给定一个 终止日期 求终止日期时的细菌数量 问题3： 计算细菌数量 1. 假设细菌的数量每天成倍增长 2. 给定一个 开始日期 和 细菌数量 3. 给定一个 终止日期 求终止日期时的细菌数量

求解思路 step1: 计算 开始日期 和 终止日期 之间的天数； step2: 计算细菌数量； step3: 打印出细菌数量；

int main(){ int year, m1, d1, num, m2, d2; scanf(“%d %d %d %d %d %d”, &year, &m1, &d1, &num, &m2, &d2); int days = DiJiTian(year, m2, d2) - DiJiTian(year, m1, d1); int result = num; for(int i = 0; i <= days; i++){ result *= 2; } printf(“%d\n”, result); return 0;

课堂作业 编写程序，实现下述功能： 1, 从控制台输入 两个 年 月 日 2，调用 DiJiTian函数计算这两个日期之间 相隔几天 1, 从控制台输入 两个 年 月 日 2，调用 DiJiTian函数计算这两个日期之间 相隔几天 3，向控制台输出结果 请同学们拿出笔和纸， 1. 写下 姓名和学号； 2. 写下 满足上述要求的程序；