0

我有这个代码：

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"

#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;

__fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { }

int Fibonacci(int nNumber) {
    if (nNumber == 0)
        return 0;
    if (nNumber == 1)
        return 1;

    return Fibonacci(nNumber-1) + Fibonacci(nNumber-2);
}

void __fastcall TForm1::Button1Click(TObject *Sender) {
    int k=0;
    int val;

    k = StrToInt(Edit1->Text);

    for (int i=0; i < k; i++) {
        val =  Fibonacci(i);
        Form1->ListBox1->Items->Add("F"+IntToStr(i)+"-->"+IntToStr(val));
    }
}

如何制作 2 个线程来分别计算和打印斐波那契数列的偶数和奇数索引数？

这是 Builder 6 中的练习。

4

2 回答 2

3

您可以使用仅使用偶数或奇数元素的斐波那契数的公式。开发这个公式：

f(n) = f(n-1) + f(n-2) [1]
f(n-1) = f(n-2) + f(n-3) [2]
f(n-2) = f(n-3) + f(n-4) [3]

Combining [1] and [2]:
f(n) = 2 * f(n-2) + f(n-3) [4]

Rearranging [3]:
f(n-3) = f(n-2) - f(n-4) [5]

Combining [4] and [5]:
f(n) = 3 * f(n-2) - f(n-4) [6]

现在每个线程都可以使用 [6] 计算偶数或奇数斐波那契数，而无需等待其他线程的结果。

int Fibonacci(int nNumber) {
    switch (nNumber)
    {
    case 0: return 0;
    case 1: return 1;
    case 2: return 1;
    case 3: return 2;
    default: return 3 * Fibonacci(nNumber-2) - Fibonacci(nNumber-4);
    }
}

但是，这可能会破坏您的练习，使事情变得比预期的要简单得多。

于 2013-07-10T15:13:42.943 回答
2

有很多方法可以做到这一点。Anatolyg 的回答非常好；这确实是解决该问题的理想方式。

但是，就计算效率而言，计算斐波那契数列的方式存在很大问题。


注意：您可以在此处更改几乎所有算法，以便它只计算偶数或赔率。这些只是计算斐波那契数的更好方法。

您当前计算数字的方式不是很有效。使用当前算法仅计算一个数字的算法的时间复杂度已经是 O(2^n)，甚至不计算循环中的重复调用。一个计算斐波那契数的小程序不应该仅仅为了计算前 100 个数就占用整个 CPU 一分钟。

一个更好的递归算法如下（来自this page）：

unsigned long fib(unsigned int n) {
    return n == 0 ? 0 : fib2(n, 0, 1);
}
unsigned long fib2(unsigned int n, unsigned long p0, unsigned long p1) {
    return n == 1 ? p1 : fib2(n - 1, p1, p0 + p1);
}

我们现在可以fib(n)只计算 O(n) 的值，而不是 O(2^n)。

这是另一种更有效的 O(n) 算法：

unsigned long fib(unsigned int n) {
    unsigned long a=0,b=1; 
    for(unsigned long i = 0; i<n; i++)
        a=(b+=a)-a; //there are a number of other variations on this statement,
                    //but that's not the point.
    return a;
}


但是，在您的上下文中，如果您使用它作为您的函数，它仍然存在另一个问题，即它是Schlemiel the Painter's Algorithm。这是不好的。因为它必须计算所有的数字，所以每次你要为每个数字取 O(n)，然后你调用它 n 次，总时间复杂度为 O(n^2)。这仍然比您之前的 O(2^n) 好得多，但仍然不好。

我们可以做得更好。

#INCLUDE <cmath>

#DEFINE (phi) (1.618033988749894848204586834365638117720309179805762862135448L)
#DEFINE (phiC) (–0.618033988749894848204586834365638117720309179805762862135448L)
#DEFINE (root5) (2.236067977499789696409173668731276235440618359611525724270897L)
//using long doubles to minimize the truncation errors,
//as fibonacci numbers can get extremely large

unsigned long fib(unsigned int n) {
    return lrint(((pow(phi,n)-pow(phiC,n))/root5);
}

这个使用Binet 的公式直接计算结果，而不是按顺序计算它们，所以这个从多个线程运行会特别容易。

假设目标机器可以在 O(1) 中计算长双指数，那么输出所有斐波那契数的算法只有 O(n)。然而，许多架构不能，所以你很可能最终会得到，函数的 O(n)，整个程序的 O(n^2)。

我们可以做得更好。

#INCLUDE <iterator>

class FibIterator: public std::Iterator<const unsigned long>{
    unsigned long a=0,b=1;
public:
    std::Iterator& operator++() {
        unsigned long c = b;
        b+=a;
        a=c;
        return(*this);
    }
    std::Iterator& operator--() {
        unsigned long c = a;
        a=b-a;
        b=c;
        return(*this);
    }
    const unsigned long& operator*(){
        return a;
    }
}

（可能无法 100% 工作，我已经好几年没有编写过这么多的 c++ 代码了）

由于您是一个接一个地计算它们，因此无需每次都重新计算所有内容。当您知道前两个斐波那契数时，计算下一个数只需 O(1)。这段代码实际上是用于Iterator将迭代斐波那契数列的类型。这也可以实现为一个简单的函数，但这种方式更方便，因为您可以使用它来填充整个列表，只需一次调用。

如果你只是将它用作你的 for 循环的一部分，你可以只用 O(n) 计算你想要的所有数字。

于 2013-07-10T16:11:10.920 回答