noip信息競(jìng)賽共享2013級(jí)輔導(dǎo)第四節(jié)講

第四講枚舉算法2014.02.22一.回顧For與while的區(qū)別與聯(lián)系：1、for必須能預(yù)先確定循環(huán)次數(shù)。循環(huán)控制變量，每次自動(dòng)加1，不能人為的改變。2、while可以不知道循環(huán)次數(shù)。在循環(huán)體內(nèi)必須有修改循環(huán)控制變量的語(yǔ)句，否則死循環(huán)。循環(huán)控制變量的改變可以不是1。3、能用for的一定能用while實(shí)現(xiàn)。總的循環(huán)次數(shù)<=107循環(huán)嵌套就是循環(huán)體內(nèi)還有循環(huán)，可能有多層。區(qū)別于并列的循環(huán)。n:=4;

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

（2）fori:=1tondoforj:=1tondowrite('*');writeln;讀程序，寫(xiě)出輸出結(jié)果（3）fori:=1tondowrite('*');writeln;forj:=1tondowrite('*');writeln;fork:=1tondowrite('*');writeln;（4）fori:=1tondobeginforj:=1tondobeginfork:=1tondowrite('*');writeln;end;writeln;end;數(shù)組定義一批變量，便于保存大量的數(shù)據(jù)。var數(shù)組名列表：array[下標(biāo)范圍]of基類(lèi)型；vara,b:array[1..1000]oflongint;數(shù)組名字a,b;使用時(shí)：數(shù)組名[下標(biāo)]，下標(biāo)不能超過(guò)范圍。變量：a[1],a[2],a[3],…,a[1000]引用：a[i],a[i+10],a[i+j]…。下標(biāo)可以是常量、變量或表達(dá)式。常用for循環(huán)輸入和輸出數(shù)組元素：fori:=1tondoread(a[i]);fori:=1tondowrite(a[i]);數(shù)學(xué)相關(guān)：1.模運(yùn)算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.歐幾里得算法（輾轉(zhuǎn)相除）求最大公約數(shù)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.二.枚舉算法定義為了得到問(wèn)題的解，列舉出解的所有可能的情況，根據(jù)要求進(jìn)行逐一判斷，從而求出問(wèn)題解的一種算法，適合用于狀態(tài)較少，比較簡(jiǎn)單的問(wèn)題。大多數(shù)情況使用For循環(huán)實(shí)現(xiàn)舉例：【例1】水仙花數(shù)【問(wèn)題描述】若三位數(shù)abc，滿足a3+b3+c3=abc，則稱(chēng)abc為水仙花數(shù)。如153，13+53+33=1+125+27=153，則153稱(chēng)為水仙花數(shù)。編程求100～999中的所有的水仙花數(shù)。兩種方法：1：枚舉100—999，分離出百十個(gè)位，然后判斷。2：分別枚舉百十個(gè)位?！纠?】換錢(qián)問(wèn)題：要將一張100元的大鈔票，換成等值的10元、5元、2元、1元一張的小鈔票，每次換成40張小鈔票，每種至少1張。如，有一種換法：10元：1張5元：5張2元：31張1元：3張求：一共有多少種換法。思考：(1)一張1000的換成400張，有多少種換法？(2)一張5000的換成2000張，有多少種換法？【例3】抽簽游戲【問(wèn)題描述】你和你的朋友在玩一個(gè)簡(jiǎn)單的游戲：你的朋友將寫(xiě)有數(shù)字的n個(gè)紙片放在他的口袋中，你可以從他的口袋中抽出4次紙片，每次抽出紙片后記下紙片上的數(shù)字后再將其放在口袋中，如果這4個(gè)數(shù)字的和恰好是m，就算你贏，否則你的朋友贏。你挑戰(zhàn)了好幾回都沒(méi)贏，于是想寫(xiě)個(gè)程序驗(yàn)證是否有贏的可能性，即是否存在抽取4次和為m的方案，如果存在輸出yes，否則輸出no?！据斎搿康谝恍校簄。第二行：m。第三行：k1,k2,…,kn。分別代表n個(gè)紙片上的數(shù)字。【輸出】如果存在收取4次的和為m，輸出yes，不存在輸出no。【擴(kuò)展】1.如果找到一次和為m后，是否有必要再抽？如果不需要怎么修改程序？2.如果每次抽出的不再放回口袋?break在for中使用，退出當(dāng)前for循環(huán)結(jié)構(gòu)?！纠?】解方程【問(wèn)題描述】已知方程如下：a1x1-a2x2+a3x3-a4x4+a5x5-a6x6=0其中：x1,x2,…,x6是未知數(shù)，a1,a2,…,a6是系數(shù)數(shù)。且方程中的所有數(shù)均為正整數(shù)。假設(shè)未知數(shù)1≤xi≤M,i=1,,,6，求這個(gè)方程的正整數(shù)解的個(gè)數(shù)(方程解得個(gè)數(shù)<=1015)?！据斎搿康谝恍?，M。第二行，系數(shù)ai，中間用空格隔開(kāi)?！据敵觥糠匠探獾脗€(gè)數(shù)。方法1:6層循環(huán)方法2：移項(xiàng)后分左右分別枚舉，各3層循環(huán)?！纠?】最大三角形（加強(qiáng)版）有n(<=1000)根木棍，已知他們的長(zhǎng)度(<=10000)，現(xiàn)在從中選出3根2木棍組成周長(zhǎng)盡可能長(zhǎng)的三角形。請(qǐng)計(jì)算出最大周長(zhǎng)，如果無(wú)法組成三角形輸出”no”.輸入第一行：n第二行:n根木棍的長(zhǎng)度。如：輸入：5234510輸出：12（選345）【數(shù)據(jù)范圍限制】范圍限制：n<1000。方法1:3層枚舉3條邊。方法2：排序后一次枚舉實(shí)現(xiàn)//查找x，找到輸出位置，否則輸出no。//查找第一個(gè)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.選擇排序算法的實(shí)現(xiàn)：選擇排序算法基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最小的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。對(duì)待排序的序列a[1],a[2],……a[n]進(jì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]交換，這樣經(jīng)過(guò)第i遍處理后，a[i]是所有的中的第i小。即前i個(gè)數(shù)就已經(jīng)排好序了。n-1遍處理后，剩下的最后一個(gè)一定是最大的，不需要再處理了，排序結(jié)束。方法1：fori:=1ton-1doforj:=i+1tondoifa[i]>a[j]thenbegintem:=a[i];a[i]:=a[j]