从问题到程序.ppt

1、从问题到程序,裘宗燕 北京大学数学学院 2005年,第四章基本程序设计技术,学习程序设计需要注意规律性的东西。 三种流程模式是重要总结。,本章还讨论： 基本输入和输出 递归的程序设计 其他控制结构,顺序模式最简单 选择模式：要确定判断条件及不同情况下的动作 开始的难点在实现重复执行的循环。重复执行比较复杂，牵涉问题多，是本章重点,4.1循环程序设计,写循环首先要发现循环。注意计算中的重复性动作，引进循环可能统一描述和处理。,重复动作的常见实例： 一批类似数据做同样加工处理 累积一批可按规律算出的数据（累加等） 反复从一个结果算出下一结果（递推）,若重复次数很多，就应该考虑用循环 如果重复次数无

2、法确定，就必须用循环描述,例：求13到315所有数的平方根之和。,可以一个个地加，但更方便的方法是写循环。 需要一个变量保存部分和，逐步把各平方根加上去； 需要一个变量保存变动轨迹，从初值开始每次修改。,典型for循环。假定已有总和变量sum和循环变量n： for (sum = 0.0, n = 13; n = 315; +n) sum += sqrt(n);,向下循环： for (sum = 0.0, n = 315; n = 13; -n) sum += sqrt(n);,这里的两个循环等效。一般采用向上循环,可以用while语句重写，两种结构功能上等效。,例，求 13, 315 间每隔7

3、的各整数的平方根之和。,一般不用浮点数控制循环，尤其是增量为小数或包含小数时。例：求从0到100每隔0.2的数的平方根之和：,double sum, x; for (sum=0.0, x=0.2; x=100.0; x+=0.2) sum += sqrt(x);,由于浮点计算误差，不能保证循环500次。应写：,int n; double sum; for (sum = 0.0, n = 1; n = 500; +n) sum += sqrt(0.2*n);,例1：打印出 1 到 200 间的完全平方数。,方法一：逐个检查，遇平方数打印。 重复做，每次检查一个数。循环框架： for (n = 1

4、; n = 200; n+) if (n 是完全平方数) 打印 n;,需填充：数是否完全平方数，没有直接判断手段。,可以顺序检查，是否存在某数，其平方恰为n。 这构成（循环内的）新循环，需要一个新循环变量。,m可以从1开始，递增，直至m*m大于n： for (m = 1; m * m = n; m+) if (m * m = n) 打印 n;,综合起来可得到完整程序： #include int main () int m, n; for (n = 1; n = 200; n+) for (m = 1; m * m = n; m+) if (m * m = n) printf(%d , n);

5、printf(n); /* 最后输出一个换行符 */ return 0; ,内层循环结束： 1，找到m使m*m=n（n是完全平方数） 2，试探了所有可能，但都不成功（n不是）,方法二：需要打印的一定是从1开始连续几个整数的平方，可从1开始打印到平方大于200为止。 for (n = 1; n * n = 200; +n) printf(%d , n * n); /*注意打印什么*/,还可以考虑利用递推公式：,方法一：产生所有备选数据（1到200的整数），检查排除不合格的。生成与检查是解决问题的常用方法。 方法二是针对具体问题的特定方法。,例 2：写函数判断整数是否为素数（谓词）。 类型特征可用

6、 int isprime(int)，返回0/1值,n是素数则它没有真因子，m是n的因子用(n%m = 0)描述，若 mn 就够了。函数定义：,int isprime (int n) /* n是否素数 */ int m = 2; for ( ; m * m = n; m+) if (n % m = 0) return 0; return 1; /* 没有因子，是素数 */ ,从循环中退出：isprime发现一个因子就可做结论。return使函数结束，也导致循环结束。 函数不完善，对1给出“是素数” ，负数也会给出不合理结果。 应该在循环前处理特殊情况： if (n = 1) return 0;

7、负数问题？ 如果需要可以另外考虑处理。,例3，艰难旅程（浮点误差）。乌龟要去环球。第1秒爬1米，第2秒爬1/2米，第3秒爬1/3米，第4秒爬1/4米，。问一小时能爬出多远？爬20米需多少秒？,根据数学，乌龟能完成环球，可以爬得任意远。 这里想比较float和double的计算误差情况。,这里只考虑20米需要多少时间。写出下面函数： long scndsf (float d) long i; float x = 0.0; for (i = 1; x d; +i) x += 1/(float)i; return i - 1; ,写下面语句，执行时总也不输出： printf(%lds, %fmn,s

8、cndsf(20.),20.);,修改为如下语句： for (x = 10.0; x = 20.0; x += 1.0) printf(%lds, %fmn,scndsf(x),x); 程序输出： 12367s, 10.000000m 33617s, 11.000000m 91328s, 12.000000m 248695s, 13.000000m 662167s, 14.000000m 1673859s, 15.000000m 而后又没反应了。,考虑如下的测试函数： void test_float () long i; float sum = 0.0, sum0 = -1.0; for (i

9、 = 1; sum != sum0; +i) sum0 = sum; sum += 1 / (float)i; printf (float: %ld terms at %fn, i-1, sum); 程序很快就输出了一行： float: 2097152 terms at 15.403683,对乌龟活动的模拟受到数据表示精度和范围的限制。,用double改写程序，20亿秒时和还增长，输出： 2000000000s, 21.993629m 经过大约63年半，乌龟爬了近22米。在大约2亿5千万秒（约8年）爬过了20米，这是题目第二部分的答案。 由于long为32位表示，在此范围内没找到用double

10、类型的增长结束点。但一定比用float大得多。,特殊情况中浮点误差积累可能更迅速。两个重要情况： 1）将一批小的数加到很大的数上，会导致丢掉小的数的重要部分，甚至小数整个被丢掉（例中情况） 2）两个值接近的数相减，可能导致精度大大下降,例4：求x立方根的迭代公式： 写函数求立方根，要求： 函数取名cbrt，特征：double cbrt(double x),无法确定循环次数，只能用循环。 只能按题目给出循环条件（计算方法的研究结果）,求新迭代值要用到x。判断终止需要先后两个近似值，必须用两个变量，这可看作是两个合作的迭代变量。,函数的主要部分： double x1, x2; if (x = 0.

11、0) return 0.0; /*特殊情况*/ x1 = x; x2 = (2.0*x1 + x / (x1*x1) / 3.0; while (fabs(x2 - x1) / x1) = 1E-6) x1 = x2; x2 = (2.0*x1 + x / (x1*x1) / 3.0; return x2;,这个程序的一个缺点是同一表达式写了两次。书上利用C的特点给了一种简化写法，供参考 学习了其他结构后有改进的写法,例5：定义函数，利用公式 求 近似值。设为double dsin(double x)。 方法：循环累加，n 趋向无穷的过程中项值趋于0，而累加值趋向函数值。需要用循环。 保存累加

12、和的变量sum ，循环中求出的项值用 t 保存。,sum = 0.0; 对n为0计算t; while (需要继续) sum = sum + t; 计算下一个t; ,循环结束条件：例如用项绝对值小于 。,问题：t 的值如何计算？ 第一个 t就是 x; 分析可以发现项值的递推公式：,double dsin (double x) double s = 0.0, t = x; int n = 0; while (t = 1E-6 | t = -1E-6) s += t; n = n + 1; t = -t*x*x / (2*n) / (2*n + 1); return s; ,一些情况： 实参值很小时

13、，循环将很快结束。 实参绝对值很大时循环可能做许多次，项的绝对值可能达到很大，n 值也可能超出整数的表示范围 可考虑用fmod把参数归约到0，2 之内,启示： 理解问题非常重要。发现了项的递推性质能节省许多计算（否则就要再写一个嵌套循环完成项的计算） 级数收敛性质能帮人认识情况，改进计算方法 写程序时必须仔细考虑问题本身的性质,4.2 循环中的问题,从循环中退出 有时需要从正在执行的循环中退出。,对6200的各偶数验证哥德巴赫猜想，利用isprime： for(n = 6; n = 200; n += 2) for(m = 3; m = n/2; m+= 2) if(isprime(m) ,问

14、题：有多种分解时将产生多对输出。如对10： 10=3+7 10=5+5,前面写isprime时借助return退出了循环,希望每个偶数只输出一行。 怎样在发现素数对后停止？增加对循环的控制：把发现素数分解作为条件加入。,引入整型变量found，值0表示未发现素数对。发现时将found赋1。内循环开始时found置0。应修改内层循环条件。修改后循环是： for(n = 6; n = 200; n += 2) for(found=0, m=3; m=n/2 ,这种需求很常见。C语言引进了专门的控制语句,break语句，形式： break; break只能用在循环语句（及switch语句）里，使最内

15、层（循环可嵌套）循环语句（或switch）立即停止，执行从被终止循环（或switch）之后继续。,可用break解决循环中退出问题，放在条件下。完成前例的程序段： for (n = 6; n = 200; n += 2) for (m = 3; m = n/2; m += 2) if (isPrime(m) ,利用break重写前面求立方根的函数： double cbrt (double x) double x1, x2 = x; if (x = 0.0) return 0.0; while (1) x1 = x2; x2 = (2.0*x1 + x / (x1*x1) / 3.0; if (

16、fabs(x2-x1)/x1) 1E-6) break; return x2; ,也可以在 break 处直接写 return x2。,循环中的几种变量 循环中常出现几类变量，注意这些有助于对循环的思考和分析。也是写循环程序的经验总结 注意：分类不是绝对的，不同类别没有截然界限,1）循环控制变量(循环变量)：循环前设初值，循环中递增/递减，达到/超过界限时循环结束。它们控制循环的进行/结束。 for中常有这类变量。 for(n = 0; n = 0; -n) . . for(n = 2; n 52; n += 4) . 这种循环是固定次数的循环。这种循环可能展开,2）累积变量：循环中常用 +=

17、 或 *= 等更新。初值常用运算的单位元（加用0；乘用1为初值）。循环结束时变量终值被作为循环计算结果。,3）递推变量：前两类变量的推广。几个协同工作的变量，每次由几个变量推出一个新值，其余依次更新。 对变量x1、x2、x3，循环体可能有序列： x1 = x2; x2 = x3; x3 = . x1 . x2 .; 例如上面cbrt里的变量x1和x2。,写循环时要考虑和解决问题列表： 循环涉及到哪些变量，需引进哪些临时性变量？ 循环如何开始？循环开始前给变量什么初值？循环中变量的值如何改变？ 什么情况下继续（或终止）循环？ 循环终止后如何得到所需结果？ 用哪种结构实现循环，等等。,工作方式：分

18、析问题，发掘线索，最终完成程序。 程序设计不是教条，典型问题也无标准答案。并非最简单的问题总有多种解决方法，往往各有长短。 “正确”程序常有优劣之分。,4.3循环与递归,程序中有循环可能导致很长的计算。 没有循环结构也能描述这类计算。C语言允许递归，可在函数内调用自身，程序常常更简单清晰。,例：定义计算整数阶乘的函数： 12(n-1)n 乘的次数依赖于n，定义时不知道，每次用可能不同。,程序的典型情况：计算“次数”依赖某些参数的值。,省略号不科学。严格定义需用递归形式。,注意递归定义的形式。这也提出了一种计算方法。 如果语言允许递归定义函数，就可以直接翻译为程序。 C允许递归定义：在函数定义内

19、调用被定义函数本身。,类型特征可定为： int fact(int) 阶乘值增长极快（数学），更合适的类型特征： long fact(long),递归的函数定义： 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; ,比递归定义长，需要引进多个局部变量。,fact实现的计算过程很不简单。 计算中fact被递归调用的次数由实参确定。,考虑负参数值处理。可改为： n=1 ? 1

20、 : .,递归定义导致的计算过程 参数不同fact递归调用次数（步数）不同。 定义只有一个语句，可能要许多步才能完成。包含递归（和循环）的程序产生的计算过程和性质更复杂，能完成更复杂工作，理解和书写也更困难。,递归的函数定义需要条件表达式或if，必须区分： 直接给出结果的情况。是递归的基础 需要递归处理的情况。其中把对较复杂情况的计算归结为对更简单情况的计算 基本运算/关系判断/条件表达式，加函数定义和递归定义构成了一个（理论上）“足够强的”的程序语言。,程序实例 Fibonacci（斐波那契）序列的递归定义：,Fibonacci 序列增长很快，返回值选long。递归定义： long fib

21、(int n) return n2 ? 1 : fib(n-1) + fib(n-2); 负参数值定义为 1。这是“合理”处置。,问题分析：这个程序好不好？ 一方面，很好！程序与数学定义的关系很清晰，正确性容易确认，定义易读易理解。,但这个定义有一个本质性缺点。示意图：,存在大量重复计算，参数越大重复计算越多。 有关系吗？,随着参数增大，计算中重复增长迅速，最快的微机上一分钟大约可以算出fib(45) 参数加1，fib多用近一倍时间(指数增长)。最快的微机一小时算不出fib(55)，算fib(100)要数万年,计算需时间，复杂计算需要很长时间。这是计算机的本质特征/弱点。说明它不万能，有些事清

22、“不能”做。,求Fibonacci 值有更好计算办法（下面介绍）。,人们发现了许多实际问题，理论上说可用计算机解决（可写出计算它的程序），但对规模大的情况（“大的参数 n”），人类永远等不到计算完成。 这时能说问题解决了吗？ 理解这个情况对于理解计算机是非常重要的。 这里有一大类问题称为计算中的“难解问题”，其中有许多很实际的问题（规划、调度、优化等）。 这方面的理论和实际技术的研究极为重要：计算复杂性，难解问题，“P = NP？”问题。 另外，对于许多问题的实用的有效算法，有极大的理论价值和实际价值。,为计算过程计时 统计程序/程序片段的计算时间有助于理解程序性质。许多语言或系统都提供了内部

23、计时功能。,有关函数在time.h，统计程序时间时程序头部应写： #include 在程序里计时，通常写表达式： clock()/CLOCKS_PER_SEC 得到从程序开始到表达式求值时所经历的秒数。 注意：有些老的C系统（如Turbe-C）用 CLK_TCK。,确定计算fib(45)所需要的时间的程序： #include #include long fib (int n) return n=1 ? 1 : fib(n-1)+fib(n-2); int main () /* 自己做其他试验 */ double x; x = clock() / CLK_TCK; fib(45); x = cl

24、ock() / CLK_TCK - x; printf(Timing fib(45): %f.n, x); return 0; ,Fibonacci数的递推计算 易见 1）F1和F2是1 2）知道连续两个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; /* 对吗？ */,循环结束时i等于n，这时c的值是Fn。要

25、得到此结论，可设法证明：每次判断 i 的值时c正是 Fi。 上面循环保证这种关系，可以通过归纳证明：,for (c = a+b, i = 2; i n; +i) a = b; b = c; c = a + b; ,第一次判断时 i 的值是 2，c 的值2，正是 Fi（且 a 的值是Fi-1 ，b 的值是Fi-2 ） 若某次判断时 i 值是 k（小于n），循环体中的语句使a变成Fk-1 ，b变成Fk ，c变成Fk+1 。i 值增 1 使我们又有a为Fi-2 ，b变成Fi-1 ，c变成Fi 根据归纳法，每次判断 i 的值时c正是 Fi。,循环实现重复性计算，循环体可能执行多次。如何保证对各种数据都

26、能正确完成计算？ 循环中变量不断变化。写循环要考虑变量间的关系，保证某些关系在循环中不变：循环的不变关系。 写循环时最重要的就是想清循环中应维持变量间的什么关系才能保证循环结束时变量能处在所需状态。写完循环后应仔细检查是否满足要求。 循环不变关系（循环不变量）是理解循环、写好循环的关键。这个方面有很多研究，有许多理论结果。,问题：用循环的函数比用递归定义的好吗？ 新函数在计算时间上有极大优越性。计算时间由循环次数确定。循环体执行次数大致为n。fib(100)只需约100次循环，几乎察觉不到所花费时间。 新函数定义较复杂，有复杂的循环。要理解程序意义，确认函数对任何参数都算出Fibonacci值

27、，需要借助“循环不变关系”的概念和细致分析。 上面分析中没考虑数据表示范围，long类型一般无法表示fib(100)。,注意：这个例子并不是说明递归比循环的效率低。完全可以写出计算fib的同样高效的递归定义的函数,求最大公约数（greatest common divisor，GCD）： 写函数 long gcd(long, long),方式1：k取初值1后递增，大于m或n之一时结束。 如何得到所需结果? m和n可能有多个公约数，最后的k值不是m和n的公约数（它已大于两数之一）。,解法1：逐个检查，直到找到能同时整除m和n的最大整数（生成与检查）。需辅助变量k记录检查值。简单方式：k顺序取值（初

28、值/更新/结束），可用循环实现。,需要记录循环中找到的公约数。,只需记录已找到最大的公约数，用变量d，初值1（是公约数），遇到新公约数（一定更大）时记入d： if (m % k = 0 /* k为新找到的公约数 */,有了d及其初值，k可以从2开始循环。函数定义： long gcd (long m, long n) long d = 1, k = 2; for ( ; k = m 参数互素时初值1会留下来，也正确。,还有一些特殊情况需要处理： 1）m和n都为0需特殊处理。例如令函数返回值0； 2）若m和n中一个为0，gcd是另一个数。函数的返回值正确。也可直接判断处理； 3）m、n为负时函数返

29、回1，可能不对。 应在循环前加语句： if (m = 0 ,可能方式2：令k从某大数开始递减，找到的第一个公约数就是最大公约数。 k初值可取m和n中小的一个。 结束条件：k值达到1或找到了公约数。1总是公约数。,程序主要部分可写为： for (k = (m n ? n : m); m % k != 0 | n % k != 0; k-) ; /* 空循环体 */ return k; /*循环结束时k是最大公约数 */,本方法比前一方法简单一些。 两种方法的共同点是重复测试。这类方法的缺点是效率较低，参数大时循环次数很多。,解法2：求GCD有著名的欧几里德算法（欧氏算法，辗转相除法）。最大公约数

30、的递归定义：,函数定义（递归）：假设第二个参数非0，且参数都不小于0。与数学定义直接对应： long gcd1 (long m, long n) return m%n = 0 ? n : gcd1(n,m%n); ,对欧氏算法的研究保证了本函数能结束，对较大的数计算速度也很快，远远优于顺序检查。,对特殊情况可另写一函数，其主体是对gcd1的调用： long gcd(long m, long n) if (m 0) m = -m; if (n 0) n = -n; return n = 0 ? m : gcd1(m, n); ,函数定义（循环）： 辗转相除就是反复求余数，也是重复性工作，可用循环

31、结构实现。 出发点m和n；循环判断m%n是否为0，若是则n为结果；否则更新变量：令m取n的原值，n取m%n的原值。为正确更新需用辅助变量r，正确的更新序列： r = m % n; m = n; n = r;,循环可写为： for (r = m%n; r != 0; r = m%n) m = n; n = r; ,下面函数定义假定参数值不小于0（否则可以在前面增加判断和处理）： 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;

32、 ,参数是局部变量，可在函数体里使用和修改。 请考虑，这里的循环不变式是什么？,河内塔（ hanoi塔，梵塔）问题,本问题用递归写程序很简单，用循环解决较困难。 问题出自古印度（一说西藏）。某神庙有三根细柱，64个大小不等、中心有孔的金盘套在柱上，构成梵塔。僧侣日夜不息地将圆盘从一柱移到另一柱，规则是每次只移一个盘，大盘不能放到小盘上。 开始时圆盘从大到小套在一根柱上，据说所有圆盘都搬到另一根柱时世界就要毁灭。,要求写程序模拟搬圆盘过程，打印出搬动指令序列。 为方便，分别将三根圆柱命名为a、b和c，假定开始时所有圆盘都在a上，要求最终搬到b。,初看问题似乎没规律。求解的关键在于看到问题的“递归

33、性质”。搬64个盘的问题可归结为两次搬63个盘。,一般情况：搬n个圆盘的问题可以归结为搬n-1个圆盘 把n个盘从柱1搬到柱2的工作可以如下完成： 从柱1借助柱2将n-1个圆盘搬到柱3； 将最大圆盘从柱1搬到柱2； 从柱3借助柱1将n-1个圆盘搬到柱2；,void moveone (char from, char to) printf(%c - %cn, 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); moveon

34、e(from, to); henoi(n-1, by, to, from); ,moveone定义为函数是为了方便。函数调用： henoi(6, a, b, c);,4.4 基本输入输出（IO）,IO通过标准库进行 常用函数 scanf getchar putchar 需要（同printf）,格式输入函数scanf 功能与printf对应。 scanf从标准输入读数据，根据格式描述将实际输入转换到指定类型，转换结果赋给指定变量： scanf(格式描述串, printf(Please input a number: ); scanf(%d, ,程序执行后输出提示串： Please input a

35、 number: 等待人的输入。得到输入数据后输出并结束。程序的行为依赖于当时的输入（与前面程序不同）,注意实数类型的转换描述与printf的差异。,例：设有变量定义： int n; double x; float y; 可以写语句： scanf(%d %lf %f, ,常用的 scanf 转换描述：,读数值时， sacnf格式串里的转换描述之间的空格并不必要。上面语句写成下面形式，效果一样。： scanf(%d%lf%f, 如果这里的转换描述之间没字符或只有空格，输入的数据之间也只能有空白字符，不能有其他字符。 格式串里一般不写转换描述之外的东西。如果写 %d, %lf, %f 就是要求用逗

36、号分隔输入数据，若输入时不注意就会导致数据不能正常读入。建议不要这样写。 scanf格式串的细节在第八章有详细介绍。,缓冲式输入 若程序要求从标准输入取得信息（如执行scanf），我们由键盘输入，在按Enter键后程序才能得到输入数据 造成这种情况的原因是操作系统通常采用“缓冲式”输入方式，把来自键盘的输入临时保存在 “输入缓冲区”（操作系统管理下的一块内存区域）里，直至人按了Enter键，才把缓冲区里的数据送给程序，这时scanf等输入函数才能读到数据,程序经常需要输入一批数据，通过一个循环处理。为此需要在循环中反复调用输入函数 下面讨论这种循环输入中的控制问题,通过计数器控制的输入循环 如

37、果事先知道需要输入的数据项数，就可以用计数器控制输入循环。如由各月降雨量统计一年总量：,#include int main() double x, sum; int n; for (sum = 0, n = 0; n 12; +n) printf(Enter next data: ); scanf(%lf, ,假定写程序时不清楚需要输入的数据的确切项数，就无法采用计数循环的简单方法。 一种方式是用一个特殊 “结束标志” 控制循环。该“结束标志”应是一个特殊输入值，具有与输入数据同样的类型，但又不是正常输入数据。 让程序在循环中不断检测得到的数据，一旦看到这个特殊数据，就知道用户要求结束了。 采

38、用这种技术，循环结束条件就是写程序的人与使用者之间的一种约定，当输入满足约定时程序就结束。,用特殊结束值控制输入循环,例，计算货物总值，每次输入单价和数量。可考虑用特殊值通知程序数据已输入完，例如用单价为0。,#include int main() double price = 1.0, amount, sum = 0.0; while (price != 0) printf(Next data (price amount): ); scanf(%lf %lf, ,这个程序中循环体的执行次数，完全由程序执行时外部提供的输入数据项数决定。,上面两种方式可以解决许多数据输入循环的控制问题，但有时也

39、会遇到困难。 例：假定现在要写程序，求一批输入数据的平均值。 事先不知道可能输入哪些数据。任何数值都可能出现在需要求平均值的数据中。 如果选0作为“结束标志”，而实际数据里有0，这个程序就不能正确处理了（任何选择都有问题）。 这种情况具有普遍性，要解决这类问题，就需要进一步理解scanf的功能。,深入理解scanf scanf的返回值是int，它顺序处理格式串： 根据格式串要求完成输入、转换和对变量的赋值 工作正常结束时返回所完成的数据转换项数 如果一开始就遇到文件结束，就返回一个特殊符号常量 EOF（是一个int值，后面再介绍） 如果没处理完整个格式串就失败时，返回已完成的数据转换项数,sc

40、anf 用输入数据与正在处理的转换描述比较，如果相符就完成一项转换。例如：若转换描述是 %d，输入得到的是一串数字，就把它们转换为一个整数 如果实际输入与转换描述不匹配，转换失败,scanf要求三方面一致：格式串中转换描述、对应参数的类型、运行中提供的数据形式。假如格式串要求做整数转换，赋给整型变量。若实际输入不是一串数字，scanf也无法正常完成工作 在格式串要求读整数或者浮点数，scanf会跳过遇到的空白字符，从下一非空白字符开始处理,下面函数调用可能产生三种返回值： scanf(%lf, while (scanf(%lf, /* 什么情况下循环结束？ */,只要scanf的返回值不是1，

41、循环就结束,遇到文件结束或错误数据时 scanf 不返回1。如果上面程序遇到输入字母m，转换失败就会导致循环结束。 更好的方式是利用标准库定义的符号常量EOF。 如果把标准输入定向到某个文件，在读完文件里所有数据后scanf就会返回EOF值。 EOF 是什么？一般的C系统把EOF定义为-1，它一定不是正数，不会与scanf的其他返回值混淆。 默认情况下，标准输入从键盘得到数据。许多系统里可以用Ctrl-Z或Ctrl-D组合键送入文件结束信息。 前面程序运行时，如果按了这种组合键，scanf 就会返回EOF并导致循环结束。,例：统计一批输入数据的个数和最小值/最大值/平均值,循环读入数据，并完成

42、其他工作。 两个变量记录已知的最小/最大值。读数据中考虑更新，使其保存已读数据的最小最大值（循环不变性质）。 两个变量记录数据个数，记录已读入数据之和。循环中要正确更新（循环不变性质）。,问题：保存最大值和最小值的变量的初始值？ 下面程序假定最少有一个输入数据，用读入的第一个数据作为最大和最小变量的初始值。,#include int main () double sum = 0.0, biggest, smallest, x; int count = 1; scanf(%lf, /* 要求至少有一个输入数据 */,关于输入循环的总结 要输入一批数据时，可根据情况采用不同控制方式循环。主要的三种

43、控制方式： 1. 程序内部自主控制，根据程序内部情况决定循环继续或终止，是否继续读入。这一技术的缺点是不够灵活，难以处理事先不清楚项数的输入数据。 2. 从输入数据类型里选一个特殊值作为结束标志值，程序使用者可用它通知程序输入结束。这一技术的缺点是有时难以找到合适的结束标志值。 3. 通过输入函数的返回值，控制循环的继续或结束。 以后的程序实例中还会频繁使用它们。,字符IO函数getchar和putchar getchar是无参函数，从标准输入读一个字符，返回字符的编码值。getchar的类型特征： int getchar(void) 典型使用（输入的字符赋给变量c）： c = getchar

44、();,标准输入默认连到键盘。没有输入数据时getchar等待，直到人输入字符（并换行）。 返回类型int的问题下面解释。,putchar把一字符送到标准输出： putchar(O); putchar(K); 两字符送到标准输出，使字符显示在屏幕上。 例：写程序把由输入的一个字符输出并换行： #include int main () int c; c = getchar(); putchar(c); putchar(n); return 0; /*执行情况？*/,输入一系列字符 假设要由标准输入得到的多个字符送到标准输出，需要反复读入/输出字符，应该写循环： while (.) c = get

45、char(); putchar(c); 本程序具有普遍性：putchar(c)是处理过程的代表，可根据需要换成其他程序片段。,怎样描述循环条件？ 首先要问的是：希望在什么条件下结束循环？,两种可能： 1）程序内部确定，与实际输入无关。例如用计数器，读入若干个字符后结束。,#include int main () /* 读10个字符，输出各个字符的编码 */ int c, n; for (n = 0; n 10; +n) c = getchar(); printf(%dn, c); return 0; ,2）根据实际输入决定。循环条件与输入有关，是编程者和使用者的协议，得到满足条件的输入时结束循

46、环。,例：输入读一行，输出各字符的编码： #include int main () int c; while (1) /*循环执行多少次由输入行包含多少字符确定*/ c = getchar(); if (c = n) break; printf(%d , c); return 0; ,也可要求遇到其他字符结束。何时结束是一种约定。,处理任意的输入字符 前面方法需要选一个字符作为表示结束的特殊字符。这个字符就不能再作为输入中的正常字符了。 要处理键盘能输入的所有字符，应怎样写结束条件？,标准库定义了符号常量EOF（End Of File/文件结束），getchar遇文件结束返回EOF。如果标准输

47、入定向到文件，getchar就会从文件读，文件读完时返回值EOF。 由键盘输入文件结束：用Ctrl-Z送文件结束信息。,EOF是什么？ 一般系统定义为-1（具体值并不重要）。程序里只需判断输入函数的返回值是否与EOF值相同。,while (c = getchar() != EOF) . . /* 对输入的实际处理 */ EOF的值不能与任何字符编码相同。若getchar返回char，就无法给出EOF值。所以getchar返回int。,总结：正常情况下getchar返回读入的字符，遇文件结束返回EOF值。应该用int变量接收getchar的返回值，以保证正确判断输入结束。,如果用char变量，值

48、超出char范围时结果无定义 char ch; while (ch = getchar() != EOF) .,注意：赋值操作有值，注意加括号。,例：统计（由标准输入得到的）文件中的字符个数。,#include int main () int c; long n = 0; while (c = getchar() != EOF) n+; printf(%ldn, n); return 0; ,标准输入默认连接到键盘。 程序执行到getchar等待输入，得到输入后处理。 用Ctrl-Z发信息可使循环结束。,缓冲式输入：键盘输入字符（行），按Enter键后才能送给程序。因为操作系统通常采用缓冲式输

49、入方式。,从系统中的命名文件读入： 设源程序是count.c，编译结果是count.exe。 用命令行方式启动程序，将标准输入定向到文件（设被统计文件是abcd.txt）： count abcd.txt,读入循环中可以完成对输入内容的各种处理，例如： 统计某个字符出现的次数， 统计文件中的行数等等 练习中包含许多这种题目,输入函数的返回值 程序可分为两类：一类自主运行，产生结果后结束；另一类不断与外界交流（交互式程序）。,交互式程序时应设法处理各种可能情况，特别需要获得有关输入情况的信息，以便恰当处理。 标准输入函数用返回值说明执行情况。如scanf返回int值，指明完成转换项数，遇文件结束返

50、回EOF。,若程序要求输入三个整数，一种写法： while(scanf(%d%d%d, /* 吃掉一行字符*/ ,标准输入可看作很长的字符序列。输入函数从这个序列最前面的取字符。 getchar取走一个字符。scanf可能取走几个字符（如果符合要求）；无法转换时一个也不取。没取走的字符仍在那里。 scanf工作到处理完所有转换描述或转换失败，返回正确完成的转换项数。,例，若把上面程序中循环的条件部分改为： while (scanf(%lf, 执行过程如图。,与while的差异在于判断在后，至少执行语句一次。,do-while使用较少，没有for和while多。,用do-while结构重写求立方

51、根函数： double cbrt(double x) double x1, x2 = x; if (x = 0.0) return 0.0; /*处理特殊情况*/ do x1 = x2; x2 = (2.0*x1 + x / (x1*x1) / 3.0; while (fabs(x2 - x1) / x1) = 1E-6); return x2; ,break语句已介绍。 continue语句 形式： continue; 只能用在循环里，使最内层循环体的一次执行结束，进入下次循环。while/do-while的随后动作是条件判断；for的随后动作是变量更新。,goto语句/转移语句/转跳语句

52、最老的控制语句。现在已很少用。许多语言仍提供。 goto语句与标号配合，实现函数体内的任意控制转移。 标号可写在任何语句前面作为goto的目标。形式是： 标号名: 标号名是标识符。 goto语句的形式： goto 标号名; 作用（语义）：使控制转到标号处继续执行。,break、continue是受限的goto，实现固定方式的控制转移。循环和分支也是goto的包装。 FORTRAN就有goto语句。,无节制地用goto写程序，费解，常带有难发现的错误。 1968年Dijkstra撰文“goto是有害的” 。六年大辩论的结果是结构程序设计革命，语言都引进“标准”控制结构，教育和实践中提倡结构化程序

53、设计。 对goto的认识：不用或尽量少用。,大部分goto实际上是为构造条件或循环： 1）向前转跳2）向后转跳 label: . . goto label; . . . goto label;label: . 用循环或条件重写的程序更清晰易读，不容易有错。 随便使用goto是不良编程习惯。不合理的goto表明对问题欠分析，没做好流程分解，函数抽象等，写的是不成熟的程序。,开关语句（switch语句）,多分支结构，根据一个整型值选择。形式： switch (整型表达式) case 整型常量表达式: 语句序列 . . default: 语句序列 常量表达式常用整数/字符等。default部分可缺，

54、语句序列可缺，可含多个语句。“case 整型常量表达式:”看作标号。,语义：求值整型表达式，将值顺序与各整型常量表达式比较，遇到相等时转入执行；无匹配但有default则从default:处继续；没有default时结束。,例，按x的值确定分支，1和2分别处理，其他统一处理 switch (x) case 1: . . break; case 2: . . break; default: . . break; ,各case标号值必须互不相同。 习惯在各分支最后写break，包括最后分支。 规定：如果分支最后无break，语句序列执行完后进入下一分支的语句序列。这导致一种代码共享。 一般认为，除

55、非几个分支的语句相同，否则不提倡共享。因为这导致程序段相互依赖，对程序修改不利。,while (c = getchar() != EOF) switch (c) case : nb+; break; case1: case2: case3: case4: case5: case6: case7: case8: case9: case0: nd+; break; case n: nl+; break; case : case : nc+; break; default: nn+; break; ,例：分别对空格/数字/行数/花括号/其他字符计数。,4.6 程序设计实例,例：简单交互式计算器。假定

56、它可以输入并计算： 128+365 254+1438 10313+524 输入一行算一个结果。直至用户要求结束。,显然程序里应有一个基本循环： while (还有输入) 取得数据 计算并输出 可考虑用scanf读数据，用文件结束或非数字表示输入结束。,#include int main () int left, right; printf(Small calculator.n); printf(Any no-digit character to stop.n); while(scanf(%d, ,“常量”是标识符形式，在程序里代表同一常数的东西。 用enum定义（枚举）可方便地定义一组符号常量

57、： enum NUM = 10, LEN = 20;,定义枚举常量,例： #include enum START = 0, END = 300, STEP = 20; int main (void) int c; for (c = START; c = END; c += STEP) printf(C = %d, F = %fn, c, c * 5.0/9.0 + 32.0); return 0; /*这样的程序更容易修改*/,符号形式表示能帮人理解程序意义。 程序里两个0可能代表不同意义，数值形式没有任何区分。采用符号常量可提高可读性。 将所需常数定义为符号常量，在程序中统一使用是很好的方法

58、。 使程序更容易修改（修改时不必浏览整个程序）。对大程序的作用更明显。 第五章介绍其他常量定义方式。enum的详细讨论在第九章，目前作为一种定义符号整型常量的机制。,单词计数问题 正文文件可看成字符序列，空白字符（空格 、制表符t、换行符n）把序列分隔为一个个“单词”。要求写程序统计文件中的单词个数。,需要一个计数器，遇到一个词将计数器加一。 考虑用函数getchar读字符。程序主要部分的框架： while (文件未结束) 遇到一个词时计数器加一; 打印统计信息;,用getchar输入，很容易判断文件结束。问题是如何确定“遇到了一个词”。,若读的字符是单词首字符，则计数器加一。 读入字符过程中需要区分是否空白。 问题：非空白字符未必是词的开始，是否新词要看前一字符是否空白。可见：不能孤立地处理，要参考前面情况。必须做情况记录，以便后面参考。,前后关系分两种情况：1）读到空白，随后遇非空白字符就是新词；2）读到非空白，随后不会遇到新词。 可看作处理过程的不同状态。两种状态：1）读在词外（遇到非空白是新词）；2）读在词内。 在读入字符的过程中读入状态也不断转换。,典型，可以用有限状态转换系统（自动机）描述。,IN/OUT（词里/词外）表示两种读入状态。 读字符的动态过程可以用图示形象描述。 在从OUT转换到IN时，遇到新词，计数。,