(HDUACM201303版_05)篩選法及預(yù)處理(附菜鳥的23個(gè)經(jīng)典錯(cuò)誤)

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

2、nfor(i=2;in;i+)n if(n%i=0) break; nif(i=n) printf(YESn);nelse printf(NOn);nn2/10/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);nn2/10/20227例例2-求所有素?cái)?shù)求所有素?cái)?shù)n題目描述：給定一個(gè)N（1N100000），請(qǐng)按照遞增次序輸出所有小于等于N的素?cái)?shù)。nSam

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

4、。n說(shuō)明：整數(shù)1特殊處理即可。2/10/202210效果演示效果演示0 000000 000000 000000 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142/10/202211效果演示效果演示0 001000 000000 000000 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142/10/202212效果演示效果演示0 001001 000000 000000 01 15 54 43 32 26 67 7111110109 98 81

5、212 131317171616151514142/10/202213效果演示效果演示0 001001 000010 000000 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142/10/202214效果演示效果演示0 001001 001011 001010 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142/10/202215效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110

6、109 98 81212 131317171616151514142/10/202216效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142/10/202217效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142/10/202218效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 6

7、7 7111110109 98 81212 131317171616151514142/10/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; 2/10/202220思考思考-常規(guī)篩選法的

8、改進(jìn)？常規(guī)篩選法的改進(jìn)？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; 2/10/202221例例3-求素?cái)?shù)個(gè)數(shù)求素?cái)?shù)個(gè)數(shù)n題目描述：給定一個(gè)N（1N100000），請(qǐng)輸出小于等于N的素?cái)?shù)的個(gè)數(shù)。n測(cè)試數(shù)據(jù)有C組，（1C100000）

9、.nSample Input：10nSample Output:42/10/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; n2/10/202223題目分析題目分析(1)n題目特點(diǎn)：

10、數(shù)據(jù)量超大！n分析：前面算法的瓶頸：每組數(shù)據(jù)都求素?cái)?shù).n如何改進(jìn)以加快求解速度？n可否一次篩選，多次查找？n這就是預(yù)處理思想2/10/202224預(yù)處理參考代碼預(yù)處理參考代碼n#includen#includenint a100001;nint main()nint i,j,n,count;nfor(i=2;i=100000;i+)n if(ai=0)n for(j=i+i;j=100000;j+=i)n aj=1; /以上代碼還是樸素篩選，需改進(jìn)以上代碼還是樸素篩選，需改進(jìn)nwhile(scanf(%d,&n)=1)n count=0;nfor(i=2;i=n;i+)nif(ai=0

11、) ncount+;nprintf(%dn,count); nreturn 0; n2/10/202225題目分析題目分析(2)n相對(duì)之前，算法有否改進(jìn)；n但依然風(fēng)險(xiǎn)很大n哪個(gè)地方依然影響效率？n如何改進(jìn)？n請(qǐng)自己完成n再思考再思考:若求某一段數(shù)中素?cái)?shù)的個(gè)數(shù)呢若求某一段數(shù)中素?cái)?shù)的個(gè)數(shù)呢?2/10/202226篩選法思想的其他應(yīng)用篩選法思想的其他應(yīng)用n1215 七夕節(jié)n題目大意：求一個(gè)數(shù)的真因子之和nSample Input：n2n10n20Sample Output：n8n222/10/202227題目分析題目分析n本題特點(diǎn)同前例題：數(shù)據(jù)量很大（可達(dá)50萬(wàn)），每個(gè)數(shù)據(jù)也不小，同樣可達(dá)50萬(wàn)。n

12、常見(jiàn)方法：預(yù)處理篩法n思考：這個(gè)篩法和求素?cái)?shù)的篩法細(xì)節(jié)區(qū)別在哪里？n再思考：如果是求一個(gè)數(shù)的因子的數(shù)量，哪里需要變化？2/10/2022281215參考代碼參考代碼n略 :)2/10/202229菜鳥的菜鳥的2 23 3個(gè)經(jīng)典錯(cuò)誤個(gè)經(jīng)典錯(cuò)誤.2/10/202230以以1089 A1089 AB B為例為例nSample Inputn1 5n10 20nSample Outputn6n302/10/202231菜鳥之傷（菜鳥之傷（1 1）n#includenvoid main()nnint a,b;nscanf(“%d%d”,&a,&b);nprintf(“%dn”,a+b);n

13、2/10/202232菜鳥之傷（菜鳥之傷（1 1）n總結(jié)：程序不能處理多組數(shù)據(jù)的問(wèn)題是最常見(jiàn)的入門問(wèn)題，只要掌握幾種常見(jiàn)的類型，就可以輕松掌握了，具體處理方法曾在第一次課件有詳細(xì)描述，這里省略了2/10/202233菜鳥之傷（菜鳥之傷（2 2）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)!=0)nprintf(“%dn”,a+b);n2/10/202234菜鳥之傷（菜鳥之傷（2 2）n總結(jié)：文件結(jié)束符EOF的值是-1而不是0，所以while(scanf()!=0)常常會(huì)因?yàn)樗姥h(huán)而造成TLE，這個(gè)必須牢記。n

14、說(shuō)明：不僅僅菜鳥，很多老鳥也常常因?yàn)椴蛔⒁膺@點(diǎn)而犯錯(cuò)誤，而且還常常因?yàn)橄氩坏綍?huì)犯這種低級(jí)錯(cuò)誤而想不到原因。2/10/202235菜鳥之傷（菜鳥之傷（3 3）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)!=EOF);nprintf(“%dn”,a+b);n2/10/202236菜鳥之傷（菜鳥之傷（3 3）n總結(jié)：while 或者 for循環(huán)的條件外面誤加了分號(hào)，編譯不影響，但是結(jié)果循環(huán)體沒(méi)有真正得到多次執(zhí)行；n說(shuō)明：菜鳥常犯的錯(cuò)誤，往往因?yàn)榫幾g能通過(guò)而不能迅速察覺(jué)，尤其比賽中n提醒：提醒：當(dāng)你將scanf();

15、語(yǔ)句加上while循環(huán)以處理多組數(shù)據(jù)問(wèn)題的時(shí)候尤其注意因?yàn)橹坝蟹痔?hào)，很容易忘記去掉！2/10/202237菜鳥之傷（菜鳥之傷（4 4）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b) =2)nprintf(“%dn”,a+b);n2/10/202238菜鳥之傷（菜鳥之傷（4 4）n總結(jié)：C語(yǔ)言中，賦值符號(hào)和判斷是否相等的邏輯符號(hào)具有完全不同的含義，往往因?yàn)槲覀兊牧?xí)慣問(wèn)題，在編程中誤將判斷是否相等的邏輯符號(hào)寫成賦值符號(hào)。同樣的，這種失誤也會(huì)因?yàn)椴挥绊懢幾g而影響查錯(cuò)的時(shí)間。n說(shuō)明：菜鳥常犯的錯(cuò)誤，但是有過(guò)幾次教訓(xùn)就

16、會(huì)牢記了，呵呵2/10/202239以以1001 Sum Problem1001 Sum Problem為例為例nSample Inputn1n100nSample Outputn1n50502/10/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); 2/10/202241菜鳥之傷（菜鳥之傷（5 5）n總結(jié)：忘記變量的初始化是典型的菜鳥問(wèn)題，不必緊張，多經(jīng)歷幾次就牢記了n說(shuō)明：普通變量的初始化還比較容易查找

17、，而用來(lái)保存計(jì)算結(jié)果的數(shù)組的初始化更是容易忘記！2/10/202242菜鳥之傷（菜鳥之傷（6 6）#includevoid main() int i,n,s=0; while(scanf(“%d”,&n) =1) for(i=1;i=n;i+) s+=i; printf(“%dnn”,s); 2/10/202243菜鳥之傷（菜鳥之傷（6 6）n總結(jié)：變量初始化放在循環(huán)外，是一個(gè)典型的ACM初級(jí)錯(cuò)誤，因?yàn)锳CM賽題的多組測(cè)試特性，如果不能在循環(huán)內(nèi)初始化，將只能確保第一組數(shù)據(jù)沒(méi)問(wèn)題，而很多入門者習(xí)慣只測(cè)試一組數(shù)據(jù)，很容易忽略這個(gè)問(wèn)題。nn說(shuō)明：菜鳥常犯的錯(cuò)誤，關(guān)鍵是要理解為什么這樣會(huì)有問(wèn)題

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

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

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

21、nt 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(“%dnn”,s);n2/10/202251菜鳥之傷（菜鳥之傷（1010）n總結(jié)：這也是一個(gè)經(jīng)典錯(cuò)誤，雖然為循環(huán)體加了大括號(hào)，但是并沒(méi)有包含全部的信息，造成的后果是只有一次輸出盡管對(duì)于每組數(shù)據(jù)都處理了，但是只輸出最后一組結(jié)果。n由于很多同學(xué)習(xí)慣每次只測(cè)試一組數(shù)據(jù)，就更容易忽略這個(gè)錯(cuò)誤了.n再次證明再次證明好習(xí)慣很重要！好習(xí)慣很重要！2/10/202252菜鳥之傷（菜鳥之傷（1111）n假設(shè)不會(huì)中間溢出，下面的

22、程序是否有問(wèn)題？n#includenvoid main()nint i,n,s;n while(scanf(“%d”,&n) =1)n n s=n(n+1)/2;n printf(“%dnn”,s);n n2/10/202253菜鳥之傷（菜鳥之傷（1111）n總結(jié)：這也是受數(shù)學(xué)習(xí)慣影響而可能出現(xiàn)的一個(gè)錯(cuò)誤，當(dāng)然，這個(gè)錯(cuò)誤很好檢查，因?yàn)榫幾g不能通過(guò)的n總結(jié)出這個(gè)只是因?yàn)榇_實(shí)會(huì)出現(xiàn)這個(gè)情況，而對(duì)于極度沒(méi)有編程經(jīng)驗(yàn)的同學(xué)來(lái)說(shuō)，有時(shí)候也會(huì)帶來(lái)困擾2/10/202254還是以還是以A AB B為例為例n題目描述：計(jì)算AB的值，輸入數(shù)據(jù)每行包含2個(gè)正整數(shù)，如果輸入數(shù)據(jù)是兩個(gè)負(fù)數(shù)，則結(jié)束輸入。nSa

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

24、之傷（菜鳥之傷（1313）n上一個(gè)程序的改進(jìn)版：上一個(gè)程序的改進(jìn)版：n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)=2)n if(a=-1 & b=-1) return;n printf(“%dn”,a+b);n2/10/202258菜鳥之傷（菜鳥之傷（1313）n總結(jié)：題目描述是負(fù)數(shù)結(jié)束輸入，Sample Input最后給出的是-1，如果讀題不仔細(xì)，很容易陷入思維定勢(shì)，而會(huì)不加思索在程序中用-1判斷，這樣就真的會(huì)發(fā)生不幸的事件盡管我也認(rèn)為這個(gè)陷阱有點(diǎn)陰，而且未必有很大意義，但是題目并沒(méi)錯(cuò)，而你確實(shí)讀題

25、不仔細(xì)n說(shuō)明：算是經(jīng)典的小陷阱，現(xiàn)在很少出現(xiàn)了2/10/202259繼續(xù)以繼續(xù)以A AB B為例為例n題目描述：給定2個(gè)整數(shù)A和B，如果A+B0，請(qǐng)輸出”O(jiān)K!”，否則請(qǐng)輸出”No”nSample Inputn1 5n1 -5nSample OutputnOK!nNo2/10/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”); n2/10/202261菜鳥之傷（菜鳥之傷（14

26、14）n總結(jié)：字符串輸出的大小寫問(wèn)題對(duì)于菜鳥需要特別注意，其實(shí)，不管是全大寫、全小寫，還是首字母大寫，你盡管復(fù)制即可（沒(méi)有電子版，另當(dāng)別論），當(dāng)然還要注意是否有標(biāo)點(diǎn)符號(hào)等情況。n說(shuō)明：菜鳥常犯錯(cuò)誤，稍有經(jīng)驗(yàn)即可避免2/10/202262以以11701170Balloon Comes!為例為例nSample Inputn4n+ 1 2n- 1 2n* 1 2n/ 1 2nSample Outputn3n-1n2n0.502/10/202263菜鳥之傷（菜鳥之傷（1515）nint n,a,b,i;nchar p;nscanf(%d,&n);nfor (i=0;in;i+)nn scanf

27、(%c%d%d,&p,&a,&b);n if( ) n2/10/202264菜鳥之傷（菜鳥之傷（1515）n剛才程序的改進(jìn)版剛才程序的改進(jìn)版: :nint n,a,b,i;nchar p;nscanf(%d,&n);ngetchar();nfor (i=0;in;i+)nn scanf(%c%d%d,&p,&a,&b);n if( .) nn是否還有問(wèn)題？如何修改？是否還有問(wèn)題？如何修改？2/10/202265菜鳥之傷（菜鳥之傷（1515）n總結(jié)：字符和數(shù)字的混合輸入帶來(lái)的問(wèn)題，也是一個(gè)常常困擾使用C語(yǔ)言編程的同學(xué)的經(jīng)典問(wèn)題，關(guān)鍵就是程序

28、未能及時(shí)接收回車符，而誤將回車當(dāng)作下一組數(shù)據(jù)的首字母，你可以通過(guò)添加一句getchar(); 輕松解決該問(wèn)題。n說(shuō)明：菜鳥的經(jīng)典錯(cuò)誤，如果之前沒(méi)有遇到過(guò)，很難一下子反應(yīng)過(guò)來(lái)，當(dāng)然，遇到一次以后就不成為問(wèn)題了2/10/2022662007 2007 平方和與立方和平方和與立方和n給定一段連續(xù)的整數(shù)，求出他們中所有偶數(shù)的平方和以及所有奇數(shù)的立方和。nSample Inputn1 3n2 5nSample Outputn4 28n20 1522/10/202267菜鳥之傷（菜鳥之傷（1616）#includevoid main() int m,n; while(scanf(“%d%d” ,&

29、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”,y,x); 2/10/202268菜鳥之傷（菜鳥之傷（1616）n總結(jié)：題目并沒(méi)有保證數(shù)據(jù)是遞增的，但人往往有思維定勢(shì)，而很多題目的設(shè)計(jì)就是針對(duì)這一點(diǎn)！不要埋怨，這種訓(xùn)練能很好的培養(yǎng)我們審慎的思維習(xí)慣。n說(shuō)明：這種錯(cuò)誤經(jīng)歷過(guò)以后還是比較容易牢記的，所以說(shuō)有時(shí)候經(jīng)驗(yàn)很重要。2/10/202269菜鳥之傷（菜鳥之傷（1717）n以下的程序輸出什么？n#includen#includenint main()nn

30、int j=0;nfor(j=0;j5;j+)nncoutj=;nprintf(%dn,j);nnreturn 0;n2/10/202270菜鳥之傷（菜鳥之傷（1717）n 期望輸出：nj=0nj=1nj=2nj=3nj=4n 實(shí)際輸出：n?2/10/202271菜鳥之傷（菜鳥之傷（1717）n總結(jié)：在一個(gè)程序中同時(shí)使用C和C+的輸出語(yǔ)句，很容易帶來(lái)問(wèn)題，原因就是輸出機(jī)制不完全一樣（一個(gè)不帶緩沖，一個(gè)帶緩沖），所以盡量避免C和C+輸出語(yǔ)句混用。n說(shuō)明：這是傳說(shuō)中的經(jīng)典錯(cuò)誤，據(jù)說(shuō)曾困擾某牛人于現(xiàn)場(chǎng)賽 :-)2/10/202272以以2004 2004 成績(jī)轉(zhuǎn)換成績(jī)轉(zhuǎn)換 為例為例n題目描述：題目描

31、述：輸入一個(gè)百分制的成績(jī)t，將其轉(zhuǎn)換成對(duì)應(yīng)的等級(jí)，具體轉(zhuǎn)換規(guī)則如下： 90100為A; 8089為B; 7079為C; 6069為D; 059為E;n輸出描述：輸出描述：對(duì)于每組輸入數(shù)據(jù)，輸出一行。如果輸入數(shù)據(jù)不在0100范圍內(nèi)，請(qǐng)輸出一行：“Score is error!”。2/10/202273菜鳥之傷（菜鳥之傷（1818）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 cas

32、e 5:n case 4:printf(An); case 3:printf(Bn);n case 2:printf(Cn); case 1:printf(Dn);n default:printf(En); n n return 0;n 2/10/202274菜鳥之傷（菜鳥之傷（1818）n總結(jié)：C語(yǔ)言中的case語(yǔ)句要求在每個(gè)case的處理后面都要跟break；（特殊需求除外），而如果因?yàn)椴涣私饣蛘卟恍⌒亩鄙俨糠謆reak;則執(zhí)行的效果也許會(huì)不符合你最初的設(shè)計(jì)。n說(shuō)明：C語(yǔ)言的基本功很重要2/10/202275以以2046 2046 骨牌鋪方格骨牌鋪方格 為例為例n題目描述：題目描述：在2

33、n的一個(gè)長(zhǎng)方形方格中,用一個(gè)1 2的骨牌鋪滿方格,輸入n ,輸出鋪放方案的總數(shù).n輸入描述：輸入描述：輸入數(shù)據(jù)由多行組成，每行包含一個(gè)整數(shù)n,表示該測(cè)試實(shí)例的長(zhǎng)方形方格的規(guī)格是2n (0n=50)。2/10/202276菜鳥之傷（菜鳥之傷（1919）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 n2/10/202277菜鳥之傷（菜鳥之傷（1919）n總結(jié)：數(shù)組下標(biāo)越界是最常見(jiàn)

34、的Runtime Error，也是菜鳥常犯的錯(cuò)誤，除了需要扎實(shí)的C語(yǔ)言基本功，編程中的注意力集中也是需要的（很多時(shí)候不是不知道理論，而是不注意）n說(shuō)明：一般情況，你可以通過(guò)將數(shù)組開的大點(diǎn)而盡量避免這個(gè)問(wèn)題2/10/202278以以1425 Sort1425 Sort為例為例n題目描述：題目描述：給你n個(gè)整數(shù)，請(qǐng)按從大到小的順序輸出其中前m大的數(shù)。n輸入描述：輸入描述：每組測(cè)試數(shù)據(jù)有兩行，第一行有兩個(gè)數(shù)n,m(0n,m1000000)，第二行包含n個(gè)各不相同，且都處于區(qū)間-500000,500000的整數(shù)。2/10/202279菜鳥之傷（菜鳥之傷（2020）n#includenvoid main

35、()nn int n,m,i,num1000000;n while(scanf(“%d%d”,&n,&m)=2)n . n2/10/202280菜鳥之傷（菜鳥之傷（2020）n總結(jié)：ACM編程中，使用很大的數(shù)組是很常見(jiàn)的做法，但如果超大的數(shù)組被定義成局部變量，則很容易出現(xiàn)Runtime Error，解決辦法也很簡(jiǎn)單：定義成全局變量即可。原因是局部變量分配在棧（較?。?，全局變量分配在堆（較大）；n說(shuō)明：這里所說(shuō)的超大也不能無(wú)限制的大，可以根據(jù)題目的內(nèi)存限制進(jìn)行估算2/10/202281求求A A B Bn題目描述：給定2個(gè)整數(shù)A和B，請(qǐng)計(jì)算AB.nSample Inputn2 3n3 3nSample Outputn8n272/10/202282菜鳥之傷（菜鳥之傷（2 21 1）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)=2)nn printf(“%dn”,ab);n2/10/202283菜鳥之傷（菜鳥之傷（2 21 1）n總結(jié)：n不