IBM Ponder This #270 · 2020 年 10 月

本题纪念 Frances Allen 及其 1970 年论文 Control flow analysis。控制流图把单入口、单出口且内部不含跳转的代码块作为顶点，可能从一个块转到另一个块时连有向边。

使用以下玩具语言：赋值 X=Y；算术 X=Y OP Z，OP 可为 +、-、*、/、%；无条件跳转 JMP A；X 为零时跳转的 JMP_ZERO X A；必须处于程序最后一行的 RETURN X；以及随机跳向所列任一行的 CHAOS LINES。变量位置和常数按命令定义使用，每行先写行号。

构造至多二十行程序，以以下两行开始：

 10 A = a
 20 B = b

对任意整数 a>b，程序返回其最大公因数，同时控制流图中从入口到出口、长度为 $n$ 的路径数构成序列：

0, 2, 2, 5, 8, 17, 32, 65, 128, 257,...

参见 https://oeis.org/A052531。

附加问题：再构造一个求最大公因数的程序，使其入口到出口路径计数序列在前二十项内出现 1970。

以下为格式示例程序及其控制流图：

 10 A = 20
 20 B = 20
 30 C = A - B
 40 JMP_ZERO C 70
 50 C = A - 20
 60 CHAOS 30, 40, 80
 70 JMP 90
 80 JMP 30
 90 RETURN A

解答

认真尝试后再打开

待补充。