歷年noip普及組(c)完善程序題總結(jié)歸納(已修改)
2025-04-05 23:22 本頁面
【正文】 完善程序題總結(jié)歸納 By：七（6） yx一、【題目】（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶數(shù)都可寫成兩個質(zhì)數(shù)之和。迄今為止，這仍然是一個著名的世界難題，被譽為數(shù)學(xué)王冠上的明珠。試編寫程序，驗證任一大于2且不超過n的偶數(shù)都能寫成兩個質(zhì)數(shù)之和。includeiostreamusing namespace std。int main(){ const int SIZE=1000。 int n,r,p[SIZE],i,j,k,ans。 bool tmp。 cinn。 r=1。 p[1]=2。 for(i=3。i=n。i++) { ① 。 for(j=1。j=r。j++) if(i% ② ==0) { tmp=false。 break。 } if(tmp) { r++。 ③ 。 } } ans=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++。 } coutansendl。 return 0。}若輸入n為2010，則輸出 ⑤ 時表示驗證成功，即大于2且不超過2010的偶數(shù)都滿足哥德巴赫猜想?！舅惴ā肯萬or一遍，找出質(zhì)數(shù)，然后對每一個偶數(shù)進行一一匹配（2除外），效率O（n^3）【代碼】tmp=1；p[j]。p[r]=j。p[j]+p[k]1004【年份】2010年二、【題目】(過河問題) 在一個月黑風(fēng)高的夜晚,有一群人在河的右岸,過橋時必須借照燈光來照明,不幸的是,獨木橋上最多能承受兩個人同時經(jīng)過,由于只有一盞燈,(2=N1000)和這N個人單獨過橋需要的時間,請計算總共最少需要多少時間,他們才能全部到達河左岸. 例如,有3個人甲、乙、丙,他們單獨過橋的時間分別為4,:甲、乙一起過橋到河的左岸,甲單獨回到河的右岸將燈帶回,然后甲、丙在一起過橋到河的左岸,總時間為2+1+4=7.includeiostreamincludecstringusing namespace 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,hour[size]。bool pos[size]。int max(int a,int b){return ab?a:b。}int go(bool stage){ int i,j,num,tmp,ans。 if(stage==right_to_left) { num=0。 ans=0。 for(i=1。i=n。i++) if(pos[i]==right) { num++。 if( hour[i]ans) ans=hour[i]。 } if( ① ) return ans。 ans=infinity。 for(i=1。i=n1。i++) if(pos[i]==right) for(j=i+1。j=n。j++) if(pos[j]==right) { pos[i]=left。 pos[j]=left。 tmp=max(hour[i],hour[j])+ ② 。 if(tmpans) ans=tmp。 pos[i]=right。 pos[j]=right。 } return ans。 } if(stage==left_to_right) { ans=infinity。 for(i=
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1