原来斐波拉契数列还有这种写法，你知道吗？-木庄网络博客

本文摘自PHP中文网，作者php是最好的语言，侵删。

百度下“斐波拉契的非递归写法”，也有不少的答案，但是并不令人满意，首先是太复制难懂，其次是性能和递归差不多。

一说到斐波拉契数列，无论是程序菜鸟，还是技术老手，首先想到的，肯定是递归写法。然后，技术老手与程序菜鸟不同的地方，就是会想到将递归的结果存起来以减少重复计算。这些都是些很常规的操作，但是你有没有想过，斐波拉契数列还能用非递归的方法来写？
百度下“斐波拉契的非递归写法”，也有不少的答案，但是并不令人满意，首先是太复制难懂，其次是性能和递归差不多。一开始我也想自己写个，只要模拟递归调用的调用栈不就行了嘛，不过这种想法真是有点想当然了，写出来的程序也很复杂。怎么办呢？这时候，树的深度优先遍历就可以派上用场了。
首先，我们定义树结点：

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;
      }

上述算法的核心思想是，遍历栈，pop出栈顶元素，如果已经访问过（visited为true）,就跳过（上面代码由于采用了保存子树结果的优化，会有个特殊情况要处理，下文会详述）；否则，将当前父结点的visited标记为true，代表已访问过，并push到栈；然后将其子结点都push到栈。

如果按照这个思路，写出来的代码不会是上面那个样子的，代码量少得多也简洁得多，不过算法复杂度就会像递归写法差不多，因为存在重复计算。

那怎么办呢，解决办法只有一个，空间换时间，将子树的结果存起来，如果对应子树已经计算过有结果，就不再往下一层的深度遍历了，直接使用结果。我们将子树结果保存在了一个数组里面：

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

通常如果子树已经有结果，按逻辑来说应该就会被访问过。不过存在特例，就是一开始的子树0和子树1：

1 2	`childrenResultMemo[0] =` `1;` `childrenResultMemo[1] =` `1;`

只需在这个特例的分支里面累加结果即可：

1	`sum += childrenResultMemo[cur.Value];`

怎么样，这种写法是不是很少见？其实斐波拉契数列的求值过程就像是树的深度优先遍历。所以只要是深度优先遍历的实现，完全就是可行的。

Python打印斐波拉契数列实例

PHP实现斐波那契数列

C#高级编程(第11版) C# 7 & .NET Core 2.0（.NET开发经典名著）

￥125.8元 清华大学出版社

作者:[美]克里斯琴·内格尔（Christian Nagel）著。出版时间：2019年3月。

转载请注明出处：木庄网络博客 » 原来斐波拉契数列还有这种写法，你知道吗？

原来斐波拉契数列还有这种写法，你知道吗？

C#高级编程(第11版) C# 7 & .NET Core 2.0（.NET开发经典名著）

相关推荐

评论