資源描述：
《onlinejudge例題講解》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、OnlineJudge例題講解南開ACM協(xié)會(huì)http://acm.nankai.edu.cn1002:[NKPC1]Lucy的難題f(n)當(dāng)n>=50025002的時(shí)候，f(n)=n-5；當(dāng)n<50025002的時(shí)候，f(n)=f(f(n+2005))?，F(xiàn)在請(qǐng)您試試編程解決Lucy的難題！初步想法：intf(intn){if(n<50025002)returnf(f(n+2005)); returnn-5; }RuntimeError1002:[NKPC1]Lucy的難題錯(cuò)誤原因：遞歸層數(shù)太多，棧溢出簡(jiǎn)單的改進(jìn)----->遞歸化為循
2、環(huán)用m表示f的層數(shù)，f(m,n)表示參數(shù)n嵌套了m層f，例如f(3,n)=f(f(f(n))) f(1,n)=f(n) f(0,n)=nwhile(1==scanf("%d",&n)){m=1;while(m>0){if(n>=50025002){n=n-5;--m;}else{n+=2005;++m;}}printf("%d",n);}1002:[NKPC1]Lucy的難題進(jìn)一步改進(jìn)設(shè)k<50025002但k+2005>=50025002 f(1,k)=f(2,k+2005)=f(1,k+2000)也即f(k)=f(k+200
3、0)設(shè)k+2005*m<50025002但k+2005*(m+1)>=50025002時(shí)有f(1,k)=f(1,k+2000)1002:[NKPC1]Lucy的難題當(dāng)k+2005*(m+1)<50025002但k+2005*(m+2)>=50025002時(shí)f(1,k)=f(2,k+2005)=f(2,k+2005+2000*t) =f(1,k+2000*(t+1))進(jìn)一步可知f(k)=f(k+2000)仍然成立這樣得到一個(gè)簡(jiǎn)單的方法，如果n<50025002，將n累加2000，直到超過50025002即可，代碼略1263:粗心的物理
4、學(xué)家計(jì)算1+1/2+1/3+…+1/n其中n<=5*10^6輸入n輸出計(jì)算結(jié)果，保留12位小數(shù)doubles;//記錄最終計(jì)算結(jié)果inti,j;1263:粗心的物理學(xué)家while(scanf("%d",&j)==1){s=0;for(i=1;i<=j;++i)s+=1./i;printf("%.12lf",s);}WrongAnswer為什么？1263:粗心的物理學(xué)家精度問題利用C++計(jì)算1e10+1e-10并保留12位小數(shù)：printf(“%.12lf”,1e10+1e-10);結(jié)果為10000000000.0000000
5、00000原因是double本身精度有限如果將上述程序中的循環(huán)改為for(i=j;i>=1;--i)s+=1./i;則AC1023:A+B+C+D+...的挑戰(zhàn)輸入有多行數(shù)據(jù)，每行有若干整數(shù)，這些整數(shù)數(shù)以空格分割，請(qǐng)分別求出每行整數(shù)的和。SampleInput10020044545SampleOutput304901023:A+B+C+D+...的挑戰(zhàn)如果用普通的讀入方法讀入整數(shù)，則無法知道什么時(shí)候是一行的結(jié)束有很多處理方法，這里介紹用getchar()getchar()無參數(shù)，它讀入一個(gè)字符，可以是轉(zhuǎn)義字符，返回值為int型，表示
6、ASCII思考：getchar()返回值為什么不是char?1023:A+B+C+D+...的挑戰(zhàn)intsum,a;charch; //sum為結(jié)果，a為當(dāng)前數(shù)ch=getchar()反復(fù)讀入字符，有以下幾種情況1，ch>=‘0’&&ch<=‘9’，則a=a*10+ch-’0’;2，ch==‘’，一行讀入結(jié)束，則輸出sum3，ch==‘‘，當(dāng)前數(shù)讀入結(jié)束，sum+=a;a=01023:A+B+C+D+...的挑戰(zhàn)也可以利用cin.getline函數(shù)讀入一整行，包括空格，或者gets函數(shù)也可以得到相同效果讀入一整行之后，可以同樣采
7、取上述方法解題，但如果熟悉strtok函數(shù)的話實(shí)際上還有更好的做法，留作自學(xué)1046:正整數(shù)劃分問題將一個(gè)正整數(shù)n表示成一系列正整數(shù)的和，如：N=n1+n2+…+nk（其中n1≥n2≥…≥nk≥1，k≥1） 正整數(shù)n的一個(gè)這種表示成為正整數(shù)n的一個(gè)劃分。 現(xiàn)在給出一個(gè)正整數(shù)n（80≥n≥1），求n的不同劃分一共有多少種。1046:正整數(shù)劃分問題假設(shè)n已經(jīng)劃分出一個(gè)數(shù)字為n1，則n-n1的劃分成為一個(gè)子問題，因此可以考慮動(dòng)態(tài)規(guī)劃（DynamicProgramming=DP）但是n-n1的劃分必須滿足一個(gè)條件：劃分出的最大數(shù)字不超過n1
8、，因此我們可以設(shè)dp[i][j]表示將i進(jìn)行劃分，劃分出的最大數(shù)字不超過j的種類1046:正整數(shù)劃分問題初始值a[1][i]=1,a[i][1]=1(i>=1) a[0][i]=1(i>=0)思考這里為什么不設(shè)為=0遞推a[i][j]
