理解令人困惑的算法符号
Understanding confusing algorithm notation
我无法理解一本书在描述 prng 测试算法时使用的符号。以下是一些有问题的片段：
我的困惑是：j的意义是什么？它根本没有明确定义。它应该是向量的索引吗？那怎么不从0开始呢？
继续：
我知道左箭头是赋值。但是算法再次引用 j 并且仅引用 j0 和 j1。同样，它似乎是 j 的索引。但是后来我对 "Then for j <- j, j1 - 1 ..., j0 " 这一行感到特别困惑，因为它似乎指的是递减 j 的索引，但它是从 j 本身而不是下标中减去的。
非常感谢任何帮助，谢谢。
j 是一个虚拟变量。当您为 j0 <= j <= j1 编写 A[j] 时，它用作占位符来表示 A 在 j0 和 j1 之间的索引处的所有元素。
当您编写算法时，您可能会声明一个或多个循环变量来反映这一点。
在我看来，j 这里有多个独立的用法。这是数学家编写的 CS 文本的典型特征，他们——你可能会惊讶地发现——通常对他们的符号非常草率，期望 reader 能够吸引所有 排序 事物的含义和上下文。
在第一段中，作者使用 V[j] 来引用数组 的 20 元素向量 的任意元素（和 j 从零开始）。他们正在定义如何从一维随机数流填充这个固定宽度向量数组（您可能会发现将其视为二维数组会更舒服）。如果我明确地写出数组的前两行，也许会有帮助？
V0 = (Y0, Y1, Y2, ... Y19)
V1 = (Y20, Y21, Y22, ... Y39)
⋮
Vj = (Y[j*20], Y[j*20+1], ... Y[j*20+19])
在第二段中，A[j] 也是数组的任意元素，但它是一个不同的、不相关的浮点数数组。
在第三段和第四段中，j、j0和j1似乎是三个独立的索引变量，并且通过将算法塞入使情况更加混乱散文。作者应该使用伪代码并选择更好的变量名。这是生成伪代码版本的尝试 - 不过，我故意保留了错误的变量名，因此您可以看到对应关系。
Algorithm_S (m, n):
# S1: Initialize.
var A: float[n+1]
var j, j0, j1: int
for j in 0, 1, ..., n:
A[j] ← 0
A[1] ← 1
# S2: Update probabilities.
j0 ← 1
j1 ← 1
repeat n-1 times:
j1 ← j1 + 1
for j in j1, j1 - 1, ..., j0:
A[j] ← (j/m)*A[j] + (1 + 1/m - j/m)*A[j-1]
if A[j] < 1e-20:
A[j] ← 0
if j = j1: j1 ← j1 - 1
if j = j0: j0 ← j0 + 1
# S3: ...
我不确定这是否正确，因为即使像这样打开包装后它对我来说也没有多大意义。问题可能是你只引用了算法的前两步，所以我不知道这个 "auxiliary array of probabilities" 将用于什么，我不知道代码 是否应该 做它正在做的事。不用担心。
总而言之：您之所以感到困惑，是因为这本书令人困惑。不是你的错。我会建议你找一本不那么令人困惑的书，当你有更多的练习阅读数学期刊文章时，也许再回到这本书。
我无法理解一本书在描述 prng 测试算法时使用的符号。以下是一些有问题的片段：
我的困惑是：j的意义是什么？它根本没有明确定义。它应该是向量的索引吗？那怎么不从0开始呢？
继续：
我知道左箭头是赋值。但是算法再次引用 j 并且仅引用 j0 和 j1。同样，它似乎是 j 的索引。但是后来我对 "Then for j <- j, j1 - 1 ..., j0 " 这一行感到特别困惑，因为它似乎指的是递减 j 的索引，但它是从 j 本身而不是下标中减去的。
非常感谢任何帮助，谢谢。
j 是一个虚拟变量。当您为 j0 <= j <= j1 编写 A[j] 时，它用作占位符来表示 A 在 j0 和 j1 之间的索引处的所有元素。
当您编写算法时，您可能会声明一个或多个循环变量来反映这一点。
在我看来，j 这里有多个独立的用法。这是数学家编写的 CS 文本的典型特征，他们——你可能会惊讶地发现——通常对他们的符号非常草率，期望 reader 能够吸引所有 排序 事物的含义和上下文。
在第一段中，作者使用 V[j] 来引用数组 的 20 元素向量 的任意元素（和 j 从零开始）。他们正在定义如何从一维随机数流填充这个固定宽度向量数组（您可能会发现将其视为二维数组会更舒服）。如果我明确地写出数组的前两行，也许会有帮助？
V0 = (Y0, Y1, Y2, ... Y19)
V1 = (Y20, Y21, Y22, ... Y39)
⋮
Vj = (Y[j*20], Y[j*20+1], ... Y[j*20+19])
在第二段中，A[j] 也是数组的任意元素，但它是一个不同的、不相关的浮点数数组。
在第三段和第四段中，j、j0和j1似乎是三个独立的索引变量，并且通过将算法塞入使情况更加混乱散文。作者应该使用伪代码并选择更好的变量名。这是生成伪代码版本的尝试 - 不过，我故意保留了错误的变量名，因此您可以看到对应关系。
Algorithm_S (m, n):
# S1: Initialize.
var A: float[n+1]
var j, j0, j1: int
for j in 0, 1, ..., n:
A[j] ← 0
A[1] ← 1
# S2: Update probabilities.
j0 ← 1
j1 ← 1
repeat n-1 times:
j1 ← j1 + 1
for j in j1, j1 - 1, ..., j0:
A[j] ← (j/m)*A[j] + (1 + 1/m - j/m)*A[j-1]
if A[j] < 1e-20:
A[j] ← 0
if j = j1: j1 ← j1 - 1
if j = j0: j0 ← j0 + 1
# S3: ...
我不确定这是否正确，因为即使像这样打开包装后它对我来说也没有多大意义。问题可能是你只引用了算法的前两步，所以我不知道这个 "auxiliary array of probabilities" 将用于什么，我不知道代码 是否应该 做它正在做的事。不用担心。
总而言之：您之所以感到困惑，是因为这本书令人困惑。不是你的错。我会建议你找一本不那么令人困惑的书，当你有更多的练习阅读数学期刊文章时，也许再回到这本书。