1

我只是在编写递归斐波那契算法的改进线性版本，并意识到我的布尔表达式看起来非常糟糕且不可读。有没有更清洁的方法来做我想做的事情？

int fibonacci(int num) {

    if (num <= 1)
        return num;

    // starts looking ugly here

    int a = intExists(num-1);
    int b = intExists(num-2);

    bool aAndB = (a != -1 && b != -1);
    bool justA = (a != -1 && b == -1);
    bool justB = (a == -1 && b != -1);

    int number = 0;

    if (aAndB)
        number = (a + b);
    else if (justA)
        number = (a + fibonacci(num - 2));
    else if (justB)
        number = (fibonacci(num-1) + b);
    else
        number = (fibonacci(num - 1) + fibonacci(num - 2));

    map.push_back(Pair(num, number));

    return number;
}

谢谢

4

9 回答 9

2

你为什么不做aand bas bools 并分配那些trueifa == -1和falseelse 。然后，表达式将变得更容易处理。

于 2013-08-02T14:21:44.577 回答
2

如果你在谈论：

bool aAndB = (a != -1 && b != -1);

然后我会说，“不”。

这段代码在我看来非常具有表现力。 aAndB在它诞生的那一刻就被初始化了，而且条件非常明确。当您第一次开始使用 C++ 时，这可能看起来有点奇怪，但在您知道这将是第二天性之前，其他构造会显得很愚蠢。

我建议的一件事是，aAndB const如果您不打算更改它：

const bool aAndB = (a != -1 && b != -1);

这更具表现力。

它还可能为编译器提供额外的机会来优化您的代码。

记住——编写代码供人类理解。不是让计算机理解的。

于 2013-08-02T14:23:51.383 回答
1

可以做一个 switch 语句来清理 if else 语句。除此之外只需添加评论

于 2013-08-02T14:21:26.110 回答
1

您可以重写它以使用条件分支，如下所示：

int fibonacci(int num) {

    if (num <= 1)
        return num;

    int a = intExists(num-1);
    int b = intExists(num-2);

    const bool isA = (a != -1);   // change in the definition
    const bool isB = (b != -1);   // change in the definition

    int number = 0;

    if (isA && isB)
        number = (a + b);
    else if (isA)   // conditionnal branching
        number = (a + fibonacci(num - 2));
    else if (isB)   // conditionnal branching
        number = (fibonacci(num-1) + b);
    else
        number = (fibonacci(num - 1) + fibonacci(num - 2));

    map.push_back(Pair(num, number));

    return number;
}
于 2013-08-02T14:25:51.330 回答
1

我假设intExists(n)查找map，如果n在那里找到，则返回，fibonacci(n)否则返回-1。然后你可以这样做：

int fibonacci(int num) {

    if (num <= 1)
        return num;

    int a = intExists(num-1);
    int b = intExists(num-2);

    if (a == -1) // if a wasn't found, then compute it
        a = fibonacci(num-1);

    if (b == -1) // if b wasn't found, then compute it
        b = fibonacci(num-2);

    int number = a + b;
    map.push_back(std::make_pair(num, number));

    return number;
}

奖金：

这是fibonnacci()基于Binet 公式的另一个完全不同的实现：

#include <cmath>

int fibonacci(int n) {
    static const double e1 =  1.6180339887498948482045868343656;  // = (1 + sqrt(5)) / 2
    static const double e2 = -0.61803398874989484820458683436564; // = (1 - sqrt(5)) / 2
    static const double c =   0.44721359549995793928183473374626; // = 1 / sqrt(5);
    double f = c * (std::pow(e1, n) - std::pow(e2, n));
    return static_cast<int>(f + 0.5);
}

int main() {
    for (int n = 1; n < 15; ++n)
        std::cout << fibonacci(n) << ' ';
}

它输出：

1 1 2 3 5 8 13 21 34 55 89 144 233 377

于 2013-08-02T14:56:08.950 回答
0

普通的 C++ 代码足够干净：

bool a = intExists(num-1);
bool b = intExists(num-2);

if (a && b) {
  //
} else if (a) {
  //
} else if (b) {
  //
} else {
  //
}
于 2013-08-02T14:24:06.503 回答
0 
int a = intExists(num-1);
int b = intExists(num-2);

bool aAndB = (a != -1 && b != -1);
bool justA = (a != -1 && b == -1);
bool justB = (a == -1 && b != -1);

快速查看您采用的方法。什么情况下justB可以true？（提示：从不）

这应该可以帮助您简化方法，尽管有比memoization更好的方法。

于 2013-08-02T14:26:57.670 回答
0

更改intExists为返回布尔值，您可以执行如下 switch-case 语句：

bool a = intExists(num-1);
bool b = intExists(num-2); 

switch ((a << 1) + b) {
default: // none exists
case 1: // only b exist
case 2: // only a exist
case 3: // both exists
}

基本原理是将这些布尔值转换为二进制数

于 2013-08-02T15:04:03.413 回答
0

稍微剧烈的重写是让外部函数处理查找表。
这样，您一次不需要关心多个值。

这个使用map所以我不必写太多来测试它，但它应该很容易适应：

std::map<int, int> table;

int fibonacci(int num);

int value(int num)
{
    int result = table[num];
    if (!result)
    {
        result = fibonacci(num);
        table[num] = result;
    }
    return result;
}

int fibonacci(int num) 
{
    if (num <= 2)
        return 1;
    return value(num - 1) + value(num - 2);
}
于 2013-08-02T15:11:39.263 回答