ACM程序设计-东北林业大学 acm05.pptVIP

ACM程序设计 东北林业大学 陈宇 Lg_chenyu@ 今天你AC 了吗？ 第6讲 DP入门 我校的ACM在线评测系统 课件下载地址： /kj/acm05.ppt 例1斐波那契数列 nefu 85 计算斐波那契数列的值！该数列为1 1 2 3 5 8 13 21 ......... 有多组数据，每组1行，用N表示，1 = N = 50。 输出Fibonacci(N)的值! 代码： int n; long long feibo[51]; feibo[1]=1; feibo[2]=1; for(int i=3;i=50;i++) feibo[i]=feibo[i-1]+feibo[i-2];//打表 while(cinn) coutfeibo[n]endl; 用递归能做吗？ long long data[51]; long long fblq(int n) { if (n==1||n==2) return 1; else { if (data[n]==0) data[n]=fblq(n-1)+fblq(n-2); //看看这个！ 只算1次！ return data[n]; } } 现在同学们在纸上计算下题： 计算N! input 有多组数据，每组一行，用N表示，0 = N = 20; output 输出N！ 递归的代码： #include cstdlib #include iostream using namespace std; long long data[21]; long long jc(int n) { if (n==0||n==1) return 1; if (data[n]==0) data[n]=n*jc(n-1); return data[n]; } 递推的代码： #include cstdlib #include iostream using namespace std; int main(int argc, char *argv[]) { int n; long long data[51]; memset(data,0,sizeof(data)); data[0]=1;data[1]=1; for(int i=2;i=20;i++) data[i]=i*data[i-1]; while(cinn) coutdata[n]endl; system(PAUSE); return EXIT_SUCCESS; } Nefu20 穿过街道 一个城市的街道布局如下:从最左下方走到最右上方,每次只能往上或往右走,一共有多少种走法? input 输入很多行行数,每行1个数字代表n的值,当n=0时结束(2=n=15) output 输出对应每行n值的走法. sample_input 1 2 10 5 0 sample_output 2 6 184756 252 递归的代码： int f[100][100]; int getf(int x,int y) { if (f[x][y]!=-1) return f[x][y]; int result; if (x==0||y==0) result=1; else result=getf(x-1,y)+getf(x,y-1); f[x][y]=result; return result; } Main() int main(int argc, char *argv[]) { int i,j,n; memset(f,-1,sizeof(f)); while(cinn) { if (n==0) break; coutgetf(n,n)endl; } system(PAUSE); return EXIT_SUCCESS; } 其实这题递推的代码更短： int n; long long data[21][21]; for(int i=0;i=20;i++) { data[i][0]=1;// 处理边界 data[0][i]=1;// 处理边界 } for(int j=1;j=20;j++) for(int k=1;k=20;k++)