《基本程序设计技术讲稿.ppt》由会员分享，可在线阅读，更多相关《基本程序设计技术讲稿.ppt（109页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于基本程序设计技术第一页，讲稿共一百零九页哦第四章第四章基本程序设计技术基本程序设计技术第二页，讲稿共一百零九页哦学习程序设计需要注意规律性的东西。学习程序设计需要注意规律性的东西。三种流程模式是重要总结。三种流程模式是重要总结。本章还讨论：本章还讨论：基本输入和输出基本输入和输出递归的程序设计递归的程序设计其他控制结构其他控制结构顺序模式最简单顺序模式最简单选择模式：要确定判断条件及不同情况下的动作选择模式：要确定判断条件及不同情况下的动作开开始始的的难难点点在在实实现现重重复复执执行行的的循循环环。重重复复执执行行比比较较复复杂，牵涉问题多，是本章重点杂，牵涉问题多，是本章重点第三页，讲
2、稿共一百零九页哦4.1循环程序设计循环程序设计写循环首先要发现循环。注意计算中的重复性动作，引写循环首先要发现循环。注意计算中的重复性动作，引进循环可能统一描述和处理。进循环可能统一描述和处理。重复动作的常见实例：重复动作的常见实例：一批类似数据做同样加工处理一批类似数据做同样加工处理累积一批可按规律算出的数据（累加等）累积一批可按规律算出的数据（累加等）反复从一个结果算出下一结果（递推）反复从一个结果算出下一结果（递推）若重复次数若重复次数很多很多，就应该考虑用循环，就应该考虑用循环如果重复次数如果重复次数无法确定无法确定，就必须用循环描述，就必须用循环描述第四页，讲稿共一百零九页哦例：求例
3、：求13到到315所有数的平方根之和。所有数的平方根之和。可以一个个地加，但更方便的方法是写循环。可以一个个地加，但更方便的方法是写循环。需要一个变量保存部分和，逐步把各平方根加上去；需要一个变量保存部分和，逐步把各平方根加上去；需要一个变量保存变动轨迹，从初值开始每次修改。需要一个变量保存变动轨迹，从初值开始每次修改。典型典型for循环。假定已有总和变量循环。假定已有总和变量sum和循环变量和循环变量n：for(sum=0.0,n=13;n=13;-n)sum+=sqrt(n);这里的两个循环等效。一般采用向上循环这里的两个循环等效。一般采用向上循环第五页，讲稿共一百零九页哦可以用可以用wh
4、ile语句重写，两种结构功能上等效。语句重写，两种结构功能上等效。例，求例，求 13,315 间每隔间每隔7的各整数的平方根之和。的各整数的平方根之和。一般不用浮点数控制循环一般不用浮点数控制循环，尤其是增量为小数或包含小数时。，尤其是增量为小数或包含小数时。例：求从例：求从0到到100每隔每隔0.2的数的平方根之和：的数的平方根之和：doublesum,x;for(sum=0.0,x=0.2;x=100.0;x+=0.2)sum+=sqrt(x);由于浮点计算误差，不能保证循环由于浮点计算误差，不能保证循环500次。应写：次。应写：intn;doublesum;for(sum=0.0,n=1
5、;n=500;+n)sum+=sqrt(0.2*n);第六页，讲稿共一百零九页哦例例1：打印出打印出 1 到到 200 间的完全平方数。间的完全平方数。方法一方法一：逐个检查，遇平方数打印。：逐个检查，遇平方数打印。重复做，每次检查一个数。循环框架：重复做，每次检查一个数。循环框架：for(n=1;n=200;n+)if(n是完全平方数是完全平方数)打印打印n;需填充：数是否完全平方数，没有直接判断手段。需填充：数是否完全平方数，没有直接判断手段。可以可以顺序检查，顺序检查，是否存在是否存在某数，其平方恰为某数，其平方恰为n。这构成（循环内的）新循环，需要一个新循环变量。这构成（循环内的）新循
6、环，需要一个新循环变量。m可以从可以从1开始，递增，开始，递增，直至直至m*m大于大于n：for(m=1;m*m=n;m+)if(m*m=n)打印打印n;第七页，讲稿共一百零九页哦综合起来可得到完整程序：综合起来可得到完整程序：#includeintmain()intm,n;for(n=1;n=200;n+)for(m=1;m*m=n;m+)if(m*m=n)printf(%d,n);printf(n);/*最后输出一个换行符最后输出一个换行符*/return0;内层循环结束：内层循环结束：1，找到，找到m使使m*m=n（n是完全平方数）是完全平方数）2，试探了所有可能，但都不成功（，试探了所
7、有可能，但都不成功（n不是不是）第八页，讲稿共一百零九页哦方方法法二二：需需要要打打印印的的一一定定是是从从1开开始始连连续续几几个个整整数数的的平平方方，可可从从1开始打印到平方大于开始打印到平方大于200为止。为止。for(n=1;n*n=200;+n)printf(%d,n*n);/*注意打印什么注意打印什么*/还可以考虑利用递推公式：还可以考虑利用递推公式：方方法法一一：产产生生所所有有备备选选数数据据（1到到200的的整整数数），检检查查排排除除不不合格的。合格的。生成与检查生成与检查是解决问题的常用方法。是解决问题的常用方法。方法二是针对具体问题的特定方法。方法二是针对具体问题的特
8、定方法。第九页，讲稿共一百零九页哦例例 2：写函数判断整数是否为素数（谓词）。写函数判断整数是否为素数（谓词）。类型特征可用类型特征可用intisprime(int)，返回，返回0/1值值n是素数则它没有真因子，是素数则它没有真因子，m是是n的因子用的因子用(n%m=0)描描述，若述，若mn就够了。就够了。函数定义：函数定义：intisprime(intn)/*n是否素数是否素数*/intm=2;for(;m*m=n;m+)if(n%m=0)return0;return1;/*没有因子，是素数没有因子，是素数*/第十页，讲稿共一百零九页哦从从循循环环中中退退出出：isprime发发现现一一个个
9、因因子子就就可可做做结结论论。return使函数结束，也导致循环结束。使函数结束，也导致循环结束。函函数数不不完完善善，对对1给给出出“是是素素数数”，负负数数也也会会给给出出不不合合理理结果。结果。应该在循环前处理特殊情况：应该在循环前处理特殊情况：if(n=1)return0;负数问题？负数问题？如果需要可以另外考虑处理。如果需要可以另外考虑处理。第十一页，讲稿共一百零九页哦例例3，艰难旅程（浮点误差）。乌龟要去环球。第艰难旅程（浮点误差）。乌龟要去环球。第1秒爬秒爬1米，米，第第2秒爬秒爬1/2米，第米，第3秒爬秒爬1/3米，第米，第4秒爬秒爬1/4米，米，。问一小。问一小时能爬出多远？
10、爬时能爬出多远？爬20米需多少秒？米需多少秒？根据数学，乌龟能完成环球，可以爬得任意远。根据数学，乌龟能完成环球，可以爬得任意远。这里想比较这里想比较float和和double的计算误差情况。的计算误差情况。这里只考虑这里只考虑20米需要多少时间。写出下面函数：米需要多少时间。写出下面函数：longscndsf(floatd)longi;floatx=0.0;for(i=1;xd;+i)x+=1/(float)i;returni-1;第十二页，讲稿共一百零九页哦写下面语句，执行时总也不输出：写下面语句，执行时总也不输出：printf(%lds,%fmn,scndsf(20.),20.);修改为
11、如下语句：修改为如下语句：for(x=10.0;x=1E-6)x1=x2;x2=(2.0*x1+x/(x1*x1)/3.0;returnx2;这这个个程程序序的的一一个个缺缺点点是是同同一一表表达达式式写写了了两两次次。书书上上利利用用C的的特点给了一种简化写法，供参考特点给了一种简化写法，供参考学习了其他结构后有改进的写法学习了其他结构后有改进的写法第十七页，讲稿共一百零九页哦例例5：定义函数，利用公式：定义函数，利用公式求求 近似值。设为近似值。设为doubledsin(doublex)。方法：循环累加，方法：循环累加，n 趋向无穷的过程中项值趋于趋向无穷的过程中项值趋于0，而累加，而累加
12、值趋向函数值。值趋向函数值。需要用循环需要用循环。保存累加和的变量保存累加和的变量sum，循环中求出的项值用，循环中求出的项值用 t 保存。保存。sum=0.0;对对n为为0计算计算t;while(需要继续需要继续)sum=sum+t;计算下一个计算下一个t;循环结束条件：例如用项绝对值小于循环结束条件：例如用项绝对值小于 。第十八页，讲稿共一百零九页哦问题：问题：t 的值如何计算？的值如何计算？第一个第一个 t就是就是 x;分析可以发现项值的递推公式：分析可以发现项值的递推公式：doubledsin(doublex)doubles=0.0,t=x;intn=0;while(t=1E-6|t=
13、-1E-6)s+=t;n=n+1;t=-t*x*x/(2*n)/(2*n+1);returns;第十九页，讲稿共一百零九页哦一些情况一些情况：实参值很小时，循环将很快结束。实参值很小时，循环将很快结束。实参绝对值很大时循环可能做许多次，项的绝对值可能达到实参绝对值很大时循环可能做许多次，项的绝对值可能达到很大，很大，n 值也可能超出整数的表示范围值也可能超出整数的表示范围可考虑用可考虑用fmod把参数归约到把参数归约到0，2 之内之内启示启示：理解问题非常重要。发现了项的递推性质能节省许多计算理解问题非常重要。发现了项的递推性质能节省许多计算（否则就要再写一个嵌套循环完成项的计算）（否则就要再
14、写一个嵌套循环完成项的计算）级数收敛性质能帮人认识情况，改进计算方法级数收敛性质能帮人认识情况，改进计算方法写程序时必须仔细考虑问题本身的性质写程序时必须仔细考虑问题本身的性质第二十页，讲稿共一百零九页哦4.2 循环中的问题循环中的问题从循环中退出从循环中退出有时需要从正在执行的循环中退出。有时需要从正在执行的循环中退出。对对6200的各偶数验证哥德巴赫猜想，利用的各偶数验证哥德巴赫猜想，利用isprime：for(n=6;n=200;n+=2)for(m=3;m=n/2;m+=2)if(isprime(m)&isprime(n-m)printf(%d=%d+%dn,n,m,n-m);问题：有
15、多种分解时将产生多对输出。如对问题：有多种分解时将产生多对输出。如对10：10=3+710=5+5前面写前面写isprime时借助时借助return退退出了循环出了循环第二十一页，讲稿共一百零九页哦希望每个偶数只输出一行。希望每个偶数只输出一行。怎样在发现素数对后停止？增加对循环的控制：把发现素数怎样在发现素数对后停止？增加对循环的控制：把发现素数分解作为条件加入。分解作为条件加入。引入整型变量引入整型变量found，值，值0表示未发现素数对。发现时将表示未发现素数对。发现时将found赋赋1。内循环开始时。内循环开始时found置置0。应修改内层循环条件。应修改内层循环条件。修改后循环是：修
16、改后循环是：for(n=6;n=200;n+=2)for(found=0,m=3;m=n/2&!found;m+=2)if(isprime(m)&isprime(n-m)printf(%d=%d+%dn,n,m,n-m);found=1;这种需求很常见。这种需求很常见。C语言引进了专门的控制语句语言引进了专门的控制语句第二十二页，讲稿共一百零九页哦break语句语句，形式：，形式：break;break只能用在循环语句（及只能用在循环语句（及switch语句）里，使最内层（循语句）里，使最内层（循环可嵌套）循环语句（或环可嵌套）循环语句（或switch）立即停止，执行从被终止）立即停止，执行从
17、被终止循环（或循环（或switch）之后继续。）之后继续。可可用用break解解决决循循环环中中退退出出问问题题，放放在在条条件件下下。完完成成前前例例的的程序段：程序段：for(n=6;n=200;n+=2)for(m=3;m=n/2;m+=2)if(isPrime(m)&isPrime(n-m)printf(%d=%d+%dn,n,m,n-m);break;第二十三页，讲稿共一百零九页哦利用利用break重写前面求立方根的函数：重写前面求立方根的函数：doublecbrt(doublex)doublex1,x2=x;if(x=0.0)return0.0;while(1)x1=x2;x2=(
18、2.0*x1+x/(x1*x1)/3.0;if(fabs(x2-x1)/x1)1E-6)break;returnx2;也可以在也可以在break处直接写处直接写returnx2。第二十四页，讲稿共一百零九页哦循环中的几种变量循环中的几种变量循循环环中中常常出出现现几几类类变变量量，注注意意这这些些有有助助于于对对循循环环的的思思考考和和分析。也是写循环程序的经验总结分析。也是写循环程序的经验总结注意：分类不是绝对的，不同类别没有截然界限注意：分类不是绝对的，不同类别没有截然界限1）循环控制变量）循环控制变量(循环变量循环变量)：循环前设初值，循环中递增：循环前设初值，循环中递增/递递减，达到减
19、，达到/超过界限时循环结束。它们控制循环的进行超过界限时循环结束。它们控制循环的进行/结束。结束。for中常有这类变量。中常有这类变量。for(n=0;n=0;-n).for(n=2;n52;n+=4).这种循环是固定次数的循环。这种循环可能展开这种循环是固定次数的循环。这种循环可能展开第二十五页，讲稿共一百零九页哦2）累积变量：循环中常用）累积变量：循环中常用+=或或*=等更新。初值常用运算等更新。初值常用运算的单位元（加用的单位元（加用0；乘用；乘用1为初值）。循环结束时变量终值为初值）。循环结束时变量终值被作为循环计算结果。被作为循环计算结果。3）递推变量：前两类变量的推广。几个协同工作
20、的变量，每）递推变量：前两类变量的推广。几个协同工作的变量，每次由几个变量推出一个新值，其余依次更新。次由几个变量推出一个新值，其余依次更新。对变量对变量x1、x2、x3，循环体可能有序列：，循环体可能有序列：x1=x2;x2=x3;x3=.x1.x2.;例如上面例如上面cbrt里的变量里的变量x1和和x2。第二十六页，讲稿共一百零九页哦写循环时要考虑和解决问题列表写循环时要考虑和解决问题列表：循环涉及到哪些变量，需引进哪些临时性变量？循环涉及到哪些变量，需引进哪些临时性变量？循环如何开始？循环开始前给变量什么初值？循环中变量循环如何开始？循环开始前给变量什么初值？循环中变量的值如何改变？的值
21、如何改变？什么情况下继续（或终止）循环？什么情况下继续（或终止）循环？循环终止后如何得到所需结果？循环终止后如何得到所需结果？用哪种结构实现循环，等等。用哪种结构实现循环，等等。工作方式工作方式：分析问题，发掘线索，最终完成程序。：分析问题，发掘线索，最终完成程序。程序设计不是教条，典型问题也无标准答案。并非最简单的问程序设计不是教条，典型问题也无标准答案。并非最简单的问题总有多种解决方法，往往各有长短。题总有多种解决方法，往往各有长短。“正确正确”程序常有优劣之分。程序常有优劣之分。第二十七页，讲稿共一百零九页哦4.3循环与递归循环与递归程序中有循环可能导致很长的计算。程序中有循环可能导致很
22、长的计算。没有循环结构也能描述这类计算。没有循环结构也能描述这类计算。C语言允许递归，可在函语言允许递归，可在函数内调用自身，程序常常更简单清晰。数内调用自身，程序常常更简单清晰。例：定义计算整数阶乘的函数：例：定义计算整数阶乘的函数：12(n-1)n乘的次数依赖于乘的次数依赖于n，定义时不知道，每次用可能不同。，定义时不知道，每次用可能不同。程序的典型情况：计算程序的典型情况：计算“次数次数”依赖某些参数的值。依赖某些参数的值。省略号不科学。严格定义需用递归形式。省略号不科学。严格定义需用递归形式。第二十八页，讲稿共一百零九页哦注意递归定义的形式。这也提出了一种计算方法。注意递归定义的形式。
23、这也提出了一种计算方法。如果语言允许递归定义函数，就可以直接翻译为程序。如果语言允许递归定义函数，就可以直接翻译为程序。C允许递归定义：在函数定义内调用被定义函数本身。允许递归定义：在函数定义内调用被定义函数本身。类型特征可定为：类型特征可定为：intfact(int)阶乘值增长极快（数学），更合适的类型特征：阶乘值增长极快（数学），更合适的类型特征：longfact(long)第二十九页，讲稿共一百零九页哦递归的函数定义：递归的函数定义：longfact(longn)returnn=0?1:n*fact(n-1);也可以用循环定义：也可以用循环定义：longfact1(longn)longi
24、,f=1;for(i=2;i=n;+i)f*=i;returnf;比递归定义长，需要引进多个局部变量。比递归定义长，需要引进多个局部变量。第三十页，讲稿共一百零九页哦fact实现的计算过程很不实现的计算过程很不简单。简单。计算中计算中fact被递归调用的被递归调用的次数由实参确定。次数由实参确定。考虑负参数值处理。可改为：考虑负参数值处理。可改为：n=1?1:.第三十一页，讲稿共一百零九页哦递归定义导致的计算过程递归定义导致的计算过程参数不同参数不同fact递归调用次数（步数）不同。递归调用次数（步数）不同。定义定义只有一个只有一个语句语句，可能要许多步才能完成。包含递归，可能要许多步才能完成
25、。包含递归（和循环）的程序产生的计算过程和性质更复杂，能完成（和循环）的程序产生的计算过程和性质更复杂，能完成更复杂工作，理解和书写也更困难。更复杂工作，理解和书写也更困难。递归的函数定义需要条件表达式或递归的函数定义需要条件表达式或if，必须区分：，必须区分：直接给出结果的情况直接给出结果的情况。是递归的基础。是递归的基础需需要要递递归归处处理理的的情情况况。其其中中把把对对较较复复杂杂情情况况的的计计算算归归结结为对更简单情况的计算为对更简单情况的计算基基本本运运算算/关关系系判判断断/条条件件表表达达式式，加加函函数数定定义义和和递递归归定定义义构构成成了一个（理论上）了一个（理论上）“
26、足够强的足够强的”的程序语言的程序语言。第三十二页，讲稿共一百零九页哦程序实例程序实例Fibonacci（斐波那契）序列的递归定义：（斐波那契）序列的递归定义：Fibonacci 序列增长很快，返回值选序列增长很快，返回值选long。递归定义。递归定义：longfib(intn)returnn2?1:fib(n-1)+fib(n-2);负参数值定义为负参数值定义为 1。这是。这是“合理合理”处置。处置。问题分析问题分析：这个程序好不好？：这个程序好不好？一一方方面面，很很好好！程程序序与与数数学学定定义义的的关关系系很很清清晰晰，正正确确性性容容易易确认，定义易读易理解。确认，定义易读易理解。
27、第三十三页，讲稿共一百零九页哦但这个定义有一个本质性缺点。示意图：但这个定义有一个本质性缺点。示意图：第三十四页，讲稿共一百零九页哦存在大量重复计算，参数越大重复计算越多。存在大量重复计算，参数越大重复计算越多。有关系吗？有关系吗？随随着着参参数数增增大大，计计算算中中重重复复增增长长迅迅速速，最最快快的的微微机机上上一一分分钟大约可以算出钟大约可以算出fib(45)参参数数加加1，fib多多用用近近一一倍倍时时间间(指指数数增增长长)。最最快快的的微微机机一一小时算不出小时算不出fib(55)，算，算fib(100)要数万年要数万年计计算算需需时时间间，复复杂杂计计算算需需要要很很长长时时间
28、间。这这是是计计算算机机的的本本质质特特征征/弱点。说明它不万能，有些事清弱点。说明它不万能，有些事清“不能不能”做。做。求求Fibonacci 值有更好计算办法（下面介绍）。值有更好计算办法（下面介绍）。第三十五页，讲稿共一百零九页哦人人们们发发现现了了许许多多实实际际问问题题，理理论论上上说说可可用用计计算算机机解解决决（可可写写出出计计算算它它的的程程序序），但但对对规规模模大大的的情情况况（“大大的的参参数数 n”），人人类类永远等不到计算完成。永远等不到计算完成。这时能说问题解决了吗？这时能说问题解决了吗？理解这个情况对于理解计算机是非常重要的。理解这个情况对于理解计算机是非常重要的
29、。这这里里有有一一大大类类问问题题称称为为计计算算中中的的“难难解解问问题题”，其其中中有有许多很实际的问题（规划、调度、优化等）。许多很实际的问题（规划、调度、优化等）。这这方方面面的的理理论论和和实实际际技技术术的的研研究究极极为为重重要要：计计算算复复杂杂性性，难难解解问题，问题，“P=NP？”问题。问题。另另外外，对对于于许许多多问问题题的的实实用用的的有有效效算算法法，有有极极大大的的理理论论价值和实际价值。价值和实际价值。第三十六页，讲稿共一百零九页哦为计算过程计时为计算过程计时统统计计程程序序/程程序序片片段段的的计计算算时时间间有有助助于于理理解解程程序序性性质质。许许多多语语
30、言或系统都提供了内部计时功能。言或系统都提供了内部计时功能。有关函数在有关函数在time.h，统计程序时间时程序头部应写：，统计程序时间时程序头部应写：#include在程序里计时，通常写表达式：在程序里计时，通常写表达式：clock()/CLOCKS_PER_SEC得到得到从程序开始到表达式求值从程序开始到表达式求值时所经历的秒数。时所经历的秒数。注意：有些老的注意：有些老的C系统（如系统（如Turbe-C）用）用 CLK_TCK。第三十七页，讲稿共一百零九页哦确定计算确定计算fib(45)所需要的时间的程序：所需要的时间的程序：#include#includelongfib(intn)re
31、turnn=1?1:fib(n-1)+fib(n-2);intmain()/*自己做其他试验自己做其他试验*/doublex;x=clock()/CLK_TCK;fib(45);x=clock()/CLK_TCK-x;printf(Timingfib(45):%f.n,x);return0;第三十八页，讲稿共一百零九页哦Fibonacci数的递推计算数的递推计算 易见易见 1）F1和和F2是是12）知道连续两个）知道连续两个Fibonacci数，就可算出下一个数，就可算出下一个递推计算方式：逐个前推，可用循环实现：递推计算方式：逐个前推，可用循环实现：longfib1(intn)longa=1
32、,b=1,c,i;if(n=1)return1;for(c=a+b,i=2;in;+i)a=b;b=c;c=a+b;returnc;/*对吗？对吗？*/第三十九页，讲稿共一百零九页哦循环结束时循环结束时i等于等于n，这时，这时c的值是的值是Fn。要得到此结论，可设。要得到此结论，可设法证明：法证明：每次判断每次判断 i 的值时的值时c正是正是Fi。上面循环保证这种关系，可以通过归纳证明：上面循环保证这种关系，可以通过归纳证明：for(c=a+b,i=2;in;+i)a=b;b=c;c=a+b;第一次判断时第一次判断时 i 的值是的值是 2，c 的值的值2，正是，正是 Fi（且（且 a 的值是的
33、值是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。第四十页，讲稿共一百零九页哦循环实现重复性计算，循环体可能执行多次。如何保证对各循环实现重复性计算，循环体可能执行多次。如何保证对各种数据都能正确完成计算？种数据都能正确完成计算？循环中变量不断变化。写循环要考虑变量间的关系，保循环中变量不断变
34、化。写循环要考虑变量间的关系，保证某些关系在循环中不变：证某些关系在循环中不变：循环的不变关系循环的不变关系。写循环时最重要的就是想清写循环时最重要的就是想清循环中应维持变量间的什么关循环中应维持变量间的什么关系系才能保证循环结束时变量能处在所需状态。写完循环后才能保证循环结束时变量能处在所需状态。写完循环后应仔细检查是否满足要求。应仔细检查是否满足要求。循环不变关系（循环不变关系（循环不变量循环不变量）是理解循环、写好循环的）是理解循环、写好循环的关键。这个方面有很多研究，有许多理论结果。关键。这个方面有很多研究，有许多理论结果。第四十一页，讲稿共一百零九页哦问题：用循环的函数比用递归定义的
35、好吗？问题：用循环的函数比用递归定义的好吗？新新函函数数在在计计算算时时间间上上有有极极大大优优越越性性。计计算算时时间间由由循循环环次次数数确确定定。循循环环体体执执行行次次数数大大致致为为n。fib(100)只只需需约约100次循环，几乎察觉不到所花费时间。次循环，几乎察觉不到所花费时间。新新函函数数定定义义较较复复杂杂，有有复复杂杂的的循循环环。要要理理解解程程序序意意义义，确确认认函函数数对对任任何何参参数数都都算算出出Fibonacci值值，需需要要借借助助“循循环不变关系环不变关系”的概念和细致分析。的概念和细致分析。上上面面分分析析中中没没考考虑虑数数据据表表示示范范围围，lon
36、g类类型型一一般般无无法法表表示示fib(100)。注意：这个例子并不是说明递归比循环的效率低。完全可以注意：这个例子并不是说明递归比循环的效率低。完全可以写出计算写出计算fib的同样高效的递归定义的函数的同样高效的递归定义的函数第四十二页，讲稿共一百零九页哦求最大公约数求最大公约数（greatest common divisor，GCD）：写函数写函数longgcd(long,long)方式方式1：k取初值取初值1后递增，大于后递增，大于m或或n之一时结束。之一时结束。如何得到所需结果如何得到所需结果?m和和n可能有多个公约数，最后的可能有多个公约数，最后的k值不值不是是m和和n的公约数（它
37、已大于两数之一）。的公约数（它已大于两数之一）。解法解法1：逐个检查，直到找到能同时整除：逐个检查，直到找到能同时整除m和和n的最大整数的最大整数（生成与检查）。需辅助变量（生成与检查）。需辅助变量k记录检查值。简单方式：记录检查值。简单方式：k顺序取值（初值顺序取值（初值/更新更新/结束），可用循环实现。结束），可用循环实现。需要记录循环中找到的公约数。需要记录循环中找到的公约数。第四十三页，讲稿共一百零九页哦只需记录已找到最大的公约数，用变量只需记录已找到最大的公约数，用变量d，初值，初值1（是公约数）（是公约数），遇到新公约数（一定更大）时记入，遇到新公约数（一定更大）时记入d：if(m
38、%k=0&n%k=0)d=k;/*k为新找到的公约数为新找到的公约数*/有了有了d及其初值，及其初值，k可以从可以从2开始循环。函数定义：开始循环。函数定义：longgcd(longm,longn)longd=1,k=2;for(;k=m&k=n;k+)if(m%k=0&n%k=0)d=k;returnd;参数互素时初值参数互素时初值1会留下来，也正确。会留下来，也正确。第四十四页，讲稿共一百零九页哦还有一些特殊情况需要处理：还有一些特殊情况需要处理：1）m和和n都为都为0需特殊处理。例如令函数返回值需特殊处理。例如令函数返回值0；2）若若m和和n中中一一个个为为0，gcd是是另另一一个个数数
39、。函函数数的的返返回回值值正正确确。也可直接判断处理；也可直接判断处理；3）m、n为负时函数返回为负时函数返回1，可能不对。，可能不对。应在循环前加语句：应在循环前加语句：if(m=0&n=0)return0;if(m0)m=-m;if(nn?n:m);m%k!=0|n%k!=0;k-);/*空循环体空循环体*/returnk;/*循环结束时循环结束时k是最大公约数是最大公约数*/本方法比前一方法简单一些。本方法比前一方法简单一些。两两种种方方法法的的共共同同点点是是重重复复测测试试。这这类类方方法法的的缺缺点点是是效效率率较较低低，参数大时循环次数很多。参数大时循环次数很多。第四十六页，讲稿
40、共一百零九页哦解法解法2：求：求GCD有著名的欧几里德算法（欧氏算法，辗转相除有著名的欧几里德算法（欧氏算法，辗转相除法）。最大公约数的递归定义：法）。最大公约数的递归定义：函函数数定定义义（递递归归）：假假设设第第二二个个参参数数非非0，且且参参数数都都不不小小于于0。与数学定义直接对应：。与数学定义直接对应：longgcd1(longm,longn)returnm%n=0?n:gcd1(n,m%n);对对欧欧氏氏算算法法的的研研究究保保证证了了本本函函数数能能结结束束，对对较较大大的的数数计计算算速度也很快，远远优于顺序检查。速度也很快，远远优于顺序检查。第四十七页，讲稿共一百零九页哦对特
41、殊情况可另写一函数，其主体是对对特殊情况可另写一函数，其主体是对gcd1的调用：的调用：longgcd(longm,longn)if(m0)m=-m;if(n%cn,from,to);voidhenoi(intn,charfrom,charto,charby)if(n=1)moveone(from,to);elsehenoi(n-1,from,by,to);moveone(from,to);henoi(n-1,by,to,from);moveone定义为函数是为了方便。定义为函数是为了方便。函数调用：函数调用：henoi(6,a,b,c);第五十三页，讲稿共一百零九页哦4.4 基本输入输出（基
42、本输入输出（IO）IO通过标准库进行通过标准库进行常用函数常用函数scanfgetcharputchar需要需要（同（同printf）第五十四页，讲稿共一百零九页哦格式输入函数格式输入函数scanf功能与功能与printf对应。对应。scanf从从标标准准输输入入读读数数据据，根根据据格格式式描描述述将将实实际际输输入入转转换换到到指指定类型，转换结果赋给指定变量：定类型，转换结果赋给指定变量：scanf(格式描述串格式描述串,&变量名变量名,.)格格式式描描述述串串与与printf的的类类似似，其其中中的的转转换换描描述述（以以%开开头头）说明输入形式和转换方式。说明输入形式和转换方式。其其
43、他他参参数数（个个数数应应与与格格式式串串中中转转换换描描述述一一致致）指指明明接接受受输输入入的的程程序变量。形式是在序变量。形式是在变量名变量名前面加前面加&符号。符号。注意：注意：必须写必须写&符号，不写将引起严重问题符号，不写将引起严重问题。第五十五页，讲稿共一百零九页哦简单示例：简单示例：#includeintmain()inti,n;printf(Pleaseinputanumber:);scanf(%d,&n);printf(%d%dn,n,n*n);return0;程序执行后输出提示串：程序执行后输出提示串：Pleaseinputanumber:等等待待人人的的输输入入。得得到
44、到输输入入数数据据后后输输出出并并结结束束。程程序序的的行行为依赖于当时的输入（与前面程序不同）为依赖于当时的输入（与前面程序不同）第五十六页，讲稿共一百零九页哦注意实数类型的转换描述与注意实数类型的转换描述与printf的的差异差异。例：设有变量定义：例：设有变量定义：intn;doublex;floaty;可以写语句：可以写语句：scanf(%d%lf%f,&n,&x,&y);常用的常用的 scanf转换描述：转换描述：第五十七页，讲稿共一百零九页哦读数值时，读数值时，sacnf格式串里的格式串里的转换描述之间的空格并不必要。转换描述之间的空格并不必要。上面语句写成下面形式，效果一样。：上
45、面语句写成下面形式，效果一样。：scanf(%d%lf%f,&n,&x,&y);如果如果这里这里的转换描述之间没字符或只有空格，输入的数据的转换描述之间没字符或只有空格，输入的数据之间也只能有空白字符，不能有其他字符。之间也只能有空白字符，不能有其他字符。格式串里一般不写转换描述之外的东西。如果格式串里一般不写转换描述之外的东西。如果写写%d,%lf,%f就是要求用逗号分隔输入数据，若输入时不注意就会导致数就是要求用逗号分隔输入数据，若输入时不注意就会导致数据不能正常读入。建议不要这样写。据不能正常读入。建议不要这样写。scanf格式串的细节在第八章有详细介绍。格式串的细节在第八章有详细介绍。
46、第五十八页，讲稿共一百零九页哦缓冲式输入缓冲式输入若程序要求从标准输入取得信息（如执行若程序要求从标准输入取得信息（如执行scanf），我们由键），我们由键盘输入，在按盘输入，在按Enter键后程序才能得到输入数据键后程序才能得到输入数据造成这种情况的原因是操作系统通常采用造成这种情况的原因是操作系统通常采用“缓冲式缓冲式”输入方式，输入方式，把来自键盘的输入临时保存在把来自键盘的输入临时保存在“输入缓冲区输入缓冲区”（操作系统管理（操作系统管理下的一块内存区域）里，直至人按了下的一块内存区域）里，直至人按了Enter键，才把缓冲区里键，才把缓冲区里的数据送给程序，这时的数据送给程序，这时sc
47、anf等输入函数才能读到数据等输入函数才能读到数据程序经常需要输入一批数据，通过一个循环处理。为此需要在程序经常需要输入一批数据，通过一个循环处理。为此需要在循环中反复调用输入函数循环中反复调用输入函数下面讨论这种循环输入中的控制问题下面讨论这种循环输入中的控制问题第五十九页，讲稿共一百零九页哦通过计数器控制的输入循环通过计数器控制的输入循环如果事先知道需要输入的数据项数，就可以用计数器控制输入如果事先知道需要输入的数据项数，就可以用计数器控制输入循环。如由各月降雨量统计一年总量：循环。如由各月降雨量统计一年总量：#includeintmain()doublex,sum;intn;for(su
48、m=0,n=0;n12;+n)printf(Enternextdata:);scanf(%lf,&x);sum+=x;printf(AnnualPrecipitation:%fn,sum);return0;第六十页，讲稿共一百零九页哦假定写程序时不清楚需要输入的数据的确切项数，就无法假定写程序时不清楚需要输入的数据的确切项数，就无法采用计数循环的简单方法。采用计数循环的简单方法。一种方式是用一个特殊一种方式是用一个特殊“结束标志结束标志”控制循环。该控制循环。该“结束标结束标志志”应是一个特殊输入值，具有与输入数据同样的类型，但又应是一个特殊输入值，具有与输入数据同样的类型，但又不是正常输入数
49、据。不是正常输入数据。让程序在循环中不断检测得到的数据，一旦看到这个特殊让程序在循环中不断检测得到的数据，一旦看到这个特殊数据，就知道用户要求结束了。数据，就知道用户要求结束了。采用这种技术，循环结束条件就是写程序的人与使用者采用这种技术，循环结束条件就是写程序的人与使用者之间的一种约定，当输入满足约定时程序就结束。之间的一种约定，当输入满足约定时程序就结束。用特殊结束值控制输入循环用特殊结束值控制输入循环第六十一页，讲稿共一百零九页哦例，计算货物总值，每次输入单价和数量。可考虑用特殊例，计算货物总值，每次输入单价和数量。可考虑用特殊值通知程序数据已输入完，例如用单价为值通知程序数据已输入完，
50、例如用单价为0。#includeintmain()doubleprice=1.0,amount,sum=0.0;while(price!=0)printf(Nextdata(priceamount):);scanf(%lf%lf,&price,&amount);sum+=price*amount;printf(Totalprice:%fn,sum);return0;这个程序中循环体的执行次数，完全由程序执行时外部提供这个程序中循环体的执行次数，完全由程序执行时外部提供的输入数据项数决定。的输入数据项数决定。第六十二页，讲稿共一百零九页哦上面两种方式可以解决许多数据输入循环的控制问题，上面两种方