算法(4th ed)(64):基础——基础编程模型 3.14

阅读数:29 2019 年 10 月 30 日 07:09

算法(4th ed)(64):基础——基础编程模型 3.14

(提高题)

1.1.26 将三个数字排序。假设 abct 都是同一种原始数字类型的变量。证明以下代码能够将 abc 按照升序排列:

复制代码
if (a > b) { t = a; a = b; b = t; }
if (a > c) { t = a; a = c; c = t; }
if (b > c) { t = b; b = c; c = t; }

1.1.27 二项分布。估计用以下代码计算 binomial(100, 50, 0.25) 将会产生的递归调用次数:

复制代码
public static double binomial(int N, int k, double p)
{
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);
}

将已经计算过的值保存在数组中并给出一个更好的实现。

1.1.28 删除重复元素。修改BinarySearch 类中的测试用例来删去排序之后白名单中的所有重复元素。

1.1.29 等值键。为 BinarySearch 添加一个静态方法rank(),它接受一个键和一个整型有序数组(可能存在重复键)作为参数并返回数组中小于该键的元素数量,以及一个类似的方法 count() 来返回数组中等于该键的元素的数量。注意:如果 ij 分别是 rank(key,a)count(key,a) 的返回值,那么 a[i..i+j-1] 就是数组中所有和 key 相等的元素。

1.1.30 数组练习。编写一段程序,创建一个 N×N 的布尔数组 a[][]。其中当 ij 互质时(没有相同因子),a[i][j]true,否则为 false

1.1.31 随机连接。编写一段程序,从命令行接受一个整数 Ndoublep01 之间)作为参数,在一个圆上画出大小为 0.05 且间距相等的 N 个点,然后将每对点按照概率 p 用灰线连接。

1.1.32 直方图。假设标准输入流中含有一系列 double 值。编写一段程序,从命令行接受一个整数 N 和两个 doublelr。将 (l,r) 分为 N 段并使用 StdDraw 画出输入流中的值落入每段的数量的直方图。

1.1.33 矩阵库。编写一个 Matrix 库并实现以下 API:

public class Matrix
   static     double  dot(double[] x, double[] y)向量点乘
   static double[][]  mult(double[][] a, double[][] b)矩阵和矩阵之积
   static double[][]  transpose(double[][] a)转置矩阵
   static   double[]  mult(double[][] a, double[] x)矩阵和向量之积
   static   double[]  mult(double[] y, double[][] a)向量和矩阵之积

编写一个测试用例,从标准输入读取矩阵并测试所有方法。

1.1.34 过滤。以下哪些任务需要(在数组中,比如)保存标准输入中的所有值?哪些可以被实现为一个过滤器且仅使用固定数量的变量和固定大小的数组(和 N 无关)?在每个问题中,输入都来自于标准输入且含有 N01 的实数。

  • 打印出最大和最小的数
  • 打印出所有数的中位数
  • 打印出第 k 小的数,k 小于 100
  • 打印出所有数的平方和
  • 打印出 N 个数的平均值
  • 打印出大于平均值的数的百分比
  • N 个数按照升序打印
  • N 个数按照随机顺序打印

评论

发布