ch07.md · 天津大学-刘昉/juliabasics

# 迭代

本章介绍迭代，有关重复执行语句块的能力。在5.8节中，我们已经通过使用递归见到了一种迭代。在4.2节中，通过使用 `for` 循环，我们见到了另外一种类型。本章，我们再介绍一种类型，使用 `while` 语句。但首先我想再谈谈变量的赋值。

---

## 重赋值

也许你已经发现，可以对同一个变量进行多次赋值。一次新的赋值使一个已经存在的变量指向一个新值（停止指向老值）。

```julia {.numberLines}
julia> x = 5
5
julia> x = 7
7
```

第一次显示 `x` 时，它的值是5；第二次，它的值是7。*重赋值*的状态图如下图。

![x的状态图](./pictures/merreas.png "Spiral")

在这里，需要说明一下容易混淆的地方。由于Julia使用等号（`=`）进行赋值，因此不能将 `a=b` 解释成数学表达式中的相等断言（即声明 `a` 和 `b` 是相等的）。

首先，相等是对称关系而赋值则不是。例如，在数学中，如果$a=7$，那么$7=a$。但在Julia中语句 `a=7` 是正确的，`7=a` 不正确。

同时，在数学中，相等断言永远为真或假。如果当前$a=b$，那么$a$将永远与$b$相等。在Julia中赋值语句能使两个变量相等，但它们不必总是保持那种状态：

```julia {.numberLines}
julia> a = 5
5
julia> b = a    # a and b are now equal
5
julia> a = 3    # a and b are no longer equal
3
julia> b
5
```

第5行改变了 `a` 的值但没有改变 `b` 的值，因此它们不再相等。

>对变量重新赋值常常非常有用，但要小心使用。如果变量值频繁变化，会使程序难于阅读和调试。
>定义一个与变量同名的函数是非法的。

---

## 更新变量

重赋值的一种常见形式是更新，也即变量的新值依赖于旧值。

```julia {.numberLines}
julia> x = x + 1
8
```

它的含义是“获取 `x` 的当前值，加1，然后以新值更新 `x`。”

如果你试图更新一个不存在的变量，你会得到一个错误，因为Julia先计算等号右侧的值，然后再将它赋给左侧的变量：

```julia {.numberLines}
julia> y = y + 1
ERROR: UndefVarError: y not defined
```

你也应该可以判断出，赋值运算符 `=` 是右结合的：

```julia {.numberLines}
julia> Base.operator_associativity(:(=))
:right
```

在更新一个变量前，你必须先对它进行初始化，通常使用一个简单的赋值语句：

```julia {.numberLines}
julia> y = 0
0
julia> y = y + 1
1
```

对一个变量加1进行更新称为*递增*；减1称为*递减*。

---

## `While` 语句

计算机常用来自动完成循环任务。重复同样的或相似的任务而不出错，这点恰恰是计算机的强项，人类的弱项。在计算程序中，重复也叫做*迭代*。

我们已经见过两个函数，`countdown` 和 `printn`，它们使用递归来迭代。因为迭代非常普遍，Julia提供了相应的语言特点来使它变得简单。其中之一是我们在4.2节里见到的 `for` 语句。后面我们会再次用到它。

另外一个是 `while` 语句。下面是使用 `while` 语句的 `countdown` 版本：

```julia {.numberLines}
function countdown(n)
    while n > 0
        print(n, " ")
        n = n - 1
    end
    println("Blastoff!")
end
```

你会发现 `while` 语句读起来就像英语一样。它的含义是，“当 `n` 大于0时，显示 `n` 值，然后对 `n` 做递减。当达到0时，显示单词Blastoff！”。

更一般地，`while` 语句的执行流程如下：

1. 判断条件是真还是假。
2. 如果为假，退出 `while` 语句，继续执行后面的语句。
3. 如果条件为真，运行主体，然后返回到步骤 1。

这种流程叫做循环，因为第三步循环返回到了顶部。

循环的主体应该改变一个或几个变量，使条件最终变成“假”来结束循环。否则循环会永远重复下去，这称为*无限循环*。对于计算机科学家来说，一个无穷的乐趣就是观看洗发水上的说明：“洗漱，冲洗，重复”，实际上它是一个无限循环。

>国外厂商为了防止有人误（或有意）服用洗发水而受到控告，形成了这样一个看起来好像很幼稚可笑的说明书。

在 `countdown` 的例子中，我们可以证明循环会停止：如果 `n` 为0或负数，循环从不执行。否则，每次循环，`n` 值都会变小，直到为0。

对于有些循环，却并不容易判断。例如：

```julia {.numberLines}
function seq(n)
    while n != 1
        println(n)
        if n % 2  == 0      # n is even
            n = n / 2
        else                # n is odd
            n = 3n + 1
        end
    end
end
```

这个循环的条件是 `n!=1`，因此循环会一直执行到 `n` 等于1，这使得条件为假。

每次循环，程序输出 `n` 值然后检查它的奇偶性。如果为偶数，将 `n` 除以2。如果是奇数，以 `3n+1` 替换 `n`。例如，如果输入参数是3，`n` 的结果是3，10，5，16，8，4，2，1。

由于 `n` 有时增大有时减小，因此很难证明 `n` 是否最终会变为1，或者程序是否会终止。对于一些特殊的 `n` 值，我们可以证明循环会终止。例如，如果初始值是2的指数，每次循环过后 `n` 总是偶数，直到变为1。前面那个例子就是以16开始的这种数列形式结束的。

问题的难点在于是否我们可以证明对于所有正数 `n`，程序都会终止。目前，还没有人能够对该问题进行证实或证伪。

### 习题7-1

使用迭代重写5.9节中的函数 `printn`。

---

## `break`

有时，你事先并不知道什么时候要结束循环，而是在循环体内遇到特定的情况才结束。在这种情况下，你可以使用 `break` 语句来跳出循环。

例如，假设你想接受用户的输入，直到输入 `done` 来终止输入。你可以写成：

```julia {.numberLines}
while true
    print("> ")
    line = readline()
    if line == "done"
        break
    end
    println(line)
end
println("Done!")
```

循环条件为 `true`，也就是总为真，因此循环会一直执行直到遇到 `break` 语句。

每次循环，它以一个小三角符号，`>`，提示用户输入。如果用户输入 `done`，`break` 语句会退出循环。否则，程序会打印用户输入的任何东西，然后返回到循环的顶部。下面是一个执行实例：

```julia {.numberLines}
> not done
not done
> done
Done!
```

以这种方式写 `while` 循环是十分常见的，因为它允许你在任何地方检查条件（而不仅仅是在顶部），这样你就可以主动地设置停止条件（“当这种情况发生就停止”）而不是被动地停止（“直到那种情况发生前保持运行”）。

---

## `continue`

`break` 语句退出循环。但如果在循环体内遇到 `continue` 语句时，执行流程会略过当前循环体内的其他语句而直接跳到迭代的起始位置来开始下一次迭代。例如：

```julia {.numberLines}
for i in 1:10
    if i % 3 == 0
        continue
    end
    print(i, " ")
end
```

输出为：

```julia {.numberLines}
1 2 4 5 7 8 10
```

如果 `i` 可以被3整除，`continue` 语句停止当前迭代，并立即开始下一个迭代。在1到10的范围内，只打印不能被3整除的数字。

---

## 平方根

循环常常在程序中用来计算数值解，其方法是先假设一个近似解，然后通过循环不断改进这个解。

例如，计算平方根的一种方法是牛顿法。假设你需要计算 $a$ 的平方根。以任意估计解 $x$ 开始，你可以通过下面的公式计算一个更优的估计解：

$$y=\frac{1}{2}(x+\frac{a}{x})$$

例如，如果 $a$ 等于4，$x$ 等于3：

```julia {.numberLines}
julia> a = 4
4
julia> x = 3
3
julia> y = (x + a/x ) / 2
2.1666666666666665
```

结果更接近正确答案了（$\sqrt{4}=2$）。如果我们以新的估计解重复上面的过程，得到的结果更加接近：

```julia {.numberLines}
julia> x = y
2.1666666666666665
julia> y = (x + a/x ) / 2
2.0064102564102564
```

再经过几次更新，估计解就几乎等于真实解：

```julia {.numberLines}
julia> x = y
2.0064102564102564
julia> y = (x + a/x ) / 2
2.0000102400262145
julia> x = y
2.0000102400262145
julia> y = (x + a/x ) / 2
2.0000000000262146
```

一般来说，在得到正确答案前我们不知道需要重复多少次，但由于估计解最终会停止变化，因此我们知道这时已经得到了最终答案：

```julia {.numberLines}
julia> x = y
2.0000000000262146
julia> y = (x + a/x ) / 2
2.0
julia> x = y
2.0
julia> y = (x + a/x ) / 2
2.0
```

当 `y==x` 时，我们可以停止。下面是一个循环，它以初始估计值 `x` 开始，对估计值不断改进直到它停止变化：

```julia {.numberLines}
while true
    println(x)
    y = (x + a/x ) / 2
    if y == x
        break
    end
    x = y
end
```

对于大多数的 `a` 值，这段代码都工作良好，但一般来说对浮点数做相等比较是危险的。浮点数值只是近似正确的：大多数的有理数，像是 $\frac{1}{3}$，和无理数，像是 $\sqrt{2}$，都不能用 `Float64` 精确表示。

与其检验 `x` 和 `y` 是否精确相等，更好的做法是使用内置函数 `abs` 来计算两个数差值的绝对值或大小：

```julia {.numberLines}
if abs(y-x) < ɛ
    break
end
```

这里 `ɛ`（`\varepsilonTab`）可以设为像 `0.0000001` 这样的数值来确定多么接近才算是足够接近。

---

## 算法

牛顿法是*算法*的一个例子：它是求解一类问题的机械过程（在这个例子中，计算平方根值）。

为了解释什么叫做算法，我们可以先看看什么不是算法。当学习一位数的乘法时，你肯定背诵过乘法表。实际上，你记忆了100个特殊的结果。这种类型的知识就不是算法。

但如果你比较“懒”，你也许会学习一些小技巧。例如，为了得到$n$和9的乘积，你可以在十位上写上$n-1$，个位上写上$10-n$。这个小技巧对于计算任何一位数与9相乘都适用。这个就是一种算法！

相似地，我们在加法中用到的进位，减法中的借位和长除法都是算法。算法的一个特点是执行它们不需要任何智力。它们是机械的过程，按照算法列表中的步骤依次执行。

执行算法是很枯燥的，但设计算法是一个既有趣又富于智力挑战的事情，同时也是计算机科学的核心。

一些人们做起来很自然，没有什么困难或奇怪的事情，却很难用算法来实现。理解自然语言就是一个很好的例子。我们很自然地在做这件事情，但目前为止，还没有谁能够解释我们是*如何*做到这点的，或者至少在算法层面上无法实现。

---

## 调试

当你开始编写大型程序时，你会发现需要花费大量时间进行调试。更多的代码意味着更多的出错机会和更多隐藏错误的地方。

节省调试时间的一个有效方法是“二分调试法”。例如，在你的程序里有 100 行代码，如果每次检验一条，则需要100步。

相反的，如果将程序一分为二，在代码中部或靠近中部，选择一个中间变量的值进行检查，增加一条打印语句（或者其它具有检验效果的代码）并运行程序。

如果中间检测节点的结果是错误的，那么问题一定出现在程序的上半部分。如果结果正确，问题则在下半部分。

每使用一次这种方法，你需要检查的程序就会减半。经过6步后（代码数量小于100），至少在理论上，你就会把问题聚焦到一至两行代码上。

在实践中，并不能总是轻易地找到“程序的中间位置”，也不总是有可能对它进行检验。我们没有必要去数代码的行数然后找到确切的中点位置。相反，想想程序可能出错的地方和容易进行检查的位置。然后选择一个前后出错概率相等的位置进行检测。

---

## 术语

重赋值
: 对一个已经存在的变量赋予新值。

更新
: 变量的新值依赖于旧值的赋值语句。

初始化
: 给将要更新的变量一个初始值的赋值语句。

递增
: 更新一个变量，使其值增大（增幅通常为1）。

递减
: 更新一个变量，使其值减小。

迭代
: 使用递归函数或循环重复地执行一组语句。

`while` 语句
: 允许由条件控制的迭代语句。

`break` 语句
: 允许跳出循环的语句。

`continue` 语句
: 循环内允许跳到循环顶部，开始下一次迭代的语句。

无限循环
: 停止条件永远不被满足的循环。

算法
: 解决一类问题的通用过程。

---

## 习题

### 习题7-2

复制7.6节的循环并将它封装成名为 `mysqrt` 的函数，将 `a` 做为输入参数，选择合适的 `x`，返回 `a` 的平方根的一个估计值。

为了检验函数，写一个名为 `testsquareroot` 的函数，打印一个如下所示的表格：

``` 
a   mysqrt             sqrt               diff
-   ------             ----               ----
1.0 1.0                1.0                0.0
2.0 1.414213562373095  1.4142135623730951 2.220446049250313e-16
3.0 1.7320508075688772 1.7320508075688772 0.0
4.0 2.0                2.0                0.0
5.0 2.23606797749979   2.23606797749979   0.0
6.0 2.449489742783178  2.449489742783178  0.0
7.0 2.6457513110645907 2.6457513110645907 0.0
8.0 2.82842712474619   2.8284271247461903 4.440892098500626e-16
9.0 3.0                3.0                0.0
```

第一列是数 `a`；第二列是由 `mysqrt` 计算出来的平方根值；第三列是由 `sqrt` 计算出来的平方根值；第四列是两个估计差值的绝对值。

>可以使用 Julia 内置函数 `rpad` 实现快速排版。

**[参考答案](https://gitee.com/tju-liufang/juliabasics/tree/master/scr/mysqrt.jl)**

### 习题7-3

内置函数 `Meta.parse` 接受一个字符串并将它转换成表达式。在Julia中，这个表达式可以使用函数 `eval` 来计算。例如：

```julia {.numberLines}
julia> expr = Meta.parse("1+2*3")
:(1 + 2 * 3)
julia> eval(expr)
7
julia> expr = Meta.parse("sqrt(π)")
:(sqrt(π))
julia> eval(expr)
1.7724538509055159
```

写一个名为 `evalloop` 的函数，迭代等待用户输入，使用 `eval` 来计算输入表达式并打印结果。该过程一直持续下去直到用户输入 `done`，然后返回最后一个表达式的计算结果。

### 习题7-4

数学家 [Srinivasa Ramanujan](https://brilliant.org/wiki/srinivasa-ramanujan/) 发现可以使用一个无穷序列来近似得到$\frac{1}{π}$的值：

$$\frac{1}{π}=\frac{2\sqrt{2}}{9801}\sum\frac{(4k)!(1103+26390k)}{(k!)^4396^{4k}}$$

写一个名为 `estimatepi` 的函数，使用这个公式计算并返回 $π$ 的一个估计值。使用 `while` 循环计算求和符号中的项，直到最后一项小于 `1e-15`（在Julia中代表$10^{-15}$）。你可以与$π$比较来检验结果。

**[参考答案](https://gitee.com/tju-liufang/juliabasics/tree/master/scr/estimatepi.jl)**

天津大学-刘昉/juliabasics

简介

发行版

贡献者

语言

近期动态

天津大学-刘昉/juliabasics .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

语言

近期动态

搜索帮助

天津大学-刘昉/juliabasics