检查字符串是否包含斐波那契数列的一部分
Check if string includes part of Fibonacci Sequence
我应该遵循哪种方法来创建一个算法来找出给定字符串中是否存在斐波那契数列？
该字符串仅包含没有空格的数字，并且可能有多个序列，我需要找到所有这些。
如果如您的评论所述第一个数字必须少于 6 位，您可以简单地搜索 25 个斐波那契数中的一个（只有 25 个少于 6 位）的所有位置，然后尝试展开这1个数字序列在两个方向上。
更新后：
当您只查找至少包含 3 个数字的序列时，您甚至可以加快速度。
预构建以前 25 个斐波纳契数之一开头的所有 25 个 3 数字符串，与搜索我上面建议的单个斐波那契数相比，这应该会提供更少的匹配。
然后搜索它们（如上所述并尝试扩展找到的 3 数序列）。
我会说你应该首先找到所有有趣的斐波那契数列（6 位或更少数字，不超过 30）并将它们存储到一个数组中。
然后，循环输入字符串中的每个位置，并尝试在其中找到 最长 可能的斐波那契数（也就是说，您必须浏览数组 向后).
如果找到一些 Fib 数，那么您必须分叉到第二个算法，该算法仅包括从当前位置到末尾遍历数组，尝试匹配以下子字符串中的每个项目。匹配结束后，必须回到主算法，从当前位置继续在输入字符串中查找。
None这两个算法都是递归的，也不算太贵。
更新
好的。如果不允许使用任何表格，您仍然可以使用此方法在第一个循环中替换获取最佳斐波纳奇数的方法：应用您的公式而不是索引。
以下是我的处理方法。
主要算法可以搜索三元组，然后尝试将它们扩展到尽可能长的序列。
这给我们留下了寻找三胞胎的子问题。因此，如果您正在扫描字符串以查找斐波那契数，您可以利用的一件事是下一个数字必须具有相同的数字位数或多一个数字。
例如如果您有字符串“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 个斐波纳契数之一开头的所有 25 个 3 数字符串，与搜索我上面建议的单个斐波那契数相比，这应该会提供更少的匹配。
然后搜索它们（如上所述并尝试扩展找到的 3 数序列）。
我会说你应该首先找到所有有趣的斐波那契数列（6 位或更少数字，不超过 30）并将它们存储到一个数组中。
然后，循环输入字符串中的每个位置，并尝试在其中找到 最长 可能的斐波那契数（也就是说，您必须浏览数组 向后).
如果找到一些 Fib 数，那么您必须分叉到第二个算法，该算法仅包括从当前位置到末尾遍历数组，尝试匹配以下子字符串中的每个项目。匹配结束后，必须回到主算法，从当前位置继续在输入字符串中查找。
None这两个算法都是递归的，也不算太贵。
更新
好的。如果不允许使用任何表格，您仍然可以使用此方法在第一个循环中替换获取最佳斐波纳奇数的方法：应用您的公式而不是索引。
以下是我的处理方法。
主要算法可以搜索三元组，然后尝试将它们扩展到尽可能长的序列。
这给我们留下了寻找三胞胎的子问题。因此，如果您正在扫描字符串以查找斐波那契数，您可以利用的一件事是下一个数字必须具有相同的数字位数或多一个数字。
例如如果您有字符串“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 的所有三元组来工作。