资源描述：
《onlinejudge例题讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、OnlineJudge例题讲解南开ACM协会http://acm.nankai.edu.cn1002:[NKPC1]Lucy的难题f(n)当n>=50025002的时候，f(n)=n-5；当n<50025002的时候，f(n)=f(f(n+2005))。现在请您试试编程解决Lucy的难题！初步想法：intf(intn){if(n<50025002)returnf(f(n+2005)); returnn-5; }RuntimeError1002:[NKPC1]Lucy的难题错误原因：递归层数太多，栈溢出简单的改进----->递归化为循
2、环用m表示f的层数，f(m,n)表示参数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的难题进一步改进设k<50025002但k+2005>=50025002 f(1,k)=f(2,k+2005)=f(1,k+2000)也即f(k)=f(k+200
3、0)设k+2005*m<50025002但k+2005*(m+1)>=50025002时有f(1,k)=f(1,k+2000)1002:[NKPC1]Lucy的难题当k+2005*(m+1)<50025002但k+2005*(m+2)>=50025002时f(1,k)=f(2,k+2005)=f(2,k+2005+2000*t) =f(1,k+2000*(t+1))进一步可知f(k)=f(k+2000)仍然成立这样得到一个简单的方法，如果n<50025002，将n累加2000，直到超过50025002即可，代码略1263:粗心的物理
4、学家计算1+1/2+1/3+…+1/n其中n<=5*10^6输入n输出计算结果，保留12位小数doubles;//记录最终计算结果inti,j;1263:粗心的物理学家while(scanf("%d",&j)==1){s=0;for(i=1;i<=j;++i)s+=1./i;printf("%.12lf",s);}WrongAnswer为什么？1263:粗心的物理学家精度问题利用C++计算1e10+1e-10并保留12位小数：printf(“%.12lf”,1e10+1e-10);结果为10000000000.0000000
5、00000原因是double本身精度有限如果将上述程序中的循环改为for(i=j;i>=1;--i)s+=1./i;则AC1023:A+B+C+D+...的挑战输入有多行数据，每行有若干整数，这些整数数以空格分割，请分别求出每行整数的和。SampleInput10020044545SampleOutput304901023:A+B+C+D+...的挑战如果用普通的读入方法读入整数，则无法知道什么时候是一行的结束有很多处理方法，这里介绍用getchar()getchar()无参数，它读入一个字符，可以是转义字符，返回值为int型，表示
6、ASCII思考：getchar()返回值为什么不是char?1023:A+B+C+D+...的挑战intsum,a;charch; //sum为结果，a为当前数ch=getchar()反复读入字符，有以下几种情况1，ch>=‘0’&&ch<=‘9’，则a=a*10+ch-’0’;2，ch==‘’，一行读入结束，则输出sum3，ch==‘‘，当前数读入结束，sum+=a;a=01023:A+B+C+D+...的挑战也可以利用cin.getline函数读入一整行，包括空格，或者gets函数也可以得到相同效果读入一整行之后，可以同样采
7、取上述方法解题，但如果熟悉strtok函数的话实际上还有更好的做法，留作自学1046:正整数划分问题将一个正整数n表示成一系列正整数的和，如：N=n1+n2+…+nk（其中n1≥n2≥…≥nk≥1，k≥1） 正整数n的一个这种表示成为正整数n的一个划分。 现在给出一个正整数n（80≥n≥1），求n的不同划分一共有多少种。1046:正整数划分问题假设n已经划分出一个数字为n1，则n-n1的划分成为一个子问题，因此可以考虑动态规划（DynamicProgramming=DP）但是n-n1的划分必须满足一个条件：划分出的最大数字不超过n1
8、，因此我们可以设dp[i][j]表示将i进行划分，划分出的最大数字不超过j的种类1046:正整数划分问题初始值a[1][i]=1,a[i][1]=1(i>=1) a[0][i]=1(i>=0)思考这里为什么不设为=0递推a[i][j]
