(HDUACM2012版_05)篩選法及預(yù)處理(附菜鳥的22個經(jīng)典錯誤)

1、ACM程序設(shè)計程序設(shè)計杭州電子科技大學(xué) 劉春英4/9/20222每周一星（每周一星（4）：）：axie4/9/20223第五講第五講篩選法及預(yù)處理篩選法及預(yù)處理（附（附- -菜鳥的菜鳥的2222個經(jīng)典錯誤）個經(jīng)典錯誤）4/9/20224例例1-素數(shù)判斷素數(shù)判斷n題目描述：給定一個N（1N100000），請判斷N是否是素數(shù)，如果是素數(shù)，則請輸出YES，否則輸出NO。nSample Input：45nSample Output:NOYES4/9/20225常見樸素算法常見樸素算法n#includenint main()nnint i,n;nwhile(scanf(%d,&n)=1)nfor

2、(i=2;in;i+)n if(n%i=0) break; nif(i=n) printf(YESn);nelse printf(NOn);nn4/9/20226樸素算法優(yōu)化版本樸素算法優(yōu)化版本n#includen#includenint main()nint i,n,x;nwhile(scanf(%d,&n)=1)nx=(int)sqrt(n);nfor(i=2;ix) printf(YESn);nelse printf(NOn);nn4/9/20227例例2-求所有素數(shù)求所有素數(shù)n題目描述：給定一個N（1N100000），請按照遞增次序輸出所有小于等于N的素數(shù)。nSample In

3、put：10nSample Output:2 3 5 74/9/20228題目分析題目分析n題目特點：不是求一個素數(shù)，而是求一段素數(shù)（一種常見的情況就是求指定范圍的所有的素數(shù)）n如果還用常規(guī)求素數(shù)方法，可能的問題是？4/9/20229篩選法求素數(shù)篩選法求素數(shù)n基本思想基本思想：素數(shù)的倍數(shù)一定不是素數(shù)n實現(xiàn)方法實現(xiàn)方法：用一個長度為N+1的數(shù)組保存信息（0表示素數(shù)，1表示非素數(shù)），先假設(shè)所有的數(shù)都是素數(shù)（初始化為0），從第一個素數(shù)2開始，把2的倍數(shù)都標(biāo)記為非素數(shù)（置為1），一直到大于N；然后進(jìn)行下一趟，找到2后面的下一個素數(shù)3，進(jìn)行同樣的處理，直到最后，數(shù)組中依然為0的數(shù)即為素數(shù)。n說明：整數(shù)1

4、特殊處理即可。4/9/202210效果演示效果演示0 000000 000000 000000 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514144/9/202211效果演示效果演示0 001000 000000 000000 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514144/9/202212效果演示效果演示0 001001 000000 000000 01 15 54 43 32 26 67 7111110109 98 81212 1313171

5、71616151514144/9/202213效果演示效果演示0 001001 000010 000000 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514144/9/202214效果演示效果演示0 001001 001011 001010 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514144/9/202215效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109 98 81212 1

6、31317171616151514144/9/202216效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514144/9/202217效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514144/9/202218效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109 98 8

7、1212 131317171616151514144/9/202219參考代碼（篩選法）參考代碼（篩選法）n#includen#includenint a100001;nint main()n int i,j,n;nwhile(scanf(%d,&n)=1)nfor(i=2;i=n;i+)nif(ai=0)nfor(j=i+i;j=n;j+=i)naj=1; nprintf(2);nfor(i=3;i=n;i+)nif(ai=0) printf( %d,i); nprintf(n); nreturn 0; 4/9/202220思考思考-常規(guī)篩選法的改進(jìn)？常規(guī)篩選法的改進(jìn)？n#inclu

8、den#includenint a100001;nint main()n int i,j,n;nwhile(scanf(%d,&n)=1)nfor(i=2;i=n;i+)nif(ai=0)nfor(j=i+i;j=n;j+=i)naj=1; nprintf(2);nfor(i=3;i=n;i+)nif(ai=0) printf( %d,i); nprintf(n); nreturn 0; 4/9/202221例例3-求素數(shù)個數(shù)求素數(shù)個數(shù)n題目描述：給定一個N（1N100000），請輸出小于等于N的素數(shù)的個數(shù)。n測試數(shù)據(jù)有C組，（1C100000）.nSample Input：10nSa

9、mple Output:44/9/202222常規(guī)篩選法代碼常規(guī)篩選法代碼n#includen#includenint a100001;nint main()nint i,j,n,count;n while(scanf(%d,&n)=1)n count=0;nfor(i=2;i=n;i+)nif(ai=0)nfor(j=i+i;j=n;j+=i)naj=1; nfor(i=2;i=n;i+)nif(ai=0) ncount+;nprintf(%dn,count); nreturn 0; n4/9/202223題目分析題目分析(1)n題目特點：數(shù)據(jù)量超大！n分析：前面算法的瓶頸：每組數(shù)據(jù)

10、都求素數(shù).n如何改進(jìn)以加快求解速度？n可否一次篩選，多次查找？n這就是預(yù)處理思想4/9/202224預(yù)處理參考代碼預(yù)處理參考代碼n#includen#includenint a100001;nint main()nint i,j,n,count;nfor(i=2;i=100000;i+)nif(ai=0)nfor(j=i+i;j=100000;j+=i)naj=1; nwhile(scanf(%d,&n)=1)n count=0;nfor(i=2;i=n;i+)nif(ai=0) ncount+;nprintf(%dn,count); nreturn 0; n4/9/202225題目分

11、析題目分析(2)n相對之前，算法有否改進(jìn)；n但依然風(fēng)險很大n哪個地方依然影響效率？n如何改進(jìn)？n請自己完成n再思考再思考:若求某一段數(shù)中素數(shù)的個數(shù)呢若求某一段數(shù)中素數(shù)的個數(shù)呢?4/9/202226篩選法思想的其他應(yīng)用篩選法思想的其他應(yīng)用n1215 七夕節(jié)n題目大意：求一個數(shù)的真因子之和nSample Input：n2n10n20Sample Output：n8n224/9/202227題目分析題目分析n本題特點同前例題：數(shù)據(jù)量很大（可達(dá)50萬），每個數(shù)據(jù)也不小，同樣可達(dá)50萬。n常見方法：預(yù)處理篩法n思考：這個篩法和求素數(shù)的篩法細(xì)節(jié)區(qū)別在哪里？n再思考：如果是求一個數(shù)的因子的數(shù)量，哪里需要變化

12、？4/9/2022281215參考代碼參考代碼n略 :)4/9/202229菜鳥的菜鳥的2222個經(jīng)典錯誤個經(jīng)典錯誤.4/9/202230以以1089 A1089 AB B為例為例nSample Inputn1 5n10 20nSample Outputn6n304/9/202231菜鳥之傷（菜鳥之傷（1 1）n#includenvoid main()nnint a,b;nscanf(“%d%d”,&a,&b);nprintf(“%dn”,a+b);n4/9/202232菜鳥之傷（菜鳥之傷（1 1）n總結(jié)：程序不能處理多組數(shù)據(jù)的問題是最常見的入門問題，只要掌握幾種常見的類型，就

13、可以輕松掌握了，具體處理方法曾在第一次課件有詳細(xì)描述，這里省略了4/9/202233菜鳥之傷（菜鳥之傷（2 2）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)!=0)nprintf(“%dn”,a+b);n4/9/202234菜鳥之傷（菜鳥之傷（2 2）n總結(jié)：文件結(jié)束符EOF的值是-1而不是0，所以while(scanf()!=0)常常會因為死循環(huán)而造成TLE，這個必須牢記。n說明：不僅僅菜鳥，很多老鳥也常常因為不注意這點而犯錯誤，而且還常常因為想不到會犯這種低級錯誤而想不到原因。4/9/202235菜鳥之傷

14、（菜鳥之傷（3 3）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)!=EOF);nprintf(“%dn”,a+b);n4/9/202236菜鳥之傷（菜鳥之傷（3 3）n總結(jié)：while 或者 for循環(huán)的條件外面誤加了分號，編譯不影響，但是結(jié)果循環(huán)體沒有真正得到多次執(zhí)行；n說明：菜鳥常犯的錯誤，往往因為編譯能通過而不能迅速察覺，尤其比賽中n提醒：提醒：當(dāng)你將scanf();語句加上while循環(huán)以處理多組數(shù)據(jù)問題的時候尤其注意因為之前有分號，很容易忘記去掉！4/9/202237菜鳥之傷（菜鳥之傷（4 4）n#

15、includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b) =2)nprintf(“%dn”,a+b);n4/9/202238菜鳥之傷（菜鳥之傷（4 4）n總結(jié)：C語言中，賦值符號和判斷是否相等的邏輯符號具有完全不同的含義，往往因為我們的習(xí)慣問題，在編程中誤將判斷是否相等的邏輯符號寫成賦值符號。同樣的，這種失誤也會因為不影響編譯而影響查錯的時間。n說明：菜鳥常犯的錯誤，但是有過幾次教訓(xùn)就會牢記了，呵呵4/9/202239以以1001 Sum Problem1001 Sum Problem為例為例nSample Inputn1n

16、100nSample Outputn1n50504/9/202240菜鳥之傷（菜鳥之傷（5 5）#includevoid main() int i,n,s; while(scanf(“%d”,&n) =1) for(i=1;i=n;i+) s+=i; printf(“%dnn”,s); 4/9/202241菜鳥之傷（菜鳥之傷（5 5）n總結(jié)：忘記變量的初始化是典型的菜鳥問題，不必緊張，多經(jīng)歷幾次就牢記了n說明：普通變量的初始化還比較容易查找，而用來保存計算結(jié)果的數(shù)組的初始化更是容易忘記！4/9/202242菜鳥之傷（菜鳥之傷（6 6）#includevoid main() int i,

17、n,s=0; while(scanf(“%d”,&n) =1) for(i=1;i=n;i+) s+=i; printf(“%dnn”,s); 4/9/202243菜鳥之傷（菜鳥之傷（6 6）n總結(jié)：變量初始化放在循環(huán)外，是一個典型的ACM初級錯誤，因為ACM賽題的多組測試特性，如果不能在循環(huán)內(nèi)初始化，將只能確保第一組數(shù)據(jù)沒問題，而很多入門者習(xí)慣只測試一組數(shù)據(jù)，很容易忽略這個問題。nn說明：菜鳥常犯的錯誤，關(guān)鍵是要理解為什么這樣會有問題，真正理解后，修改也就不難了。4/9/202244菜鳥之傷（菜鳥之傷（7 7）n#includenvoid main()nint i,n,s;nwhil

18、e(scanf(“%d”,&n) =1)nns=n*(n+1)/2;nprintf(“%dnn”,s);nn4/9/202245菜鳥之傷（菜鳥之傷（7 7）n總結(jié)：數(shù)組越界還能在提交后收到Runtime Error的信息反饋，而運(yùn)算中的數(shù)據(jù)溢出則往往只能收到Wrong Answer的錯誤提示，所以這種錯誤往往容易被誤導(dǎo)成算法問題；n說明：不僅菜鳥，就是大牛甚至大神，也常常犯這種錯誤，只是情況復(fù)雜些而已4/9/202246菜鳥之傷（菜鳥之傷（8 8）n#includenvoid main()nint i,n,s;nwhile(scanf(“%d”,&n) =1)nns=n/2*(

19、n+1);nprintf(“%dnn”,s);nn4/9/202247菜鳥之傷（菜鳥之傷（8 8）n總結(jié)：當(dāng)兩個整數(shù)進(jìn)行運(yùn)算的時候，運(yùn)算結(jié)果一定還是整數(shù)，所以不要因為常規(guī)數(shù)學(xué)慣性思維的影響而認(rèn)為結(jié)果可能為浮點數(shù)；而不同數(shù)據(jù)類型一同運(yùn)算的時候，運(yùn)算結(jié)果的數(shù)據(jù)類型和相對復(fù)雜的類型一致（比如 整數(shù)+實數(shù)，結(jié)果類型是實數(shù)）4/9/202248菜鳥之傷（菜鳥之傷（9 9）n#includenvoid main()nint i,n,s;n while(scanf(“%d”,&n) =1)n if(n%2=0)n s=n/2*(n+1);n elsen s=(n+1)/2*n;n printf(“%

20、dnn”,s);n4/9/202249菜鳥之傷（菜鳥之傷（9 9）n總結(jié)：寫for或者while等任何循環(huán)語句的時候，不管循環(huán)體內(nèi)有幾個語句，務(wù)必養(yǎng)成都加上一對大括號的好習(xí)慣。n常常碰到的情況是這樣的本來循環(huán)體內(nèi)只有一條語句，確實不用大括號，但是在修改程序的過程中，循環(huán)體內(nèi)增加了其他語句，而這時卻忘記了添加大括號！n所以說好習(xí)慣很重要！4/9/202250菜鳥之傷（菜鳥之傷（1010）n#includenvoid main()nint i,n,s;n while(scanf(“%d”,&n) =1)n if(n%2=0)n s=n/2*(n+1);n elsen s=(n+1)/2*n

21、; n printf(“%dnn”,s);n4/9/202251菜鳥之傷（菜鳥之傷（1010）n總結(jié)：這也是一個經(jīng)典錯誤，雖然為循環(huán)體加了大括號，但是并沒有包含全部的信息，造成的后果是只有一次輸出盡管對于每組數(shù)據(jù)都處理了，但是只輸出最后一組結(jié)果。n由于很多同學(xué)習(xí)慣每次只測試一組數(shù)據(jù)，就更容易忽略這個錯誤了.n再次證明再次證明好習(xí)慣很重要！好習(xí)慣很重要！4/9/202252菜鳥之傷（菜鳥之傷（1111）n假設(shè)不會中間溢出，下面的程序是否有問題？n#includenvoid main()nint i,n,s;n while(scanf(“%d”,&n) =1)n n s=n(n+1)/2;

22、n printf(“%dnn”,s);n n4/9/202253菜鳥之傷（菜鳥之傷（1111）n總結(jié)：這也是受數(shù)學(xué)習(xí)慣影響而可能出現(xiàn)的一個錯誤，當(dāng)然，這個錯誤很好檢查，因為編譯不能通過的n總結(jié)出這個只是因為確實會出現(xiàn)這個情況，而對于極度沒有編程經(jīng)驗的同學(xué)來說，有時候也會帶來困擾4/9/202254還是以還是以A AB B為例為例n題目描述：計算AB的值，輸入數(shù)據(jù)每行包含2個正整數(shù)，如果輸入數(shù)據(jù)是兩個負(fù)數(shù)，則結(jié)束輸入。nSample Inputn1 5n-1 -1nSample Outputn64/9/202255菜鳥之傷（菜鳥之傷（1212）n#includenvoid main()nnint

23、 a,b;nwhile(scanf(“%d%d”,&a,&b)=2)n if(a=-1 & b=-1) return;n printf(“%dn”,a+b);n4/9/202256菜鳥之傷（菜鳥之傷（1212）n總結(jié)：正如判斷相等要用“=”一樣，C語言中進(jìn)行邏輯與的運(yùn)算也是需要兩個字符“&”，類似的邏輯或運(yùn)算也是兩個字符“|”，如果是單個的字符，含義就完全不同了4/9/202257菜鳥之傷（菜鳥之傷（1313）n上一個程序的改進(jìn)版：上一個程序的改進(jìn)版：n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&

24、a,&b)=2)n if(a=-1 & b=-1) return;n printf(“%dn”,a+b);n4/9/202258菜鳥之傷（菜鳥之傷（1313）n總結(jié)：題目描述是負(fù)數(shù)結(jié)束輸入，Sample Input最后給出的是-1，如果讀題不仔細(xì)，很容易陷入思維定勢，而會不加思索在程序中用-1判斷，這樣就真的會發(fā)生不幸的事件盡管我也認(rèn)為這個陷阱有點陰，而且未必有很大意義，但是題目并沒錯，而你確實讀題不仔細(xì)n說明：算是經(jīng)典的小陷阱，現(xiàn)在很少出現(xiàn)了4/9/202259繼續(xù)以繼續(xù)以A AB B為例為例n題目描述：給定2個整數(shù)A和B，如果A+B0，請輸出”O(jiān)K!”，否則請輸出”No”n

25、Sample Inputn1 5n1 -5nSample OutputnOK!nNo4/9/202260菜鳥之傷（菜鳥之傷（1414）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)=2)n if(a+b0) printf(“OK!n”);n else printf(“NOn”); n4/9/202261菜鳥之傷（菜鳥之傷（1414）n總結(jié)：字符串輸出的大小寫問題對于菜鳥需要特別注意，其實，不管是全大寫、全小寫，還是首字母大寫，你盡管復(fù)制即可（沒有電子版，另當(dāng)別論），當(dāng)然還要注意是否有標(biāo)點符號等情況。n說明：菜鳥

26、常犯錯誤，稍有經(jīng)驗即可避免4/9/202262以以11701170Balloon Comes!為例為例nSample Inputn4n+ 1 2n- 1 2n* 1 2n/ 1 2nSample Outputn3n-1n2n0.504/9/202263菜鳥之傷（菜鳥之傷（1 15 5）nint n,a,b,i;nchar p;nscanf(%d,&n);nfor (i=0;in;i+)nn scanf(%c%d%d,&p,&a,&b);n if( ) n4/9/202264菜鳥之傷（菜鳥之傷（1 15 5）n剛才程序的改進(jìn)版剛才程序的改進(jìn)版: :nint n,a

27、,b,i;nchar p;nscanf(%d,&n);ngetchar();nfor (i=0;in;i+)nn scanf(%c%d%d,&p,&a,&b);n if( .) nn是否還有問題？如何修改？是否還有問題？如何修改？4/9/202265菜鳥之傷（菜鳥之傷（1515）n總結(jié)：字符和數(shù)字的混合輸入帶來的問題，也是一個常常困擾使用C語言編程的同學(xué)的經(jīng)典問題，關(guān)鍵就是程序未能及時接收回車符，而誤將回車當(dāng)作下一組數(shù)據(jù)的首字母，你可以通過添加一句getchar(); 輕松解決該問題。n說明：菜鳥的經(jīng)典錯誤，如果之前沒有遇到過，很難一下子反應(yīng)過來，當(dāng)然，遇到一次

28、以后就不成為問題了4/9/2022662007 2007 平方和與立方和平方和與立方和n給定一段連續(xù)的整數(shù)，求出他們中所有偶數(shù)的平方和以及所有奇數(shù)的立方和。nSample Inputn1 3n2 5nSample Outputn4 28n20 1524/9/202267菜鳥之傷（菜鳥之傷（1 16 6）#includevoid main() int m,n; while(scanf(“%d%d” ,&m,&n) =2) int i,x=0,y=0; for(i=m;i=n;i+) if(i%2=0) y=y+i*i; else x=x+i*i*i; printf(“%d %dn

29、”,y,x); 4/9/202268菜鳥之傷（菜鳥之傷（1 16 6）n總結(jié)：題目并沒有保證數(shù)據(jù)是遞增的，但人往往有思維定勢，而很多題目的設(shè)計就是針對這一點！不要埋怨，這種訓(xùn)練能很好的培養(yǎng)我們審慎的思維習(xí)慣。n說明：這種錯誤經(jīng)歷過以后還是比較容易牢記的，所以說有時候經(jīng)驗很重要。4/9/202269菜鳥之傷（菜鳥之傷（1 17 7）n以下的程序輸出什么？n#includen#includenint main()nnint j=0;nfor(j=0;j5;j+)nncoutj=;nprintf(%dn,j);nnreturn 0;n4/9/202270菜鳥之傷（菜鳥之傷（1 17 7）n 期望輸出

30、：nj=0nj=1nj=2nj=3nj=4n 實際輸出：n?4/9/202271菜鳥之傷（菜鳥之傷（1 17 7）n總結(jié)：在一個程序中同時使用C和C+的輸出語句，很容易帶來問題，原因就是輸出機(jī)制不完全一樣（一個不帶緩沖，一個帶緩沖），所以盡量避免C和C+輸出語句混用。n說明：這是傳說中的經(jīng)典錯誤，據(jù)說曾困擾某牛人于現(xiàn)場賽 :-)4/9/202272以以2004 2004 成績轉(zhuǎn)換成績轉(zhuǎn)換 為例為例n題目描述：題目描述：輸入一個百分制的成績t，將其轉(zhuǎn)換成對應(yīng)的等級，具體轉(zhuǎn)換規(guī)則如下： 90100為A; 8089為B; 7079為C; 6069為D; 059為E;n輸出描述：輸出描述：對于每組輸入

31、數(shù)據(jù)，輸出一行。如果輸入數(shù)據(jù)不在0100范圍內(nèi)，請輸出一行：“Score is error!”。4/9/202273菜鳥之傷（菜鳥之傷（1 18 8）n#includenint main()n int t,a;n while(scanf(%d,&t)!=EOF)n if(t100|t0) printf(Score is error!n);n elsen a=(t-50)/10;n switch(a)n case 5:n case 4:printf(An); case 3:printf(Bn);n case 2:printf(Cn); case 1:printf(Dn);n defaul

32、t:printf(En); n n return 0;n 4/9/202274菜鳥之傷（菜鳥之傷（1 18 8）n總結(jié)：C語言中的case語句要求在每個case的處理后面都要跟break；（特殊需求除外），而如果因為不了解或者不小心而缺少部分break;則執(zhí)行的效果也許會不符合你最初的設(shè)計。n說明：C語言的基本功很重要4/9/202275以以2046 2046 骨牌鋪方格骨牌鋪方格 為例為例n題目描述：題目描述：在2n的一個長方形方格中,用一個1 2的骨牌鋪滿方格,輸入n ,輸出鋪放方案的總數(shù).n輸入描述：輸入描述：輸入數(shù)據(jù)由多行組成，每行包含一個整數(shù)n,表示該測試實例的長方形方格的規(guī)格是2n

33、 (0n=50)。4/9/202276菜鳥之傷（菜鳥之傷（1 19 9）n#includenint main()nn int i;n _int64 a50=0,1,2;n for(i=3;i=50;i+)n ai=ai-1+ai-2;n while(scanf(%d,&i)!=EOF)n printf(%I64dn,ai); n n4/9/202277菜鳥之傷（菜鳥之傷（1 19 9）n總結(jié)：數(shù)組下標(biāo)越界是最常見的Runtime Error，也是菜鳥常犯的錯誤，除了需要扎實的C語言基本功，編程中的注意力集中也是需要的（很多時候不是不知道理論，而是不注意）n說明：一般情況，你可以通過將數(shù)

34、組開的大點而盡量避免這個問題4/9/202278以以1425 1425 SortSort為例為例n題目描述：題目描述：給你n個整數(shù)，請按從大到小的順序輸出其中前m大的數(shù)。n輸入描述：輸入描述：每組測試數(shù)據(jù)有兩行，第一行有兩個數(shù)n,m(0n,m1000000)，第二行包含n個各不相同，且都處于區(qū)間-500000,500000的整數(shù)。4/9/202279菜鳥之傷（菜鳥之傷（2020）n#includenvoid main()nn int n,m,i,num1000000;n while(scanf(“%d%d”,&n,&m)=2)n . n4/9/202280菜鳥之傷（菜鳥之傷（2020）n總結(jié)：ACM編程中，使用很大的數(shù)組是很常見的做法，但如果超大的數(shù)組被定義成局部變量，則很容易出現(xiàn)Runtime Error，解決辦法也很簡單：定義成全局變量即可。原因是局部變量分配在棧（較?。?，全局變量分配在堆（較大）；n說明：這里所說的超大也不能無限制的大，可以根