【免费】AlgorithmsForProgrammers资源-CSDN文库

需积分: 0 49 浏览量 2010-09-01 10:49:29 上传评论收藏 4.82MB PDF 举报

### 知识点总结：《程序员的算法》 #### 标题与描述解析 - **标题：“Algorithms For Programmers”**：此标题表明本书旨在为程序员提供算法方面的指导和资源。 - **描述：“Algorithms For Programmers”**：描述简短地重申了标题的内容，强调了该书是面向程序员的算法指南。 #### 核心知识点概述本书分为三个主要部分：低级算法、排列算法以及排序与搜索算法。以下是对每个部分的详细介绍： ### I. 低级算法 #### 1.1 位操作技巧（Bit Wizardry） - **简介**：介绍了一些基本但重要的位操作技巧，这些技巧对于高效编程至关重要。 - **内容**： - **Trivia**：包括一些有趣的事实和小技巧。 - **Operations on individual bits**：涉及如何单独处理二进制位。 - **Operations on low bits or blocks of a word**：讨论如何处理单词中的低位或位块。 - **Extraction of ones, zeros, or blocks near transitions**：讲解如何提取特定模式或转换附近的位。 - **Computing the index of a single set bit**：介绍计算单个设置位索引的方法。 - **Operations on high bits or blocks of a word**：探讨如何处理单词中的高位或位块。 - **Functions related to the base-2 logarithm**：列出与二进制对数相关的函数。 - **Counting bits and blocks of a word**：介绍如何统计单词中的位数和位块数量。 - **Counting bits of many words**：解释如何对多个单词进行位计数。 - **Words as bitsets**：将单词视为位集的应用示例。 - **Avoiding branches**：讨论如何通过位操作避免分支语句。 - **Bit-wise rotation of a word**：介绍位级别的旋转操作。 - **Functions related to bit-wise rotation and binary necklaces**：探讨与位级别旋转和二进制项链相关的函数。 - **Reversing the bits of a word**：说明如何反转单词中的位顺序。 - **Bit-wise zip**：介绍位级别的打包操作。 - **Gray code and parity**：讲解格雷码及其奇偶校验。 - **Bit sequency**：讨论位序列的概念和应用。 - **Powers of the Gray code**：分析格雷码的幂次运算。 - **Invertible transformations on words**：讨论可逆变换在单词上的应用。 - **Space-filling curves**：介绍空间填充曲线的概念。 - **Scanning for zero bytes**：讲解扫描零字节的方法。 - **2-adic inverse and square root**：讨论2-进制逆元和平方根的计算方法。 - **Radix-2 representation**：介绍基数2表示法。 - **A sparse signed binary representation**：讲解稀疏有符号二进制表示。 - **Generating bit combinations**：介绍生成位组合的方法。 - **Generating bit subsets of a given word**：解释如何生成给定单词的位子集。 - **Binary words as subsets in lexicographic order**：讨论二进制单词作为字典序子集的应用。 - **Minimal-change bit combinations**：介绍最小变化位组合。 - **Fibonacci words**：讲解斐波那契词的概念。 - **Binary words and parentheses strings**：探讨二进制单词和括号字符串之间的关系。 - **Permutations via primitives**：介绍通过原语实现排列的方法。 - **CPU instructions often missed**：列举经常被忽视的CPU指令。 ### II. 排列算法 #### 2.1 Revbin排列 - **简介**：介绍revbin排列的概念和应用。 - **内容**：包括revbin排列的基本原理和示例。 #### 2.2 Radix排列 - **简介**：讨论radix排列的特点及其实现方式。 - **内容**：包括radix排列的具体算法和实例。 #### 2.3 原地矩阵转置 - **简介**：介绍如何在不使用额外空间的情况下转置矩阵。 - **内容**：包括原地矩阵转置的算法实现。 #### 2.4 三重反转技术 - **简介**：探讨一种称为“三重反转”的特殊排列技术。 - **内容**：包括三重反转技术的详细描述。 #### 2.5 Zip排列 - **简介**：介绍Zip排列的概念。 - **内容**：包括Zip排列的具体实现方法。 #### 2.6 反转Zip排列 - **简介**：探讨反转Zip排列的实现方法。 - **内容**：包括反转Zip排列的具体算法。 #### 2.7 XOR排列 - **简介**：介绍XOR排列的概念。 - **内容**：包括XOR排列的具体实现。 #### 2.8 格雷码排列 - **简介**：讨论基于格雷码的排列。 - **内容**：包括格雷码排列的实现方法。 #### 2.9 反转格雷码排列 - **简介**：介绍反转格雷码排列的概念。 - **内容**：包括反转格雷码排列的具体实现。 #### 2.10 一般排列及其操作 - **简介**：概括一般排列的定义及其常见操作。 - **内容**：包括一般排列的定义、实现及操作方法。 ### III. 排序与搜索算法 #### 3.1 排序 - **简介**：介绍排序算法的基本概念。 - **内容**：包括排序算法的不同类型及其实现。 #### 3.2 二分搜索 - **简介**：介绍二分搜索算法的原理。 - **内容**：包括二分搜索的具体步骤及示例。 #### 3.3 索引排序 - **简介**：介绍索引排序的基本原理。 - **内容**：包括索引排序的具体实现方法。以上内容为《程序员的算法》一书中各章节的主要知识点概述。通过对这些内容的学习，读者可以深入了解位操作、排列算法以及排序和搜索算法的相关知识，并掌握其实现方法和技术细节。

资源详情

资源评论

资源推荐

Algorithms for programmers

ideas and source code

This do cument is work in progress: read the “important remarks” near the beginning

J¨org Arndt

arndt@jjj.de

Draft version

of 2008-August-03

The latest version and the accompanying software is online at http://www.jjj.de/fxt/.

CONTENTS iii

Contents

Important remarks about this document xi

I Low level algorithms 1

1 Bit wizardry 3

1.1 Trivia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Operations on individual bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3 Operations on low bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4 Extraction of ones, zeros, or blocks near transitions . . . . . . . . . . . . . . . . . . . . . 12

1.5 Computing the index of a single set bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6 Operations on high bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.7 Functions related to the base-2 logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.8 Counting bits and blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.9 Counting bits of many words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.10 Words as bit sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.11 Avoiding branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.12 Bit-wise rotation of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1.13 Functions related to bit-wise rotation and binary necklaces . . . . . . . . . . . . . . . . . 30

1.14 Reversing the bits of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

1.15 Bit-wise zip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

1.16 Gray code and parity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

1.17 Bit sequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

1.18 Powers of the Gray code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

1.19 Invertible transforms on words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

1.20 Space ﬁlling curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

1.21 Scanning for zero bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

1.22 2-adic inverse and square root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

1.23 Radix −2 representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

1.24 A sparse signed binary representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

1.25 Generating bit combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

1.26 Generating bit subsets of a given word . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

1.27 Binary words as subsets in lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . 73

1.28 Minimal-change bit combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

1.29 Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

1.30 Binary words and parentheses strings * . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

1.31 Permutations via primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

1.32 CPU instructions often missed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

2 Permutations 91

2.1 The revbin permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

2.2 The radix permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

[fxtbook draft of 2008-August-03]

iv CONTENTS

2.3 In-place matrix transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

2.4 The triple reversion technique * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

2.5 The zip permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

2.6 The reversed zip permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

2.7 The XOR permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

2.8 The Gray code permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

2.9 The reversed Gray code permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

2.10 General permutations and their operations . . . . . . . . . . . . . . . . . . . . . . . . . . 109

3 Sorting and searching 121

3.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

3.2 Binary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

3.3 Index sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

3.4 Pointer sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

3.5 Sorting by a supplied comparison function . . . . . . . . . . . . . . . . . . . . . . . . . . 127

3.6 Determination of unique elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

3.7 Unique elements with inexact types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

3.8 Determination of equivalence classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

3.9 Determination of monotonicity and convexity * . . . . . . . . . . . . . . . . . . . . . . . . 137

3.10 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

3.11 Counting sort and radix sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

3.12 Searching in unsorted arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

4 Data structures 147

4.1 Stack (LIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

4.2 Ring buﬀer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

4.3 Queue (FIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

4.4 Deque (double-ended queue) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

4.5 Heap and priority queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

4.6 Bit-array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

4.7 Left-right array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

4.8 Finite state machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

4.9 Emulation of coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

II Combinatorial generation 169

5 Conventions and considerations 171

5.1 About representations and orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

5.2 Ranking, unranking, and counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

5.3 Characteristics of the algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

5.4 Optimization techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

5.5 The implementations, demo-programs, and timings . . . . . . . . . . . . . . . . . . . . . 173

6 Combinations 175

6.1 Lexicographic and co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

6.2 Order by preﬁx shifts (cool-lex) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

6.3 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

6.4 The Eades-McKay strong minimal-change order . . . . . . . . . . . . . . . . . . . . . . . 182

6.5 Two-close orderings via endo/enup moves . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

6.6 Recursive generation of certain orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

7 Compositions 193

7.1 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

[fxtbook draft of 2008-August-03]

CONTENTS v

7.2 Co-lexicographic order for compositions into exactly k parts . . . . . . . . . . . . . . . . 195

7.3 Compositions and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

7.4 Minimal-change orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

8 Subsets 201

8.1 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

8.2 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

8.3 Ordering with De Bruijn sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

8.4 Shifts-order for subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

8.5 k-subsets where k lies in a given range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210

9 Mixed radix numbers 219

9.1 Counting (lexicographic) order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

9.2 Gray code order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

9.3 gslex order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

9.4 endo order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

9.5 Gray code for endo order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

10 Permutations 233

10.1 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

10.2 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

10.3 Factorial representations of permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

10.4 An order from reversing preﬁxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

10.5 Minimal-change order (Heap’s algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

10.6 Lipski’s Minimal-change orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

10.7 Strong minimal-change order (Trotter’s algorithm) . . . . . . . . . . . . . . . . . . . . . . 254

10.8 Minimal-change orders from factorial numbers . . . . . . . . . . . . . . . . . . . . . . . . 259

10.9 Orders where the smallest element always moves right . . . . . . . . . . . . . . . . . . . . 265

10.10 Single track orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

10.11 Star-transposition order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

10.12 Derangement order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

10.13 Recursive algorithm for cyclic permutations . . . . . . . . . . . . . . . . . . . . . . . . . . 279

10.14 Minimal-change order for cyclic permutations . . . . . . . . . . . . . . . . . . . . . . . . . 281

10.15 Permutations with special properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

11 Subsets and permutations of a multiset 291

11.1 Subsets of a multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

11.2 Permutations of a multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

12 Gray codes for strings with restrictions 299

12.1 Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

12.2 Generalized Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

12.3 Digit x followed by at least x zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

12.4 Generalized Pell words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

12.5 Sparse signed binary words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

12.6 Strings with no two successive nonzero digits . . . . . . . . . . . . . . . . . . . . . . . . . 310

12.7 Strings with no two successive zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

12.8 Binary strings without substrings 1x1 or 1xy1 . . . . . . . . . . . . . . . . . . . . . . . . 313

13 Parenthesis strings 317

13.1 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317

13.2 Gray code via restricted growth strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

13.3 The number of parenthesis strings: Catalan numbers . . . . . . . . . . . . . . . . . . . . 324

13.4 Increment-i RGS and k-ary trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325

[fxtbook draft of 2008-August-03]

剩余987页未读，继续阅读

评论收藏

内容反馈

口水无痕

粉丝: 2
资源: 32

Algorithms For Programmers

评论0

最新资源

Algorithms For Programmers

评论0

Algorithms

Algorithms for programmers

Algorithms for programmers ideas and source code

Practical Algorithms for Programmers，Andrew Binstock,John Rex

Algorithms For Programmers- Ideas And Source Code

Algorithms for programmers(2)

(ebook).Algorithms for Programmers.pdf

DSP Algorithms for programmersDSP Algorithms for programmers

Algorithms for Programmers ideas and source code

Algorithms in C

DSP_Algorithms_for_programmers.rar_algorithms

DSP.Algorithms.For.Programmers.gz_algorithms

程序员与算法工程师计算器

最新资源