斐波那契字符串定义如下:
例如，前几个斐波那契字符串是
a
bc
abc
bcabc
abcbcabc
给定一行和一个偏移量，目标是确定该偏移量处的字符。更正式地:
我编写了以下代码来解决问题:
#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个Fibonacci字符串，则几乎可以肯定会用完内存。 F(50)是12,586,269,025，因此您仅需要12GB的内存即可容纳它!
解决方案的直觉是，由于斐波那契字符串的每一行都是由前几行的字符组成的，因此您可以将(行，偏移量)对转换为另一行(行，偏移量)，其中新行是始终使用比您开始时使用的弦更小的斐波那契弦。如果重复了足够多次，最终您将返回到第0行或第1行的斐波那契字符串，在这种情况下，可以立即读出答案。
为了使该算法起作用，我们需要建立一些事实。首先，让我们将斐波那契数列定义为零索引；也就是说，顺序是
F(0) = 0
F(1) = 1
F(n+2) = F(n) + F(n + 1)
鉴于此，我们知道斐波那契字符串的第n行(一个索引)在其中总共有F(n + 1)个字符。您可以通过归纳快速查看:
使用此知识，让我们假设我们想要找到斐波那契弦的第七行的第七个字符。我们知道第七行由第五行和第六行的串联组成，因此字符串如下所示:
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)部分。由于我们正在寻找该行的第七个字符，这意味着我们正在寻找R(4)的7-F(4)= 7-3 =第四个字符，所以现在我们去寻找。同样，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 --;
}
}
}
但是我们当然可以做得更好。特别是，如果您得到的行号惊人地大(例如十亿)，那么不断重复循环从行中减去两个直到小于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)，我只是证明它是正确的。 :-)但我希望这有助于回答您的问题。我真的很喜欢这个问题!