noip信息竞赛共享2013级辅导第四节讲

第四讲枚举算法2014.02.22一.回顾For与while的区别与联系：1、for必须能预先确定循环次数。循环控制变量，每次自动加1，不能人为的改变。2、while可以不知道循环次数。在循环体内必须有修改循环控制变量的语句，否则死循环。循环控制变量的改变可以不是1。3、能用for的一定能用while实现。总的循环次数<=107循环嵌套就是循环体内还有循环，可能有多层。区别于并列的循环。n:=4;

（1）fori:=1tondowrite('*');writeln;forj:=1tondowrite('*');writeln;

（2）fori:=1tondoforj:=1tondowrite('*');writeln;读程序，写出输出结果（3）fori:=1tondowrite('*');writeln;forj:=1tondowrite('*');writeln;fork:=1tondowrite('*');writeln;（4）fori:=1tondobeginforj:=1tondobeginfork:=1tondowrite('*');writeln;end;writeln;end;数组定义一批变量，便于保存大量的数据。var数组名列表：array[下标范围]of基类型；vara,b:array[1..1000]oflongint;数组名字a,b;使用时：数组名[下标]，下标不能超过范围。变量：a[1],a[2],a[3],…,a[1000]引用：a[i],a[i+10],a[i+j]…。下标可以是常量、变量或表达式。常用for循环输入和输出数组元素：fori:=1tondoread(a[i]);fori:=1tondowrite(a[i]);数学相关：1.模运算anmodp//anmodp=(…((((amodp)*a)modp)*a)modp…*a)modp

vara,n,s,p,i:longint;beginreadln(a,n,p);s:=1;fori:=1tondos:=(s*a)modp;writeln(s);readln;end.2.欧几里得算法（辗转相除）求最大公约数gcd(a,b)//gcd(a,b)=gcd(b,amodb)//gcd(a,0)=avara,b,r:longint;beginreadln(a,b);whileb>0dobeginr:=amodb;a:=b;b:=r;end;writeln(a);end.二.枚举算法定义为了得到问题的解，列举出解的所有可能的情况，根据要求进行逐一判断，从而求出问题解的一种算法，适合用于状态较少，比较简单的问题。大多数情况使用For循环实现举例：【例1】水仙花数【问题描述】若三位数abc，满足a3+b3+c3=abc，则称abc为水仙花数。如153，13+53+33=1+125+27=153，则153称为水仙花数。编程求100～999中的所有的水仙花数。两种方法：1：枚举100—999，分离出百十个位，然后判断。2：分别枚举百十个位。【例2】换钱问题：要将一张100元的大钞票，换成等值的10元、5元、2元、1元一张的小钞票，每次换成40张小钞票，每种至少1张。如，有一种换法：10元：1张5元：5张2元：31张1元：3张求：一共有多少种换法。思考：(1)一张1000的换成400张，有多少种换法？(2)一张5000的换成2000张，有多少种换法？【例3】抽签游戏【问题描述】你和你的朋友在玩一个简单的游戏：你的朋友将写有数字的n个纸片放在他的口袋中，你可以从他的口袋中抽出4次纸片，每次抽出纸片后记下纸片上的数字后再将其放在口袋中，如果这4个数字的和恰好是m，就算你赢，否则你的朋友赢。你挑战了好几回都没赢，于是想写个程序验证是否有赢的可能性，即是否存在抽取4次和为m的方案，如果存在输出yes，否则输出no。【输入】第一行：n。第二行：m。第三行：k1,k2,…,kn。分别代表n个纸片上的数字。【输出】如果存在收取4次的和为m，输出yes，不存在输出no。【扩展】1.如果找到一次和为m后，是否有必要再抽？如果不需要怎么修改程序？2.如果每次抽出的不再放回口袋?break在for中使用，退出当前for循环结构。【例4】解方程【问题描述】已知方程如下：a1x1-a2x2+a3x3-a4x4+a5x5-a6x6=0其中：x1,x2,…,x6是未知数，a1,a2,…,a6是系数数。且方程中的所有数均为正整数。假设未知数1≤xi≤M,i=1,,,6，求这个方程的正整数解的个数(方程解得个数<=1015)。【输入】第一行，M。第二行，系数ai，中间用空格隔开。【输出】方程解得个数。方法1:6层循环方法2：移项后分左右分别枚举，各3层循环。【例5】最大三角形（加强版）有n(<=1000)根木棍，已知他们的长度(<=10000)，现在从中选出3根2木棍组成周长尽可能长的三角形。请计算出最大周长，如果无法组成三角形输出”no”.输入第一行：n第二行:n根木棍的长度。如：输入：5234510输出：12（选345）【数据范围限制】范围限制：n<1000。方法1:3层枚举3条边。方法2：排序后一次枚举实现//查找x，找到输出位置，否则输出no。//查找第一个xvara:array[1..1000]oflongint;n,i,k,x:longint;beginreadln(n);fori:=1tondoread(a[i]);readln(x);k:=0;fori:=1tondoifa[i]=xthenk:=i;ifk>0thenwriteln(k)elsewriteln('no');readln;end.//找最小的放在第1位置vara:array[1..1000]oflongint;n,i,j,k,tem:longint;beginreadln(n);fori:=1tondoread(a[i]);k:=1;fori:=2tondoifa[i]<a[k]thenk:=i;tem:=a[1];a[1]:=a[k];a[k]:=tem;writeln(a[1]);writeln(a[k]);end.选择排序算法的实现：选择排序算法基本思想：每一趟从待排序的数据元素中选出最小的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。对待排序的序列a[1],a[2],……a[n]进行n-1遍处理：第1遍处理是从a[1],a[2],……a[n]中选择最小的放在a[1]位置；第2遍处理是从a[2],a[3],……a[n]中选择最小的放在a[2]位置；

……第i遍处理是从a[i],a[i+1],……a[n]中找最小的元素与a[i]交换，这样经过第i遍处理后，a[i]是所有的中的第i小。即前i个数就已经排好序了。n-1遍处理后，剩下的最后一个一定是最大的，不需要再处理了，排序结束。方法1：fori:=1ton-1doforj:=i+1tondoifa[i]>a[j]thenbegintem:=a[i];a[i]:=a[j]