lh循环结构程序设计

设有两个正整数m和n，如何求其最大公约数？,有多种方法，例如：令k等于从m和n中较小的数，用k去除m和n，若不能整除，则令k的值减去1，直到某个值能同时将m和n整除。,求最大公约数,求最大公约数(笨办法),#include int main( ) int m, n, k; scanf(%d%d,设有两个正整数m和n，如何求其最大公约数？,有多种方法，例如：令k等于m和n中的较小者，用k去除m和n，若不能整除，则令k的值减去1，直到某个值能同时将m和n整除。求解速度最快的方法是辗转相除法。,辗转相除法(欧几里得算法)：给定两个正整数m和n，求它们的最大公约数(公因子)。步骤1:【求余数】以n除m并令r为所得余数(0rn)步骤2:【余数为0?】若r=0，则算法结束；n即为答案步骤3:【互换】置mn， nr，转向步骤1。,求最大公约数,求最大公约数,求最大公约数流程图,求最大公约数程序,#include int main( ) return 0;,Y,N,r不等于0?,输出n的值,输入正整数m和n,开始,结束,m n; n rr m % n,r m % n,while (r != 0) m = n; n = r; r = m % n;,printf(input two integers:);scanf(%d%d,r = m % n;,int m, n, r;,printf(ngcd = %dn ,n);,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;,while和switch综合运用示例,主要内容,for语句break语句continue语句do-while语句,C的循环语句,C语言提供了描述循环计算的语句： while语句 for语句 do.while语句,学习循环结构程序设计就是掌握以上语句的使用方法,分析问题，在求解过程中：存在一个（些）运算（动作）需要重复进行（循环）若干次。重复的次数是事先确定的，或者是根据条件确定的。处理循环计算需要明确的三个问题：循环体：哪些运算（动作）是需要重复进行的；循环条件：重复这些运算的条件是什么，即在什么情况下终止/继续这个重复的过程。循环准备：在进行重复的运算处理之前，需要进行的准备工作是什么；,循环结构程序的编写要点,for语句,for语句的格式和含义,for语句的基本格式：,for(表达式1;表达式2;表达式3) 循环体语句A,for语句的含义：1) 计算表达式1；2) 计算表达式2,若表达式2的值为“假”，则结束for语句的执行,转4)；否则，执行循环体语句A;3) 计算表达式3, 然后转2)；4) 执行for语句之后的第一条语句；,for语句:1+2+.+100,#include main( ) int i, s; printf( %dn ,s);,B,Y,N,I 1S 0,I=100?,S S+I,输出S的值,开始,结束,I I+1,A,C,for(i = 1,s = 0; i = 100;i+) s += i;,#include int main( ) int i, s; i = 1; s = 0; while (i =1; k-) if ( n % k = 0 ,continue语句,continue语句的作用,执行流程到达continue语句时，结束本轮循环，开始下一轮循环,continue语句的应用举例,输出100200之间所有不能被3整除的整数。,#include main( ) int n; for(n = 100; n = 200; n+) if (n % 3 = 0) continue; printf(%dt, n); /*end of for*/,循环语句应用举例,已知鸡兔共笼，头共45个，脚共120只，问鸡、兔各几何？,#include int main( ) int chicken, rabbits; for (chicken = 0; chicken = 45; chicken+) rabbits = 45 chicken; if (chicken * 2 + rabbits * 4 = 120) break; /*end of for*/ printf(chicken: %dt rabbits: %dn , chicken, rabbits); return 0;,a = 0; b = 45;while (2*a+4*b != 120) a+; b-;,单重循环和多重循环,for语句和while语句,for语句的基本格式：,for(表达式1;表达式2;表达式3) 循环体语句A,while语句的格式：,while (表达式p) 循环体语句A,循环语句应用举例,已知鸡兔共笼，头共45个，脚共120只，问鸡、兔各几何？,#include int main( ) int chicken, rabbits; for (chicken = 0; chicken = 45; chicken+) rabbits = 45 chicken; if (chicken * 2 + rabbits * 4 = 120) break; /*end of for*/ printf(chicken: %dt rabbits: %dn , chicken, rabbits); return 0;,循环体语句可以是语言允许的任何语句，多于一条语句时必须用括起来,例如，艰难旅程（浮点误差）。乌龟要去环球。第1秒爬1米，第2秒爬1/2米，第3秒爬1/3米，第4秒爬1/4米，。问一小时能爬出多远？爬20米需多少秒？,这里只考虑爬20米需要多少时间。写出下面的代码：#include #include int main() long i; float x = 0.0; /路程 for (i=1; x20; +i) x = x+ 1.0/i; printf(%ldn,i - 1); return 0;,运行开始运行后，很长时间看不到输出,例如，艰难旅程（浮点误差）。乌龟要去环球。第1秒爬1米，第2秒爬1/2米，第3秒爬1/3米，第4秒爬1/4米，。问一小时能爬出多远？爬20米需多少秒？,#include #include int main()long i=1;float x = 0.0, a=0.0;for (x=10.0; x20.0; x+=1.0)for(; ax; i+)a += 1.0/i;printf(%ld s, %lf m n, i-1, a);return 0;,分别观察： 爬10米所用的时间爬11米所用的时间爬20米所用的时间,输出：12367s, 10.000000m33617s, 11.000000m91328s, 12.000000m248695s, 13.000000m662167s, 14.000000m1673859s, 15.000000m之后有一会儿没反应，然后输出错误的数据（因为溢出）。,例如，艰难旅程（浮点误差）。乌龟要去环球。第1秒爬1米，第2秒爬1/2米，第3秒爬1/3米，第4秒爬1/4米，。问一小时能爬出多远？爬20米需多少秒？,#include #include int main()long i=1;double x = 0.0, a=0.0;for (x=10.0; x20.0; x+=1.0)for(; ax; i+)a += 1.0/i;printf(%ld s, %lf m n, i-1, a);return 0;,很快就输出：12367s, 10.000043m33617s, 11.000018m91380s, 12.000003m248397s, 13.000001m675214s, 14.000001m1835421s, 15.000000m4989191s, 16.000000m13562027s, 17.000000m36865412s, 18.000000m100210581s, 19.000000m272400600s, 20.000000m,将上面代码中的float改为double，20亿秒时还增长，输出： 2000000000s, 21.993629m经过大约63年半，乌龟爬了近22米。在大约2亿5千万秒（约8年）爬过了20米，这是题目第二部分的答案。由于long为32位表示，在此范围内没找到用double类型的增长结束点。但一定比用float大得多。,特殊情况中浮点误差积累可能更迅速。有两个重要情况：将一批小的数加到很大的数上，会导致丢掉小的数的重要部分，甚至小数整个被丢掉（例中情况）两个值接近的数相减，可能导致精度大大下降,百钱百鸡问题,中国古代数学家张丘建在他的算经中曾提出著名的“百钱百鸡问题”，其题目如下： 鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？,百钱百鸡问题,解：设i、j、k分别代表公鸡、母鸡、小鸡的数量，根据题意列方程：,根据题意可知，i、j、k的范围一定是0到100的正整数，那么，最简单的解题方法是：穷举i、j、k每一种可能的取值组合，直接代入方程组，若满足该方程组则是一组解。这样即可得到问题的全部解。,百钱百鸡问题,i 0,i 20?,买母鸡和小鸡,开始,结束,i i + 1,i = 0;while (i 20 ) i+;, int i, j, k; /*i、j、k分别表示公鸡、母鸡和小鸡的数目*/ ,j = 0;while (j 34) j+;,k = 0;while ( k 100) if ( i + j + k = 100 ,百钱百鸡问题(while),输出：0 25 753 20 774 18 787 13 808 11 8111 6 8312 4 84,for(i = 0; i 20; i+ ) /*设定公鸡的数目*/ ,int main( ) int i, j, k; /*i、j、k分别表示公鸡、母鸡和小鸡的数目*/ return 0;,for(j = 0; j 34; j+) /*设定母鸡的数目*/ ,for(k = 0; k 100; k+) /*设定小鸡的数目*/ if ( i + j + k = 100 ,百钱百鸡问题（for）,输出：0 25 754 18 788 11 8112 4 84,for(i = 0; i 20; i+ ) /*设定公鸡的数目*/ ,int main( ) int i, j