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を作成し、それらを as ifおよびboolother に割り当ててみませんか。すると、表現が扱いやすくなります。truea == -1false

于 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

次のように、条件分岐を使用するように書き直すことができます。

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

if else ステートメントを少しクリーンアップするために、switch ステートメントを実行できます。それ以外はコメントを追加するだけです

于 2013-08-02T14:21:26.110 に答える
1

私はそれが検索し、そこで見つかった場合はそれを返すと仮定intExists(n)してmapいます。次に、これを行うことができます：nfibonacci(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;
}

ボーナス：

これは、 Binet の公式fibonnacci()に基づいた別の完全に異なる実装です。

#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

ブール値を返すように変更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
}

理論的根拠は、これらのブール値を 2 進数に変換することです。

于 2013-08-02T15:04:03.413 に答える
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

少し思い切った書き直しは、外部関数がルックアップ テーブルを処理できるようにすることです。
そうすれば、一度に複数の値を気にする必要がなくなります。

これは使用する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 に答える