我应该采用哪种方法来创建一个算法来确定给定字符串中是否存在斐波纳契序列?
该字符串仅包含没有空格的数字,并且可能有多个序列,我需要找到所有这些。
这是我如何处理这个问题。
主算法可以搜索三元组,然后尝试将它们扩展到尽可能长的序列。
这给我们留下了寻找三胞胎的子问题。因此,如果您正在扫描字符串以查找斐波那契数字,您可以利用的一件事是下一个数字必须具有相同的位数或一个数字。
例如如果你有字符串“987159725844”并且正在考虑“[987] 159725844”那么你需要关注的下一件事是“987 [159] 725844”和“987 [1597] 25844”。然后你会发现下一部分是“[2584] 4”或“[25844]”。
获得3个数字后,您可以检查它们是否与C - B == B - A
形成算术级数。如果他们这样做,您现在可以通过查看比率是否大约为1.6然后将斐波纳契迭代向下运行到初始条件1,1来检查它们是否来自斐波那契序列。
然后整个算法通过扫描查找从宽度1开始,然后宽度2,宽度3到6的所有三元组来工作。
如果您的评论说第一个数字必须少于6位数,那么您可以简单地搜索25个斐波那契数字中的一个(仅有25个少于6位数)的所有位置,并尝试扩展这个1数字序列两个方向。
更新后:
当您只查找至少3个数字的序列时,您甚至可以加快速度。
预先建立了所有25个3个数字字符串,以25个第一个斐波纳契数字中的一个开头,这应该比搜索我上面建议的单个斐波纳契数字少得多。
然后搜索它们(如上所述并尝试扩展找到的3个数字序列)。
我要说你应该首先找到所有有趣的Fibonacci项目(有6个或更少的数字,不超过30个)并将它们存储到一个数组中。
然后,循环输入字符串中的每个位置,并尝试在那里找到最长的Fibonacci数(也就是说,您必须向后浏览数组)。
如果找到某个Fib数,则必须分叉到辅助算法,该算法仅包括从当前位置到末尾的数组,尝试匹配以下子字符串中的每个项目。当匹配结束时,您必须返回主算法以继续从当前位置搜索输入字符串。
这两种算法都不是递归的,也不是太昂贵。
更新
好。如果不允许使用表,您仍然可以使用此方法在第一个循环中替换获取bext Fibo编号的方式:应用您的公式,而不是索引。