过程化语句及程序设计.ppt

第四章 过程化语句及程序设计,第一节 结构化程序设计,结构化程序设计是荷兰科学家在1965年提出的主要思想是通过分解复杂问题为若干简单问题的方式降低程序的复杂性。主要观点是采用自顶向下、逐步细化的程序设计方法同时严格使用三种基本控制结构构造程序。三种基本控制结构是指顺序结构、选择结构和循环结构。所有的程序结构都可以分解为这三个基本控制结构。,三种基本结构,按照操作的执行顺序，程序可以分为三类基本结构：顺序结构选择结构循环结构1996年，计算机科学家Bohm和Jacopini证明：任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这三种结构组合而成。所以，这三种结构就被称为程序设计的三种基本结构，也是结构化程序设计建议采用的结构。,1、顺序结构,在顺序结构的程序里，各操作是按照它们出现的先后顺序执行的。如下图所示，操作1和操作2按自上而下地顺序执行。这是最简单的一种基本结构。这个结构里只有一个入口点A和一个出口点B，其特点是从入口点A开始，按顺序执行所有操作，直至出口点B处。事实上，所有的程序的总流程总是一个顺序结构。,2、选择结构,选择结构，也叫分支结构。选择结构的程序里存在一些分支，程序通过对一些条件的判断选择执行的分支。按照分支数目，选择结构又可以分为单选择、双选择和多选择三种形式。,3、循环结构,在循环结构中，是反复地执行一系列操作，直到某条件为假（或为真）时才终止循环。按照判断条件出现的位置，可以分为while循环结构和until循环结构。,while循环结构,while循环结构中，先判断条件，如下图所示。如果A不大于1，则直接退出循环体到达流程出口处；如果满足A大于1，执行操作1，并且在操作1结束后返回到循环入口，重新判断条件；如果A还是大于1，再次执行操作1，再返回结构入口，如此反复。,until型循环结构,until型循环结构中，在结构入口处先执行循环体，然后再判断条件，如下图所示。当程序执行完操作1后，判断A是否大于1。如果是，则再执行操作1；然后再次判断A是否大于1；如果结果仍然为是，则再次执行操作1,循环结构,在这两种结构中，操作1都可能被反复执行，直到A的值不大于1，才结束程序。同样，循环型结构也只有一个入口点A和一个出口点B。合理地使用顺序结构、选择结构和循环结构这三种基本结构，可以组合成复杂的高级结构；而所有的复杂结构都可以分解为这三种基本结构。,程序和算法,程序=算法+数据结构,对操作的描述。即操作步骤算法(algorithm)。,指定数据的类型和数据的组织形式数据结构(data structure)。,数据结构是一个个实体，是程序存储、组织数据的方式；而算法是将它们联系在一起的手段。,什么是算法,算法就是解决一个问题的完整的步骤描述，是指完成一个任务准确而完整的步骤描述，也就是说给于初始状态或数据，按照算法描述的步骤进行运算，能够得出所要求或所期望的终止状态或输出数据。解决一个问题的方法有高明的的，也有糟糕的；同样，同一个问题的算法也存在优劣之分。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。,算法优劣的衡量,算法的时间复杂度是指执行算法需要消耗的时间资源，其表征了算法执行的效率问题，既解决问题的速度。算法的空间复杂度是指执行算法需要占用的内存空间，其表征了算法执行需要的资源，也就是解决问题付出的代价。很显然，算法的效率越高、代价越小，其性能越优异。,算法描述方法,当算法过程比较复杂时，单靠自然语言来描述算法将显得十分困难，让人难以准确理解。此时，需要借助其他的算法描述手段，主要有：算法语言，有伪代码、各种程序设计语言、计算机语言等。图形描述，如流程图和N-S图，图的描述应与算法语言的描述对应；形式语言，用数学的方法，可以避免自然语言的二义性。,程序流程图,程序流程图是算法的图形描述方式。它使用一些简单的几何图形来表示各种不同性质的程序操作，使用流程线将各个图形连接起来，指示算法的执行过程。由于流程图的符号统一，且画法简单，结构清晰，逻辑性强，便于理解，因此成为描述程序流程的主要方法。下图中的图形是流程图中常用的一些标志。,常见程序流程图图形符号,N-S流程图,由I.Nassi和B.Shneiderman在1973年提出。去掉了程序流程图中的流程线（当程序流程复杂时，程序流程图的流线使人眼花缭乱），将整个流程放在一个大框中，使程序流程更清晰。,C/C+的控制语句,if()else（条件语句）for()（循环语句）while()（循环语句）dowhile()（循环语句）continue（结束本次循环语句）switch（多分支选择语句）break（终止执行switch或循环语句）return（从函数返回语句）goto（转向语句）,第二节 顺序结构编程,掌握了数据类型、表达式以及基本的输入输出方法后，就可以编写程序来解决一些简单问题。例：交换两个变量#include/预处理命令int main()int a=1,b=2;/定义待交换的两个整型变量，并赋值 int tmp;/定义一个整型变量作为中间交换用 cout交换前:a=a,b=bendl;tmp=a;a=b;b=tmp;cout交换后:a=a,b=bendl;,例：求一元二次方程式ax2+bx+c=0的根。a,b,c的值在运行时由键盘输入，它们的值满足b2-4ac0。#include/预处理命令#include/要用到数学函数sqrt，应包含头文件cmath.hint main()float a,b,c,x1,x2;/声明语句 cinabc;/对象调用语句 x1=(-b+sqrt(b*b-4*a*c)/(2*a);/表达式语句 x2=(-b-sqrt(b*b-4*a*c)/(2*a);coutx1=x1endl;coutx2=x2endl;return 0;,第二节选择结构编程,C/C+语言提供了多种手段来实现选择结构：if语句、switch语句、条件表达式和逻辑表达式。它们各有优劣和适用的场景。if语句是C/C+语言中实现选择结构最常用的方式。当if语句和else语句组合时候时，可以实现更灵活更复杂的选择结构。学会熟练地使用if语句是C/C+编程的基础。,if()else,在if语句中，用括号中表达式的值来判断程序的流向，如果表达式的值不为0（即为true），表示条件成立；否则（即表达式的值等于0或false）表示条件不成立。,if p44,if(条件表达式)语句;或if(条件表达式)语句;,语义：如果条件表达式的值为真，则执行其后的语句，否则不执行该语句。,int main()int a,b,max;coutab;max=a;if(maxb)max=b;coutmax=max;,ifelse p45,if(条件表达式)语句1;else 语句2;,语义：如果条件表达式的值为真，则执行语句1，否则执行语句2。,int main()int a,b;coutab;if(ab)coutmax=a;else coutmax=b;,ifelseif,if(条件表达式1)语句1;else if(条件表达式2)语句2;else if(条件表达式3)语句3;else if(条件表达式m)语句m;else 语句n;,语义：依次判断表达式的值，当出现某个值为真时，则执行其对应的语句。然后跳到整个if语句之外继续执行程序。如果所有的表达式均为假，则执行语句n。,int main()/ASCII码的判断 char c;coutc;if(c=0,使用if语句中注意问题,1、表达式通常是逻辑表达式或关系表达式，但也可以是其它表达式，如赋值表达式等，甚至也可以是一个变量。例如，if(a=5)语句;if(b)语句;，都是允许的。2、在if语句中，条件判断表达式必须用括号括起来，在语句之后必须加分号。3、在if语句中的3种形式中，所有的语句应为单个语句，如果要想在满足条件时执行一组（多个）语句，则必须把这一组语句用括起来。但要注意的是在之后，不能再加分号。,条件表达式中的=与=,C/C+语言中赋值运算符（=）和等于运算符（=）只相差一个等号，前者多写一个“=”符号就变成后者，而后者少写“=”也变成前者。这种错误在编程中十分常见。而且，这两种写法都是合法的写法，编译器无法自动检测。如果这种错误出现在if语句的判断表达式中，很可能出现期望外的，逻辑完全不一样的程序。因此，编程时必须特别小心！例：,int a=1;if(a=2)coutYesn;elseNon“输出：No,int a=1;if(a=2)coutYesn;elseNon“输出：Yes,if的嵌套 二义性 p46,if(x=0)if(x50)coutx is okn else coutx is not okn,if(x=0)if(x50)coutx is okn else coutx is not okn,if(x=0)if(x50)coutx is oknelse coutx is not okn,解释1,解释2,规则,if-else语句成对的规则：else连接到上面没有配对的且为可见的if上。if(条件)if(条件)if(条件)语句;else 语句;,正确的配对。用括起来的第三if不可见了,程序的改进,if(x=0)if(x50)coutx is oknelse coutx is not okn,if(x=0&x50)coutx is oknelse coutx is not okn,两个程序的比较,if语句的嵌套int main()int a,b;coutab;if(a!=b)if(ab)coutbn;else cout“abn;else cout“a=bn;,if-else-if语句int main()int a,b;coutab;if(a=b)coutb)printf(“abn);else cout“abn;,如果在条件语句中，只执行单个赋值语句时，常可以用条件表达式来实现。不但使程序简洁，也提高了运行效率。条件运算符为?和：由条件运算符组成的条件表达式的一般形式为：表达式1?表达式2表达式3,条件运算符和条件表达式 p47,条件表达式,条件为真时表达式,条件为假时表达式,条件语句：if(ab)max=a;else max=b;可以用条件表达式写成：max=(ab)?a:b;执行该语句的语义是：ab为真，则把a赋予max，否则把b赋予max。,条件表达式中的类型及转换,条件表达式中，表达式1的类型可以与表达式2和表达式3的类型不同:int x;int m;m=x?a:b;表达式2和表达式3的类型必须相同，若不同则需要进行类型转换，此时条件表达式的值的类型为二者中较高的类型。xy?1:1.5如果xy，则条件表达式的值为1.5，若xy，值应为1，由于C+把1.5按双精度数处理，双精度的类型比整型高，因此，将1转换成双精度数，以此作为表达式的值。,使用条件表达式时，注意点,1、条件表达式通常用于赋值语句中。2、条件运算符的运算优先级低于关系运算符和算术运算符，但高于赋值符。max=(ab)?a:b;可以去掉括号写成max=ab?a:b;3、条件运算符?和:是一对运算符，不能分开单独使用。4、条件运算符的结合方向是自右至左。例：ab?a:cd?c:d 应理解为 ab?a:(cd?c:d)这也就是条件表达式的嵌套情形。,switch语句 p60,if 语句是二分支选择语句，一个条件会出现两种可能性。而在实际生活中，一个条件会出现多种可能性，虽然可以用嵌套的if语句来处理，但整个程序结构可读性就比较差了。switch语句是多分支选择语句，当条件值为一系列的整数值时，用switch语句就显得更加直观和简捷。switch也称为开关语句。,switch语句的一般形式,switch（表达式）case 常量表达式1：语句组1 case 常量表达式2：语句组2.case 常量表达式n：语句组n default：语句组n+1 执行switch语句时，先计算表达式，再与每一种情况常量表达式进行比较。如果某一情况常量表达式等于表达式的值，控制就转向该情况常量表达式后面的相应语句。如果没有相匹配的就转到default。如果没有相匹配，也没有default就不执行任何语句。,根据考试成绩的等级输出出百分制分数段,switch(grade)case A:cout85100n;case B:cout7084n;case C:cout6069n;case D:cout60n;default:couterrorn;本例中要求输入一个等级，输出一个分数段。但当输入A之后，却执行case A及以后的所有语句，输出了所有的分数段。这当然是不希望的。为什么会出现这种情况呢？,case语句通常和break语句联用,上述情况恰恰反映了switch语句的一个特点。在switch语句中，“case 常量表达式”只相当于一个语句标号，表达式的值和某标号相等则转向该标号执行，但不能在执行完该标号的语句后自动跳出整个switch语句，所以出现了上述继续执行后面的所有语句的情况。为了避免这种情况，C/C+提供了break语句，专用于跳出switch语句。case语句通常和break语句联用，以保证多路分支的正确实现。,switch语句的实用形式,switch（表达式）case 常量表达式1:语句组1;break;case 常量表达式2:语句组2;break;.case 常量表达式n:语句组n;break;default:语句组n+1;最后一个分支可省略break语句。,例 p61,switch(grade)case A:cout85100n;break;case B:cout7084n;break;case C:cout6069n;break;case D:cout60n;break;default:couterrorn;,switch使用的注意,switch后面括号中的表达式只能是整型数、字符型或枚举型表达式。p61在case后的各常量表达式的值不能相同，否则会出现错误。各case和default子句的先后顺序可以变动，而不影响程序执行结果。P62default子句可以省略。在csae后，允许有多个语句，可以不用括起来。多个case可以共用一组执行语句。P62switch语句可以嵌套。p62,if和switch p63,如果根据分数输出其成绩等级，就只能用if而不能用switch了。因为条件是一个范围，而不是单独的整数。if(grade=85,第三节 循环结构编程,当程序要反复执行同一操作时，就必须使用循环结构。很多问题都必须使用循环结构。比如，树的遍历，数组输出，链表的操作等等。循环结构的功能是：通过设置执行循环体的条件和改变循环变量，从而重复执行一系列操作。C/C+语言中提供了for语句、while语句、do-while语句和goto语句来实现循环结构。,for语句,语言循环操作的实现使计算机真正充当了替代人工作的角色。for语句是C/C+编程中最主要的循环语句。for语句用法简单，用以实现在满足某一条件下一系列操作的重复执行，其实现的循环结构逻辑清晰。,for循环结构 p58,for语句的一般形式：for(表达式1;表达式2;表达式3)循环体表达式1：循环初始化表达式2：条件测试判断表达式3：状态修正一个循环包括：(1)循环初始状态(2)条件判断(3)状态修正(4)循环体其执行过程如p58所述。,反复做10次输出”Hello”,for(int i=1;i=10;+i)coutHello.;for语句头上的括号中由两个部分隔开了三个部分，分别表示：（1）循环变量初始化(int i=1)；（2）条件判断(i=10)表示循环的结束判断，当条件为假时，则说明循环应该结束；（3）循环变量的增量(+i表示循环的状态修正)。for语句花括弧中的部分为循环体，它可以由若干条语句组成，当循环体只含一条语句时，其外面的花括弧（表示语句块）可以省略。,反复做10次输出”Hello”执行流程的理解,for(int i=1;i=10;i+)coutHello.;最初i的值为1，判断i=10为真，所以开始执行循环体。即输出一个“Hello.”。然后，返回去进行状态修正，i的值变成2，在进行条件判断，i=10为真，所以又一次执行循环体，输出第二个“Hello.”。再去状态修正，再去条件判断直到最后，当i为11，条件（i=10）为假时，循环终止，即本for循环语句执行完成。整个循环共执行了10次。,for循环：求1+2+3+100的值,如果不考虑用计算公式(首项+尾项)项数2，而是逐项相加，应为下列语句：int sum=0;sum=sum+1;sum=sum+2;sum=sum+3;sum=sum+100;coutsumendl;该序列中，中间的100条语句都做相似的操作：sum=sum+i只不过i的值从1逐一变化到100，对此可以将这100条语句拿出来作为循环来设计。,for循环：求1+2+3+100的值,循环变量从1到100注意变化，循环体中，不断累计循环变量，要相加的值正好与循环变量同步增长：int sum=0;for(int i=1;i=100;i+)/循环变量在for头部定义，/这是一个好的做法。p60 sum+=i;coutsumendl;如果把第一句放在循环体内，就会起不到累计的作用，因为每次都创建sum，并执行sum=0，并会导致最后输出因sum只从属于for而出现sum没定义的错误。如果把最后一句放入循环体，就会导致共输出100个不同的值，也不是想要的结果形式。,for语句变化-省略初始化 p58,原来的代码在这里：int sum=0;for(int i=1;i=100;i+)sum+=sum i;coutsumendl;,int sum=0;int i=1;for(;i=100;i+)/分号不能省 sum+=i;coutsumendl;循环变量的初始化放在for循环的外部定义。这样可以使循环变量在循环结束之后，仍然存在。在某些情况下便于查看循环是否正常退出。,for语句变化-省略条件测试 p59,int sum=0;for(int i=1;i+)/分号不能省 sum+=i;if(i=100)break;coutsumendl;这表明可以在循环体中测试循环结束条件，并用break退出循环，而省略for循环结构描述中的条件测试部分。省略条件测试部分，相当于让循环体执行永不停止。循环的退出在每一轮都可以测试退出条件，但也可以在循环体中，通过测试条件，决定执行break的时机，达到退出循环的目的。,原来的代码在这里：int sum=0;for(int i=1;i=100;i+)sum+=sum i;coutsumendl;,for语句变化-省略状态修正,由于i+即i=i+1，sum+=i即sum=sum+i，因此上述循环还可以表示成：int sum=0;for(int i=1;i=100;)/分号不能省 sum+=i+;/同时修改循环变量coutsumendl;该循环体中改变循环变量的值和累加赋值合二为一，省略for循环结构描述中的修正循环变量部分。,原来的代码在这里：int sum=0;for(int i=1;i=100;i+)sum+=sum i;coutsumendl;,for语句变化-省略初始化和状态修正,int sum=0;int i=1;for(;i=100;)sum+=i+;coutsumendl;要注意的是for语句在格式上，其两个分号不能少！,for语句变化-省略初始化、状态测试及修正,int sum=0;int i=1;for(;)sum+=i+;if(i100)break;coutsumendl;要注意的是for语句在格式上，其两个分号不能少！,for语句变化-从100到1倒过来累计,int sum=0;for(int i=100;i=1;i-)sum+=i;coutsumendl;for循环的循环变量可以从这一头变化到那一头，也可以从那一头变化到这一头。,原来的代码在这里：int sum=0;for(int i=1;i=100;i+)sum+=sum i;coutsumendl;,多重循环输出水仙花数,所谓水仙花数是指一个三位数，其各位数字立方之和等于该数本身。解：为了输出所有的水仙数，可以使用3层for循环，最外层循环变量为三位数的百位数，中层循环变量为三位数的十位数，内层循环变量为个位数，循环的结果是遍历了100999，在循环体中判断该三位数是否是水仙数。,输出水仙花数,#include int main()int a,b,c;int narcissus;coutNarcissus numbers:n;for(a=1;a 10;+a)/*百位数*/for(b=0;b 10;+b)/*十位数*/for(c=0;c 10;+c)/*个位数*/narcissus=a*100+b*10+c;/*计算该三位数的值*/*判断这个三位数是否为水仙花数*/if(a*a*a+b*b*b+c*c*c=narcissus)coutnarcissus;coutendl;/*换行，调整输出样式*/return 0;,while语句,while语句是C/C+语言中循环结构的另一种实现方式。它和for语句的结构有很大不同之处，在不同的场景中各有优劣；两者还可以相互转换。,while循环结构 p54,while语句的形式：while(条件表达式)循环体int sum=0;int i=1;while(i=100)sum=sum+i;i=i+1;coutsumendl;,for与while循环,for循环：int sum=0;int i=1;for(;i=100;)sum+=i+;coutsumendl;已经演变成了while循环：int sum=0;int i=1;while(i=100)sum+=i+;coutsumendl;,do-while语句,do-while语句是while语句的一个变体。for语句与while语句都是对进入循环进行条件判断，先做条件判断，再执行循环体；而do-while则是对跳出循环进行条件判断，先执行循环体，后再做条件判断。,do-while循环结构 p56,do-while 语句的形式：do 循环体while(条件表达式)int sum=0;int i=1;do sum=sum+i;i=i+1;while(i=100);coutsumendl;,while和do-while的比较,do-while循环在循环体的底部进行继续执行条件的测试，所以它至少将执行一次循环。而while 语句在循环的顶部进行测试，有可能永远不执行循环体。,while和do-while的比较 例,int main()int sum=0,i;cini;while(i=10)sum=sum+i;i+;coutsum;,int main()int sum=0,i;cini;do sum=sum+i;i+;while(i=10);coutsum;,比较：输入小于等于10时的结果？输入大于10的结果？,循环结构与选择结构的嵌套,情况1：while(循环条件判断)if(选择条件判断)分支;循环体;情况2：if(选择条件判断)分支;while(循环条件判断)循环体,例,打印图形。按输入边长，打印正方形。偶数行（从0行开始计算）充填=，奇数行充填+。例如输入1，则打印：=输入5，则打印：=+=+=有两种解决方案,int main(void)/方案1 int i,j;int length;cout0):length;/输入正方形长度/外层循环：填充length*length正方形 for(i=0;i length;+i)for(j=0;j length;+j)/内层循环：填充一行/根据行数的奇偶性决定输出内容 if(0=i%2)cout=;else cout+;cout“n”;/换行 return 0;,方案改进,上述方案中，在打印每一个字符之前都需要执行if判断，以检查行号的奇偶性，代价比较大。下面的方案把选择结构从内层循环体提升一层，放到外层循环体。打印之前判断行号的奇偶性。这样条件判断之需要执行length次，明显好于上一个方案的length*length 次；但可读性上要比上一个方案差，但也不会很糟糕。,int main(void)/方案2 int i,j;int length;cout0):length;/输入正方形长度/填充length*length正方形 for(i=0;i length;+i)/使用选择结构包含循环结构的方式 if(0=i%2)for(j=0;j length;+j)/偶数行 cout=;else for(j=0;j length;+j)/奇数行 cout+;cout“n”;/换行 return 0;,转向语句break,用在while，do-while，for和switch语句中。在switch语句中，用break来使流程跳出switch语句，继续执行switch后的语句。在循环语句中，用break从最近的封闭循环体内跳出。for(;)for(;)break;a=1;/break跳至此处,转向语句continue,continue语句在循环中，作用为结束本次循环，即跳过循环体中尚未执行的语句，接着进行下一次是否执行循环的判定。for(int n=100;n=200;n+)if(n%3=0)continue;/转向执行for括号中的表达式进行/条件判断 coutnendl;,continue与break的区别,continue语句只结束本次循环，而不是终止整个循环的执行。break语句则是终止整个循环，不再进行条件判断。,第四节 循环设计,循环是程序设计入门中最重要的内容之一。用得最多的是for语句，因为它能描述循环体的初始和结束状态，以及中间步长。while是for的一种特例，在循环不含明确的循环变量时，用while会更简捷。而do-while循环的使用机会大大少于前两者，因为大多数循环可以用前两者描述，没有必要用do-while。一般常见的循环控制的类型有：字符图形类、逻辑判断类、素数判定类、级数逼近类、排序和查找（数组）类等。,字符图形例1：输出字母图形,MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM,用for循环编程画出图形。图形一共10行，每行增加一个字符，所以应循环10次，每次输出一行，其循环模式为：for(int i=1;i=10;+i)输出第i行 换行,其中“输出第i行”是在for循环中的一个小循环。每次执行时其长度都是不一样的，但长度的变化正好与i同步，所以可以依赖i来实现。,字符图形例1,MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM,注意到第i行的M字符数与i的关系：行i M数111 2223334441010 10所以，可以得到“输出第i行”的循环为 for(int j=1;j=i;+j)cout“M”;,字符图形例1,将内、外循环套起来，就有了完整的程序：#includeint main()for(int i=1;i=10;+i)for(int j=1;j=i;+j)coutM;coutendl;/换行 对付这种字符图形，一般用两重循环，外循环遍历所有行，内循环遍历行中每个字符。,举一反三,字符图形的排列图形除了有正直角三角形之外，还有其它各种图形如：倒直角三角形及其它朝向的直角三角形、等腰三角形、梯形、菱形、平行四边形等等。都可以通过程序来实现,字符图形例2：输出金字塔字母图形,A ABC ABCDE ABCDEFGABCDEFGHI,外循环的形式 for(int i=1;i=5;+i)输出若干空格 输出若干字符 换行 如果要输出A起头依序的n(n27)个字母。可以 for(int i=1;in;+i)coutchar(A+i-1);/括号内的整型转换成 char型 或者 for(char ch=A;chA+n;+ch)coutch;,字符图形例2,A ABC ABCDE ABCDEFGABCDEFGHI,每一行中的空格数与字符数与i的关系行 空格数 字符数141 233325 0 9第i行的空格数为5-i个，字符数为2i-1。因此输出空格数和字符数的内循环分别为：for(int j=1;j=5-i;+j)cout“”;for(char ch=A;chA+2*i-1;+ch)coutch;,字符图形例2,将内、外循环套起来#includeint main()for(int i=1;i=5;+i)for(int j=1;j=5-i;+j)cout;for(char ch=A;chA+2*i-1;+ch)coutch;coutn;,举一反三,字符图形排列的另一种形式就是与计算与字符的变化结合在一起，例如：九九乘法表、杨辉三角形、日历及各种其它换算表。,素数判定穷举法 p68,给定一个整数m，判断其是否为素数。对于判断一个数m是否为素数，最朴素的方法是按素数的定义，试除以从2开始到m-1的整数，如果无一例外地不能整除，则该数一定是素数。可以用运算符%，进行取余操作，例如13%5的值为3。利用取余操作可以判定一个数是否能被另一个数除尽。也就是说以个数是否为另一个数的因子，若存在这样的因子，则立即可以判定该数不是素数而终止程序。等到2到m-1的数都尝试过了，就可以最后断定该数一定是素数了。,#include int main()long m;cout m;int i;for(i=2;im;i+)/找m的因数 if(m%i=0)break;if(m=i)/判断m是否被小于m的数整除 cout m is prime.n;else cout m isnt prime.n;,素数判定平方根法,在数学上，假定某个整数m不是素数，则一定可以表示成两个因子的积：m=ij 假定ij则i2ij=mj2即i2mj2即所以必定有一个因子不大于m的平方根。故判断m是否为素数，只要试除到m的平方根就可以了，不必一直到m-1。,#include#include int main()long m;cout m;double sqrtm=sqrt(m);/用到math.h int i;for(i=2;i=sqrtm;i+)if(m%i=0)break;if(sqrtmi)cout m is prime.n;else cout m isnt prime.n;,举一反三,有关素数的问题很多：判断一个数是否为素数。求a,b区间中的所有素数。在若干个区间中求素数的个数。,逻辑判断百钱买百鸡,对于逻辑判断的问题，一般都要考虑全部的可能性，然后从这些可能性中按条件逐一排查，直到最后获得某个结论。例：雄鸡7元一只，母鸡5元一只，小鸡1元3只。花100元钱，买100只鸡，如果雄鸡、母鸡和小鸡都必须有，则雄鸡、母鸡和小鸡应各买几只？解：考虑全部可能性时，先考虑雄鸡、母鸡和小鸡的取值范围（也可以从金额着手）。由于各种鸡都必须要有，所以雄鸡的最高耗用金额为100-5-1=94元，取7的倍数，得91元，所以雄鸡数的范围为113，同理，母鸡数的范围为118，小鸡数的范围为396，注意小鸡数虽可以花100-7-5=88元来买264只，但由于总鸡数的限制，小鸡数应98。,百钱买百鸡程序的表达模式,for(列举所有可能的情况)/可能为多重循环 if(条件1不满足)continue if(条件2不满足)continue/if(条件n不满足)continue 输出结果之一或者累计符合所有条件的方案,雄鸡数+母鸡数+小鸡数=100(cock+hen+chick-100=0)买雄鸡款+买母鸡款+小鸡款=100(7*cock+5*hen+chick/3-100=0)小鸡数为3的倍数(chick%3=0),本问题条件,上述问题的反条件值：(cock+hen+chick-100！=0)(7*cock+5*hen+chick/3-100！=0)(chick%3！=0)只要条件值不等于0，那就是真，因此条件“x!=0”与条件“x”等价。,百钱买百鸡 解1,#include int main()for(int cock=1;cock=13;+cock)for(int hen=1;hen=18;+hen)for(int chick=1;chick=96;+chick)if(7*cock+5*hen+chick/3-100)continue;if(cock+hen+chick-100)continue;if(chick%3)continue;coutCock:cock,Hen:hen,Chick:100-cock-henendl;,百钱买百鸡 解2,优化：由于 chick=100-cock-hen，可以省略chick这重循环。所有chick用100-cock-hen代替。#include int main()for(int cock=1;cock=13;+cock)for(int hen=1;hen=18;+hen)if(7*cock+5*hen+(100-cock-hen)/3-100)continue;if(100-cock-hen)%3)continue;coutCock:cock,Hen:hen,Chick:100-cock-henendl;,百钱买百鸡 解3,还有一种模式：for(列举所有可能的情况)if(条件1满足&条件2满足&条件n满足)输出结果之一或者累计符合所有条件的方案,#include int main()for(int cock=1;cock=13;+cock)for(int hen=1;hen=18;+hen)if(100-cock-hen)%3=0,百钱买百鸡 解4,#include int main()for(int cock=1;cock=13;+cock)for(int hen=1,chick=99-cock;hen=18;+hen,chick-)if(chick%3=0,举一反三,猴子吃桃问题、谁打烂了玻璃、搬砖问题、鸡鸭同笼等问题都要求有一个正确逻辑判断方法。,级数逼近求 p66,对于无穷数列求和，逼近到某个近似值得情况，如用公式：/411/3+1/51/7+求的近似值，直到最后一项的绝对值小于10-6为止。分析：整数不能表示小数，所以的值用浮点double表示。按公式，先求/4。数列的第n项是(-1)n-1/(2n-1)，第n项与第n-1项的符号关系变一下，分母加2。,级数逼近求 解1,根据循环变量n，求得第n项的值，累计，然后条件判断，若满足结束条件，则退出。循环结束条件为前一个累计和与后一个累计和的差小于10的负6次方。由于前后两次累计的结果之差的绝对值等于后一次加上去的值，所以，也可以通过判断后一项的绝对值小于10的负6次方而得到循环退出条件。,#include#include#includeint main()double sum=0,item=1;for(int n=1;fabs(item)1e-6;+n)item*=(-1.0)*(2*n-3)/(2*n-1);/(2*n-3)定正负 sum+=item;coutPi=setiosflags(ios:fixed)setprecision(6)sum*4endl;,条件：绝对值小于10的负6次方,级数逼近求 解2,先设定一个初项，然后一边累计，一边根据前一项求下一项，一直累计，直到满足条件为止。#include#includeint main()double sum=0,item=1;for(int denom=1,sign=1;fabs(item)1e-6;denom+=2,sign*=-1)item=sign/double(denom);sum+=item;coutPi=sum*4endl;,级数逼近求 解3：while解 p67,#include#includeint main()double sum