Skip to content

Commit aa23625

Browse files
facertfacert
authored
Merge pull request #27 from qiwihui/master
 第四、五、六章数学公式和代码块统一
2 parents 60dbccc + 69b9bce commit aa23625

57 files changed

Lines changed: 407 additions & 452 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎4.递归/4.1.目标/README.md‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,4 +8,3 @@
88
* 将递归理解为一种迭代形式。
99
* 实现问题的递归公式化。
1010
* 了解计算机系统如何实现递归。
11-

‎4.递归/4.10.汉诺塔游戏/README.md‎

Lines changed: 7 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2,13 +2,12 @@
22

33
汉诺塔是由法国数学家爱德华·卢卡斯在 1883 年发明的。他的灵感来自一个传说，有一个印度教寺庙，将谜题交给年轻的牧师。在开始的时候，牧师们被给予三根杆和一堆 64 个金碟，每个盘比它下面一个小一点。他们的任务是将所有 64 个盘子从三个杆中一个转移到另一个。有两个重要的约束，它们一次只能移动一个盘子，并且它们不能在较小的盘子顶部上放置更大的盘子。牧师日夜不停每秒钟移动一块盘子。当他们完成工作时，传说，寺庙会变成灰尘，世界将消失。
44

5-
虽然传说是有趣的，你不必担心世界不久的将来会消失。移动 64 个盘子的塔所需的步骤数是 `2^64 -1 = 18,446,744,073,709,551,615264-1 = 18,446,744,073,709,551,615`。以每秒一次的速度，即`584,942,417,355584,942,417,355` 年！。
5+
虽然传说是有趣的，你不必担心世界不久的将来会消失。移动 64 个盘子的塔所需的步骤数是 `2^64 - 1 = 18,446,744,073,709,551,615264 - 1 = 18,446,744,073,709,551,615`。以每秒一次的速度，即 `584,942,417,355584,942,417,355` 年！。
66

77
Figure 1 展示了在从第一杆移动到第三杆的过程中的盘的示例。请注意，如规则指定，每个杆上的盘子都被堆叠起来，以使较小的盘子始终位于较大盘的顶部。如果你以前没有尝试过解决这个难题，你现在应该尝试下。你不需要花哨的盘子，一堆书或纸张都可以。
88

99
![4.10.汉诺塔游戏.figure1](assets/4.10.%E6%B1%89%E8%AF%BA%E5%A1%94%E6%B8%B8%E6%88%8F.figure1.png)
1010

11-
1211
*Figure 1*
1312

1413
我们如何递归地解决这个问题？我们的基本情况是什么？让我们从下到上考虑这个问题。假设你有一个五个盘子的塔，在杆一上。如果你已经知道如何将四个盘子移动到杆二上，那么你可以轻松地将最底部的盘子移动到杆三，然后再将四个盘子从杆二移动到杆三。但是如果你不知道如何移动四个盘子怎么办？假设你知道如何移动三个盘子到杆三;那么很容易将第四个盘子移动到杆二，并将它们从杆三移动到它们的顶部。但是如果你不知道如何移动三个盘子呢？如何将两个盘子移动到杆二，然后将第三个盘子移动到杆三，然后移动两个盘子到它的顶部？但是如果你还不知道该怎么办呢？当然你会知道移动一个盘子到杆三足够容易。这听起来像是基本情况。
@@ -21,27 +20,25 @@ Figure 1 展示了在从第一杆移动到第三杆的过程中的盘的示例
2120

2221
只要我们遵守规则，较大的盘子保留在栈的底部，我们可以使用递归的三个步骤，处理任何更大的盘子。上面概要中唯一缺失的是识别基本情况。最简单的汉诺塔是一个盘子的塔。在这种情况下，我们只需要将一个盘子移动到其最终目的地。 一个盘子的塔将是我们的基本情况。 此外，上述步骤通过在步骤1和3中减小塔的高度，使我们趋向基本情况。Listing 1 展示了解决汉诺塔的 Python 代码。
2322

24-
````
23+
```python
2524
def moveTower(height,fromPole, toPole, withPole):
2625
if height >= 1:
2726
moveTower(height-1,fromPole,withPole,toPole)
2827
moveDisk(fromPole,toPole)
2928
moveTower(height-1,withPole,toPole,fromPole)
30-
````
29+
```
30+
3131
*Listing 1*
3232

3333
请注意，Listing 1 中的代码与描述几乎相同。算法的简单性的关键在于我们进行两个不同的递归调用，一个在第 3 行上，另一个在第 5 行。在第 3 行上，我们将初始杆上的底部圆盘移动到中间。下一行简单地将底部盘移动到其最终的位置。然后在第 5 行上，我们将塔从中间杆移动到最大盘子的顶部。当塔高度为 0 时检测到基本情况; 在这种情况下不需要做什么，所以 `moveTower` 函数简单地返回。关于以这种方式处理基本情况的重点是，从 `moveTower` 简单地返回以使 `moveDisk` 函数被调用。
3434

3535
函数 `moveDisk`，如 Listing 2 所示，非常简单。它所做的就是打印出一个盘子从一杆移动到另一杆。 如果你输入并运行 `moveTower` 程序，你可以看到它给你一个非常有效的解决方案。
3636

37-
````
37+
```python
3838
def moveDisk(fp,tp):
3939
print("moving disk from",fp,"to",tp)
40-
````
40+
```
41+
4142
*Listing 2*
4243

4344
现在你已经看到了 `moveTower` 和 `moveDisk` 的代码，你可能会想知道为什么我们没有明确记录什么盘子在什么杆上的数据结构。这里有一个提示：如果你要明确地跟踪盘子，你会使用三个 Stack 对象，每个杆一个。 答案是 Python 提供了我们需要调用的隐含的栈。
44-
45-
46-
47-

‎4.递归/4.11.探索迷宫/README.md‎

Lines changed: 17 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -2,10 +2,8 @@
22

33
在这一节中，我们将讨论一个与扩展机器人世界相关的问题：你如何找到自己的迷宫？ 如果你在你的宿舍有一个扫地机器人（不是所有的大学生？）你希望你可以使用你在本节中学到的知识重新给它编程。 我们要解决的问题是帮助我们的乌龟在虚拟迷宫中找到出路。 迷宫问题的根源与希腊的神话有关，传说忒修斯被送入迷宫中以杀死人身牛头怪。忒修斯用了一卷线帮助他找到回去的退路，当他完成杀死野兽的任务。在我们的问题中，我们将假设我们的乌龟在迷宫中间的某处，必须找到出路。 看看 Figure 2，了解我们将在本节中做什么。
44

5-
65
![4.11.探索迷宫.figure2](assets/4.11.%E6%8E%A2%E7%B4%A2%E8%BF%B7%E5%AE%AB.figure2.png)
76

8-
97
*Figure 2*
108

119
为了使问题容易些，我们假设我们的迷宫被分成“正方形”。迷宫的每个正方形是开放的或被一段墙壁占据。乌龟只能通过迷宫的空心方块。 如果乌龟撞到墙上，它必须尝试不同的方向。乌龟将需要一个程序，以找到迷宫的出路。这里是过程：
@@ -36,7 +34,7 @@ Maze 类还重载索引运算符 `[]` ，以便我们的算法可以轻松访问
3634

3735
让我们来查看称为 `searchFrom` 的搜索函数的代码。代码如 Listing 3 所示。请注意，此函数需要三个参数：迷宫对象，起始行和起始列。 这很重要，因为作为递归函数，搜索在每次递归调用时开始。
3836

39-
````
37+
```python
4038
def searchFrom(maze, startRow, startColumn):
4139
maze.updatePosition(startRow, startColumn)
4240
# Check for base cases:
@@ -63,7 +61,8 @@ def searchFrom(maze, startRow, startColumn):
6361
else:
6462
maze.updatePosition(startRow, startColumn, DEAD_END)
6563
return found
66-
````
64+
```
65+
6766
*Listing 3*
6867

6968
你会看到代码的第一行（行 2）调用 `updatePosition`。这只是为了可视化算法，以便你可以看到乌龟如何探索通过迷宫。接下来算法检查四种基本情况中的前三种：乌龟是否碰到墙（行 5）？乌龟是否回到已经探索过的格子（行 8）？乌龟有没有到达出口（行 11）？如果这些条件都不为真，则我们继续递归搜索。
@@ -72,7 +71,7 @@ def searchFrom(maze, startRow, startColumn):
7271

7372
`Maze` 类的代码如 Listing 4，Listing 5 和 Listing 6 所示。`__init__` 方法将文件的名称作为其唯一参数。此文件是一个文本文件，通过使用 `+` 字符表示墙壁，空格表示空心方块，并使用字母 `S` 表示起始位置。Figure 3 是迷宫数据文件的示例。迷宫的内部表示是列表的列表。 `mazelist` 实例变量的每一行也是一个列表。此辅助列表使用上述字符，每格表示一个字符。Figure 3 中的数据文件，内部表示如下所示：
7473

75-
````
74+
```python
7675
[ ['+','+','+','+',...,'+','+','+','+','+','+','+'],
7776
['+',' ',' ',' ',...,' ',' ',' ','+',' ',' ',' '],
7877
['+',' ','+',' ',...,'+','+',' ','+',' ','+','+'],
@@ -84,13 +83,13 @@ def searchFrom(maze, startRow, startColumn):
8483
['+',' ','+','+',...,' ',' ','+',' ',' ',' ','+'],
8584
['+',' ',' ',' ',...,' ',' ','+',' ','+','+','+'],
8685
['+','+','+','+',...,'+','+','+',' ','+','+','+']]
87-
````
86+
```
8887

8988
`drawMaze` 方法使用这个内部表示在屏幕上绘制迷宫的初始视图。
9089

9190
Figure 3：示例迷宫数据文件
9291

93-
````
92+
```python
9493
++++++++++++++++++++++
9594
+ + ++ ++ +
9695
+ + + +++ + ++
@@ -102,14 +101,15 @@ Figure 3：示例迷宫数据文件
102101
+ +++++++ S + +
103102
+ + +++
104103
++++++++++++++++++ +++
105-
````
104+
```
105+
106106
*Figure 3*
107107

108108
如 Listing 5 所示，`updatePosition` 方法使用相同的内部表示来查看乌龟是否遇到了墙。它还用 `.` 或 `-` 更新内部表示，以表示乌龟已经访问了特定格子或者格子是死角。 此外，`updatePosition` 方法使用两个辅助方法`moveTurtle` 和 `dropBreadCrumb` 来更新屏幕上的视图。
109109

110110
最后，`isExit` 方法使用乌龟的当前位置来检测退出条件。退出条件是当乌龟已经到迷宫的边缘时，即行零或列零，或者在最右边列或底部行。
111111

112-
````
112+
```python
113113
class Maze:
114114
def __init__(self,mazeFileName):
115115
rowsInMaze = 0
@@ -140,10 +140,11 @@ class Maze:
140140
-(rowsInMaze-1)/2-.5,
141141
(columnsInMaze-1)/2+.5,
142142
(rowsInMaze-1)/2+.5)
143-
````
143+
```
144+
144145
*Listing 4*
145146

146-
````
147+
```python
147148
def drawMaze(self):
148149
for y in range(self.rowsInMaze):
149150
for x in range(self.columnsInMaze):
@@ -195,10 +196,11 @@ def updatePosition(self,row,col,val=None):
195196

196197
if color:
197198
self.dropBreadcrumb(color)
198-
````
199+
```
200+
199201
*Listing 5*
200202

201-
````
203+
```python
202204
def isExit(self,row,col):
203205
return (row == 0 or
204206
row == self.rowsInMaze-1 or
@@ -207,9 +209,6 @@ def isExit(self,row,col):
207209

208210
def __getitem__(self,idx):
209211
return self.mazelist[idx]
210-
````
211-
*Listing 6*
212-
213-
214-
212+
```
215213

214+
*Listing 6*

‎4.递归/4.12.动态规划/README.md‎

Lines changed: 14 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414

1515
执行我们刚才描述的算法如 Listing 7 所示。在第 3 行，我们检查基本情况;也就是说，我们正试图支付硬币的确切金额。如果我们没有等于找零数量的硬币，我们递归调用每个小于找零额的不同的硬币值。第 6 行显示了我们如何使用列表推导将硬币列表过滤到小于当前找零的硬币列表。递归调用也减少了由所选硬币的值所需要的总找零量。递归调用在第 7 行。注意在同一行，我们将硬币数 `+1` ，以说明我们正在使用一个硬币的事实。
1616

17-
```` python
17+
```python
1818
def recMC(coinValueList,change):
1919
minCoins = change
2020
if change in coinValueList:
@@ -27,7 +27,8 @@ def recMC(coinValueList,change):
2727
return minCoins
2828

2929
print(recMC([1,5,10,25],63))
30-
````
30+
```
31+
3132
*Listing 7*
3233

3334
Listing 7 中的算法是非常低效的。事实上，它需要 `67,716,925` 个递归调用来找到 4 个硬币的最佳解决 63 美分问题的方案。要理解我们方法中的致命缺陷，请参见 Figure 5，其中显示了 377 个函数调用所需的一小部分，找到支付 26 美分的最佳硬币。
@@ -36,12 +37,11 @@ Listing 7 中的算法是非常低效的。事实上，它需要 `67,716,925`
3637

3738
![4.12.动态规划.figure5](assets/4.12.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92.figure5.png)
3839

39-
4040
*Figure 5*
4141

4242
减少我们工作量的关键是记住一些过去的结果，这样我们可以避免重新计算我们已经知道的结果。一个简单的解决方案是将最小数量的硬币的结果存储在表中。然后在计算新的最小值之前，我们首先检查表，看看结果是否已知。如果表中已有结果，我们使用表中的值，而不是重新计算。 ActiveCode 1 显示了一个修改的算法，以合并我们的表查找方案。
4343

44-
```` python
44+
```python
4545
def recDC(coinValueList,change,knownResults):
4646
minCoins = change
4747
if change in coinValueList:
@@ -59,7 +59,8 @@ def recDC(coinValueList,change,knownResults):
5959
return minCoins
6060

6161
print(recDC([1,5,10,25],63,[0]*64))
62-
````
62+
```
63+
6364
*ActiveCode 1*
6465

6566
注意，在第 6 行中，我们添加了一个测试，看看我们的列表是否包含此找零的最小硬币数量。如果没有，我们递归计算最小值，并将计算出的最小值存储在列表中。使用这个修改的算法减少了我们需要为四个硬币递归调用的数量，63美分问题只需 221 次调用！
@@ -79,7 +80,7 @@ print(recDC([1,5,10,25],63,[0]*64))
7980

8081
Listing 8 用一个动态规划算法来解决我们的找零问题。 `dpMakeChange` 有三个参数：一个有效硬币值的列表，我们要求的找零额，以及一个包含每个值所需最小硬币数量的列表。 当函数完成时，`minCoins` 将包含从 0 到找零值的所有值的解。
8182

82-
````
83+
```python
8384
def dpMakeChange(coinValueList,change,minCoins):
8485
for cents in range(change+1):
8586
coinCount = cents
@@ -88,7 +89,8 @@ def dpMakeChange(coinValueList,change,minCoins):
8889
coinCount = minCoins[cents-j]+1
8990
minCoins[cents] = coinCount
9091
return minCoins[change]
91-
````
92+
```
93+
9294
*Listing 8*
9395

9496
注意，`dpMakeChange` 不是递归函数，即使我们开始使用递归解决这个问题。重要的是要意识到，你可以为问题写一个递归解决方案但并不意味着它是最好的或最有效的解决方案。在这个函数中的大部分工作是通过从第 4 行开始的循环来完成的。在这个循环中，我们考虑使用所有可能的硬币对指定的金额进行找零。就像我们上面的 11 分的例子，我们记住最小值，并将其存储在我们的 `minCoins` 列表。
@@ -99,7 +101,7 @@ ActiveCode 2 展示了 `dpMakeChange` 算法修改为跟踪使用的硬币，以
99101

100102
注意，我们打印的硬币直接来自 `coinsUsed` 数组。对于第一次调用，我们从数组位置 `63` 开始，然后打印 `21`。然后我们取 `63-21 = 42`，看看列表的第 42 个元素。我们再次找到 21 存储在那里。 最后，数组第 21 个元素21 也包含 21，得到三个 21。
101103

102-
````
104+
```python
103105
def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
104106
for cents in range(change+1):
105107
coinCount = cents
@@ -133,10 +135,11 @@ def main():
133135
print(coinsUsed)
134136

135137
main()
136-
````
138+
```
139+
137140
*AcitveCode 2*
138141

139-
````
142+
```python
140143
Making change for 63 requires
141144
3 coins
142145
They are:
@@ -145,6 +148,4 @@ They are:
145148
21
146149
The used list is as follows:
147150
[1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]
148-
````
149-
150-
151+
```

‎4.递归/4.13.总结/README.md‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,4 +8,3 @@
88
* 递归在某些情况下可以代替迭代。
99
* 递归算法通常可以自然地映射到你尝试解决的问题的表达式。
1010
* 递归并不总是答案。有时，递归解决方案可能比迭代算法在计算上更昂贵。
11-

‎4.递归/4.2.什么是递归/README.md‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,3 @@
11
## 4.2.什么是递归
22

33
**递归**是一种解决问题的方法，将问题分解为更小的子问题，直到得到一个足够小的问题可以被很简单的解决。通常递归涉及函数调用自身。递归允许我们编写优雅的解决方案，解决可能很难编程的问题。
4-
5-

‎4.递归/4.3.计算整数列表和/README.md‎

Lines changed: 30 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
我们将以一个简单的问题开始，你已经知道如何不使用递归解决。 假设你想计算整数列表的总和，例如：`[1,3,5,7,9]`。 计算总和的迭代函数见ActiveCode 1。函数使用累加器变量（`theSum`）来计算列表中所有整数的和，从 0 开始，加上列表中的每个数字。
44

5-
````
5+
```python
66
def listsum(numList):
77
theSum = 0
88
for i in numList:
@@ -11,48 +11,64 @@ def listsum(numList):
1111

1212
print(listsum([1,3,5,7,9]))
1313

14-
````
14+
```
15+
1516
*Activecode 1*
1617

1718
假设没有 `while` 循环或 `for` 循环。你将如何计算整数列表的总和？如果你是一个数学家，你可能开始回忆加法是一个函数，这个函数定义了两个整数类型的参数。故将列表和问题从加一个列表重新定义为加一对整数，我们可以把列表重写为一个完全括号表达式。如下所示：
18-
![4.3.计算整数列表和.1](assets/4.3.%E8%AE%A1%E7%AE%97%E6%95%B4%E6%95%B0%E5%88%97%E8%A1%A8%E5%92%8C.1.png)
19+
20+
$$
21+
((((1+3)+5)+7)+9)
22+
$$
1923

2024
我们也可以把表达式用另一种方式括起来
21-
![4.3.计算整数列表和.2](assets/4.3.%E8%AE%A1%E7%AE%97%E6%95%B4%E6%95%B0%E5%88%97%E8%A1%A8%E5%92%8C.2.png)
25+
26+
$$
27+
(1+(3+(5+(7+9))))
28+
$$
2229

2330
注意，最内层的括号（7 + 9）我们可以没有循环或任何特殊的结构来解决它。 事实上，我们可以使用以下的简化序列来计算最终的和。
24-
![4.3.计算整数列表和.3](assets/4.3.%E8%AE%A1%E7%AE%97%E6%95%B4%E6%95%B0%E5%88%97%E8%A1%A8%E5%92%8C.3.png)
2531

26-
我们如何能把这个想法变成一个 Python 程序？ 首先，让我们以 Python 列表的形式重述求和问题。 我们可以说列表 `numList` 的和是列表的第一个元素`numList[0]` 和列表其余部分`numList [1:]` 之和的总和。 以函数形式表述：
27-
![4.3.计算整数列表和.4](assets/4.3.%E8%AE%A1%E7%AE%97%E6%95%B4%E6%95%B0%E5%88%97%E8%A1%A8%E5%92%8C.4.png)
32+
$$
33+
\begin{aligned}
34+
total=(1+(3+(5+(7+9))))&\\
35+
total=(1+(3+(5+16)))&\\
36+
total=(1+(3+21))&\\
37+
total=(1+24)&\\
38+
total=25&
39+
\end{aligned}
40+
$$
41+
42+
我们如何能把这个想法变成一个 Python 程序？ 首先，让我们以 Python 列表的形式重述求和问题。 我们可以说列表 `numList` 的和是列表的第一个元素`numList[0]` 和列表其余部分`numList[1:]` 之和的总和。 以函数形式表述：
43+
44+
$$
45+
listSum(numList)=first(numList)+listSum(numList)
46+
$$
2847

2948
在这个方程式中，`first(numList)` 返回列表的第一个元素，`rest(numList)` 返回除第一个元素之外的所有元素列表。这很容易在 Python 中表示，如 ActiveCode 2 中所示。
3049

31-
````
50+
```python
3251
def listsum(numList):
3352
if len(numList) == 1:
3453
return numList[0]
3554
else:
3655
return numList[0] + listsum(numList[1:])
3756

3857
print(listsum([1,3,5,7,9]))
39-
````
58+
```
59+
4060
*Active code 2*
4161

4262
在这个清单中有几个关键地方。 首先，在第 2 行，我们检查列表是否为一个元素。这个检查是至关重要的，是我们的函数的转折子句。 长度为 1 的列表和是微不足道的; 它只是列表中的数字。 第二，在第 5 行函数调用自己！ 这就是我们称 listum 算法递归的原因。递归函数是调用自身的函数。
4363

4464
Figure 1 展示了对列表`[1,3,5,7,9]` 求和所需的一系列递归调用。 你应该把这一系列的调用想象成一系列的简化。 每次我们进行递归调用时，我们都会解决一个较小的问题，直到达到问题不能减小的程度。
45-
![4.3.计算整数列表和.figure1](assets/4.3.%E8%AE%A1%E7%AE%97%E6%95%B4%E6%95%B0%E5%88%97%E8%A1%A8%E5%92%8C.figure1.png)
4665

66+
![4.3.计算整数列表和.figure1](assets/4.3.%E8%AE%A1%E7%AE%97%E6%95%B4%E6%95%B0%E5%88%97%E8%A1%A8%E5%92%8C.figure1.png)
4767

4868
*Figure 1*
4969

5070
当我们到达简单问题的点，我们开始拼凑每个小问题的答案，直到初始问题解决。Figure 2 展示了在 `listsum` 通过一系列调用返回的过程中执行的 add 操作。当 `listsum` 从最顶层返回时，我们就有了整个问题的答案。
5171

5272
![4.3.计算整数列表和.figure2](assets/4.3.%E8%AE%A1%E7%AE%97%E6%95%B4%E6%95%B0%E5%88%97%E8%A1%A8%E5%92%8C.figure2.png)
5373

54-
5574
*Figure 2*
56-
57-
58-

‎4.递归/4.3.计算整数列表和/assets/4.3.计算整数列表和.1.png‎

-6.83 KB
Binary file not shown.

‎4.递归/4.3.计算整数列表和/assets/4.3.计算整数列表和.2.png‎

-6.51 KB
Binary file not shown.

‎4.递归/4.3.计算整数列表和/assets/4.3.计算整数列表和.3.png‎

-19.4 KB
Binary file not shown.

0 commit comments

Comments
 (0)