如何避免不停止功能？

Question

我试图在Python(或伪代码)中找到一个编写高级函数的算法 - 不必停止 - 对于给定的函数列表[f1,...,fn]和给定的函数输入列表[x1,...,xn]仅打印一次fi(xj)(表示所有功能和输入对).

当然,实现这一点的天真建议是:

for f in lst1:
   for x in lst2:
      f(x)

但问题是,某些功能可能会在某些输入上永远循环.

我被允许使用一个步进器(它有一个step()方法,每次调用该函数的一个后续计算步骤)

我只需要一个关于如何做的想法或算法.

Answer 1

一般的概念是鸠尾榫.您可以交替使用各种替代方法,而不是尝试运行每个替代方案.例如,给定三个计算c1,c2,c3:

• 执行c1的步骤1
• 运行c2的第1步
• 运行c3的第1步
• 执行c1的第2步
• 运行c2的步骤2,它终止
• 运行c3的第2步
• 执行c1的第3步
• 运行c3的第3步
• ...

如果计算停止,则该过程在有限时间内达到其停止状态,而不管有多少其他计算没有停止.以这种方式运行k计算仅将每个计算减慢k倍.由于这可能是功课,我不会详细说明如何将其应用于您的具体问题.

当然,如果任何计算没有停止,这不会停止.这是不可避免的(参见停机问题),而不是一个问题,因为你与那些完成做停止(在你的情况:他们的输出结果),你输入一个徒劳的无限循环之前.