原来斐波拉契数列还有这种写法,你知道吗?
时间:2018-07-27 10:49
百度下“斐波拉契的非递归写法”,也有不少的答案,但是并不令人满意,首先是太复制难懂,其次是性能和递归差不多。
一说到斐波拉契数列,无论是程序菜鸟,还是技术老手,首先想到的,肯定是递归写法。然后,技术老手与程序菜鸟不同的地方,就是会想到将递归的结果存起来以减少重复计算。这些都是些很常规的操作,但是你有没有想过,斐波拉契数列还能用非递归的方法来写?
百度下“斐波拉契的非递归写法”,也有不少的答案,但是并不令人满意,首先是太复制难懂,其次是性能和递归差不多。一开始我也想自己写个,只要模拟递归调用的调用栈不就行了嘛,不过这种想法真是有点想当然了,写出来的程序也很复杂。怎么办呢?这时候,树的深度优先遍历就可以派上用场了。
首先,我们定义树结点:
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到栈。
如果按照这个思路,写出来的代码不会是上面那个样子的,代码量少得多也简洁得多,不过算法复杂度就会像递归写法差不多,因为存在重复计算。
那怎么办呢,解决办法只有一个,空间换时间,将子树的结果存起来,如果对应子树已经计算过有结果,就不再往下一层的深度遍历了,直接使用结果。我们将子树结果保存在了一个数组里面:
long[] childrenResultMemo = new long[n+1];
通常如果子树已经有结果,按逻辑来说应该就会被访问过。不过存在特例,就是一开始的子树0和子树1:
childrenResultMemo[0] = 1; childrenResultMemo[1] = 1;
只需在这个特例的分支里面累加结果即可:
sum += childrenResultMemo[cur.Value];
怎么样,这种写法是不是很少见?其实斐波拉契数列的求值过程就像是树的深度优先遍历。所以只要是深度优先遍历的实现,完全就是可行的。
相关文章:
Python打印斐波拉契数列实例
PHP实现斐波那契数列
相关视频:
数据结构探险—队列篇
以上就是原来斐波拉契数列还有这种写法,你知道吗?的详细内容,更多请关注gxlsystem.com其它相关文章!