算法

译者序

译者认为这是一本非常好的入门书籍。因为内容通俗易懂、编排用心，没有太多数学和编程基础的人也能看懂。没有介绍像动态规划这样的重要思想算是一个遗憾。

前言

本书的配套网站 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]);
}
  1. 等值键。为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
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,457评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,837评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,696评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,183评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,057评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,105评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,520评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,211评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,482评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,574评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,353评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,213评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,576评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,897评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,174评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,489评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,683评论 2赞 335