歷年noip普及組c完善程序題總結(jié)歸納

1、完善程序題總結(jié)歸納By:( 6) yx一、【題目】 (哥德巴赫猜想)哥德巴赫猜想是指，任一大于2的偶數(shù)都可寫成兩個質(zhì)數(shù)之和。迄今為止，這仍然是一個著名的世界難題，被譽(yù)為數(shù)學(xué)王冠上的明珠。 試編寫程序,驗證任一大于2且不超過n的偶數(shù)都能寫成兩個質(zhì)數(shù)之和。#in cludeusing n amespace std;int mai n()const int SIZE=1000;int n ,r,pSIZE,i,j,k,a ns;bool tmp;cinn;r=1;p1=2;for(i=3;i=n ;i+) ;for(j=1;j=r;j+)if(i%=0)tmp=false;break;if(tmp)

2、r+;an s=0;for(i=2;i=n/2;i+)tmp=false;for(j=1;j=r;j+)for(k=j;k=r;k+)if(i+i=)tmp=true;break;if(tmp)ans+;couta nse ndl;return 0;若輸入n為2010，則輸出 時表示驗證成功，即大于 2且不超過2010的偶數(shù)都滿足哥德巴赫猜想。【算法】先for 一遍，找出質(zhì)數(shù)，然后對每一個偶數(shù)進(jìn)行一一匹配(2除外)，效率0(23)【代碼】1、tmp=1 ； 2、pj;3、pr=j;4、pj+pk5、1004【年份】2010年二、【題目】 (過河問題)在一個月黑風(fēng)高的夜晚，有一群人在河的右岸，想

3、通過唯一的 一根獨(dú)木橋走到河的左岸.在伸手不見五指的黑夜里，過橋時必須借照燈光來照明，不幸的是, 他們只有一盞燈.另外，獨(dú)木橋上最多能承受兩個人同時經(jīng)過，否則將會坍塌.每個人單獨(dú)過獨(dú)木橋都需要一定的時間，不同的人要的時間可能不同.兩個人一起過獨(dú)木橋時，由于只有一 盞燈，所以需要的時間是較慢的那個人單獨(dú)過橋所花費(fèi)的時間現(xiàn)在輸入 N(2=N1000)和這N個人單獨(dú)過橋需要的時間，請計算總共最少需要多少時間，他們才能全部到達(dá)河左岸例如，有3個人甲、乙、丙，他們單獨(dú)過橋的時間分別為 1、2、4,則總共最少需要的 時間為7.具體方法是：甲、乙一起過橋到河的左岸 ，甲單獨(dú)回到河的右岸將燈帶回 ，然后甲、

4、丙在一起過橋到河的左岸，總時間為2+1+4=7.#in clude#in cludeusing n amespace std;const int size=100;const int infinity = 10000;const bool left=1;const bool right =0;const bool left_to_right=1;const bool right_to_left=0;int n, hoursize;bool possize;int max(i nt a,i nt b)retur n ab?a:b;int go(bool stage)int i,j,num,tmp

5、,ans;if(stage=right_to_left)num=0;an s=0;for(i=1;ia ns)an s=houri;if()return ans;ans=infini ty;for(i=1;i=n _1;i+)if(posi=right)for(j=i+1;j=n ;j+)if(posj=right)posi=left;posj=left;tmp=max(houri,hourj)+if(tmpa ns) an s=tmp;posi=right;posj=right;return ans;if(stage=left_to_right)ans=infini ty;for(i=1;i

6、=n ;i+)if()posi=right;tmp=;if(tmpa ns)an s=tmp; ;return ans;return 0;int mai n()int i;cinn;for(i=1;i houri;posi=right;coutgoright_to_left)e ndl;return 0;【算法】利用深搜，左右交替尋找最優(yōu)解（maybe是動態(tài)規(guī)劃）【代碼】1、num=2;2、go1;3、posj=1;4、houri+go0;5、posi=1;【年份】2010年三、【題目】（子矩陣）給輸入一個n 1*m1的矩陣a，和n2*m2的矩陣b，問a中是否存在子矩陣和 bThere isn

7、o an swer相等。若存在，輸出所有子矩陣左上角的坐標(biāo)：若不存在輸出#in clude using n amespace std;const int SIZE = 50;int n1,m1, n2,m2,aSIZESIZE,bSIZESIZE;int mai n()int i,j,k1,k2;bool good,haveA ns;cinn 1m1;for(i=1;i=n 1;i+)for(j=1;jaij;cinn 2m2;for(i=1;i=n 2;i+)for(j=1;j=m2;j+) ;haveA ns=false;for(i=1;i=n1-n 2+1;i+)for(j=1;j=;j

8、+) ;for(k1=1;k1=n2;k1+)for(k2=1;k2=;k2+)if(ai+k1-1j+k2-1!=bk1k2)good=false;if(good)couti je ndl; ;if(!haveA ns)coutThere is no an swerbij;2、m1-m2+1; 3、good=1;4、m2;5、haveAns=1;【年份】2011年四、【題目】(大整數(shù)開方) 輸入一個正整數(shù) n (1 nw 100),試用二分法計算它的平方根的整數(shù)部分。#in clude#in cludeusing n amespace std;con st int SIZE=200;stru

9、ct huge intint len,nu mSIZE;/其中l(wèi)en表示大整數(shù)的位數(shù)；num1表示個位，num2表示十位，以此類推huge int times(huge int a,huge int b)/計算大整數(shù)a和b的乘積int i,j;huge int ans;memset(a ns.nu m,0,sizeof(a ns. nu m);for(i=1;i=aen ;i+)for(j=1;j=ben ;j+)+=a. numi*b. nu mj;for(i=1;i0) ans.len=a.len+b.len;elsean s.le n=a.le n+b.le n-1;return ans

10、;huge int add(huge int a,huge int b)/計算大整數(shù)a和b的和int i;huge int ans;memset(a ns.nu m,0,sizeof(a ns. nu m);if(a.lenb.len)ans.len=a.len;elseans.len=b.len;for(i=1;i0)ans.len+;return ans;huge int average(huge int a,huge int b)/計算大整數(shù)a和b的平均數(shù)的整數(shù)部分int i;huge int ans;an s=add(a,b);for(i=a nsen ;i=2;i_)ans.n um

11、i-1+=()*10;ans.nu mi/=2;ans.nu m1/=2;if(ans.nu ma ns.le n=0)ans.len-;return ans;huge int plustwo(huge int a)/計算大整數(shù)a加2之后的結(jié)果int i;huge int ans;an s=a;ans.nu m1+=2;i=1;while( (i=10)ans.nu mi+1+=a ns.nu mi/10;ans.nu mi%=10;i+；if(ans.nu ma ns.len+10) ；return ans;bool over(huge int a,huge int b)/ 若大整數(shù)ab則返

12、回true ，否則返回false int i;if()return false;if( a.lenb.len )return true;for(i=a.le n; i=1;i_)if(a. nu mib. nu mi)return true;return false;int mai n()stri ng s;int i;huge int target,left,middle,right;cin s;memset(target .num ,0,sizeof(target. nu m);target.le n=s.len gth();for(i=1;i=1;i-)coutleft.numi;ret

13、urn 0;【算法】每二分一次，就判斷一下答案在哪個區(qū)間，然后在 那個區(qū)間繼續(xù)二分，避免不必要的計算?！敬a】 1、 ans.numi+j-12、ans.numi%=103、a.numi+b.numi4、ans.numi % 25、ans.len+6、a.lenb.len7、08、times(middle,middle),target【年份】 2011 年五、【題目】 (坐標(biāo)統(tǒng)計)輸入 n 個整點在平面上的坐標(biāo)。對于每個點，可以控制所 有位于它左下方的點(即 x 、y 坐標(biāo)都比它小)，它可以控制的點的數(shù)目稱為“戰(zhàn)斗力”。 依次輸出每個點的戰(zhàn)斗力， 最后輸出戰(zhàn)斗力最高的點的編號 (如果若干個點的

14、戰(zhàn)斗力并列最 高，輸出其中最大的編號)。#include using namespace std;const int SIZE =100;int xSIZE,ySIZE,fSIZE;int n,i,j,max_f,ans;int main()cinn;for(i=1;i xiyi; max_f=O;for(i=1;i=n ;i+)fi=；for(j=1;j=n ;j+)if(xjxi &) ；if()max_f=fi;；for(i=1;i=n ;i+) coutfie ndl; couta nse ndl;return 0;【算法】依次進(jìn)行戰(zhàn)斗力的計算，找出最大的一個【代碼】1、0 2、yjm

15、ax_f )4、 （ i1）& （fifi-1）（我寫的是5、ans=max_f （我寫的是 ans=i）其實我做的是對的，正確答案有bug;【年份】2012年六、【題目】（排列數(shù)）輸入兩個正整數(shù)n, m（ 1*20,1mn），在1n中任取m個數(shù)，按字典序從小到大輸出所有這樣的排列。例如:輸入：3 2輸出：1 22 33 13 2#in elude #in elude using n amespaee std;const int SIZE =25;bool usedSIZE;int dataSIZE;int n,m,i,j,k;bool flag;int mai n()cinnm;memset

16、(used,false,sizeof(used); for(i=1;i=m;i+)datai=i;usedi=true;flag=true;while(flag)for(i=1;i=m-1;i+) coutdatai; coutdatam=1;i-)；for(j=datai+1;j=n ;j+) if(!usedj)usedj=true;datai=；flag=true;break;if(flag)for(k=i+1;k=m;k+) for(j=1;j=；j+)if(!usedj)datak=j;usedj=true; break;；return 0;【算法】直接進(jìn)行枚舉，一個個進(jìn)行選擇【代碼

17、】1、02、useddatai=03、j4、n5、break【年份】2012年七、【題目】（二叉查找樹）二叉查找樹具有如下性質(zhì)：每個節(jié)點的值都大于其左子樹上所有節(jié)點的值、小于其右子樹上所有節(jié)點的值。試判斷一棵樹是否為二叉查找樹。輸入的第一行包含一個整數(shù)n,表示這棵樹有n個頂點，編號分別為1,2, -n,其中編號為1的為根結(jié)點。之后的第i行有三個數(shù)value, left_child , right_child，分別表示該節(jié)點關(guān)鍵字的值、 左子節(jié)點的編號、右子節(jié)點的編號；如果不存在左子節(jié)點或右子節(jié)點，則用0代替。輸出1表示這棵樹是二叉查找樹，輸出0則表示不是。#in clude using n a

18、mespace std;con st int SIZE = 100;con st in tINFINITE = 1000000;struct node in t left_child, right_child, value;node aSIZE;int is_bst(int root, int lower_bound, int upper_bound)int cur;if (root = 0) return 1; cur = aroot.value;if (cur lower_bound) & (1) ) &/( 3分)(is_bst(aroot.left_child, lower_bound

19、, cur) = 1) & (is_bst(2) ,(3) ,(4) ) = 1)/ (3分， 3分， 3分) return 1;return 0;int main()int i, n;cinn;2分）for (i = 1; i ai.valueai.left_childai.right_child; coutis_bst(5) , -INFINITE, INFINITE)endl;/ return 0;【算法】 就是遍歷一遍?！敬a】 1、 j-i ；2、 cur1 ； 3、 count1-;4 、count2-;5 cur1=aj ；年份】 2013 年八、【題目】（數(shù)字刪除 ）下面程序的

20、功能是將字符串中的數(shù)字字符刪除后輸出。請?zhí)羁?。（每?3 分，共12 分 ）#include using namespace std;int delnum(char *s)int i, j;j = 0;for(i = 0; si != 0; i+)if(si 9) sj = si; 2 ;return 3 ;const int SIZE = 30;int main()char sSIZE;int len, i;cin.getline(s, sizeof(s);len = delnum(s);for(i = 0; i len; i+)cout 4) ;cout endl;return 0;【算法

21、】搜索一遍，把非字母的字符保留【代碼】1、| 2 、j+ ； 3 、j 4 、si【年份】 2014 年九、【題目】（最大子矩陣和）給出m行n列的整數(shù)矩陣，求最大的子矩陣和 （子矩陣不能為空）。輸入第一行包含兩個整數(shù) m和n,即矩陣的行數(shù)和列數(shù)。之后 m行，每行n個整數(shù)，描述整 個矩陣。程序最終輸出最大的子矩陣和。 （ 最后一空 4 分，其余 3 分，共 16分） 比如在如下這個矩陣中：4 40 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2擁有最大和的子矩陣為：9 2-4 1-1 8其和為 153 3-2 10 20-1 100 -20 -2 -3最大子矩陣和為 1284

22、 40 -2 -9 -9-9 11 5 7-4 -3 -7 -6-1 7 7 5最大子矩陣和為 26#include using namespace std;const int SIZE = 100;int matrixSIZE + 1SIZE + 1;記錄第 i 行前 j 個數(shù)的和int rowsumSIZE + 1SIZE + 1; /rowsumij int m, n, i, j, first, last, area, ans;int main()cin m n; for(i = 1; i = m; i+)for(j = 1; j matrixij;ans = matrix 1for(i

23、 = 1; i = m; i +) 2 ; for(i = 1; i = m; i+)for(j = 1; j = n; j+)rowsumij = 3for(first = 1; first = n; first+)for(last = first; last = n; last+) 4for(i = 1; i ans) ans = area;if(area 0)area = 0;cout ans endl;return 0;算法】三個 for ，枚舉子矩陣左上，右上和高。遇到目前最大值就記錄下來。 【代碼】 1、 11 【 3】【 4】、【 4】 2、 rowsumi0 = 0（其實可以隨

24、便填，比如【 2】【 3】、【 6 】都可以）3、 rowsumij - 1 + matrixij； 4、 area = 0 ；5、rowsumilast - rowsumifirst - 1【年份】 2014十、【題目】 （打印月歷）輸入月份m（iw me 12），按一定格式打印2015年第m月的月 歷。 （第三、四空 2.5分，其余 3分）例如， 2015年1月的月歷打印效果如下 （第一列為周日 ）：S M T W T F S1 2 34 5 6 7 8 9 1011 12 13 14 15 16 1718 19 20 21 22 23 2425 26 27 28 29 30 31#include #include using namespace std;const int dayNum = -1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30