ホームページ > 記事 > バックエンド開発 > フィボナッチ数列もこのように書かれていることが分かりました。

フィボナッチ数列もこのように書かれていることが分かりました。

php是最好的语言オリジナル: 2018-07-27 10:49:011551ブラウズ

Baidu には「フィボナッチの非再帰記述」に対する回答がたくさんありますが、第一に難しすぎて理解できないこと、第二に再帰とパフォーマンスが似ていることなど、満足のいくものではありません。

フィボナッチ数列に関して言えば、初心者のプログラマであっても技術のベテランであっても、最初に思い浮かぶのは間違いなく再帰的な記述方法です。そして、技術のベテランとプログラムの初心者の違いは、計算の繰り返しを減らすために再帰の結果を保存することを考えるかどうかです。これらは非常に一般的な演算ですが、フィボナッチ数列が非再帰的な方法でも記述できると考えたことはありますか?
Baidu には「フィボナッチの非再帰記述」に対する回答がたくさんありますが、第一に難しすぎて理解できないこと、第二に再帰とパフォーマンスが似ていることなど、満足のいくものではありません。最初は、再帰呼び出しのコールスタックをシミュレートするものであれば、自分でも作成したいと思っていましたが、この考えは少し当たり前のことであり、作成されるプログラムも非常に複雑です。どうやってするの？このとき、ツリーの深さ優先走査が便利です。
最初に、ツリーノードを定義します。

public class Node
        {
            public Node(long value, bool visited)
            {
                Value = value;
                Visited = visited;
            }

            public long Value { get; set; }//存放结点的值
            public bool Visited { get; set; }
        }

その後、DFS のスタックの書き方を楽しく学ぶことができます

  public static long Fblc(int n)
        {
            Stack<Node> s = new Stack<Node>();
            s.Push(new Node(n, false));
            long sum = 0;
            long[] childrenResultMemo = new long[n+1];
            childrenResultMemo[0] = 1;
            childrenResultMemo[1] = 1;
            //long children = 0;
            while (s.Any())
            {
                var cur = s.Pop();
             
                    if (cur.Visited == false)
                    {
                        if (childrenResultMemo[cur.Value] == 0)
                        {
                            cur.Visited = true;
                            if (childrenResultMemo[cur.Value - 1] != 0 && childrenResultMemo[cur.Value - 2] != 0)
                            {
                                var result = childrenResultMemo[cur.Value - 1] + childrenResultMemo[cur.Value - 2];
                                childrenResultMemo[cur.Value] = result;
                                sum += result;
                                s.Push(cur);
                            }
                            else
                            {
                                s.Push(cur);
                                s.Push(new Node(cur.Value - 1, false));
                                s.Push(new Node(cur.Value - 2, false));
                            }
                        }
                        else
                        {
                            sum += childrenResultMemo[cur.Value];//保存子树结果的优化，会有个特殊情况要处理
                        }
                        
                    }
                   
                
            }

            return sum;
        }

上記のアルゴリズムの中心的な考え方は、トラバースすることです。スタックを呼び出してスタックをポップアウトします。最上位の要素が訪問されている場合 (visited が true)、スキップします (上記のコードはサブツリー結果の保存の最適化を使用しています。処理される特別なケースがあります。これについては以下で詳しく説明します)。 ; それ以外の場合、現在の親ノード訪問済みマークは true、つまり訪問されてスタックにプッシュされたことを意味し、その後、そのすべての子ノードがスタックにプッシュされます。

この考え方に従うと、作成するコードは上記とは異なります。コードの量ははるかに少なく、より簡潔になります。ただし、アルゴリズムの複雑さは再帰的アルゴリズムの複雑さと同様になります。計算が繰り返されるため、書き込みます。

何をすべきでしょうか? 解決策は 1 つだけです。空間を時間と交換し、サブツリーの結果を保存します。対応するサブツリーが計算され、結果が得られている場合、次のサブツリーの深さはトラバースしません。結果を直接使用します。サブツリーの結果を配列に保存します。

long[] childrenResultMemo = new long[n+1];

通常、サブツリーにすでに結果がある場合、論理的にはそのサブツリーにアクセスする必要があります。ただし、先頭にサブツリー 0 とサブツリー 1 がある特殊なケースもあります:

childrenResultMemo[0] = 1;
childrenResultMemo[1] = 1;

この特殊なケースのブランチに結果を追加するだけです:

sum += childrenResultMemo[cur.Value];

この書き方はどうでしょうか?めったに見られない?実際、フィボナッチ数列の評価プロセスは、ツリーの深さ優先の走査に似ています。したがって、深さ優先トラバーサルの実装である限り、完全に実現可能です。

Python でフィボナッチ数列の例を出力

#PHP でフィボナッチ数列を実装

フィボナッチ数列もこのように書かれていることが分かりました。

関連記事