Closed solidSpoon closed 3 years ago
layout: post
title: "《算法-第四版》答案系列-1.1 提高题篇"
subtitle: "本系列是《算法-第四版》一书的课后习题答案"
date: 2018-07-28 12:00:00
author: "solidSpoon"
header-img: "img/post-bg.jpg"
header-mask: 0.3
catalog: true
tags:
- 算法第四版
以下的答案在电脑端查看可以显示目录
提高题
1.1.26 将三个数字排序。假设 a、b、c 和 t 都是同一种原始数字类型的变量。证明以下代码能够将 a、b、c 按照升序排列:
1.1.27 二项分布。估计用以下代码计算
binomial(100, 50, 0.25)
将会发生的递归调用次数:将已经已经计算过的值保存在数组中并给出一个更好的实现。
1.1.28 删除重复元素。修改
BinarySearch
类的测试用例来删去排序之后白名单中的所有重复元素。答:在
BinarySearch
类中添加该方法并在测试用例中调用,传入whitelist
.1.1.29 等值键。为
BinarySearch
类添加一个静态方法rank()
,他接受一个键和一个整形有序数组(可能存在重复键)作为参数并返回数组中小于该键的元素数量,以及一个类似的方法count()
来返回数组中等于该键的元素的数量。注意:如果 i 和 j 分别是rank(key, a)
和cout(key, a)
的返回值,那么 a[i..i+j-1] 就是数组中所有和 key 相等的元素。1.1.30 数组练习。编写一段程序,创建一个 N × N 的布尔数组
a[][]
。其中当 i 和 j 互质时(没有相同因子),a[i][j]
为true
,否则为false
。1.1.31 随机连接。编写一段程序,从命令行接受一个整数 N 和 double 值 p( 0 到 1 之间)作为参数,在一个圆上画出大小为 0.05 且间距相等的 N 个点,然后将每对点按照概率 p 用灰线链接。
运行结果(改成了红线,概率为 1 时):
1.1.32 直方图。假设标准输入流中含有一系列
double
值。编写一段程序,从命令行接受一个整数 N 和两个double
值 l 和 r。将(l, r)
分为 N 段并使用StdDraw
画出输入流中的值落入每段的数量的直方图。运行结果:
1.1.33 矩阵库。编写一个
Matrix
库并实现以下API:1.1.34 过滤。以下哪些任务需要以下哪些任务需要(在数组中,比如)保存标准输入中的所有值?哪些可以被实现为一个过滤器且仅使用固定数量的变量和固定大小的数组(和N无关)?在每个问题中,输入都来自于标准输入且含有N个0到1的实数。