Il s’avère que la séquence de Fibonacci s’écrit également de cette façon, le saviez-vous ?

Il existe de nombreuses réponses à « Écriture non récursive de Fibonacci » sur Baidu, mais elles ne sont pas satisfaisantes. Premièrement, c'est trop difficile à comprendre, et deuxièmement, les performances sont à peu près les mêmes que celles de la récursion.

En ce qui concerne la séquence de Fibonacci, que vous soyez un programmeur débutant ou un vétéran technique, la première chose qui vous vient à l'esprit est définitivement la méthode d'écriture récursive. Ensuite, la différence entre les vétérans techniques et les novices en programme, c'est qu'ils penseront à sauvegarder les résultats de la récursivité pour réduire les calculs répétés. Ce sont des opérations très courantes, mais avez-vous déjà pensé que la suite de Fibonacci pouvait également être écrite de manière non récursive ?
Il existe de nombreuses réponses à « Écriture non récursive de Fibonacci » sur Baidu, mais elles ne sont pas satisfaisantes. Premièrement, c'est trop difficile à comprendre, et deuxièmement, les performances sont à peu près les mêmes que celles de la récursion. Au début, je voulais aussi en écrire un moi-même, à condition qu'il simule la pile d'appels récursifs, mais cette idée est un peu considérée comme acquise, et le programme écrit est également très compliqué. Ce qu'il faut faire? À ce stade, le Parcours de l'arbre en profondeur d'abord peut s'avérer utile.
Tout d'abord, nous définissons les nœuds de l'arbre :

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

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

Ensuite, nous pouvons volontiers apprendre à écrire la pile 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;
        }

L'idée centrale de l'algorithme ci-dessus est de parcourir la pile, d'afficher l'élément supérieur de la pile, s'il a été visité (visité est vrai), de l'ignorer (le code ci-dessus utilise l'optimisation de la sauvegarde des résultats du sous-arbre, il y aura un cas particulier à gérer, qui sera détaillé ci-dessous); sinon, la marque visitée du nœud parent actuel est vraie, ce qui signifie qu'il a été visité et poussé vers la pile, puis tous ses nœuds enfants sont poussés vers la pile ;

Si vous suivez cette idée, le code que vous écrivez ne ressemblera pas à celui ci-dessus. La quantité de code sera beaucoup plus petite et plus concise. Cependant, la complexité de l'algorithme sera similaire à celle du récursif. écrire car il y aura des calculs répétés.

Alors que devons-nous faire ? Il n'y a qu'une seule solution, échanger de l'espace contre du temps, et stocker les résultats du sous-arbre. Si le sous-arbre correspondant a été calculé et a des résultats, nous ne parcourrons plus la profondeur de. la couche suivante. Utilisez les résultats directement. Nous enregistrons les résultats du sous-arbre dans un tableau :

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

Habituellement, si le sous-arbre a déjà des résultats, il aurait logiquement dû être accédé. Il existe cependant des cas particuliers, qui sont le sous-arbre 0 et le sous-arbre 1 au début :

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

Il suffit de cumuler les résultats dans les branches de ce cas particulier :

sum += childrenResultMemo[cur.Value];

Et si ça ? Cette façon d'écrire est-elle rare ? En fait, le processus d’évaluation de la séquence de Fibonacci s’apparente à un parcours de l’arbre en profondeur. Donc, tant qu'il s'agit de la mise en œuvre d'une traversée en profondeur d'abord, c'est tout à fait réalisable.

Articles associés :

Exemple de séquence de Fibonacci d'impression Python

PHP implémente la séquence de Fibonacci

Vidéos associées :

Aventure sur la structure des données—Chapitre sur la file d'attente

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!