计算机编程课件：第4章 基本编程技术 (3)

1、第4章 基本编程技术,要目 理解输入过程 标准输入/输出及其重新定向 循环和递归 给程序计时 程序的测试和排除错误,理解scanf,scanf要求三方面一致：转换描述、对应参数的类型、实际输入。 函数调用 scanf(%lf, 可能产生三种返回值： 返回1表示成功读入一项数据，并存入了 x 返回0表示读入数据失败 返回EOF值表示遇到文件结束 scanf通过返回值通报其操作完成的情况，使我们可以在程序里利用这一信息。,理解getchar,假设要把从标准输入得到的许多字符送到标准输出，为此需要反复读入/输出字符，且字符个数不定，应该写循环： while (.) c = getchar(); .

2、通常可以让循环在遇到换行符时结束 while (1) c = getchar(); if (c = n) break; printf(%d , c); ,也可以由键盘输入文件结束标志：用Ctrl-Z送文件结束信息 while (c = getchar() != EOF) . . /* 对输入的实际处理 */ ,例4.15 一个简单的计算器程序,做一个程序，它从键盘读入如下形式的行： 128+365 254+1438 10313+524 每读入一个形式正确的行，就计算并输出结果 直至用户要求结束 很容易看到，程序的主要部分应该是一个基本循环： while (还有输入) 取得数据 计算并输出 一种

3、简单设计是遇到任何非数字非空白字符就结束程序,简单的计算器程序,#include int main () int left, right; printf(Small Calculatorn); printf(Any no-digit character to stop.n); while (scanf(%d, ,理解输入,可以把标准输入看成一个字符序列（字符流），调用输入函数就是要用掉序列最前面一个或几个字符 getchar的执行总是取出序列的第一个字符 Scanf则会用掉几个字符（如果符合转换描述要求） 序列中的字符用一个少一个，未用字符仍在输入流里 scanf转换失败时输入流保持当时状态，

4、导致转换失败的字符仍是序列里的第一个字符,输入和输出的重定向,在默认情况下，标准输入来自键盘 我们可以让它们实际从系统里的文件输入（称为输入重定向） scanf/getchar都能识别文件结束，返回EOF “”符号则是输出重定向符,输入和输出的重定向,假设计算器源程序是count.c，编译结果是count.exe。 用命令行方式启动count.exe程序，实现重定向： count out.txt 就是以： in.txt 作为标准输入 out.txt 作为标准输出,循环和递归,一段短程序如果有循环，就可能导致一段很长的计算，完成复杂的工作。 C语言允许用称为递归的方式写程序，这种方式不用循环结构

5、就能写出复杂程序，写出的许多程序更简单清晰。 什么是递归： 假设你在一个电影院，你想知道自己坐在哪一排，但是前面人很多，你懒得去数，于是你问前一排的人你坐在哪一排？，这样前面的人 (代号 A) 回答你以后，你就知道自己在哪一排了只要把 A 的答案加一，就是自己所在的排了。 不料 A 比你还懒，他也不想数，于是他也问他前面的人 B你坐在哪一排？，这样 A 可以用和你一模一样的步骤知道自己所在的排。然后 B 也如法炮制。直到他们这一串人问到了最前面的一排，第一排的人告诉问问题的人我在第一排，然后所有人都依次可以回答问他问题的人了，最后大家就都知道自己在哪一排了。,求阶乘（循环）,先考虑实现求阶乘的

6、C函数，阶乘的常见数学定义是： n! = 12(n-1)n 由于计算过程依赖于n，函数的类型特征可以规定为： long fact(long n) 很容易用循环写出函数定义： long fact1 (long n) long fac, i; for (fac = 1, i = 1; i = n; +i) fac *= i; return fac; ,求阶乘（递归）,求阶乘的严格数学定义必须用递归形式给出,C允许递归定义，允许在函数定义内调用被定义函数本身 我们用递归写出阶乘的函数定义： long fact (long n) return n = 0 ? 1 : n * fact(n-1); 这个

7、定义与上面的数学定义直接对应，比循环定义简短,递归定义的fact,但fact实现的计算过程很不简单。右图是 fact(3) 导致的计算过程，其中有多层函数调用和返回 计算中fact被递归调用的次数由实参确定 本函数定义只考虑非负参数（自然数），如果考虑参数为负，只需修改条件 n = 0 ? .,例4.18 Fibonacci序列的计算,Fibonacci序列是很重要的整数序列，其定义是：,很容易用递归定义一个函数计算序列中任一个数： long fib(int n) return n2 ? 1 : fib(n-1) + fib(n-2); 一方面：这个定义很好，程序与数学定义的关系很清晰，正确性

8、容易确认，定义容易读容易理解 另一方面：它可能导致大量的重复计算，因此完成工作可能需要很长时间,Fibonacci序列的计算,函数执行中大量重复计算（见下图）。而且，参数参数越大重复计算也越多，这导致程序变得很慢。,为计算过程计时,要看看程序是不是确实慢，可以做实验 程序头部应写： #include 在程序里计时，通常写表达式： clock()/CLOCKS_PER_SEC 它得到的是运行的秒数,为fib计时,确定计算fib(45)所需要的时间的程序： #include #include long fib (int n) return n=1 ? 1 : fib(n-1)+fib(n-2);

9、void main () double x; x = clock(); /开始计时 fib(45); x = (clock()-x)/ CLOCKS_PER_SEC; /计时结束 printf(Timing fib(45): %f.n, x); ,计算和时间,随着参数增大，该函数的计算中重复增长迅速，十几秒才可以算出 fib(45)。 参数每加1，fib 多用近一倍时间(是指数增长)。在最快微机一小时可能算不出 fib(55)，算 fib(100) 要数万年 虽然计算机很快，但完成复杂计算还是需要很长时间 这是计算机的一个本质性的特征（弱点） 也说明计算机不是万能的，有些事清实际上“不能”做，

10、因为我们等不到结果,Fibonacci序列的循环程序,Fibonacci序列可以递推计算。易见 F0和F1是1 有了连续的两个Fibonacci数，就可算出下一个 递推计算： long fib1 (int n) long f0 = 1, f1 = 1, f2, i; if (n = 1) return 1; for (f2 = f0+f1, i = 2; i n; +i) f0 = f1; f1 = f2; f2 = f0 + f1; return f1; 算 fib(100) 只需100次循环，很快,循环和递归,问题：用循环定义的fib1比用递归定义的fib好吗？ fib1在计算时间上有极大

11、优越性。计算时间由循环次数确定。循环体执行大致为n次。fib(100)只需100次循环，几乎察觉不到所用时间。注意：这里没考虑数据表示范围，long类型实际上无法表示fib(100) fib1定义较复杂，有复杂的循环，不容易理解。 注意：这个例子并不是说明递归比循环的效率低。,程序调试和排除错误,写好一个程序后，需要： 通过加工（编译和连接）产生出可执行程序 运行它，提供数据进行试验，确认它确实满足要求 试验中常常会发现错误，需要设法排除 这里牵涉到两项相互有关的工作 测试（testing）：在完成一个程序或一部分程序，通过试验性运行，仔细检查运行效果，设法确认该程序确实具有所期望行为的工作。

12、反过来说：测试就是设法用一些特别选出的数据去挖掘出程序里的错误 排错（debugging）：发现程序有错时，设法确认产生错误的根源，修改程序，排除错误的工作过程,测试的基本方法,有两类确定测试数据的基本方式： 根据程序结构确定测试数据，设法尽可能全面测试程序的各部分。相当于把程序打开，根据其内部结构考虑如何检查它，设法发现其中问题。这称为白箱测试 根据程序要解决的问题去确定测试过程和数据，不考虑程序内部如何解决问题。设法尽可能完全地检查问题领域中所有的可能性。这种方法把程序看作一个解决问题的“黑箱”，因此称为黑箱测试,白箱测试,考察程序内部结构及由此产生的执行流，设法选择数据使程序在试验运行中

13、能通过“所有”可能出现的执行流程 顺序结构只有一条执行流 “if (条件) 语句1 else语句2” 有两条可能执行流：条件成立时执行语句1；不成立时执行语句2。应设法提供测试数据，验证程序在这两种情况下都能正确工作 本质上说“while (条件) 循环体”可能产生无穷多条执行流：循环体不执行，执行1次，执行2次，。不可能穷尽地检查。常用方法是选择测试数据，检查循环的一些典型情况，包括循环体执行0次、1次、2次的情况，以及一些其他情况,黑箱测试,不考虑程序内部结构，只考虑所解决问题的情况 可能是别人的程序，内部结构不可知 即使可知也可能极其复杂，无法理解其所有的执行流 例如，如果某个函数只有一个int参数，可检查 参数为0时结果是否正确 参数为1