8

斐波那契字符串定义如下：

  • 第一个斐波那契字符串是“a”
  • 第二个斐波那契字符串是“bc”
  • (n + 2)nd 斐波那契字符串是前两个斐波那契字符串的串联。

例如，前几个斐波那契字符串是

a
bc
abc
bcabc
abcbcabc

目标是，给定一行和一个偏移量，确定该偏移量处的字符。更正式地说：

输入：用空格分隔的两个整数 - K 和 P(0 < K ≤ 10 9 ), ( < P ≤ 10 9 )，其中 K 是斐波那契字符串的行号，P 是行中的位置号。

输出：相关测试所需的字符：“a”、“b”或“c”。如果 P 大于第 k 行 (K ≤ 10 9 )，则有必要推导出 «无解»

例子：

输入： 18 58

输出：一个

我写了这段代码来解决这个问题：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int k, p;
    string s1 = "a";
    string s2 = "bc";
    vector < int >fib_numb;
    fib_numb.push_back(1);
    fib_numb.push_back(2);
    cin >> k >> p;
    k -= 1;
    p -= 1;
    while (fib_numb.back() < p) {
        fib_numb.push_back(fib_numb[fib_numb.size() - 1] + fib_numb[fib_numb.size() - 2]);
    }
    if (fib_numb[k] <= p) {
        cout << "No solution";
        return 0;
    }
    if ((k - fib_numb.size()) % 2 == 1)
        k = fib_numb.size() + 1;
    else
        k = fib_numb.size();
    while (k > 1) {
        if (fib_numb[k - 2] > p)
            k -= 2;
        else {
            p -= fib_numb[k - 2];
            k -= 1;
        }
    }
    if (k == 1)
        cout << s2[p];
    else
        cout << s1[0];
    return 0;
}

这是对的吗？你会怎么做？

4

6 回答 6

14

您可以在不显式计算任何字符串的情况下解决此问题，这可能是解决问题的最佳方法。毕竟，如果你被要求计算第 50 个斐波那契字符串，你几乎肯定会耗尽内存。F(50) 是 12,586,269,025，所以你需要超过 12GB 的内存才能容纳它！

解决方案背后的直觉是，因为斐波那契字符串的每一行都由前几行的字符组成，所以您可以将 (row, offset) 对转换为新行所在的不同 (row', offset') 对总是使用比您开始使用的更小的斐波那契字符串。如果您重复此操作足够多次，最终您将返回第 0 行或第 1 行的斐波那契字符串，在这种情况下，可以立即读出答案。

为了使这个算法工作，我们需要建立一些事实。首先，让我们将斐波那契数列定义为零索引；也就是说，序列是

F(0)   = 0
F(1)   = 1
F(n+2) = F(n) + F(n + 1)

鉴于此，我们知道斐波那契字符串的第 n 行（单索引）总共有 F(n + 1) 个字符。您可以通过归纳快速看到这一点：

  • 第 1 行的长度为 1 = F(2) = F(1 + 1)
  • 第 2 行的长度为 2 = F(3) = F(2 + 1)。
  • 对于某些行 n + 2，该行的长度由 Size(n) + Size(n + 1) = F(n + 1) + F(n + 2) = F(n + 3) = F( (n + 2) + 1)

利用这些知识，假设我们要找到斐波那契字符串第七行的第七个字符。我们知道第 7 行是由第 5 行和第 6 行串联而成的，所以字符串如下所示：

  R(7) = R(5) R(6)

第五行有 F(5 + 1) = F(6) = 8 个字符，这意味着第七行的前八个字符来自 R(5)。由于我们想要这一行中的第七个字符，并且由于 7 ≤ 8，我们知道我们现在需要查看第 5 行的第七个字符来获得这个值。好吧，第 5 行看起来像是第 3 行和第 4 行的串联：

  R(5) = R(3) R(4)

我们想找到这一行的第七个字符。现在，R(3) 中有 F(4) = 3 个字符，这意味着如果我们要查找 R(5) 的第七个字符，它将在 R(4) 部分，而不是 R( 3) 部分。由于我们正在寻找这一行的第 7 个字符，这意味着我们正在寻找 R(4) 的第 7 - F(4) = 7 - 3 = 第 4 个字符，所以现在我们看那里。同样，R(4) 被定义为

 R(4) = R(2) R(3)

R(2) 中有 F(3) = 2 个字符，所以我们不想在其中查找该行的第四个字符；这将包含在 R(3) 中。该行的第四个字符必须是 R(3) 的第二个字符。让我们看看那里。R(3) 定义为

 R(3) = R(1) R(2)

R(1)里面有一个字符，所以这一行的第二个字符一定是R(1)的第一个字符，所以我们看那里。然而，我们知道，

 R(2) = bc

所以这个字符串的第一个字符是b，这就是我们的答案。让我们看看这是否正确。斐波那契字符串的前七行是

1 a
2 bc
3 abc
4 bcabc
5 abcbcabc
6 bcabcabcbcabc
7 abcbcabcbcabcabcbcabc

果然，如果你看第七个字符串的第七个字符，你会发现它确实是一个b. 看起来这行得通！

更正式地说，我们感兴趣的递归关系如下所示：

char NthChar(int row, int index) {
    if (row == 1) return 'a';
    if (row == 2 && index == 1) return 'b';
    if (row == 2 && index == 2) return 'c';
    if (index < Fibonacci(row - 1)) return NthChar(row - 2, index);
    return NthChar(row - 1, index - Fibonacci(row - 1));
}

现在，当然，这里写的实现存在问题。因为行索引的范围可达 10 9，所以我们不可能Fibonacci(row)在所有情况下都进行计算；十亿分之一的斐波那契数太大了，无法表示！

幸运的是，我们可以解决这个问题。如果您查看斐波那契数表，您会发现 F(45) = 1,134,903,170，它大于 10 9（并且没有更小的斐波那契数大于此）。此外，由于我们知道我们关心的索引也必须不大于 10 亿，如果我们在第 46 行或更大的行中，我们将始终采用我们在斐波那契字符串的前半部分查找的分支。这意味着我们可以将代码重写为

char NthChar(int row, int index) {
    if (row == 1) return 'a';
    if (row == 2 && index == 1) return 'b';
    if (row == 2 && index == 2) return 'c';

    /* Avoid integer overflow! */
    if (row >= 46) return NthChar(row - 2, index);

    if (index < Fibonacci(row - 1)) return NthChar(row - 2, index);
    return NthChar(row - 1, index - Fibonacci(row - 1));
}

在这一点上，我们非常接近解决方案。还有一些问题需要解决。首先，上面的代码几乎肯定会炸毁堆栈，除非编译器足够好，可以使用尾递归来消除所有堆栈帧。虽然一些编译器（例如 gcc）可以检测到这一点，但依赖它可能不是一个好主意，因此我们可能应该迭代地重写这个递归函数。这是一种可能的实现：

char NthChar(int row, int index) {
    while (true) {
       if (row == 1) return 'a';
       if (row == 2 && index == 1) return 'b';
       if (row == 2 && index == 2) return 'c';

       /* Avoid integer overflow! */
       if (row >= 46 || index < Fibonacci(row - 1)) {
           row -= 2;
       } else {
           index -= Fibonacci(row - 1);
           row --;
       }
    }
}

但当然，我们仍然可以做得比这更好。特别是，如果给定一个非常大的行号（例如 10 亿），那么一遍又一遍地循环从行中减去 2 直到它小于 46 是非常愚蠢的。这更有意义只需确定在我们进行所有减法之后它最终会变成什么值。但是我们可以很容易地做到这一点。如果我们有一个至少为 46 的偶数行，我们最终会减去 2 直到它变成 44。如果我们有一个至少是 46 的奇数行，我们最终会减去 2 直到它变成 45。因此，我们可以重写上面的代码来明确处理这种情况：

char NthChar(int row, int index) {
    /* Preprocess the row to make it a small value. */
    if (row >= 46) {
        if (row % 2 == 0)
            row = 45;
        else
            row = 44;
    }

    while (true) {
       if (row == 1) return 'a';
       if (row == 2 && index == 1) return 'b';
       if (row == 2 && index == 2) return 'c';

       if (index < Fibonacci(row - 1)) {
           row -= 2;
       } else {
           index -= Fibonacci(row - 1);
           row --;
       }
    }
}

还有最后一件事要处理，如果由于角色超出范围而无法解决问题，会发生什么。但是我们可以很容易地解决这个问题：

string NthChar(int row, int index) {
    /* Preprocess the row to make it a small value. */
    if (row >= 46) {
        if (row % 2 == 0)
            row = 45;
        else
            row = 44;
    }

    while (true) {
       if (row == 1 && index == 1) return "a"
       if (row == 2 && index == 1) return "b";
       if (row == 2 && index == 2) return "c";

       /* Bounds-checking. */
       if (row == 1) return "no solution";
       if (row == 2) return "no solution";

       if (index < Fibonacci(row - 1)) {
           row -= 2;
       } else {
           index -= Fibonacci(row - 1);
           row --;
       }
    }
}

我们有一个可行的解决方案。

您可能会做的另一项优化是预先计算您需要的所有斐波那契数，并将它们存储在一个巨大的数组中。您只需要 F(2) 到 F(44) 的斐波那契值，因此您可以执行以下操作：

const int kFibonacciNumbers[45] = {
    0, 1, 1, 2, 3, 5, 
    8, 13, 21, 34, 55, 89,
    144, 233, 377, 610,
    987, 1597, 2584, 4181,
    6765, 10946, 17711, 28657,
    46368, 75025, 121393, 196418,
    317811, 514229, 832040,
    1346269, 2178309, 3524578,
    5702887, 9227465, 14930352,
    24157817, 39088169, 63245986,
    102334155, 165580141, 267914296,
    433494437, 701408733
};

使用这个预先计算的数组，代码的最终版本将如下所示：

string NthChar(int row, int index) {
    /* Preprocess the row to make it a small value. */
    if (row >= 46) {
        if (row % 2 == 0)
            row = 45;
        else
            row = 44;
    }

    while (true) {
       if (row == 1 && index == 1) return "a"
       if (row == 2 && index == 1) return "b";
       if (row == 2 && index == 2) return "c";

       /* Bounds-checking. */
       if (row == 1) return "no solution";
       if (row == 2) return "no solution";

       if (index < kFibonacciNumbers[row - 1]) {
           row -= 2;
       } else {
           index -= kFibonacciNumbers[row - 1];
           row --;
       }
    }
}

我还没有测试过这个；套用唐·克努特的话说，我只是证明它是正确的。:-) 但我希望这有助于回答你的问题。我真的很喜欢这个问题！

于 2011-08-30T20:41:14.973 回答
1

我想你的一般想法应该没问题，但我看不出你的代码将如何处理更大的 K 值，因为数字会很快变得巨大，即使使用大型整数库，计算斐波那契也可能需要很长时间(10^9) 完全正确。

幸运的是，您只被询问前 10^9 个字符。该字符串将在第 44 行（f(44) = 1134903170）已经达到那么多字符。

如果我没记错的话，从那里开始，前 10^9 个字符将简单地在第 44 行和第 45 行的前缀之间交替，因此在伪代码中：

def solution(K, P):
   if K > 45:
       if K % 2 == 0:
           return solution(44, P)
       else:
           return solution(45, P)
   #solution for smaller values of K here
于 2011-02-04T15:46:54.057 回答
0

我找到了这个。我没有进行预检查（获取k第 -th fibo 字符串的大小来测试p它），因为如果检查成功，您无论如何都必须计算它。当然，一旦k变大，您可能会遇到溢出问题（fibo 字符串的长度是索引的指数函数n......）。

#include <iostream>
#include <string>

using namespace std;

string fibo(unsigned int n)
{
    if (n == 0)
        return "a";
    else if (n == 1)
        return "bc";
    else
        return fibo(n - 2) + fibo(n - 1);

}

int main()
{
    unsigned int k, p;
    cin >> k >> p;
    --k;
    --p;
    string fiboK = fibo(k);
    if (p > fiboK.size())
        cout << "No solution" << endl;
    else
        cout << fiboK[p] << endl;
    return 0;
}

k编辑：好的，我现在明白你的意思了，即检查-th 字符串的哪个部分p驻留（即在字符串k - 2或k - 1中，并p在需要时更新）。当然，这是实现它的好方法，因为正如我在上面所说的那样，我的幼稚解决方案会爆炸得太快。

从算法的角度来看，你的方式对我来说是正确的（节省内存和复杂性）。

于 2011-02-04T10:27:07.550 回答
0

我会计算第 K 个斐波那契字符串，然后检索它的第 P 个字符。像这样的东西：

#include <iostream>
#include <string>
#include <vector>

std::string FibonacciString(unsigned int k)
{
    std::vector<char> buffer;
    buffer.push_back('a');
    buffer.push_back('b');
    buffer.push_back('c');

    unsigned int curr = 1;
    unsigned int next = 2;

    while (k --)
    {
        buffer.insert(
            buffer.end(),
            buffer.begin(),
            buffer.end());

        buffer.erase(
            buffer.begin(),
            buffer.begin() + curr);

        unsigned int prev = curr;
        curr = next;
        next = prev + next;
    }

    return std::string(
        buffer.begin(),
        buffer.begin() + curr);
}

int main(int argc, char** argv)
{
    unsigned int k, p;
    std::cin >> k >> p;

    -- p;
    -- k;

    std::string fiboK = FibonacciString(k);
    if (p > fiboK.size())
        std::cout << "No solution";
    else
        std::cout << fiboK[p];
    std::cout << std::endl;
    return 0;
}

它确实比您的版本使用更多的内存，因为它需要在每一刻存储第 N 个和第 (N+1) 个斐波那契字符串。但是，由于它非常接近定义，因此它确实适用于每个值。

k当大而小时，您的算法似乎有一些问题p。测试将使用andfib_num[k] < p取消引用数组范围之外的项目，不是吗？k = 30p = 1

于 2011-02-04T12:50:29.427 回答
0

引用维基百科，Fibonacci_word：

单词的第n个数字是 2+[nφ]-[(n+1)φ] 其中 φ 是黄金比例...

（维基百科页面中使用的唯一字符是 1 和 0。）但请注意，维基百科页面中的字符串以及 Knuth 的基本算法中的字符串是按照上面显示的字符串的相反顺序构建的；很明显，当列出字符串时，前导部分不断重复，只有一个无限长的斐波那契字符串。以上述使用顺序生成时不太清楚，因为不断重复的部分是字符串的尾随部分，但同样如此。因此，引文中的术语“单词”，除了问题“对于这一行来说n太大了吗？”之外，这一行并不重要。

不幸的是，这个公式很难应用到poster的问题上，因为在这个公式中，原始字符串的长度相同，并且poster以“a”和“bc”开头。

这个 J(ava)Script 脚本在海报选择的字符上生成斐波那契字符串，但顺序相反。（它包含用于获取命令行参数并输出到标准输出的 Microsoft 对象 WScript。）

var u, v /*Fibonacci numbers*/, g, i, k, R;
v = 2;
u = 1;
k = 0;
g = +WScript.arguments.item(0); /*command-line argument for desired length of string*/
/*Two consecutiv Fibonacci numbers, with the greater no less than the
  Fibonacci string s length*/
while (v < g)
{   v += u;
    u = v - u;
    k = 1 - k;
}
i = u - k;
while (g-- > 0)
{   /*In this operation, i += u with i -= v when i >= v (carry),
      since the Fibonacci numbers are relativly prime, i takes on
      every value from 0 up to v. Furthermore, there are u carries,
      and, therefore, u instances of character 'cb', and v-u instances
      of 'a' (no-carry). The characters are spread as evenly as can be.*/
    if ((i += u) < v)
    {   R = 'a'; // WScript.StdOut.write('a'); /* no-carry */
    } else
    {   i -= v; /* carry */
        R = 'cb'; // WScript.StdOut.write('cb')
    }
}
/*result is in R*/ // WScript.StdOut.writeLine()

我建议这样做，因为不需要实际输出字符串。可以简单地停在所需的长度，并显示最后要输出的内容。（输出代码用'//'注释掉）。当然，使用它来查找位置n处的字符的成本与n成正比。顶部的公式成本要低得多。

于 2021-11-14T01:47:41.420 回答
0

我又举了一个例子，斐波那契数列的每个对应数字都对应于 alfabet 中的字母。所以对于 1 是 a，对于 2 是 b，对于 3 是 c，对于 5 是 e...等等：

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string a = "abcdefghijklmnopqrstuvwxyz"; //the alphabet
    string a1 = a.substr(0,0); string a2 = a.substr(1,1); string nexT = a.substr(0,0);

    nexT = a1 + a2;

   while(nexT.length() <= a.length())
    {
        //cout << nexT.length() << ", ";             //show me the Fibonacci numbers
        cout << a.substr(nexT.length()-1,1) << ", "; //show me the Fibonacci letters
        a1 = a2;
        a2 = nexT;
        nexT = a1 + a2;
    }
    return 0;
}

输出：a、b、c、e、h、m、u、

于 2018-05-04T14:22:54.313 回答