精华内容
下载资源
问答
  • 算法第四版 第1.1节 习题27:计算递归调用次数,这里递归怎么二项分布: 定义:n个独立是/非试验成功次数k离散概率分布,每次实验成功概率为p,记作B(n,p,k)。 概率公式:P(ξ=K)= C(n,k) * p^k...

    问题来源:

    算法第四版 第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   

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


    展开全文
  • 2.3 两种算法的比较 19 高斯在上小学的一天,老师要求每个学生都计算1+2+…+100的结果,谁先算出来谁先回家…… 2.4 算法定义 20 现实世界中的算法千变万化,没有通用算法可以解决所有问题。甚至一个小问题,某个...
  • excel使用

    2012-11-25 17:06:01
    实际输入时候,通常应用等差数列输入法,先输入前二个值,定出自变量数与数之间步长,然后选中A2和A3两个单元格,使这二项变成一个带黑色边框矩形,再用鼠标指向这黑色矩形右下角小方块“■”,当光标...
  • Visual Studio程序员箴言中文扫描PDF

    热门讨论 2010-12-28 01:04:18
    技巧5.22 使用ctrl+c键复制工具箱选项卡中的控件,然后用ctrl+v键将该控件粘贴到另一个工具箱选项卡 115 技巧5.23 新建工具箱选项卡 116 5.1.4 任务列表 117 技巧5.24 使用任务列表创建独立于代码的用户任务...
  • 阿里系的 <a href="http://docs.kissyui.com/">KISSY</a> 框架的取名就源自 Unix 哲学中的这一条࿰c;Keep it Simple & Stupid。这也是我们在 PC 和无线时代不断提炼前端开发框架、研发模式、共享代码和开源...
  • 1.9 如何生成“半全局变量”,就是那种只能被部分源文件中的部分函数访问的变量? 存储类型 1.10 同一个静态(static)函数或变量的所有声明都必需包含static存储类型吗? 1.11 extern在函数声明中是什么意思? ...
  • 《你必须知道495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    1.9 如何生成“半全局变量”,就是那种只能被部分源文件中的部分函数访问的变量? 5 存储类型 6 1.10 同一个静态(static)函数或变量的所有声明都必须包含static存储类型吗? 6 1.11 extern在函数声明中是什么...
  • 1.9 如何生成“半全局变量”,就是那种只能被部分源文件中的部分函数访问的变量? 5 存储类型 6 1.10 同一个静态(static)函数或变量的所有声明都必须包含static存储类型吗? 6 1.11 extern在函数声明中是什么...
  • 快速删除工作表中的空行快速删除空行一次删完Excel里面多出很多的空白行 每30行为一页并加上一个标题如何实现如何实现隔行都加上标题 如何把标签页去掉的? 去掉默认的表格线(网线)表格的框线 列标的标识变了 符号...
  • 语言建模涉及开发一种统计模型,用于预测句子中的下一个单词或一个单词中的下一个单词。它是语音识别和机器翻译等任务中的前置任务。 它是语音识别和机器翻译等任务中的前置任务。 下面是一些很好的初学者语言建模...
  • 你必须知道495个C语言问题(PDF)

    热门讨论 2009-09-15 10:25:47
    3.12 我需要根据条件把一个复杂的表达式赋值给两个变量中的一 个。可以用下边这样的代码吗? ((condition) ? a : b) = complicated expression; . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 目录iii ...
  • EXCEL函数公式集

    热门讨论 2010-03-16 03:26:38
    快速删除工作表中的空行快速删除空行一次删完Excel里面多出很多的空白行 每30行为一页并加上一个标题如何实现如何实现隔行都加上标题 如何把标签页去掉的? 去掉默认的表格线(网线)表格的框线 列标的标识变了 符号...
  • C#微软培训教材(高清PDF)

    千次下载 热门讨论 2009-07-30 08:51:17
    C#--微软.NET的第一语言 本书着重介绍语言本身,比较少涉及应用,不错的入门书,从头讲起,不怕... C#语言在.NET 框架中的作用及其特性 1.1 Microsoft.NET 一场新的革命 1.1.1 什么是.NET 2000 年 6 月 ...
  • C#微软培训资料

    2014-01-22 14:10:17
    C#语言在.NET 框架中的作用及其特性 1.1 Microsoft.NET 一场新的革命 1.1.1 什么是.NET 2000 年 6 月 22 日 不论对 Microsoft 还是对整个 IT 业界都将成为值得纪念的一天 这一天 微软公司正式推出...
  •  如果不带任何参数,chkdsk 将显示当前驱动器中的磁盘状态。 drive: 指定要 chkdsk 检查的驱动器。 /p 即使驱动器不在 chkdsk 的检查范围内,也执行彻底检查。该参数不对驱动器做任何更改。 /r 找到坏扇区并...
  • <code>observe</code> 中的 <code>this.value</code> 其实就是 <code>_initData</code> 中的 <code>this._data</code>࿰c;所以给 <code>this.value</code> 添加getter 和 setter 就等于给 this._data 设置 ...
  • 11 空白在c和C++中的使用 12 理解变量 13 对变量命名 14 理解表达式 15 C/C++中的语句 16 理解程序流 17 深入程序流:理解goto语句 18 深入程序流:理解调用函数 19 理解程序的结构 20 理解C/C++中的函数 21 在函数...
  • 11 空白在c和C++中的使用 12 理解变量 13 对变量命名 14 理解表达式 15 C/C++中的语句 16 理解程序流 17 深入程序流:理解goto语句 18 深入程序流:理解调用函数 19 理解程序的结构 20 理解C/C++中的函数 21 在函数...
  • 11 空白在c和C++中的使用 12 理解变量 13 对变量命名 14 理解表达式 15 C/C++中的语句 16 理解程序流 17 深入程序流:理解goto语句 18 深入程序流:理解调用函数 19 理解程序的结构 20 理解C/C++中的函数 21 在函数...
  • 11 空白在c和C++中的使用 12 理解变量 13 对变量命名 14 理解表达式 15 C/C++中的语句 16 理解程序流 17 深入程序流:理解goto语句 18 深入程序流:理解调用函数 19 理解程序的结构 20 理解C/C++中的函数 21 在函数...
  • o 4.12 我需要根据条件把一个复杂的表达式赋值给两个变量中的一个。可以用下边这样的代码吗? ((condition) ? a : b) = complicated_expression; * 5. 指针 o 5.1 我想声明一个指针并为它分配一些空间, 但却...
  • 2、然后就可以双击“Skin_400x234.bat”、“Skin_640X480.bat”、“Skin_800X480.BAT”三个中的其中一个,这三个本质上是一样的,只要分辨率的大小不同。 3、点击“文件”-“配置”-“常规”-“共享文件夹”。 4...
  • ASP.NET精品课程+源代码

    千次下载 热门讨论 2009-01-05 20:15:51
    我们选的实践案例与课堂教学中的案例密切相关,学生感到熟悉,易于与课堂教学中的案例知识联系起来,便于理解巩固所学知识,形成知识理论实践一体化。根据实践案例,教师充当学生的组织者、指挥者、帮助者和促进者。...
  • vc++ 应用源码包_1

    热门讨论 2012-09-15 14:22:12
    引用了Splayer中的Sqlite3库,进行了测试。 SrcFirstProg 简单的窗口程序。 SuperGrid - 特别的 listview 控件 网格形式的视图,自绘了CComboBox、CEdit、CSuperGridCtrl实现。 tab 演示了CTabCtrl控件的使用方法...
  • 软件工程教程

    热门讨论 2012-07-06 23:10:29
    通过演示及讲述,讲解课程设计的整体情况,针对其设计提出一些技术及细节问题确认是否真正理解课程设计中的要点、是否掌握了进行系统设计的知识和能力、是否本人完成。如通发现没有真正设计或者不清楚技术细节,则...
  • vc++ 应用源码包_6

    热门讨论 2012-09-15 14:59:46
    引用了Splayer中的Sqlite3库,进行了测试。 SrcFirstProg 简单的窗口程序。 SuperGrid - 特别的 listview 控件 网格形式的视图,自绘了CComboBox、CEdit、CSuperGridCtrl实现。 tab 演示了CTabCtrl控件的使用方法...
  • vc++ 应用源码包_2

    热门讨论 2012-09-15 14:27:40
    引用了Splayer中的Sqlite3库,进行了测试。 SrcFirstProg 简单的窗口程序。 SuperGrid - 特别的 listview 控件 网格形式的视图,自绘了CComboBox、CEdit、CSuperGridCtrl实现。 tab 演示了CTabCtrl控件的使用方法...

空空如也

空空如也

1 2 3
收藏数 56
精华内容 22
关键字:

二项式中的c怎么计算