数学女孩4：随机算法最新章节_结城浩著_掌阅小说网

下载掌阅APP，畅读海量书库

立即打开

畅读海量书库

扫码下载掌阅APP

2.1.4　逐行调试

从现在开始，我们要利用一个测试用例——具体的输入——来一步一步地运行顺序查找算法的流程，这叫作逐行调试该算法。逐行调试的英文为walk through，也就是“一步一步运行”的意思。

测试用例如下，算法的输入为：

$\begin{cases}A={31,41,59,26,53\}\\n=5\\v=26\end{cases}$

也就是从

A[1]=31,A[2]=41,A[3]=59,A[4]=26,A[5]=53

这5个数中通过顺序查找算法来查找26这个数。

从行L1开始运行顺序查找算法的流程。

$\underline{\textcircled{1}~{\rm L1}:\mathbf{precedure}~{\rm LINEAR-SEARCH}(A,n,v)}$

这一行的意思是：名为LINEAR-SEARCH的流程即将开始。流程用英语表示为procedure。此外，这一行还表示该流程被给予了输入、和。

接着运行下一行L2。

$\underline{\textcircled{2}~{\rm L2}:k\leftarrow 1}$

在这一行，我们将变量赋值为1。运行这一行后，变量的值变为1。

变量表示我们正在注视数列中的第个数。

接着运行下一行L3。

$\underline{\textcircled{3}~{\rm L3}:\mathbf{while}~k\leqslant n~\mathbf{do}}$

在这一行，我们将判断循环的条件。关键字 $\mathbf{while}$ 表示，在满足条件期间，循环运行从 $\mathbf{while}$ 至 $\mathbf{end-while}$ 的各行。此处的条件为“ $k\leqslant n$ ”。

因为变量表示数列的大小，所以条件 $k\leqslant n$ 表示“将注视的位置限定在数列的范围内”。严格来说条件应该为 $1\leqslant k\leqslant n$ ，但因为变量从1开始增加，所以只要将的上限设为即可。

此时，因为 k=1,n=5 ，所以满足条件 $k\leqslant n$ 。

因为满足条件，接着运行下一行L4。

$\underline{\textcircled{4}~{\rm L4}:\mathbf{if}~A[k]=v~\mathbf{then}}$

在这一行，我们将判断条件。关键字 $\mathbf{if}$ 表示，只有满足条件时，流程才会运行从 $\mathbf{if}$ 至 $\mathbf{end-if}$ 的各行。此处的条件为 A[k]=v 。

条件 A[k]=v 表示“正在注视的数与要查找的数相等”。

因为此时 k=1 ，根据输入的数列得出 A[k]=A[1]=31 ，即 A[k]=31 ，而 v=26 ，不满足条件 A[k]=v 。

数列的第1个数并不是我们想要查找的数。

因为不满足条件，所以直到 $\mathbf{end-if}$ 的所有行都要跳过。

这样，我们“嘣”地就跳到了行L7。

$\underline{\textcircled{5}~{\rm L7}:k\leftarrow k+1}$

在这一行，我们将式子 k+1 赋值给变量。当前 k=1 ，因此式子 k+1 的值为2，变量的值由1变为2。

这样，我们注视的位置就向后移动了一位。

接着运行下一行L8。

$\underline{\textcircled{6}~{\rm L8}:\mathbf{end-while}}$

这一行的 $\mathbf{end-while}$ 与行L3的 $\mathbf{while}$ 相对应。

现在返回至行L3。

◎　　◎　　◎

“泰朵拉，你真是用心学习了啊。”我佩服地说。

“有、有吗……”泰朵拉支支吾吾，脸红红的。

“你穿插着解释了形式和含义，也就是程序字面上的意思和算法的思想，这样的讲解方式非常有趣。”

“啊……”面对突如其来的夸奖，泰朵拉好像不知道说什么好。

“但是，还是觉得好麻烦啊。”我一边说，一边看着泰朵拉的笔记本，上面详细记录着伪代码的说明。

“确实呢。不过只要下定决心，一边记录变量的值，一边按部就班地运行，也没有那么麻烦啦……”

“Continue。”理纱说。

◎　　◎　　◎

$\underline{\textcircled{7}~{\rm L3}:\mathbf{while}~k\leqslant n~\mathbf{do}}$

回到行L3，重新判断循环条件。

现在，因为 k=2,n=5 ，所以满足条件 $k\leqslant n$ 。

接着运行下一行L4。

$\underline{\textcircled{8}~{\rm L4}:\mathbf{if}~A[k]=v~\mathbf{then}}$

再一次判断条件，现在变量的值等于2，不满足条件 A[k]=v ，因为此时 A[2] 作为输入其值为41，而的值为26。

数列的第2个数也不是我们想要查找的数。

因此，我们跳过行L5和行L6，直接转到行L7。

$\underline{\textcircled{9}~{\rm L7}:k\leftarrow k+1}$

变量的值再次增加1，现在变量的值变为3。

接着运行下一行L8。

$\underline{\textcircled{10}~{\rm L8}:\mathbf{end-while}}$

再一次回到行L3。

◎　　◎　　◎

“重复做同一件事情呢。”我说。

“嗯。”泰朵拉接着说，“但是的值增加了吧。”

“Continue。”理纱的语气毫无起伏。

◎　　◎　　◎

$\underline{\textcircled{11}~{\rm L3}:\mathbf{while}~k\leqslant n~\mathbf{do}}$

现在，因为 k=3,n=5 ，所以满足条件 $k\leqslant n$ 。

接着运行下一行L4。

$\underline{\textcircled{12}~{\rm L4}:\mathbf{if}~A[k]=v~\mathbf{then}}$

现在 k=3 ，不满足条件 A[k]=v ，因为此时 A[3] 作为输入其值为59，而的值为26。

跳转至行L7。

$\underline{\textcircled{13}~{\rm L7}:k\leftarrow k+1}$

变量的值变为4。

接着运行下一行L8。

$\underline{\textcircled{14}~{\rm L8}:\mathbf{end-while}}$

再一次回到行L3。

◎　　◎　　◎

“还在重复做同一件事情呢。”我说。

“嗯。”泰朵拉接着说，“但是，的值在增加啊。”

“Continue。”理纱的语气依旧毫无起伏。

◎　　◎　　◎

$\underline{\textcircled{15}~{\rm L3}:\mathbf{while}~k\leqslant n~\mathbf{do}}$

现在 k=4 ，满足条件 $k\leqslant n$ 。

接着运行下一行L4。

$\underline{\textcircled{16}~{\rm L4}:\mathbf{if}~A[k]=v~\mathbf{then}}$

现在 k=4 ，条件 A[k]=v 成立！因为 A[4] 的值与26相等，我们终于满足了 $\mathbf{if}$ 的条件。

向行L5前进。

$\underline{\textcircled{17}~{\rm L5}:\mathbf{return}}$ “能找到”

$\mathbf{return}$ 是表示本流程输出的关键字。我们将运行结果设置为“能找到”，然后跳转至行L10： $\mathbf{end-procedure}$ 。

$\underline{\textcircled{18}~{\rm L10}:\mathbf{end-procedure}}$

至此，LINEAR-SEARCH流程结束。

好，就像这样，经过从 $\textcircled{1}$ 到 $\textcircled{18}$ 总共18个步骤，算法运行完成。由输入的值 $A={31,41,59,26,53\},n=5,v=26$ 得到的输出为“能找到”。

◎　　◎　　◎

“真是辛苦啊。”我说。

“呼……是啊。”泰朵拉说，“仅仅是为了判断‘在 ${31,41,59,26,53\}$ 中是否存在26’，就要下这么一番工夫，变量的值也在流程运行过程中改变了很多次，真是烦琐。”

“那么具体的动作是怎样的呢？”

“嗯，现在我们按逐行调试时的运行顺序给各行标上序号，就像这样。这便是旅行的足迹，对吧！”

逐行调试顺序查找算法

（输入为 $A={31,41,59,26,53\},n=5,v=26$ ）

“原来如此……”

“计算机先生真厉害！无论重复多少遍相似的工作也不会厌倦。”

“呃，其实我觉得泰朵拉你的毅力也很值得钦佩。”我说。

“泰朵拉计算机。”理纱说。

点击中间区域
呼出菜单

购买书籍时，会优先扣除您的代金券，再扣除阅饼；当您的余额不足时，可使用微信或支付宝支付，补足差价；
连载书籍勾选自动购买下一章后，会自动扣费，已购章节不会重复扣费；
书籍购买记录请至我的—购书记录中查询

上一章

目录

下一章

×