循环嵌套与穷举法.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,循环嵌套与穷举法,二中信息技术科 李展,五、循环嵌套,1,、,for,语句的适用情况。,2,、循环语句的相互嵌套。,for i:=1 to 3 do,for j:=1 to 4 do,writeln,(i,:,j);,读程序,写出运行结果,program ex302;,var,i,j:integer;,t :,longint,;,begin,for i:=1 to 5 do,begin,t:=1;,for j:=1 to i do,t:=t+j;,write(t,);,end;,writeln,;,end试编写能够打印输出如下图形的程序：,#,#,#,#,#,#,#,#,program ex2;,var,i,j,k:integer;,begin,for i:=8,downto,1 do,begin,for j:=1 to 8-i do write();,for j:=1 to 2*i-1 do write(#);,writeln,;,end;,readln,;,end.,选作任务：编写程序，使之能输出如下形式的“字母塔”,A,ABA,ABCBA,.,.,ABCDEFGHIJKLMNOPQRSTUVWXWVUTSRQPONMLKJIHGFEDCBA,ABCDEFGHIJKLMNOPQRSTUVWXYXWVUTSRQPONMLKJIHGFEDCBA,ABCDEFGHIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCBA,六、循环嵌套中的穷举法,根据循环嵌套，我们可以对某些问题进行穷举。所谓穷举法，即尝试问题可能的解的所有情况，那些适合情况的解就是问题的解。,例,5-7,(,课本,P47-48),例,5-8,判断一个数是否是素数,.(P48),分析,:,素数,(,质数,),的定义是除了,1,和它本身之外,没有其它的因子,(,约数,),如,2,3,5,7,11,等,.,那么其朴素的判断算法应该是,:,枚举,2,到,n-1,判断,n,能够给这些数整除,如果可以整除,则说明,n,不是素数,.,例,5-8,判断一个数,(1),是否是素数,.(P48),核心代码,:,readln,(n);,check:=true;,for i:=2 to n do,if n mod i=0 then,begin,check:=false;,break;break,语句,:,跳出,for,循环体,end;,if check then,writeln,(yes),else,writeln,(no);,问题,:,要枚举,2,至,n,次,如果,n,很大,程序会变得很慢,如何优化,?,分析,:,用我们掌握的数学知识来优化算法,.,任何正整数均可表示为,:,n:=a*b(a=b),其中必有,a=,sqrt(n,),这告诉我们,假设,n,有一个因子,a,必会有一个因子,b(b=n div a).,所以我们穷举,n,的因子的时候,只需穷举到,a,即可,.(,思考一下为什么,?),上机实践,:,请优化前面的算法,例,5-8,求,100-200,之间的所有素数,.(P48),for i:=100 to 200 do,begin,x:=2;,while(x,trunc(sqrt(i,)then write(i:8);,end;,第,5,节 控制循环或程序流程的语句,.(P49),1.Break,语句,跳出当前所在的最内层循环,2.Continue,当前循环变量加,1,并将循环控制返回到条件判断处,3.halt,终止整个程序,4.Exit,终止当前的过程或函数,.,在后面的章节会介绍,Break,语句,s:=0;,for i:=1 to 10 do,begin,inc(s);,if i=5 then break;,end;,Writeln,(s=,s);,Break,语句,s:=0;,for i:=1 to 5 do,begin,for j:=1 to 5 do,begin,if ji then break;,inc(s);,end;,end;,Writeln,(s=,s);,continue,语句,s:=0;,for i:=1 to 10 do,begin,if i mod 2=0 then continue;,inc(s);,end;,Writeln,(s=,s);,continue,语句,for i:=1 to 3 do,begin,for j:=1 to 3 do,begin,if j=i then continue;,writeln,(i:3,j:3);,end;,end;,halt,语句,Var,str,:string;,Begin,while true do,begin,readln(str,);,if,str,=,zmkm,then halt;,writeln(Wrong,Password!);,end;,writeln(Welcome,);,End.,例,水仙花数,问题描述：,求,100999,中的水仙花数。,（若三位数,ABC,，,ABC=A,3,+B,3,+C,3,则称,ABC,为水仙花数。例如,153,1,3,+5,3,+3,3,=1+125+27=153,则,153,是水仙花数。）,例,水仙花数,program ex6_1;,var,a,b,c:integer;,begin,for a:=1 to 9 do,for b:=0 to 9 do,for c:=0 to 9 do,if a*a*,a+b,*b*,b+c,*c*c=a*100+b*10+c,then,write(a,*100+b*10+c:6);,end.例,谁是冠军,P64,甲乙丙丁戊五个人在运动会上分获百米、二百米、跳高、跳远和铅球冠军，有四个人猜测比赛结果：,说：乙获铅球冠军，丁获跳高冠军。,说：甲获百米冠军，戊获跳远冠军。,说：丙获跳远冠军，丁获二百米冠军。,说：乙获跳高冠军，戊获铅球冠军。,其中每个人都只说对一句，说错一句。求五人各获哪项冠军。,例,谁是冠军,P64,分析,:,（,1,）假设将,5,个项目分别表示为,1,、,2,、,3,、,4,、,5,，用变量,a,、,b,、,c,、,d,、,e,分别表示甲乙丙丁戊获得冠军的项目。很明显，,a b c d e,的值必为,1 2 3 4 5,的一个排列。,（,2,）如何将,A,、,B,C,、,D,每个人的逻辑判断表示出来？,说：乙获铅球冠军，丁获跳高冠军。,已知,Ord,(true)=1,，,Ord,(false)=0,那么,A,说对一半，说错了一半的逻辑可表示为？,百米,(1),、二百米（,2,）、跳高（,3,）、跳远（,4,）和铅球（,5,）,分析,:,说：乙获铅球冠军，丁获跳高冠军。,Ord,(b=5)+,Ord,(d=3)=1,说：甲获百米冠军，戊获跳远冠军。,Ord,(a=1)+,ord,(e=3)=1,依此类推,For a:=1 to 5 do,for b:=1 to 5 do,for c:=1 to 5 do,for d:=1 to 5 do,begin,e:=15-a-b-c-d;,if(a*b*c*d*e=120)and,(,ord(b,=5)+ord(d=3)=1)and,(,ord(a,=1)+ord(e=4)=1)and,(,ord(c,=4)+ord(d=2)=1)and,(,ord(b,=3)+ord(e=5)=1)then,writeln,(a:3,b:3,c:3,d:3,e:3);,end;,六、循环嵌套中的穷举法,上机实践,（,P65,）,例,6-2,执行任务。,强化训练,谁是小偷。,六、循环嵌套中的穷举法,上机实践：,用,5,元钱买,100,只纽扣，其中金属纽扣每只,5,角，有机玻璃纽扣每只,1,角，小揿扣,1,分钱买,3,个，编程求出各种纽扣各买了多少只？,