第四章 函数和递归.

Presentation on theme: "第四章 函数和递归."— Presentation transcript:

1 第四章 函数和递归

2 4.1 自定义函数和结构体 计算两点欧几里德距离的函数 返回类型 函数名(参数列表) { 函数体 }
4.1 自定义函数和结构体 计算两点欧几里德距离的函数 double dist(double x1, double y1, double x2, double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } 返回类型 函数名(参数列表) { 函数体 } 函数体的最后一条语句应该是“return 表达式；”

3 4.1 自定义函数和结构体 struct 结构体名称{ 域定义 } 一个函数也可以调用其他函数
4.1 自定义函数和结构体 struct Point{ double x, y; }; double dist(struct Point a, struct Point b) { return hypot(a.x-b.x, a.y-b.y); } struct 结构体名称{ 域定义 } 一个函数也可以调用其他函数

4 4.1 自定义函数和结构体 问题：计算组合数 编写函数，参数是两个非负整数n和m，返回组合数 ，其中m≤n≤25。 例如，n=25，m=12时答案为

5 4.1 自定义函数和结构体 程序4-1 组合数（有问题）
4.1 自定义函数和结构体 程序4-1 组合数（有问题） long long factorial(int n){ long long m = 1; for(int i = 1; i <= n; i++) m *= i; return m; } long long C(int n, int m){ return factorial(n)/(factorial(m)*factorial(n-m))); } 测试：n=21 m=1 结果-1 提示：即使最终答案在所选择的数据类型范围之内，计算的中间结果仍然可能溢出。

6 4.1 自定义函数和结构体 程序4-2 组合数 思考：为什么当m<n-m时把m变成n-m
4.1 自定义函数和结构体 程序4-2 组合数 long long C(int n, int m) { if(m < n-m) m = n-m; long long ans = 1; for(int i = m+1; i <= n; i++) ans *= i; for(int i = 1; i <= n-m; i++) ans /= i; return ans; } 思考：为什么当m<n-m时把m变成n-m 提示：对复杂的表达式进行化简有时不仅能减少计算量，还能减少甚至避免中间结 果溢出。

7 4.1 自定义函数和结构体 问题：素数判定 编写函数，参数是一个正整数n，如果它是素数，返回1，否则返回0。

8 4.1 自定义函数和结构体 程序4-3 素数判定（有问题） 一旦发现x有一个大于1的因子，立刻返回0（假），只有最后才返回1（真）
4.1 自定义函数和结构体 程序4-3 素数判定（有问题） //n=1或者n太大时请勿调用 int is_prime(int n){ for(int i = 2; i*i <= n; i++) if(n % i == 0) return 0; return 1; } 只判断不超过sqrt(x)的整数i（想一想，为什么） 一旦发现x有一个大于1的因子，立刻返回0（假），只有最后才返回1（真） 注意：i*i可能会溢出！ 如果n是一个接近int的最大值的素数，则当循环到i=46340时i*i= <n；但i=46341时，i*i= ，超过了int的最大值，溢出变成负数，仍然满足i*i<n。 若n不是太大，可能出现 溢出后等于 ，终止循环； 但如果n= ，循环将一直进行下去。

9 4.1 自定义函数和结构体 程序4-4 素数判定（2） int is_prime(int n){ if(n <= 1) return 0; int m = floor(sqrt(n) + 0.5); for(int i = 2; i <= m; i++) if(n % i == 0) return 0; return 1; } 特判n≤1的情况 程序中使用了变量m，一方面避免了每次重复计算sqrt(n)，另一方面也通过四舍五入避免了浮点误差 。

10 4.2 函数调用与参数传递 形参与实参 程序4-5 用函数交换变量（错误） #include<stdio.h> void swap(int a, int b){ int t = a; a = b; b = t; } int main(){ int a = 3, b = 4; swap(3, 4); printf("%d %d\n", a, b); return 0; } 输出是“3 4”，而不是“4 3”。 函数调用的过程： 第1步，计算参数的值。 在上面的例子中，因为a=3，b=4，所以swap(a,b)等价于swap(3, 4)。 这里的3和4被称为实际参数（简称实参）。 第2步，把实参赋值给函数声明中的a和b。 注意，这里的a和b与调用时的a和b是完全不 同的。 前面已经说过，实参最后将算出具体的值，swap函数知道调用它的参数是3和4，却不知道是怎么算出来的。 函数声明中的a和b称为形式参数（简称形参）。 提示：函数的形参和在函数内声明的变量都是该函数的局部变量。 无法访问其他函数的局部变量。 局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将被释放，其中的值无法保留到下次使用。 在函数外声明的变量是全局变量，可以被任何函数使用。 操作全局变量有风险，应谨慎使用。

11 4.2 函数调用与参数传递 调用栈 第1步：编译程序。 gcc swap.c -std=c99 -g 生成可执行程序a.exe（在Linux下是a.out）。 编译选项-g告诉编译器生成调试信息。 编译 选项-std=c99告诉编译器按照C99标准编译代码。 第2步：运行gdb。 gdb a.exe 这样，gdb在运行时会自动装入刚才生成的可执行程序。 第3步：查看源码。 (gdb) l #include<stdio.h> void swap(int a, int b){ int t = a; a = b; b = t; } int main(){ int a = 3, b = 4; swap(3, 4); printf("%d %d\n", a, b); return 0; }

12 4.2 函数调用与参数传递 b命令把断点设在了第4行，r命令运行程序，之后碰到了断点并停止。
4.2 函数调用与参数传递 第4步：加断点并运行。 (gdb) b 4 Breakpoint 1 at 0x401308: file swap.c, line 4. (gdb) r Starting program: D:\a.exe Breakpoint 1, swap (a=4, b=3) at swap.c:4 4 } 第5步：查看调用栈。 (gdb) bt #0 swap (a=4, b=3) at swap.c:4 #1 0x in main () at swap.c:8 (gdb) p a $1 = 4 (gdb) p b $2 = 3 (gdb) up #1 0x in main () at swap.c:8 8 swap(3, 4); (gdb) p a $3 = 3 (gdb) p b $4 = 4 b命令把断点设在了第4行，r命令运行程序，之后碰到了断点并停止。 根据bt命令，调用栈中包含两个栈帧：#0 和#1，其中0号是当前栈帧——swap函数， 1号是其“上一个”栈帧——main函数。 这里甚至能看到swap函数的返回地址：0x ，尽管不明确其具体含义。

13 4.2 函数调用与参数传递 用指针作参数 程序4-6 用函数交换变量（正确） #include<stdio.h> void swap(int* a, int* b){ int t = *a; *a = *b; *b = t; } int main(){ int a = 3, b = 4; swap(&a, &b); printf("%d %d\n", a, b); return 0; } 提示：C语言的变量都是放在内存中的，而内存中的每个字节都有一个称为地址（address）的编号。 每个变量都占有一定数目的字节（可用sizeof运算符获得），其中第一个字节的地址称为变量的地址。

14 4.2 函数调用与参数传递 初学者易犯的错误 这个swap函数看似简单，但初学者还是很容易写错。 一种典型的错误写法是：
4.2 函数调用与参数传递 初学者易犯的错误 这个swap函数看似简单，但初学者还是很容易写错。 一种典型的错误写法是： void swap(int* a, int* b){ int *t = a; a = b; b = t; } 此写法交换了swap函数的局部变量a和b（辅助变量t必须是指针。 int t = a是错误的），但却始终没有修改它们指向的内容，因此main函数中的a和b不会改变。 另一种错误写法是： int *t; *t = *a; *a = *b; *b = *t; 因为t是一个变量（指针也是一个变量，只不过类型是“指针”），所以根据规则，它在赋值之前是不确定的。 如果这个“不确定的值”所代表的内存单元恰好是能写入的，那么这段程序将正常工作；但如果它是只读的，程序可能会崩溃。 读者可尝试赋初值int *t = 0，看看内存地址“0”能不能写。

15 4.2 函数调用与参数传递 程序4-7 计算数组的元素和（错误）
4.2 函数调用与参数传递 程序4-7 计算数组的元素和（错误） int sum(int a[]) { int ans = 0; for(int i = 0; i < sizeof(a); i++) ans += a[i]; return ans; }

16 4.2 函数调用与参数传递 程序4-8 计算数组的元素和（正确）
4.2 函数调用与参数传递 程序4-8 计算数组的元素和（正确） int sum(int* a, int n) { int ans = 0; for(int i = 0; i < n; i++) ans += a[i]; return ans; }

17 4.2 函数调用与参数传递 程序4-9 计算左闭右开区间内的元素和（两种写法）
4.2 函数调用与参数传递 程序4-9 计算左闭右开区间内的元素和（两种写法） 写法一： int sum(int* begin, int* end) { int n = end - begin; int ans = 0; for(int i = 0; i < n; i++) ans += begin[i]; return ans; } 写法二： int sum(int* begin, int* end) { int *p = begin; int ans = 0; for(int *p = begin; p != end; p++) ans += *p; return ans; }

18 4.3 递归 程序4-10 用递归法计算阶乘 #include<stdio.h> int f(int n){ return n == 0 ? 1 : f(n-1)*n; } int main() { printf("%d\n", f(3)); return 0; } 提示：C语言支持递归，即函数可以直接或间接地调用自己。 但要注意为递归函数编写终止条件，否则将产生无限递归。 𝑓 0 =1 𝑓 𝑛 =𝑛∗𝑓(𝑛−1)

19 4.4 竞赛题目选讲 例题4-2 刽子手游戏（Hangman Judge, UVa 489） 刽子手游戏其实是一款猜单词游戏，如图4- 1所示。 游戏规则是这样的：计算机想一个单词 让你猜，你每次可以猜一个字母。 如果单词里有 那个字母，所有该字母会显示出来；如果没有那 个字母，则计算机会在一幅“刽子手”画上填一 笔。 这幅画一共需要7笔就能完成，因此你最多 只能错6次。 注意，猜一个已经猜过的字母也算 错。 在本题中，你的任务是编写一个“裁判”程 序，输入单词和玩家的猜测，判断玩家赢了 （You win.）、 输了（You lose.）还是放弃了 （You chickened out.）。 每组数据包含3行，第1 行是游戏编号（-1为输入结束标记），第2行是 计算机想的单词，第3行是玩家的猜测。 后两行 保证只含小写字母。

20 4.4 竞赛题目选讲 例题4-2 刽子手游戏（Hangman Judge, UVa 489）
4.4 竞赛题目选讲 例题4-2 刽子手游戏（Hangman Judge, UVa 489） 样例输入： 1 c heese chese 2 cheese abcdefg 3 c heese abcdefgij -1 样例输出: Round 1 You win. Round 2 You chickened out. Round 3 You lose.

21 4.4 竞赛题目选讲 rnd本应叫round，但是有一个库函数也叫round，所以改名叫rnd了
4.4 竞赛题目选讲 例题4-2 刽子手游戏（Hangman Judge, UVa 489） #include<stdio.h> #include<string.h> #define maxn 100//还需要猜left个位置,错chance次之后就会输 int left, chance; char s[maxn], s2[maxn]; //答案是字符串s,玩家猜的字母序列是s2 int win, lose; //win=1表示已经赢了;lose=1表示已经输了 void guess(char ch) { … } int main() { int rnd; while(scanf("%d%s%s", &rnd, s, s2) == 3 && rnd != -1) { printf("Round %d\n", rnd); win = lose = 0; //求解一组新数据之前要初始化 left = strlen(s); chance = 7; for(int i = 0; i < strlen(s2); i++) { guess(s2[i]); //猜一个字母 if(win || lose) break; //检查状态 } //根据结果进行输出 if(win) printf("You win.\n"); else if(lose) printf("You lose.\n"); else printf("You chickened out.\n"); } return 0; } rnd本应叫round，但是有一个库函数也叫round，所以改名叫rnd了

22 4.4 竞赛题目选讲 程序4-12 刽子手游戏——guess函数
4.4 竞赛题目选讲 程序4-12 刽子手游戏——guess函数 void guess(char ch) { int bad = 1; for(int i = 0; i < strlen(s); i++) if(s[i] == ch) { left--; s[i] = ' '; bad = 0; } if(bad) --chance; if(!chance) lose = 1; if(!left) win = 1; } 提示：每猜完一个字母之后打印出s、 left、 chance等重要变量的值，很容易就能发现程序出错的位置 。一般来说，减少变量的个数对于编程和调试都会有帮助。

23 4.4 竞赛题目选讲 例题4-3 救济金发放（The Dole Queue, UVa 133） n(n<20)个人站成一圈，逆时针编号为1～n。 有两个官员，A从1开始逆时针数，B从n开始顺时针数。 在每一轮中，官员A数k个就停下来，官员B数m个就停下来（注意有可能两个官员停在同一个人上）。 接下来被官员选中的人（1个或者2个）离开队伍。 输入n，k，m输出每轮里被选中的人的编号（如果有两个人，先输出被A选中的）。 例如，n=10，k=4，m=3，输出为4 8, 9 5, 3 1, 2 6, 10, 7。 注意：输出的每个数应当恰好占3列

24 4.4 竞赛题目选讲 例题4-3 救济金发放（The Dole Queue, UVa 133）
4.4 竞赛题目选讲 例题4-3 救济金发放（The Dole Queue, UVa 133） #include<stdio.h> #define maxn 25 int n, k, m, a[maxn]; //逆时针走t步，步长是d（-1表示顺时针走），返回新位置 int go(int p, int d, int t) { … } int main() { while(scanf(“%d%d%d”, &n, &k, &m) == 3 && n) { for(int i = 1; i <= n; i++) a[i] = i; int left = n; //还剩下的人数 int p1 = n, p2 = 1; while(left) { p1 = go(p1, 1, k); p2 = go(p2, -1, m); printf("%3d", p1); left--; if(p2 != p1) { printf("%3d", p2); left--; } a[p1] = a[p2] = 0; if(left) printf(","); } printf("\n"); } return 0; }

25 4.4 竞赛题目选讲 例题4-3 救济金发放（The Dole Queue, UVa 133）
4.4 竞赛题目选讲 例题4-3 救济金发放（The Dole Queue, UVa 133） go函数： int go(int p, int d, int t) { while(t--) { do { p = (p+d+n-1) % n + 1; } while(a[p] == 0); //走到下一个非0数字 } return p; } 注意go这个函数。 当然也可以写两个函数：逆时针go和顺时针go，但是仔细思考后发现这两个函数可以合并：逆时针和顺时针数数的唯一区别只是下标是加1还是减1。 把这个+1/-1抽象为“步长”参数，就可以把两个go统一了。

26 4.4 竞赛题目选讲 例题4-4 信息解码（Message Decoding, ACM/ICPC World Finals 1991, UVa 213） 考虑下面的01串序列： 0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001, …, 1101, 1110, 00000, … 首先是长度为1的串，然后是长度为2的串，依此类推。 如果看成二进制，相同长度的后一个串等于前一个串加1。 注意上述序列中不存在全为1的串。 你的任务是编写一个解码程序。 首先输入一个编码头（例如AB#TANCnrtXc），则上述序列的每个串依次对应编码头的每个字符。 例如，0对应A，00对应B，01对应#，…，110对应X，0000对应c。 接下来是编码文本（可能由多行组成，你应当把它们拼成一个长长的01串）。 编码文本由多个小节组成，每个小节的前3个数字代表小节中每个编码的长度（用二进制表示，例如010代表长度为2），然后是各个字符的编码，以全1结束（例如，编码长度为2的小节以11结束）。 编码文本以编码长度为000的小节结束。 例如，编码头为$#**\，编码文本为 ，应这样解码：010(编码长度为2)00(#)00(#)10(*)11(小节结束)011(编码长度为3)000(\)111(小节结束)001(编码长度为1)0($)1(小节结束)000(编码结束)。

27 4.4 竞赛题目选讲 例题4-4 信息解码（Message Decoding, ACM/ICPC World Finals 1991, UVa 213） #include<stdio.h> #include<string.h> //使用memset int readchar() { … } int readint(int c) { … } int code[8][1<<8]; int readcodes() { … } int main() { while(readcodes()) { //无法读取更多编码头时退出 //printcodes(); for(;;) { int len = readint(3); if(len == 0) break; //printf("len=%d\n", len); for(;;) { int v = readint(len); //printf("v=%d\n", v); if(v == (1 << len)-1) break; putchar(code[len][v]); } } putchar('\n'); } return 0; }

28 4.4 竞赛题目选讲 例题4-4 信息解码（Message Decoding, ACM/ICPC World Finals 1991, UVa 213） 如何处理“编码文本可以由多行组成” ：再编写一个“跨行读字符”的函数readchar。 int readchar() { for(;;) { int ch = getchar(); if(ch != ‘\n’ && ch != ‘\r’) return ch; //一直读到非换行符为止 } } int readint(int c) { int v = 0; while(c--) v = v * 2 + readchar() - '0'; return v; }

29 4.4 竞赛题目选讲 例题4-4 信息解码（Message Decoding, ACM/ICPC World Finals 1991, UVa 213） 下面是函数readcodes。 首先使用memset清空数组（这是个好习惯。还记得之前讲过的多数据题目的常见错误吗？ ），编码头自身占一行，所以应该用readchar读取第一个字符，而用普通的getchar读取剩下的字符，直到\n。 这样做，代码比较简单，但有些读者可能会有些别扭。 没关系，你完全可以使用另外一套自己觉得更清晰的方法。 int readcodes() { memset(code, 0, sizeof(code)); //清空数组 code[1][0] = readchar(); //直接调到下一行开始读取。 如果输入已经结束，会读到EOF for(int len = 2; len <= 7; len++) { for(int i = 0; i < (1<<len)-1; i++) { int ch = getchar(); if(ch == EOF) return 0; if(ch == '\n' || ch == '\r') return 1; code[len][i] = ch; } } return 1; } 最后是前面提到的printcodes函数。 这个函数对于解题来说不是必需的，但对于调试却是 有用的。 void printcodes() { for(int len = 1; len <= 7; len++) for(int i = 0; i < (1<<len)-1; i++) { if(code[len][i] == 0) return; printf("code[%d][%d] = %c\n", len, i, code[len][i]); } }

30 4.5 注解与习题 类别 题号 题目名称（英文） 备注 例题4-1 UVa1339 Ancient Cipher 排序 例题4-2
4.5 注解与习题 例题一览 类别 题号 题目名称（英文） 备注 例题4-1 UVa1339 Ancient Cipher 排序 例题4-2 UVa489 Hangman Judge 自顶向下逐步求精法 例题4-3 UVa133 The Dole Queue 子过程（函数）设计 例题4-4 UVa213 Message Decoding 二进制；试输技入巧技巧；调 例题4-5 UVa512 Spreadsheet Tracking 模拟；一题多解 例题4-6 UVa12412 A Typical Homework （a.k.a Shi Xiong Bang Bang Mang） 综合练习

31 作业