OnlineJudge例题讲解.ppt

Online Judge例题讲解,南开ACM协会 ,1002: NKPC1Lucy的难题,f(n) 当 n=50025002 的时候，f(n)=n-5；当 n50025002 的时候，f(n)=f(f(n+2005)。现在请您试试编程解决Lucy的难题！ 初步想法： int f(int n) if(n50025002) return f(f(n+2005); return n-5; ,Runtime Error,1002: NKPC1Lucy的难题,错误原因：递归层数太多，栈溢出 简单的改进 - 递归化为循环 用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“, ,1002: NKPC1Lucy的难题,进一步改进 设k=50025002 f(1,k)=f(2,k+2005)=f(1,k+2000) 也即f(k)=f(k+2000) 设k+2005*m=50025002时有 f(1,k) =f(1,k+2000),1002: NKPC1Lucy的难题,当k+2005*(m+1)=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)仍然成立 这样得到一个简单的方法，如果n50025002，将n累加2000，直到超过50025002即可，代码略,1263: 粗心的物理学家,计算1+1/2+1/3+1/n 其中n=5*106 输入n 输出计算结果，保留12位小数 double s;/记录最终计算结果 int i,j;,1263: 粗心的物理学家,while(scanf(“%d“, ,Wrong Answer,为什么？,1263: 粗心的物理学家,精度问题 利用C+计算1e10+1e-10并保留12位小数：printf(“%.12lfn”,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 a=0,1023: A+B+C+D+. 的挑战,也可以利用cin.getline函数读入一整行，包括空格，或者gets函数也可以得到相同效果 读入一整行之后，可以同样采取上述方法解题，但如果熟悉strtok函数的话实际上还有更好的做法，留作自学,1046: 正整数划分问题,将一个正整数n表示成一系列正整数的和，如： N=n1+n2+nk （其中n1n2nk1， k1） 正整数n的一个这种表示成为正整数n的一个划分。 现在给出一个正整数n（80n1），求n的不同划分一共有多少种。,1046: 正整数划分问题,假设n已经划分出一个数字为n1，则n-n1的划分成为一个子问题，因此可以考虑动态规划（Dynamic Programming = DP） 但是n-n1的划分必须满足一个条件：划分出的最大数字不超过n1，因此我们可以设dpij表示将i进行划分，划分出的最大数字不超过j的种类,1046: 正整数划分问题,初始值 a1i=1,ai1=1(i=1) a0i=1(i=0) 思考这里为什么不设为=0 递推 aij=sumai-kk /ji 输出ann即可,a00=1; for(i=1;iN;+i) ai1=a1i=a0i=1; for(i=2;iN;+i) for(j=2;j=i;+j) for(k=1;k=i ,Other Problems,互动 请说出你在Online Judge上面感兴趣的题目一起讨论,welcome to NKOJ,进入Ranklist Top 20 并不困难 每天来到NKOJ，体会AC的乐趣 AC=Accepted WA（哇）=Wrong Answer TLE=Time Limit Exceeded,NKPC介绍,也即南开大学程序设计竞赛我为程序狂 每年四月举行，已举办三届 中英文两版试题，英文试题早公布 10道题目，10-14天时间，将代码提交到指定地址，不看代码内容，只根据测试数据打分，每个数据9分，10组全对另加10分 颁发奖状、奖品 计划下一届公开征题，针对低年级单独评奖,有奖解题,准备近期办一次有奖解题 低年级单独评奖，奖品以算法相关书籍为主 1-2题，难度不大