Microsoft PowerPoint - w10.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - w10.ppt"

应翁
4 years ago
Views:

1 基本程序设计技术甘锐北京大学数学科学学院例 : 定义计算整数阶乘的函数 : 1 2 (n-1) n 乘法的次数依赖于 n: 定义时不知道, 每次用可能不同 ( 程序的典型情况 ) 1 n 0 可用递归形式严格定义 n! n ( n 1)! n 0 递归定义的形式既是一种计算的方法如果语言允许递归定义函数, 就可以直接翻译为程序 C 允许递归定义 : 在函数定义内调用被定义函数本身 2 递归定义 vs. 循环定义 long fact (long n) { return n == 0? 1 : n * fact(n-1); long fact1(long n) { long i, f = 1; for (i = 2; i <= n; ++i) f *= i; return f; 3 讨论 :fact 定义简单, 实现的计算过程不简单 :fact 被递归调用的次数由计算实参确定调用 fact(3) 调用 fact(3) fact(3) 3*fact(2) fact(2) 2*fact(1) fact(1) 1*fact(0) fact(0)= 1 4 返回值 6 返回值 2 返回值 1 返回值例 : 定义函数计算 Fibonacci 序列 fib 函数的执行情况 F 1, F 1, F F F ( n 1) 0 1 n n 1 n 2 fib(5) long fib(int n) { return n<2? 1 : fib(n-1)+fib(n-2); fib(3) fib(4) fib(3) 问题 : 这个递归程序好不好? 程序遵循数学定义, 确认正确, 且易读易理解

2 为计算过程计时在程序里计时, 通常写表达式 : clock()/clocks_per_sec 可得从程序开始到该表达式求值时所经历的秒数有关函数在 time.h; 统计程序时间时, 程序头部需写 : #include <time.h> 7 #include <time.h> long fib (int n) { return n<=1? 1 : fib(n-1)+fib(n-2); /* 自己做其他试验 */ double x; x = clock(); fib(45); x = (clock() x) / CLOCKS_PER_SEC; printf("timing fib(45): %fs.\n", x); 8 Fibonacci 序列的迭代计算 F 0 和 F 1 是 1; 可以从连续的两个 Fibonacci 数计算出下一个递推计算方式 : 逐个向前推, 可用循环实现 long fib1 (int n) { long a = 1, b = 1, c, i; if (n <= 1) return 1; for (c = a + b, i = 2; i < n; ++i) { a = b; b = c; c = a + b; return c; /* 对不对? */ 9 循环实现重复性计算, 循环体可能执行多次如何保证对各种数据都能正确完成计算? 循环中变量不断变化写循环要考虑变量间的关系, 保证某些关系在循环中不变 ( 循环的不变关系循环不变量 ) 写循环时最重要的就是想清循环中应维持变量间的什么关系才能保证循环结束时变量能处在所需状态写完循环后应仔细检查是否满足要求循环定义函数 vs. 递归定义函数 10 例 : 写函数求最大公约数 (GCD) long gcd(long, long) 11 循环方式一 k 取初值 1 递增, 大于 m 或 n 之一后循环结束 12 解法一逐个检查, 直至找到能同时整除 m 和 n 的最大整数 ; 需辅助变量 k 记录检查值简单方式 :k 顺序取值 ( 初值 / 更新 / 结束 ), 可用循环实现 ; 需记录循环中已找到的最大的那个公约数 long gcd (long m, long n) { long d = 1, k = 2; /* 用 d 记录公约数 */ for ( ; k <= m && k <= n; k++) if (m % k == 0 && n % k == 0) d = k; /* k 为新找到的公约数 */ return d;

3 循环方式二 k 从某个大数开始递减, 初值可取 m 和 n 中较小的值 ; 循环结束条件 :k 值达到 1 或找到了公约数程序主要部分 for (k = (m > n? n : m); m % k!= 0 n % k!= 0; k--) ; /* 空循环体 */ return k; /* 循环结束时 k 是最大公约数 */ 13 解法二 : 最大公约数的递归定义 n mmod n 0 gcd( mn, ) gcd( nm, mod n) mmod n 0 递归函数定义 long gcd1 (long m, long n) { return m % n == 0? n : gcd1(n,m % n); 14 解法二的循环函数定义可用循环结构实现辗转相除法, 即反复求余数 long gcd2 (long m, long n) { long r; if (n == 0) return m; for (r = m % n; r!= 0; r = m % n) { m = n; n = r; return n; /* 循环不变式是什么? */ 15 河内塔 ( hanoi 塔, 梵塔 ) 问题古印度有个梵塔, 塔内有 3 根柱 A B C A 柱上套有 64 个大小不等的圆盘, 大的在下, 小的在上要把 64 个圆盘从 A 柱移到 C 柱, 每次只能移动一个圆盘, 移动可以借助 B 柱进行但在任何时候, 任何柱上的圆盘都必须保持大盘在下, 小盘在上求移动的步骤

$19 河内塔问题的算法设计 : 搬 N 个圆盘可以归结为搬 N-1 个圆盘假设需要把 N 个盘从 A 柱搬到 C 柱 : 从 A 柱借助 C 柱将 N-1 个圆盘搬到 B 柱 ; 把最大的圆盘从 A 柱搬到 C 柱 ; 从 B 柱借助 A 柱将 N-1 个圆盘搬到 C 柱 ; 20 void moveone (char from, char to) { printf("%c -> %c\n",$

4 19 河内塔问题的算法设计 : 搬 N 个圆盘可以归结为搬 N-1 个圆盘假设需要把 N 个盘从 A 柱搬到 C 柱 : 从 A 柱借助 C 柱将 N-1 个圆盘搬到 B 柱 ; 把最大的圆盘从 A 柱搬到 C 柱 ; 从 B 柱借助 A 柱将 N-1 个圆盘搬到 C 柱 ; 20 void moveone (char from, char to) { printf("%c -> %c\n", from, to); void henoi(int n,char from,char to,char by) { if (n == 1) moveone(from, to); else { henoi(n-1, from, by, to); moveone(from, to); henoi(n-1, by, to, from); 21 字符输入函数 getchar: 无参函数, 从标准输入读一个字符, 返回字符的编码值类型特征 : int getchar(void) 典型用法 : 把输入的字符赋给变量标准输入默认连到键盘 ; 无字符时 getchar 函数等待, 一直到人输入字符 ( 并回车, 即按 Enter 键 ) 后读入 22 字符输出函数 putchar: 向终端输出一个字符 putchar(c) 字符型整型数据例 : 写程序把由输入得到一个字符输出并换行 : int c; putchar(c); P109.exe putchar('\n'); 23 如何输入多个字符? 需反复读入 / 输出字符, 考虑写循环 : 问题 : 循环的条件 while (...) { putchar(c); 24

5 在程序内部控制循环 : 与实际输入无关如可用计数器, 读入规定数量个字符后结束循环 /* 读 10 个字符, 输出各个字符的编码 */ int c, n; for (n = 0; n < 10; ++n) { printf("%d\n", c); P110p1.exe 25 据实际输入控制循环 : 循环条件与输入有关, 得到满足条件的输入时即结束循环例 : 输入读一行, 输出各字符的编码 : int c; while (1) {/* 循环执行多少次由输入行包含多少字符确定 */ if (c == '\n') break; printf("%d ", c); P110p2.exe 26 如何处理任何的输入字符? 标准库定义符号常量 EOF(End Of File) 将标准输入定向到文件,getchar 可从文件读入 ; 正常情况下 getchar 返回读入的字符, 遇文件结束返回 EOF 值 ; 从键盘输入文件结束信息 :Ctrl-Z EOF 值不能与任何字符编码相同, 一般系统定义为 -1; 若 getchar 返回 char, 则无法给出 EOF 值 ; 故 while ((c = getchar())!= EOF) { getchar 返回 int; 应用 int 变量接收 getchar 的 /* 对输入的实际处理 */ 返回值, 保证正确判断输入结束如用 char 变量, 返回 EOF 值时超出 char 表示范围, 结果无定义 27 例 : 统计 ( 由标准输入得到的 ) 文件中的字符个数 long n = 0; while (getchar()!= EOF) ++n; printf("%ld\n", n); P112p2.exe 28

Microsoft PowerPoint - 01_Introduction.ppt

Microsoft PowerPoint - 01_Introduction.ppt Hello, World C 程序设计语言第 1 章章观其大略孙志岗 sun@hit.edu.cn http://sunner.cn prf("hello,, world\n"); 超级无敌考考你 : 如何把 hello 和 world 分别打印在两行? 2004-12-19 A Tutorial Introduction 2 hello.c 打印华氏温度与摄氏温度对照表计算公式 : C=(5/9)(