算法(第4版)练习题1.1.27的三种解法

这篇具有很好参考价值的文章主要介绍了算法(第4版)练习题1.1.27的三种解法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文列举了对于 算法 : 第4版 / (美) 塞奇威客 (Sedgewick, R.) , (美) 韦恩 (Wayne, K.) 著 ; 谢路云译. -- 北京 : 人民邮电出版社, 2012.10 (2021.5重印)(以下简称原书或书)中的练习题 1.1.27 的三种解法(C++ 实现),并对包含原书题中的递归方法在内的四种解法的执行时间进行了统计和对比。

◆ 要求

原书中的练习题 1.1.27 要求对如下二项分布递归过程中的值保存在数组中,

b(n,k,p) = 1.0  ( n == 0 && k == 0 )
b(n,k,p) = 0.0  (  n < 0 ||  k < 0 )
b(n,k,p) = (1.0-p) * b(n-1,k,p) + p * b(n-1,k-1,p)

◆ 解一

依然采用递归的方式,但使用二维数组保存中间结果。

如下代码所示,

static long double binomial1(int N, int K, long double p)    // #1
{
    long double x;

    long double** b = new long double*[N+1];               // #2
    long double* data = new long double[(N+1)*(K+1)];

    ...

    x = binomial1_impl(b, N, K, p);         // #3

    ...

    return x;
}

static long double binomial1_impl(long double** b, int N, int K, long double p)
{
    if (N == 0 && K == 0) return 1.0L;
    if (N < 0 || K < 0) return 0.0L;
    if (b[N][K] == -1) {
        ...                                 // #4
        b[N][K] = (1.0L-p) * binomial1_impl(b, N-1, K, p) + p * binomial1_impl(b, N-1, K-1, p);
    }
    return b[N][K];
}

保持对外的接口不变(#1),创建一个二维数组 b[0..N][0..K] 保存中间计算结果(#2),并将其传给算法实现(#3)。算法虽然还是用递归调用(#4),但由于中间结果保存在全局的二维数组中,不用频繁地压栈和弹栈去获取中间数据。此解法网络上也见于 [github] reneargento/algorithms-sedgewick-wayne 和 [github] aistrate/AlgorithmsSedgewick 。

◆ 解二

使用二维数组保持中间结果,但同时将递归改进为递推。若以横向为 x 轴,纵向为 y 轴,左上角为坐标原点,则坐标轴上的 (x,y) 点则代表二维数组的 b[y][x] 单元。

以 N = K = 4 为例,

    0   1   2   3   4

0   *   *   *   *   *  <-- * 代表待计算的单元

1   *   *   *   *   *

2   *   *   *   *   *

3   *   *   *   *   *

4   *   *   *   *   ?  <-- 最终计算结果的单元 (4,4)

仔细考察递归关系式的特点,b(-1,*,p) = 0.0, b(*,-1,p) = 0.0。由

b(0,1,p) = (1.0-p) * b(-1,1,p) + p * b(-1,0,p)
         = (1.0-p) * 0.0 + p * 0.0
         = 0.0
b(0,2,p) = (1.0-p) * b(-1,1,p) + p * b(-1,1,p)
         = (1.0-p) * 0.0 + p * 0.0
         = 0.0
...

可推论出,二维数组中的第 0 行中的所有单元(不含b[0][0])均为 0.0;由

b(1,0,p) = (1.0-p) * b(0,0,p) + p * b(0,-1,p)
         = (1.0-p) * 1.0 + p * 0.0
         = 1.0-p
b(2,0,p) = (1.0-p) * b(1,0,p) + p * b(1,-1,p)
         = (1.0-p) * (1.0-p) + p * 0.0
         = (1.0-p)^2
...

可推论出,二维数组中的第 0 列的单元为 (1.0-p)^y。

因为每个单元 b[n][k] 结果(n 代表行号,k 代表列号),依赖于 b[n-1][k-1] 和 b[n-1][k] 的结果。为了减少计算量,递推过程可仅用到二维数组的部分单元。笔者设置一个 G 点,将待计算单元的区域划分为 '#' 和 '*' 两部分,G 点在 '#' 区域中。分为以下三种情况,

第一种情况,N < K:(如 N = 4, K = 6)

    0   1   2   3   4   5   6

0   -   -   G   #   #   #   #  <-- G 点所在单元为 0.0

1   -   -   -   *   *   *   *  <-- '-' 代表不用计算的单元

2   -   -   -   -   *   *   *

3   -   -   -   -   -   *   *

4   -   -   -   -   -   -   ?  <-- 最终结果的存储单元

G 点为 b(0,K-N)。按照递推关系式容易推导出,'#' 和 '*' 区域均为 0.0,所以最终结果即 0.0。

第二种情况,N = k:(如 N = 6, K = 6)

    0   1   2   3   4   5   6

0   G   #   #   #   #   #   #  <-- G 点所在单元为 1.0

1   -   *   *   *   *   *   *

2   -   -   *   *   *   *   *

3   -   -   -   *   *   *   *

4   -   -   -   -   *   *   *

5   -   -   -   -   -   *   *

6   -   -   -   -   -   -   ?

G 点为 b(0,0)。按照递推关系式容易推导出,数组中 n = k 的单元为 p^n。所以最终结果即 p^N。

第三种情况,N > K:(如 N = 6, K = 4)

    0   1   2   3   4

0   #   #   #   #   #

1   #   #   #   #   #

2   G   #   #   #   #  <-- G 点所在单元为 (1.0-p)^2

3   -   *   *   *   *

4   -   -   *   *   *

5   -   -   -   *   *

6   -   -   -   -   ?

G 点为 b(N-K,0)。可先计算 '#' 区域中的单元,再计算 '*' 区域中的单元,得出最终结果。处理'#'区域时,为避免大量的数组下标越界判断,可以考虑先计算 0 行和 0 列的所有单元。

如下代码所示,

static long double binomial2(int N, int K, long double p)
{
    long double x;

    if (N < K) {                       // #1

        x = 0.0L;

    } else if (N == K) {                // #2

        x = powl(p, N);

    } else {                       // #3

        ...

        b[0][0] = 1.0L;

        // process '#' area                      // #4
        // calcuate [1..N-K][0]
        for (i = 1; i <= N-K; ++i)
            b[i][0] = powl(1.0L-p, i);
        // calcuate [0][1..K]
        for (j = 1; j <= K; ++j)
            b[0][j] = 0.0L;
        // calcuate [1..N-K][1..K]
        for (i = 1; i <= N-K; ++i)
            for (j = 1; j <= K; ++j)
                b[i][j] = (1.0L-p) * b[i-1][j] + p * b[i-1][j-1];

        // process '*' area                            // #5
        for (i = N-K+1; i <= N; ++i)
            for (j = i-(N-K); j <= K; ++j)
                b[i][j] = (1.0L-p) * b[i-1][j] + p * b[i-1][j-1];

        x = b[N][K];                       // #6

        ...

    }

    return x;
}

三条分支(#1、#2、#3)分别对应前述三种情况。在第三种情况下,再先处理 '#' 区域(#4),然后采用递推求值的方式处理 '*' 区域(#5),最后得到结果(#6)。

◆ 解三

此方法是从递推解法中引申出来了。进一步探究这个此二项分布的递归式,以 N = 4 且 K = 4 为例,

   0          1                2                    3                4

0  1.0


1  1.0-p      p


2  (1.0-p)^2  2*(1.0-p)*p      p^2


3  (1.0-p)^3  3*[(1.0-p)^2]*p  3*(1-p)*(p^2)        p^3


4  (1.0-p)^4  4*[(1.0-p)^3]*p  6*[(1.0-p)^2]*(p^2)  4*(1.0-p)*(p^3)  p^4

可以发现,从第 0 行到第 N 行的非零单元即“杨辉三角形”,第 n 行中的非零单元之和构成 [(1.0-p) + p]^k 的展开式。因此,解二中的第三种情况,可结合利用通项公式 C(N,K)*[(1.0-p)^(N-K)]*(p^K) 来解决。

如下代码所示,

static long double binomial3(int N, int K, long double p)
{
    long double x;

    if ...

    } else {

        x = combination(N, K) * powl(1.0L-p, N-K) * powl(p, K);

    }

    return x;
}

◆ 测试

编译并执行程序,

$ g++ -std=c++11 -o 27.out 27.cpp
$ ./27.out 10 5 0.25

为易于显示两者之间的差异,笔者选择了硬件配置偏低的实验环境一,测试并记录了 (N, K, p) 为 (10, 5, 0.25), (20, 10, 0.25), (40, 20, 0.25), (80, 40, 0.25), (100, 50, 0.25) 的情况下,原递归、解一、解二、解三执行时所消耗的时间。

结果如下图所示,

算法(第4版)练习题1.1.27的三种解法

对比可以看出,不同的解法在执行时间上的差异随着计算量的增加而逐步扩大。

◆ 最后

完整的代码和测试结果请参考 [gitee] cnblogs/17328989 。

写作过程中,笔者参考了 [github] reneargento/algorithms-sedgewick-wayne 和 [github] aistrate/AlgorithmsSedgewick 的实现方式。致 reneargento 和 aistrate 两位。文章来源地址https://www.toymoban.com/news/detail-418441.html

到了这里,关于算法(第4版)练习题1.1.27的三种解法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 拓扑排序 (算法思想+图解+模板+练习题)

    有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。 无向图没有拓扑序列。 首先我们先来解释一下什么是有向无环图: 有向就是我们两个结点之间的边是有方向的,无环的意思就是整个序列中没有几个结点通过边形成一个圆环。 下图就是一个有向无环图,它也一定

    2024年02月03日
    浏览(71)
  • 数据结构与算法系列之习题练习

    💗 💗 博客:小怡同学 💗 💗 个人简介:编程小萌新 💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞 括号匹配问题。 用队列实现栈。 用栈实现队列。 设计循环队列。 有效的括号 //用栈来实现 //左括号进栈 右括号出栈并销毁如果不匹配则return //设置两个队列,入栈

    2024年02月11日
    浏览(47)
  • 数据结构与算法--图(概念+练习题+解析)

    有向图 在有向图中有以下几点结论: 1.所有顶点的度数之和等于边数的二倍。 2.所有顶点的入度之和等于出度之和。 3.n个顶点的有向完全图有n(n-1)条边。 4.n个顶点的强连通图至少有n条边。 无向图 在无向图中有以下几点结论: 1.所有顶点的度数之和等于边数的二倍。 2.n个顶

    2024年02月04日
    浏览(45)
  • 数学建模算法与应用:预测算法(6)预测习题练习

    目录  一,水塔总水量以及流速预测问题         1.1、题目         1.2、建立模型         1.3、用MATLAB计算,将“-”替换为-1。         1.4、拟合法          二、预测产值问题         2.1、题目         2.2、建立模型  一,水塔总水量以及流速预测问题        

    2024年02月13日
    浏览(44)
  • 每天一道算法练习题--Day18 && 第一章 --算法专题 --- ----------前缀树

    字典树也叫前缀树、Trie。它本身就是一个树型结构,也就是一颗多叉树,学过树的朋友应该非常容易理解,它的核心操作是插入,查找。删除很少使用,因此这个讲义不包含删除操作。 截止目前(2020-02-04) 前缀树(字典树) 在 LeetCode 一共有 17 道题目。其中 2 道简单,8 个

    2024年02月02日
    浏览(52)
  • 每天一道算法练习题--Day22&& 第一章 --算法专题 --- ----------最大公约数

    关于最大公约数有专门的研究。 而在 LeetCode 中虽然没有直接让你求解最大公约数的题目。但是却有一些间接需要你求解最大公约数的题目。 时间复杂度:最好的情况是执行一次循环体,最坏的情况是循环到 smaller 为 1,因此总的时间复杂度为 O ( N ) O(N) O ( N ) ,其中 N 为 a 和

    2024年02月03日
    浏览(55)
  • 每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历

    二叉树作为一个基础的数据结构,遍历算法作为一个基础的算法,两者结合当然是经典的组合了。很多题目都会有 ta 的身影,有直接问二叉树的遍历的,有间接问的。比如要你找到树中满足条件的节点,就是间接考察树的遍历,因为你要找到树中满足条件的点,就需要进行遍

    2024年02月01日
    浏览(49)
  • 【数据结构】算法的时间复杂度和空间复杂度(下)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 空间复杂度也是一个数学表达式,是对一个算法在运行过程中 临时占用的额外的存储空间大小的量度 。 空间复杂度不是程序占用

    2023年04月19日
    浏览(87)
  • 【数据结构】 算法的时间复杂度和空间复杂度 (上)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何

    2023年04月14日
    浏览(41)
  • 【数据结构】算法的时间复杂度和空间复杂度 (上)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何

    2023年04月22日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包