c - 编程难题 - 斐波那契

Question

这个问题之前有一些混淆。之前，发帖者和回复者认为这是一个计算第 n 个斐波纳契数的函数，但实际上它是计算第 n 个斐波纳契数的有效函数，作为 Stack Exchange 上 codegolf 的编程难题。

f(n){int i=1,j=0,k;for(;n;n-=k==i)for(j=i-j,i+=j,k=2;i%k&&k++<i;);return i;}

这是来自

的C 76字符示例

https://codegolf.stackexchange.com/questions/6994/find-the-nth-fibonnaci-prime-in-the-shortest-code

对于 32 位有符号整数，n 的范围是 1 到 10。前 10 个斐波那契素数是:2、3、5、13、89、233、1597、28657、514229、433494437。

问题是这个函数是如何工作的？

codegolf 上的原始来源不包含解释。这可能属于 codegolf，但上一个问题是在 SO 此处提出的，我希望上一个问题的发帖人能看到这个问题并得到他/她的问题的回答。

Answer 1

让我们先缩进:

int f(int n)
{
    int i = 1, j = 0, k;
    for (; n; n -= k == i)
        for (j = i - j, i += j, k = 2; i % k && k++ < i;) ;
    return i;
}

n对于合理的输入是非零的，所以第一个循环将执行。注意 k == i尚未评估，因为第一个 for 的正文必须先执行，所以 k 没关系未初始化。

要对此进行更多数学演示，请注意 j = f(0) = 0和 i = f(2) = 1是第一个和第三个斐波那契数列。以 n = 2 开头, j = f(n-2) = 0 , i = f(n) = 1 ，为了推进 j 和 i，我们有:

j = i - j = f(n) - f(n-2) = f(n-1)
i = i + j = f(n) + f(n-1) = f(n+1)
n = n + 1

对于每个外循环，i和 j在内部循环的初始化中前进到下一个斐波那契数。

j =  1 == f(1), i =  2 == f(3)
j =  1 == f(2), i =  3 == f(4)
j =  2 == f(3), i =  5 == f(5)
j =  3 == f(4), i =  8 == f(6)
j =  5 == f(5), i = 13 == f(7)

这证实了我们的模式:我们可以从前几次迭代中看到 i比j提前两步.

i % k && k++ < i

这只是一个素数测试:它在 k 时停止等于i (如果 i 是质数，就会发生这种情况——而且 k++ < i 在技术上永远不会不为真，因为第一个条件将首先评估为假，但它有一个有用的副作用)或当 k 时是 i 的适当除数(所以 i 不是质数)。这不是最有效的方法，但它确实有效。

放 k++在 for 的条件部分loop 具有正确递增它并保存更多字符的效果(好吧，我认为只有一个)。

n -= k == i

如果i不是质数，这不会改变n ，因此将检查下一个斐波那契数列(因为 i 遍历斐波那契数列)。如果i是质数，然后递减 n ，它会倒数我们找到的斐波那契素数的数量，并且无论如何都会检查下一个素数。当它到达 0 , 我们会找到 n

The question is how does this function work?

它的工作原理是按顺序计算斐波那契数并测试每个数的素数，直到找到 n这样的素数。

稍微清理一下代码，就没什么特别的了。大部分只是很多人会写的蛮力算法，尽管由于素数检查而效率较低，并且由于想要保存尽可能多的字符而更难阅读。

最突出的部分是 i 的计算和 j ，其中 i比 j 提前两步.这个技巧可能也有保存最多字符的效果。