ACM程序設(shè)計杭州電子科技大學(xué)劉春英

2023/10/12每周一星（8）：4546

2023/10/13第九講篩選法及預(yù)處理（附-菜鳥的21個經(jīng)典錯誤）2023/10/14例1-素數(shù)判斷題目描述： 給定一個N（1<N<100000），請判斷N是否是素數(shù)，如果是素數(shù)，則請輸出YES，否則輸出NO。SampleInput： 4 5SampleOutput: NO

YES2023/10/15常見樸素算法#include<stdio.h>intmain(){ inti,n; while(scanf("%d",&n)==1) { for(i=2;i<n;i++) if(n%i==0)break; if(i==n)printf("YES\n"); elseprintf("NO\n"); }}2023/10/16樸素算法優(yōu)化版本#include<stdio.h>#include<math.h>intmain(){ inti,n,x; while(scanf("%d",&n)==1) { x=(int)sqrt(n); for(i=2;i<=x;i++) if(n%i==0)break; if(i>x)printf("YES\n"); elseprintf("NO\n"); }}2023/10/17例2-求所有素數(shù)題目描述： 給定一個N（1<N<100000），請按照遞增次序輸出所有小于等于N的素數(shù)。SampleInput： 10SampleOutput: 23572023/10/18題目分析題目特點：不是求一個素數(shù)，而是求一段素數(shù)（一種常見的情況就是求指定范圍的所有的素數(shù)）如果還用常規(guī)求素數(shù)方法，可能的問題是？2023/10/19篩選法求素數(shù)基本思想：素數(shù)的倍數(shù)一定不是素數(shù)實現(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ù)。說明：整數(shù)1特殊處理即可。2023/10/110效果演示000000000000000000015432671110981213171615142023/10/111效果演示000100000000000000015432671110981213171615142023/10/112效果演示000100100000000000015432671110981213171615142023/10/113效果演示000100100001000000015432671110981213171615142023/10/114效果演示000100100101100101015432671110981213171615142023/10/115效果演示000100100111100111015432671110981213171615142023/10/116效果演示000100100111100111015432671110981213171615142023/10/117效果演示000100100111100111015432671110981213171615142023/10/118效果演示000100100111100111015432671110981213171615142023/10/119參考代碼（篩選法）#include<stdio.h>#include<math.h>inta[100001];intmain(){inti,j,n; while(scanf("%d",&n)==1) { for(i=2;i<=n;i++) {if(a[i]==0) for(j=i+i;j<=n;j+=i) a[j]=1;} printf("2"); for(i=3;i<=n;i++) if(a[i]==0)printf("%d",i); printf("\n");} return0;}2023/10/120例3-求素數(shù)個數(shù)題目描述： 給定一個N（1<N<100000），請輸出小于等于N的素數(shù)的個數(shù)。測試數(shù)據(jù)有C組，（1<C<100000）.SampleInput： 10SampleOutput: 42023/10/121常規(guī)篩選法代碼#include<stdio.h>#include<math.h>inta[100001];intmain(){inti,j,n,count;while(scanf("%d",&n)==1){ count=0; for(i=2;i<=n;i++) {if(a[i]==0) for(j=i+i;j<=n;j+=i) a[j]=1;} for(i=2;i<=n;i++) if(a[i]==0) count++; printf("%d\n",count);} return0;}2023/10/122題目分析(1)題目特點：數(shù)據(jù)量超大！分析：前面算法的瓶頸：每組數(shù)據(jù)都求素數(shù)...如何改進(jìn)以加快求解速度？可否一次篩選，多次查找？這就是預(yù)處理思想~2023/10/123預(yù)處理參考代碼#include<stdio.h>#include<math.h>inta[100001];intmain(){inti,j,n,count; for(i=2;i<=100000;i++) {if(a[i]==0) for(j=i+i;j<=100000;j+=i) a[j]=1;} while(scanf("%d",&n)==1){ count=0; for(i=2;i<=n;i++) if(a[i]==0) count++; printf("%d\n",count);} return0;}2023/10/124題目分析(2)相對之前，算法有否改進(jìn)；但依然風(fēng)險很大——哪個地方依然影響效率？如何改進(jìn)？請自己完成~2023/10/125篩選法思想的其他應(yīng)用1215七夕節(jié)題目大意：求一個數(shù)的真因子之和SampleInput：21020SampleOutput：8222023/10/126題目分析本題特點同前例題：數(shù)據(jù)量很大（可達(dá)50萬），每個數(shù)據(jù)也不小，同樣可達(dá)50萬。常見方法：預(yù)處理篩法思考：這個篩法和求素數(shù)的篩法細(xì)節(jié)區(qū)別在哪里？再思考：如果是求一個數(shù)的因子的數(shù)量，哪里需要變化？2023/10/1271215參考代碼略:)2023/10/128菜鳥的21個經(jīng)典錯誤......2023/10/129以1089A＋B為例SampleInput151020SampleOutput6302023/10/130菜鳥之傷（1）#include<stdio.h>voidmain(){inta,b;scanf(“%d%d”,&a,&b);printf(“%d\n”,a+b);}2023/10/131菜鳥之傷（1）總結(jié)： 程序不能處理多組數(shù)據(jù)的問題是最常見的入門問題，只要掌握幾種常見的類型，就可以輕松掌握了，具體處理方法曾在第一次課件有詳細(xì)描述，這里省略了～2023/10/132菜鳥之傷（2）#include<stdio.h>voidmain(){inta,b;while(scanf(“%d%d”,&a,&b)!=0)printf(“%d\n”,a+b);}2023/10/133菜鳥之傷（2）總結(jié)：文件結(jié)束符EOF的值是-1而不是0，所以while(scanf(…)!=0)常常會因為死循環(huán)而造成TLE，這個必須牢記。

說明：不僅僅菜鳥，很多老鳥也常常因為不注意這點而犯錯誤，而且還常常因為想不到會犯這種低級錯誤而想不到原因。2023/10/134菜鳥之傷（3）#include<stdio.h>voidmain(){inta,b;while(scanf(“%d%d”,&a,&b)!=EOF);printf(“%d\n”,a+b);}2023/10/135菜鳥之傷（3）總結(jié)：while或者for循環(huán)的條件外面誤加了分號，編譯不影響，但是結(jié)果循環(huán)體沒有真正得到多次執(zhí)行；說明：菜鳥常犯的錯誤，往往因為編譯能通過而不能迅速察覺，尤其比賽中～提醒：當(dāng)你將scanf();語句加上while循環(huán)以處理多組數(shù)據(jù)問題的時候尤其注意——因為之前有分號，很容易忘記去掉！2023/10/136菜鳥之傷（4）#include<stdio.h>voidmain(){inta,b;while(scanf(“%d%d”,&a,&b)=2)printf(“%d\n”,a+b);}2023/10/137菜鳥之傷（4）總結(jié)：

C語言中，賦值符號＝和判斷是否相等的邏輯符號＝＝具有完全不同的含義，往往因為我們的習(xí)慣問題，在編程中誤將判斷是否相等的邏輯符號寫成賦值符號＝。同樣的，這種失誤也會因為不影響編譯而影響查錯的時間。說明：菜鳥常犯的錯誤，但是有過幾次教訓(xùn)就會牢記了，呵呵～2023/10/138以1001SumProblem為例SampleInput1100SampleOutput150502023/10/139菜鳥之傷（5）#include<stdio.h>voidmain(){inti,n,s;while(scanf(“%d”,&n)==1){for(i=1;i<=n;i++)s+=i;printf(“%d\n\n”,s);}}2023/10/140菜鳥之傷（5）總結(jié)： 忘記變量的初始化是典型的菜鳥問題，不必緊張，多經(jīng)歷幾次就牢記了～說明：普通變量的初始化還比較容易查找，而用來保存計算結(jié)果的數(shù)組的初始化更是容易忘記！2023/10/141菜鳥之傷（6）#include<stdio.h>voidmain(){inti,n,s=0;while(scanf(“%d”,&n)==1){for(i=1;i<=n;i++)s+=i;printf(“%d\n\n”,s);}}2023/10/142菜鳥之傷（6）總結(jié)：變量初始化放在循環(huán)外，是一個典型的ACM初級錯誤，因為ACM賽題的多組測試特性，如果不能在循環(huán)內(nèi)初始化，將只能確保第一組數(shù)據(jù)沒問題，而很多入門者習(xí)慣只測試一組數(shù)據(jù)，很容易忽略這個問題。

說明：菜鳥常犯的錯誤，關(guān)鍵是要理解為什么這樣會有問題，真正理解后，修改也就不難了。2023/10/143菜鳥之傷（7）#include<stdio.h>voidmain(){inti,n,s;while(scanf(“%d”,&n)==1){s=n*(n+1)/2;printf(“%d\n\n”,s);}}2023/10/144菜鳥之傷（7）總結(jié)： 數(shù)組越界還能在提交后收到RuntimeError的信息反饋，而運算中的數(shù)據(jù)溢出則往往只能收到WrongAnswer的錯誤提示，所以這種錯誤往往容易被誤導(dǎo)成算法問題；

說明： 不僅菜鳥，就是大牛甚至大神，也常常犯這種錯誤，只是情況復(fù)雜些而已～2023/10/145菜鳥之傷（8）#include<stdio.h>voidmain(){inti,n,s;while(scanf(“%d”,&n)==1){s=n/2*(n+1);printf(“%d\n\n”,s);}}2023/10/146菜鳥之傷（8）總結(jié)： 當(dāng)兩個整數(shù)進(jìn)行運算的時候，運算結(jié)果一定還是整數(shù)，所以不要因為常規(guī)數(shù)學(xué)慣性思維的影響而認(rèn)為結(jié)果可能為浮點數(shù)； 而不同數(shù)據(jù)類型一同運算的時候，運算結(jié)果的數(shù)據(jù)類型和相對復(fù)雜的類型一致（比如整數(shù)+實數(shù)，結(jié)果類型是實數(shù)）

2023/10/147菜鳥之傷（9）#include<stdio.h>voidmain(){

inti,n,s;

while(scanf(“%d”,&n)==1)if(n%2==0)

s=n/2*(n+1);elses=(n+1)/2*n;

printf(“%d\n\n”,s);}2023/10/148菜鳥之傷（9）總結(jié)： 寫for或者while等任何循環(huán)語句的時候，不管循環(huán)體內(nèi)有幾個語句，務(wù)必養(yǎng)成都加上一對大括號的好習(xí)慣。常常碰到的情況是這樣的——本來循環(huán)體內(nèi)只有一條語句，確實不用大括號，但是在修改程序的過程中，循環(huán)體內(nèi)增加了其他語句，而這時卻忘記了添加大括號！所以說——好習(xí)慣很重要！2023/10/149菜鳥之傷（10）#include<stdio.h>voidmain(){

inti,n,s;

while(scanf(“%d”,&n)==1){if(n%2==0)

s=n/2*(n+1);elses=(n+1)/2*n;}

printf(“%d\n\n”,s);}2023/10/150菜鳥之傷（10）總結(jié)： 這也是一個經(jīng)典錯誤，雖然為循環(huán)體加了大括號，但是并沒有包含全部的信息，造成的后果是只有一次輸出——盡管對于每組數(shù)據(jù)都處理了，但是只輸出最后一組結(jié)果。由于很多同學(xué)習(xí)慣每次只測試一組數(shù)據(jù)，就更容易忽略這個錯誤了...再次證明——好習(xí)慣很重要！2023/10/151菜鳥之傷（11）假設(shè)不會中間溢出，下面的程序是否有問題？#include<stdio.h>voidmain(){

inti,n,s;

while(scanf(“%d”,&n)==1)

{

s=n(n+1)/2;

printf(“%d\n\n”,s);

}}2023/10/152菜鳥之傷（11）總結(jié)： 這也是受數(shù)學(xué)習(xí)慣影響而可能出現(xiàn)的一個錯誤，當(dāng)然，這個錯誤很好檢查，因為編譯不能通過的~總結(jié)出這個只是因為確實會出現(xiàn)這個情況，而對于極度沒有編程經(jīng)驗的同學(xué)來說，有時候也會帶來困擾~

2023/10/153還是以A＋B為例題目描述：計算A＋B的值，輸入數(shù)據(jù)每行包含2個正整數(shù)，如果輸入數(shù)據(jù)是兩個負(fù)數(shù)，則結(jié)束輸入。SampleInput15-1-1SampleOutput62023/10/154菜鳥之傷（12）#include<stdio.h>voidmain(){inta,b;while(scanf(“%d%d”,&a,&b)==2){if(a==-1&b==-1)return;printf(“%d\n”,a+b);}2023/10/155菜鳥之傷（12）總結(jié)：正如判斷相等要用“==”一樣，C語言中進(jìn)行邏輯與的運算也是需要兩個字符“&&”，類似的邏輯或運算也是兩個字符“||”，如果是單個的字符，含義就完全不同了~2023/10/156菜鳥之傷（13）上一個程序的改進(jìn)版：#include<stdio.h>voidmain(){inta,b;while(scanf(“%d%d”,&a,&b)==2){if(a==-1&&b==-1)return;printf(“%d\n”,a+b);}2023/10/157菜鳥之傷（13）總結(jié)：題目描述是負(fù)數(shù)結(jié)束輸入，SampleInput最后給出的是-1，如果讀題不仔細(xì)，很容易陷入思維定勢，而會不加思索在程序中用-1判斷，這樣就真的會發(fā)生不幸的事件——盡管我也認(rèn)為這個陷阱有點陰，而且未必有很大意義，但是題目并沒錯，而你確實讀題不仔細(xì)～

說明：算是經(jīng)典的小陷阱，現(xiàn)在很少出現(xiàn)了2023/10/158繼續(xù)以A＋B為例題目描述：給定2個整數(shù)A和B，如果A+B>0，請輸出”O(jiān)K!”，否則請輸出”No~”SampleInput151-5SampleOutputOK!No~2023/10/159菜鳥之傷（14）#include<stdio.h>voidmain(){inta,b;while(scanf(“%d%d”,&a,&b)==2){if(a+b>0)printf(“OK!\n”);elseprintf(“NO~\n”);}}2023/10/160菜鳥之傷（14）總結(jié)：字符串輸出的大小寫問題對于菜鳥需要特別注意，其實，不管是——全大寫、全小寫，還是首字母大寫，你盡管復(fù)制即可（沒有電子版，另當(dāng)別論），當(dāng)然還要注意是否有標(biāo)點符號等情況。

說明：菜鳥常犯錯誤，稍有經(jīng)驗即可避免2023/10/161以1170BalloonComes!為例SampleInput4+12-12*12/12SampleOutput3-120.502023/10/162菜鳥之傷（15）intn,a,b,i;charp;scanf("%d",&n);for(i=0;i<n;i++){scanf("%c%d%d",&p,&a,&b);if(……)}2023/10/163菜鳥之傷（15）剛才程序的改進(jìn)版:intn,a,b,i;charp;scanf("%d",&n);getchar();for(i=0;i<n;i++){scanf("%c%d%d",&p,&a,&b);if(...)……}是否還有問題？如何修改？2023/10/164菜鳥之傷（15）總結(jié)：字符和數(shù)字的混合輸入帶來的問題，也是一個常常困擾使用C語言編程的同學(xué)的經(jīng)典問題，關(guān)鍵就是程序未能及時接收回車符，而誤將回車當(dāng)作下一組數(shù)據(jù)的首字母，你可以通過添加一句getchar();輕松解決該問題。

說明：菜鳥的經(jīng)典錯誤，如果之前沒有遇到過，很難一下子反應(yīng)過來，當(dāng)然，遇到一次以后就不成為問題了～2023/10/1652007平方和與立方和給定一段連續(xù)的整數(shù)，求出他們中所有偶數(shù)的平方和以及所有奇數(shù)的立方和。SampleInput1325SampleOutput428201522023/10/166菜鳥之傷（16）#include<stdio.h>voidmain(){intm,n;while(scanf(“%d%d”,&m,&n)==2){inti,x=0,y=0;for(i=m;i<=n;i++){if(i%2==0)y=y+i*i;elsex=x+i*i*i;}printf(“%d%d\n”,y,x);}}2023/10/167菜鳥之傷（16）總結(jié)：題目并沒有保證數(shù)據(jù)是遞增的，但人往往有思維定勢，而很多題目的設(shè)計就是針對這一點！不要埋怨，這種訓(xùn)練能很好的培養(yǎng)我們審慎的思維習(xí)慣。說明：這種錯誤經(jīng)歷過以后還是比較容易牢記的，所以說有時候經(jīng)驗很重要。2023/10/168菜鳥之傷（17）以下的程序輸出什么？#include<stdio.h>#include<iostream.h>intmain(){ intj=0; for(j=0;j<5;j++) { cout<<"j="; printf("%d\n",j); } return0;}2023/10/169菜鳥之傷（17）期望輸出：j=0j=1j=2j=3j=4實際輸出：???2023/10/170菜鳥之傷（17）總結(jié)：在一個程序中同時使用C和C++的輸出語句，很容易帶來問題，原因就是輸出機(jī)制不完全一樣（一個不帶緩沖，一個帶緩沖），所以盡量避免C和C++輸出語句混用。

說明：這是傳說中的經(jīng)典錯誤，據(jù)說曾困擾某牛人于現(xiàn)場賽:-)2023/10/171以2004成績轉(zhuǎn)換為例題目描述：輸入一個百分制的成績t，將其轉(zhuǎn)換成對應(yīng)的等級，具體轉(zhuǎn)換規(guī)則如下：90~100為A;80~89為B;70~79為C;60~69為D;0~59為E;輸出描述：對于每組輸入數(shù)據(jù)，輸出一行。如果輸入數(shù)據(jù)不在0~100范圍內(nèi)，請輸出一行：“Scoreiserror!”。2023/10/172菜鳥之傷（18）#include<stdio.h>intmain(){intt,a;while(scanf("%d",&t)!=EOF){if(t>100||t<0)printf("Scoreiserror!\n");else{a=(t-50)/10;switch(a){case5:case4:printf("A\n");case3:printf("B\n");case2:printf("C\n");case1:printf("D\n");default:printf("E\n");}}}return0;}2023/10/173菜鳥之傷（18）總結(jié)：C語言中的case語句要求在每個case的處理后面都要跟break；（特殊需求除外），而如果因為不了解或者不小心而缺少部分break;則執(zhí)行的效果也許會不符合你最初的設(shè)計。

說明：C語言的基本功很重要～2023/10/174以2046骨牌鋪方格為例題目描述：在2×n的一個長方形方格中,用一個1×2的骨牌鋪滿方格,輸入n,輸出鋪放方案的總數(shù).輸入描述：輸入數(shù)據(jù)由多行組成，每行包含一個整數(shù)n,表示該測試實例的長方形方格的規(guī)格是2×n(0<n<=50)。2023/10/175菜鳥之傷（19）#include<stdio.h>intmain(){inti;__int64a[50]={0,1,2};for(i=3;i<=50;i++)a[i]=a[i-1]+a[i-2];while(scanf("%d",&i)!=EOF){printf("%I64d\n",a[i]);}}2023/10/176菜鳥之傷（19）總結(jié)：數(shù)組下標(biāo)越界是最常見的RuntimeError，也是菜鳥常犯的錯誤，除了需要扎實的C語言基本功，編程中的注意力集中也是需要的（很多時候不是不知道理論，而是不注意）~說明：一般情況，你可以通過將數(shù)組開的大點而盡量避免這個問題~2023/10/177以1425Sort為例題目描述：給你n個整數(shù)，請按從大到小的順序輸出其中前m大的數(shù)。輸入描述：每組測試數(shù)據(jù)有兩行，第一行有兩個數(shù)n,m(0