想象一下,有两组相同大小的数字。
是否有可能以及如何创建一个函数、算法或子程序,将输入项精确映射到输出项?喜欢:
Input = 1, 2, 3, 4
Output = 2, 3, 4, 5
功能是:
f(x): return x + 1
我所说的“功能”是指比 [1] 稍微复杂一些的东西:
f(x):
if x == 1: return 2
if x == 2: return 3
if x == 3: return 4
if x == 4: return 5
这对于创建特殊的哈希函数或函数近似很有用。
更新:
我想问的是,是否有一种方法可以压缩上面 [1] 中那个简单的映射示例。
最佳答案
找到输出某些字符串(序列,函数等)的最短程序等效于找到其Kolmogorov complexity,这是不确定的。
如果“不可能”不是一个令人满意的答案,你必须限制你的问题。在所有适当限制的情况下(多项式、有理函数、线性递归),只要您了解自己在做什么,就可以轻松找到最佳算法。例子:
在多项式序列的情况下,考虑序列bn=an+1-an通常会有所帮助;这将二次关系简化为线性关系,将线性关系简化为常数序列等。但没有 Elixir 。您可能会使用遗传算法,随机猜测,检查许多内置序列及其组成等来构建一些启发式方法(例如Mathematica的FindSequenceFunction-检查该页面以了解其复杂程度)。无论如何,由于 Kolmogorov 复杂性的不可判定性,任何这样的程序——理论上——都离完美很远。在实践中,您可能会得到令人满意的结果,但这需要很多人年。
另见 another SO question 。您还可以在应用程序中为 OEIS 实现一些包装器。
领域:
大多数情况下,可以做的事情的限制在
与信息论密切相关的是编码理论,它描述了纠错码。示例结果:可以将 4 位编码为 7 位,以便可以检测和纠正任何单个错误,或检测两个错误 ( Hamming(7,4) )。
“积极”的一面是:
用于拉格朗日插值和帕德逼近的
关于algorithm - 为给定的输入和输出创建函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1539286/