首页 > 代码库 > Algorithms算法题<1.1>
Algorithms算法题<1.1>
1.1.27 二项分布。估计用一下代码计算binomial(100,50,0.25)将会产生的递归调用次数：
1 public static double binomial(int N,int k,double p){2 if(N==0 && k==0) return 1.0;3 if(N<0 || k<0) return 0.0;4 return (1.0-p)*binomial(N-1,k,p) + p*binomial(N-1,k-1,p);5 }
用这段代码来计算该二项分布的值是不现实的，因为这里是使用递归调用函数来实现的，在函数调用前，编译器要做很多准备工作，所以递归的层数较多时，程序运行速度会极慢，一种改善的方法是使用循环来代替递归。
这里使用了二项分布的一个推导公式：
N次试验发生K次的概率：P(N,K)=（1-p）f(N-1,k)+p* f(N-1,K-1）。
使用循环实现代码如下：
1 public class Test{ 2 /*使用一个二维数组来存放各项二项分布的概率 3 *行代表重复N次试验，列代表发生k次，所以在下面循环条件中需要 j<=i 4 */ 5 public static double[][] binomial(int N,int k,double p){ 6 double[][] array=new double[N+1][k+1]; 7 //给二维数组初始化第一列，避免下面执行时出现数组下标越界 8 array[0][0]=1.0; 9 for(int i=1;i<N+1;i++)10 array[i][0]=array[i-1][0]*(1-p);11 for(int i=1;i<N+1;i++)12 for(int j=1;j<=i && j<k+1;j++)13 array[i][j]=(1-p)*array[i-1][j] + p*array[i-1][j-1];14 return array;15 }16 public static void main(String[] args){17 double[][] array=binomial(100,50,0.25);18 System.out.println(array[100][50]);19 }20 }
运行结果：4.507310875086383E-8
虽然递归让一些代码看起来非常清晰，简洁。但，就效率上来讲，循环比递归快了很多倍，而且递归会带来程序调试上的问题，所以：慎用递归。
1.1.28 删除重复元素。修改BinarySearch类中的测试用例来删除排序后白名单中的所有重复元素。
这道题其实是不难的，简单来说就是如何删除数组中的重复元素，从而得到一个新的数组。可以先将数组转化为list，删除重复元素后再重新转化为数组。但本书到这里既然还没有介绍列表这种数据结构，那就仅用数组来实现吧。代码如下：
1 import java.util.Arrays; 2 public class Test{ 3 public static int[] func1(int[] a){ 4 Arrays.sort(a); 5 int length=1; 6 //获得移除重复元素后的数组长度 7 for(int i=1;i<a.length;i++){ 8 if(a[i]==a[i-1]) 9 continue;10 length++;11 }12 int[] b=new int[length];13 b[0]=a[0];14 //引入变量count记录重复元素的个数15 int count=0;16 for(int i=1;i<a.length;i++){17 if(a[i]==a[i-1]){18 count++;19 continue;20 }21 b[i-count]=a[i];22 }23 return b;24 }25 //在主函数中测试该方法26 public static void main(String[] args){27 int[] a={1,3,3,5,6,6,7,9,9,15};28 int[] b=func1(a);29 System.out.println("原数组："+Arrays.toString(a) );30 System.out.println("移除重复元素后的新数组："+Arrays.toString(b) );31 }32 }
运行结果为：
原数组：[1, 3, 3, 5, 6, 6, 7, 9, 9, 15]
移除重复元素后的新数组：[1, 3, 5, 6, 7, 9, 15]
实现起来还是挺麻烦的，所以遇到这种情况还是使用list吧。
Algorithms算法题<1.1>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。