Java编程二项分布的递归和非递归实现代码实例

本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下。

问题来源:

算法第四版 第1.1节 习题27:return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
计算递归调用次数,这里的递归式是怎么来的?

二项分布:

定义:n个独立的是/非试验中成功次数k的离散概率分布,每次实验成功的概率为p,记作B(n,p,k)。

概率公式:P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k)

其中C(n, k) = (n-k) !/(k! * (n-k)!),记作ξ~B(n,p),期望:Eξ=np,方差:Dξ=npq,其中q=1-p。

概率统计里有一条递归公式:

这个便是题目中递归式的来源。

该递推公式来自:C(n,k)=C(n-1,k)+C(n-1,k-1)。实际场景是从n个人选k个,有多少种组合?将着n个人按1~n的顺序排好,假设第k个人没被选中,则需要从剩下的n-1个人中选k个;第k个选中了,则需要从剩下的n-1个人中选k-1个。

书中二项分布的递归实现:

public static double binomial(int N, int k, double p) {
    COUNT++; //记录递归调用次数
    if (N == 0 && k == 0) {
      return 1.0;
    }
    if (N < 0 || k < 0) {
      return 0.0;
    }
    return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
  } 

实验结果:

n   k   p   调用次数
10  5  0.25  2467
20  10  0.25  2435538
30  15  0.25  2440764535 

由结果可以看出来这个递归方法需要调用的次数呈几何灾难,n到50就算不下去了。

改进的二项分布递归实现:

private static long COUNT = 0;
  private static double[][] M; 

  private static double binomial(int N, int k, double p) {
    COUNT++;
    if (N == 0 && k == 0) {
      return 1.0;
    }
    if (N < 0 || k < 0) {
      return 0.0;
    }
    if (M[N][k] == -1) { //将计算结果存起来,已经计算过的直接拿过来用,无需再递归计算
      M[N][k] = (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
    }
    return M[N][k];
  } 

  public static double Binomial(int N, int k, double p) {
    M = new double[N + 1][k + 1];
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= k; j++) {
        M[i][j] = -1;
      }
    }
    return binomial(N, k, p);
  } 

实验结果:

n    k   p   调用次数
10    5  0.25  101
20   10  0.25  452
30   15  0.25  1203
50   25  0.25  3204
100  50  0.25  5205

由实验结果可以看出调用次数大幅减小,算法可以使用。

二项分布的非递归实现:

事实上,不利用递归,直接计算组合数和阶乘,反而速度更快。

//计算组合数
public static double combination(double N, double k)
{
  double min = k;
  double max = N-k;
  double t = 0; 

  double NN=1;
  double kk=1; 

  if(min>max){
    t=min;
    min = max;
    max=t;
  } 

  while(N>max){//分母中较大的那部分阶乘约分不用计算
    NN=NN*N;
    N--;
  } 

  while(min>0){//计算较小那部分的阶乘
    kk=kk*min;
    min--;
  } 

  return NN/kk;
} 

//计算二项分布值
public static double binomial(int N,int k,double p)
{
  double a=1;
  double b=1; 

  double c =combination(N,k); 

  while((N-k)>0){ //计算(1-p)的(N-k)次方
    a=a*(1-p);
    N--;
  } 

  while(k>0){ //计算p的k次方
    b=b*p;
    k--;
  } 

  return c*a*b;
} 

实验结果:

n   k  p      二项分布值
10,  5, 0.25  0.058399200439453125
20, 10, 0.25 0.009922275279677706
50, 25, 0.25  8.44919466990397E-5  

与前面的算法比对,计算结果是正确的,而且运行速度是非常之快的。

总结

以上就是本文关于Java编程二项分布的递归和非递归实现代码实例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

您可能感兴趣的文章:

  • Java8使用lambda实现Java的尾递归
  • Java编程获取文件列表及子文件目录的方法(非递归)
  • java编程之递归算法总结
  • Java基于递归解决全排列问题算法示例
  • Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】
  • Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例
  • java递归算法实例分析
  • Java递归算法遍历部门代码示例
(0)

相关推荐

  • Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】

    本文实例讲述了Java基于栈方式解决汉诺塔问题.分享给大家供大家参考,具体如下: /** * 栈方式非递归汉诺塔 * @author zy * */ public class StackHanoi { /** * @param args */ public static void main(String[] args) { System.out.println("我们测试结果:"); System.out.println("递归方式:"); hanoiNormal(

  • Java基于递归解决全排列问题算法示例

    本文实例讲述了Java基于递归解决全排列问题算法.分享给大家供大家参考,具体如下: 排列问题 设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}.集合x中元素的全排列记为Perm(X).(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列.R的全排列可归纳如下: 当n=1时,Perm(R)=(r),其中r是集合中唯一的元素: 当n>1时,Perm(R)由(r1)Perm(R1),(r2)Perm(R2),(r3)Perm(R3)....(

  • Java编程获取文件列表及子文件目录的方法(非递归)

    废话不谈,直接进入正题,理解见代码注释. // 非递归 public List<String> scanFiles(String path) { List<String>filePaths = new ArrayList<String>(); LinkedList<File> list = new LinkedList<File>(); File dir = new File(path); File[] file = dir.listFiles(

  • java递归算法实例分析

    递归算法设计的基本思想是: 对于一个复杂的问题,把原问题分解为若干个相对简单类同的子问题,继续下去直到子问题简单到能够直接求解,也就是说到了递推的出口,这样原问题就有递推得解. 在做递归算法的时候,一定要把握住出口,也就是做递归算法必须要有一个明确的递归结束条件.这一点是非常重要的.其实这个出口是非常好理解的,就是一个条件,当满足了这个条件的时候我们就不再递归了. 关键要抓住的是: (1)递归出口 (2)地推逐步向出口逼近 递归就是方法自身调用自身的行为,注意要写好递归头,也就是什么时候退出递归

  • java编程之递归算法总结

    1.何为递归 个人理解就是自己调用自己,直到满足一个条件结束自己调用自己的过程,这个就是递归.举一个通俗的点的例子: 假设你在一个电影院,你想知道自己坐在哪一排,但是前面人很多,你懒得去数了,于是你问前一排的人「你坐在哪一排?」,这样前面的人 (代号 A) 回答你以后,你就知道自己在哪一排了--只要把 A 的答案加一,就是自己所在的排了,不料 A 比你还懒,他也不想数,于是他也问他前面的人 B「你坐在哪一排?」,这样 A 可以用和你一模一样的步骤知道自己所在的排.然后 B 也如法炮制,直到他们这

  • Java8使用lambda实现Java的尾递归

    前言 本篇介绍的不是什么新知识,而是对前面讲解的一些知识的综合运用.众所周知,递归是解决复杂问题的一个很有效的方式,也是函数式语言的核心,在一些函数式语言中,是没有迭代与while这种概念的,因为此类的循环通通可以用递归来实现,这类语言的编译器都对递归的尾递归形式进行了优化,而Java的编译器并没有这样的优化,本篇就要完成这样一个对于尾递归的优化. 什么是尾递归 本篇将使用递归中最简单的阶乘计算来作为例子 递归实现 /** * 阶乘计算 -- 递归解决 * * @param number 当前阶

  • Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例

    本文实例讲述了Java基于递归和循环两种方式实现未知维度集合的笛卡尔积.分享给大家供大家参考,具体如下: 什么是笛卡尔积? 在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员. 假设集合A={a,b},集合B={0,1,2},则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}. 如何用程序算法实现笛卡尔积? 如果编程前已知集合的数量

  • Java递归算法遍历部门代码示例

    递归是一个非常有用的知识点.写点实例帮助自己记忆 中间有过程代码 首先一个javapojo类 package com.qcf.po; import java.util.HashSet; import java.util.Set; public class Depart { private long id; private String name; private String destion; //用户 Set<User> users=new HashSet<User>(); //

  • Java编程二项分布的递归和非递归实现代码实例

    本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下. 问题来源: 算法第四版 第1.1节 习题27:return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p); 计算递归调用次数,这里的递归式是怎么来的? 二项分布: 定义:n个独立的是/非试验中成功次数k的离散概率分布,每次实验成功的概率为p,记作B(n,p,k). 概率公式:P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k

  • JAVA递归与非递归实现斐波那契数列

    斐波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci[1] )以兔子繁殖为例子而引入,故又称为"兔子数列",指的是这样一个数列:0.1.1.2.3.5.8.13.21.34.--在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起

  • java递归与非递归实现扫描文件夹下所有文件

    java扫描指定文件夹下面的所有文件,供大家参考,具体内容如下 扫描一个文件夹下面的所有文件,因为文件夹的层数没有限制可能多达几十层几百层,通常会采用两种方式来遍历指定文件夹下面的所有文件. 递归方式 非递归方式(采用队列或者栈实现) 下面我就给出两种方式的实现代码,包括了递归与非递归实现,code如下所示. java代码: package q.test.filescanner; import java.io.File; import java.util.ArrayList; import ja

  • Java排序算法三之归并排序的递归与非递归的实现示例解析

    归并有递归和非递归两种. 归并的思想是: 1.将原数组首先进行两个元素为一组的排序,然后合并为四个一组,八个一组,直至合并整个数组: 2.合并两个子数组的时候,需要借助一个临时数组,用来存放当前的归并后的两个数组: 3.将临时数组复制回原数组对应的位置. 非递归的代码如下: package mergesort; import java.util.Arrays; import java.util.Random; import java.util.Scanner; //归并排序的非递归算法 publ

  • Java二叉树的四种遍历(递归和非递归)

    二叉树的遍历可以分为前序.中序.后序.层次遍历. 前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中->左->右: 中序遍历,遍历节点的顺序为:左->中->右: 后序遍历,遍历节点的顺序为:左->右->中. 前序遍历 递归实现 public void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" &q

  • java二叉树的几种遍历递归与非递归实现代码

    前序(先序)遍历 中序遍历 后续遍历 层序遍历 如图二叉树: 二叉树结点结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } @Override public String toString(){ return "val: "+val; } } 访问函数 public void visit(TreeNode node){ System.out.print(

  • Java二叉树的四种遍历(递归与非递归)

    目录 一.先序遍历与后序遍历 二.中序遍历 三.层序遍历 一.先序遍历与后序遍历 先序遍历根节点,再遍历左子树,再遍历右子树. 后序遍历先遍历左子树,再遍历右子树,再遍历根节点. 先序遍历递归实现: public static void preOrderByRecursion(TreeNode root) { // 打印节点值 System.out.println(root.value); preOrder(root.left); preOrder(root.right); } 先序遍历的非递归

  • Java开发深入分析讲解二叉树的递归和非递归遍历方法

    目录 前言 1.递归遍历 2.非迭代遍历 3.二叉树的统一迭代法 前言 二叉树的遍历方法分为前序遍历,中序遍历,后续遍历,层序遍历. 1.递归遍历 对于递归,就不得不说递归三要素:以前序遍历为例 递归入参参数和返回值 因为要打印出前序遍历节点的数值,所以参数里需要传入List在放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void,代码如下: public void preorder(TreeNode root, List<Integer> resu

  • 数据结构 二叉树的递归与非递归

    数据结构 二叉树的递归与非递归 实例代码: #include <iostream> #include <queue> #include <stack> #include <assert.h> using namespace std; template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T

  • C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)

    C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree

随机推荐