ACM 例题讲解.ppt

Online Judge例题讲解 南开ACM协会 ?1002: [NKPC1]Lucy的难题 f(n) 当 n的时候，f(n)=n-5；当 的时候，f(n)=f(f(n+2005))。现在请您试试编程解决Lucy的难题！ 初步想法：int f(int n){ if( return f(f(n+2005)); return n-5;} ?1002: [NKPC1]Lucy的难题 错误原因：递归层数太多，栈溢出 简单的改进 ----- 递归化为循环 用m表示f的层数，f(m,n)表示参数n嵌套了m层f，例如f(3,n)=f(f(f(n)))f(1,n)=f(n)f(0,n)=n while(1==scanf(%d,n)){ m=1; while(m0){ if(n{ n=n-5;--m; } else{ n+=2005; ++m; } } printf(%d\n,n); } ?1002: [NKPC1]Lucy的难题 进一步改进 设k+2005f(1,k)=f(2,k+2005)=f(1,k+2000)也即f(k)=f(k+2000) 设k+2005*k+2005*(m+1)有f(1,k) =f(1,k+2000) ?1002: [NKPC1]Lucy的难题 当k+2005*(m+1k+2005*(m+2)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累加2000，直到超可，代码略 1263: 粗心的物理学家 计算1+1/2+1/3+…+1/n其中n=5*10^6输入n输出计算结果，保留12位小数 double s;//记录最终计算结果int i,j; 1263: 粗心的物理学家 while(scanf(%d,j)==1){ s=0; for(i=1;i=j;++i) s+=1./i; printf(%.12lf\n,s); } 为什么？ 1263: 粗心的物理学家 精度问题 利用C++计算1e10+1e-10并保留12位小数：printf(“%.12lf\n”,1e10+1e-10);结果为10000000000.000000000000 原因是double本身精度有限 如果将上述程序中的循环改为for(i=j;i=1;--i) s+=1./i; 则AC 1023: A+B+C+D+... 的挑战 输入有多行数据，每行有若干整数，这些整数数以空格分割，请分别求出每行整数的和。 Sample Input 100 200 4 45 45 Sample Output 304 90 1023: A+B+C+D+... 的挑战 如果用普通的读入方法读入整数，则无法知道什么时候是一行的结束 有很多处理方法，这里介绍用getchar() getchar()无参数，它读入一个字符，可以是转义字符，返回值为int型，表示ASCII 思考：getchar()返回值为什么不是char? 1023: A+B+C+D+... 的挑战 int sum,a; char ch;//sum为结果，a为当前数 ch=getchar()反复读入字符，有以下几种情况 1，ch=‘0’ ch=‘9’，则a=a*10+ch-’0’; 2，ch==‘\n’，一行读入结束，则输出sum 3，ch==‘ ‘，当前数读入结束，sum+=a;a=0 1023: A+B+C+D+... 的挑战 也可以利用cin.getline函数读入一整行，包括空格，或者gets函数也可以得到相同效果 读入一整行之后，可以同样采取上述方法解题，但如果熟悉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的划分成为一个子问题，因此可以考虑动态规划（Dynamic Programming = DP） 但是n-n1的划分必须满足一个条件：划分出的最大数字不超过n1，因此我们可以设dp[i][