斐波那契字符串定义如下:
例如，前几个斐波那契字符串是
a
bc
abc
bcabc
abcbcabc
目标是给定一行和一个偏移量，以确定该偏移量处的字符。更正式的:
Input: Two integers separated by a space - K and P(0 < K ≤ 109), ( < P ≤ 109), where K is the line number of the Fibonacci string and P is the position number in a row.
Output: The desired character for the relevant test: "a", "b" or "c". If P is greater than the kth row (K ≤ 109), it is necessary to derive «No solution»
Example:
input: 18 58
output: a
我写了这段代码来解决这个问题:
#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;
}
这是正确的吗？你会怎么做？
最佳答案
您可以在不显式计算任何字符串的情况下解决此问题，这可能是解决问题的最佳方法。毕竟，如果要求您计算第 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) 个字符。您可以通过归纳快速看到这一点:
使用这些知识，假设我们要找到斐波那契字符串第七行的第七个字符。我们知道第 7 行由第 5 行和第 6 行的串联组成，因此字符串如下所示:
R(7) = R(5) R(6)
第 5 行有 F(5 + 1) = F(6) = 8 个字符，这意味着第 7 行的前 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)部分。由于我们正在寻找这一行的第七个字符，这意味着我们正在寻找 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));
}
现在，当然，这里所写的实现存在问题。因为行索引的范围可以达到 109，所以我们不可能计算
Fibonacci(row)在所有情况下;十亿分之一的斐波那契数太大了，无法表示!幸运的是，我们可以解决这个问题。如果您查看斐波那契数表，您会发现 F(45) = 1,134,903,170，它大于 109(并且没有比这更小的斐波那契数)。此外，由于我们知道我们关心的索引也必须不大于 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 --;
}
}
}
我还没有测试过这个；套用 Don Knuth 的话，我只是证明它是正确的。 :-) 但我希望这有助于回答您的问题。我真的很喜欢这个问题!
关于c++ - 确定斐波那契字符串的各个字母？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4896720/