研发埠

标题: [编程题] 一个recursion的问题 [打印本页]

作者: 苏晓晓 时间: 2013-8-16 10:07
标题: [编程题] 一个recursion的问题
要用recursion做，不能出现loop大意是这样一个数组a1 = 10 50 40 20 50 40 30统计另一个数组a2是否包含在a1中，a2在a1中可以不连续比如另一个数组a2 =10 20 40 则只有一种包含方式，返回1a2=50 40 30 则有3种包含方式返回3header是int countIncludes(const double a1[], int n1, const double a2[], int n2)我的想法是算出a2中每个数在a1中出现的次数c，然后c1*c2*c3...就能得出结果，可是由于a2的样子也不清楚，我就迷茫了...求各位帮忙...

作者: 王培培 时间: 2013-8-16 10:14
典型的DP問題，我把參數改成了int，思路是是一樣的。floatingpoint是不能用等號來比較是否相等的，有numericalprecision 的問題。int countIncludes( int a[], int n, int b[], intm){ if(m==0) return 1;// 或者 if(m<=0)，防止非法長度 if(n==0) return 0;// 或者 if(n<=0) //也可以加上if(m>n) return 0; 不加的話用下面的recursion也能得到正確答案 if(a[0]==b[0] ) returncountIncludes(a+1,n-1,b+1,m-1)+countIncludes(a+1,n-1,b,m); else returncountIncludes(a+1,n-1,b,m);}Time: O(nm)

欢迎光临研发埠 (http://bbs.yanfabu.com/)