算法
2019-01-21 本文已影响12人
tangyefei
译者序
译者认为这是一本非常好的入门书籍。因为内容通俗易懂、编排用心，没有太多数学和编程基础的人也能看懂。没有介绍像动态规划这样的重要思想算是一个遗憾。
前言
本书的配套网站 algs4.cs.princeton.edu 提供了丰富的关于数据结构和算法的资料。
TODO 进行探索，看是否能将网站和图书结合起来使用。
第1章 基础
本章介绍学习算法和数据结构所需要的基本工具：
- 首先介绍的是基础编程模型，即Java语言的基本使用
- 接下来是数据抽象并定义抽象数据类型以进行模块化编程
- 之后学习三种基础的抽象数据类型：背包、队列、栈
- 最后描述了分析算法性能的方法，并且给出了一个案例分析
我们关注的大多数算法都需要适当地组织数据，由此产生了数据结构。数据结构与算法的关系十分密切，作者的观点是它是算法的副产品或结果。理解算法必须学习数据结构，因此本书中会讨论多数数据结构的性质。
学习算法的原因是它们能够节约非常多的资源，甚至能让我们完成一些本不可能完成的任务，精心设计的算法在任何领域都是解决大型问题的最有效的方法。本书的焦点就在那些复杂算法分解后的子问题的算法，他们是被证实为在很多领域内是解决困难问题的有效方法。
1.1 基础编程模型
1.1.1-1.1.10
略，因为自己有过使用Java的经验，并且预备使用JavaScript实现算法因此略过该部分
基础练习
13. 编写一段代码，打印出一个M行N列的二维数组的转制（交换行和列）。
/* Analyze
先遍历行，会先把每一行的所有列号的下标暴露
反过来，先遍历列，会先把每一列的所有行号暴露
但是取值仍旧要将行号放在前面，列号放在后面，这是由2维数组的存储结构决定的
*/
// JavaScript Impl
function reversePrint(array, M, N) {
for (let i = 0; i < N; i++) {
let line = '';
for (let j = 0; j < M; j++) {
line += (array[j][i] + ' ');
}
console.log(line);
}
}
// Test
var array = [
[11, 12, 13],
[21, 22, 23]
];
var M = 2, N = 3;
reversePrint(array, M, N)
// Test Output
// 11 21
// 12 22
// 13 23
14编写一个静态方法lg(), 接受一个整形参数N，返回不大于log2N的最大整数。
/* Analyze
数值初始为2，操作次数为1
连续做乘以2的操作，直到大于N（<=N要继续做乘法）
返回 `操作次数-1` 作为返回结果
*/
function f(){}
// JavaScript Impl
function lg(N) {
if(N == 1) return 0;
var value = 2, result = 1;
while(value <= N) {
result += 1;
value *= 2;
}
return result - 1;
}
// Test
lg(1) // 0
lg(2) // 1
lg(4) // 2
lg(1025) // 10
16. 给出exR1(6)的返回值：
//Java Define
public static String exR1(int n) {
if(n <= 0) return "";
return exR1(n-3) + n + exR1(n-2) + n;
}
// JavaScript
function exR1(int n) {
if(n <= 0) return "";
return exR1(n-3) + n + exR1(n-2) + n;
}
// Calculate
e6
e3 + 6 + e4 + 6
(e0 + 3 + e1 + 3) + 6 + (e1 + 4 + e2 + 4) + 6
(e0 + 3 + (e-2 + 1 + e-1 + 1) + 3) + ((e-2 + 1 + e-1 + 1) + 4 + (e-1 + 2 + e0 + 2) + 4 ) + 6
3+1+1+3+1+1+4+2+2+4+6
result: 31131142246
// Execute Result
311361142246
Miss a 6 in third step
17. 找出以下函数的问题
//Java Define
public static String exR1(int n) {
String s = exR1(n-3) + n + exR1(n-2) + n;
if(n <= 0) return "";
return s;
}
exR2会永远循环调用，退出代码 n <= 0 永远不会被执行
18. 略
本题执行结果会有6次左右的递归运算，但是连续的乘法使结果变得非常大。作者尝试用一道练习题来告诉我们，递归可能导致最终的运算结果非常大，使用时候需要评估运算量。
19. 在计算机上运行以下程序
// JavaScript Define
function fibonacci(n) {
if(n === 0 || n === 1) return n;
return fibonacci(n-1) + fibonacci(n - 2);
}
for (let i = 0; i < 100; i++) {
console.log(i + ' ' + fibonacci(i));
}
计算机上运行这段程序1小时所能得到的N的最大值是多少？开发一个更好的实现，用数组保存已经计算的值。
// JavaScript Update One
for (let i =0; i < 100; i++) {
var start = new Date();
let result = fibonacci(i);
var end = new Date();
console.log(i + ' ' + (end.getTime() - start.getTime())/1000 + ' ' + result)
}
答：尝试记录每次调用 fibonacci 的执行时间，发现从45开始，执行时间已经长达16s，并且N每加1，执行时间近乎是成倍的执行时间，必须减少重复运算来提高执行效率，目测很可能1小时下只能执行到54左右。优化后的代码如下（执行时间不到1秒）：
// JavaScript Update Two
var caches = new Array(100);
function fibonacci(n) {
if(chaches[n]) return caches[n];
if(n === 0 || n === 1) return n;
return fibonacci(n-1) + fibonacci(n - 2);
}
for (let i = 0; i < 100; i++) {
var start = new Date();
let result = caches[i] = fibonacci(i);
var end = new Date();
console.log(i + ' ' + (end.getTime() - start.getTime())/1000 + ' ' + result)
}
20. 编写一个递归的静态方法计算ln(N!)的值
基础的数学知识(百度百科)：
- a的x次方等于N（a>0，且a不等于1），那么数x叫做以a为底N的对数，记作x=logaN。其中，a叫做对数的底数，N叫做真数。
- 自然对数 以无理数e为底 记为ln。
- 常用对数 以10为底的对数 记为lg。
对数基本公式
//JavaScript
function ln(N) {
if(N == 1) return 0;
return Math.log(N) + ln(N-1);
}
24. 给出使用欧几里得算法计算102
// JavaScript
function euclid(p, q) {
if(q > p) {var t = p; p = q; q = t}
console.log(p + ','+ q);
if(q == 0) return p;
return euclid(q,p-q);
}
euclid(102,24)
// 102,24
// 78,24
// 54,24
// 30,24
// 24,6
// 18,6
// 12,6
// 6,6
// 6,0
euclid(1 111 111， 1 234 567);
//...
//Uncaught RangeError: Maximum call stack size exceeded
对应地将 `p-q` 改为 `p%q`，因为p和q差值巨大的时候，会大量的时间用于递归。
25. 数学归纳法证明欧几里得算法那能够对任意一非负整数的 p 和 q 的最大公约数。
假设：p, q的最大公约是是r，假定p >= q
证明：
p/r = p1(整数)
q/r = q1(整数)
(p-q)/r=p1-q1 同样为整数
那么 p 和 p-q 的最大公约数也是r
如果其中p-q为0，那么r 的值即等于此时的p的值
提高题
27. 二项分布。估计用以下代码计算 binomial(100, 50, 0.25)将会产生的递归调用次数，将已经计算过的值保存在数组中并给出一个更好的实现。
// JavaScript Slow
function binomial(N, k, 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);
}
binomial(5, 2, .25); // 0.263671875
binomial(5, 3, .25); // 0.087890625
binomial(5, 0, .25); // 0.2373046875
binomial(5, 5, .25); // 9.765625E-4
// JavaScript Quick
function binomial(N, k, p) {
var mArray = new Array(N + 1);
for (let i = 0; i <= N; i++) {
mArray[i] = new Array(k + 1);
}
mArray[0][0] = 1;
for (let i = 1; i <= N; i++) {
mArray[i][0] = (1-p)*mArray[i-1][0];
}
for (let i = 1; i <= k; i++) {
mArray[0][i] = 0;
}
for (let i = 1; i <= k; i++) {
for (let j = 1; j <= N; j++) {
mArray[j][i] = (1-p)*mArray[j-1][i] + p*mArray[j-1][i-1];
}
}
console.log(mArray[N][k]);
}
- 等值键。为BinarySearch类添加一个静态方法rank(key, a)，它接受一个键和一个整形有序数组（可能存在重复键）作为参数返回数组中小于该键的元素数量，以及一个类似的方法count(key, a)返回该数组中等于该键的元素的数量。
// JavaScript
function rank(key, a) {
var lo = 0, ro = a.length - 1;
var mo = -1;
var li = 0;
while(lo <= ro) {
li ++;
if(li == 1000) break;
var mid = parseInt((lo + ro) / 2);
if(a[mid] >= key) {
ro = mid - 1;
} else if(a[mid] < key) {
mo = mid;
lo = mid + 1;
}
}
return mo;
}
console.log(rank(1, [1,1,2,2,2,3,3,3,3])); // -1
console.log(rank(2, [1,1,2,2,2,3,3,3,3])); // 1
console.log(rank(4, [1,1,2,2,2,3,3,3,3])); // 8
console.log(rank(3, [1,1,2,2,2,3,3,3,3])); // 4
console.log(rank(11, [1,3,5,7,9,11,11,15,19])); // 4
function count(key, a) {
var lo = 0, ro = a.length - 1;
var mo1 = -1, mo2 = -1;
while(lo <= ro) {
var mid = parseInt((lo + ro) / 2);
if(a[mid] >= key) {
ro = mid - 1;
} else {
mo1 = mid;
lo = mid + 1;
}
}
lo = 0, ro = a.length - 1;
while(lo <= ro) {
var mid = parseInt((lo + ro) / 2);
if(a[mid] <= key) {
lo = mid + 1;
} else {
mo2 = mid;
ro = mid - 1;
}
}
if(mo1 == -1 && mo2 == -1) return 0;
else if(mo1 == -1) return mo2 + 1;
else if(mo2 == -1) return a.length - (mo1 + 1);
else return mo2 - mo1 - 1;
}
console.log(count(5, [1,2,3,4,5,6])) // 1
console.log(count(5, [1,2,5,5,5,6])) // 3
console.log(count(8, [1,2,5,5,5,6])) // 0
