找到斐波那契词序列的第 n 个词 (Java)
find nth word of a fibonacci word sequence (Java)
我正在尝试解决这个作业：
令x[0] =0； x[1] =1; x[i] = x[i-2] + x[i-1]
找到单词 x[n] 的第 k 个字符，看它是“0”还是“1”，边界为 1 <= k < n <= 93
例如，对于序列 0110110101101，我们有
x[0] = 0
x[1] = 1
x[2] = 01
x[3] = 101
x[4] = 01101
x[5] = 10101101
当我测试 n = 44 及更高时，IDE 抛出 OutOfMemoryError java 堆 space。我知道我正在做的方式会存储序列的第 n 个单词、第 n-1 个单词和第 n-2 个单词，这会占用大量内存，但我想不出更好的方法。
在论文的一些草稿工作之后，我还看到要找到 n = 3 之后的第 n 个单词，while 循环只需要 运行 n-2 次但没有运气实现
我还尝试将每个单词存储在一个字符串 ArrayList 中并使用递归进行，但效率更低
如有任何提示，我们将不胜感激
这是我的代码
import java.util.Scanner;
public class BinarySequence {
public static void main(String[] args) {
Scanner read = new Scanner(System.in);
int t = read.nextInt(); //number of test to run
while (t>0){
String s0 = "0";
String s1 = "1";
int n = read.nextInt(); //nth fibonacci word
int k = read.nextInt(); // kth char of the word
System.out.println(fib(s0,s1,n-1).charAt(k-1));
t--;
}
}
private static String fib(String s0,String s1, int n) {
String ans ="";
if(n==0)
return s0;
else if(n==1)
return s1;
else {
while(n>=0){
ans = s0+s1;
s0=s1;
s1=ans;
n--;
}
return ans;
}
}
}
输入k被限制在1和92之间，所以为了计算序列字符串你只需要前92个字符。但是，对于每个不同的 x[i] 值，字符串的开头都会发生变化。对于第一个 11¹ x[i] 值，字符串取决于 x[i-1] 和 x[i-2] 的完整值，但是 after/at 第一个 x[i] 值取决于 x[i-2] 已经足够长，x[i-1] 的值不再重要，因为它在结果的末尾连接。 x[i-1] 和 x[i-2] 对于较大索引的值可以显示为：
x[i-1] = 1111111...1111111 + xxxxxxxxxx
x[i-2] = 2222222...2222222 + yyyyyyyyyy
x[i] = 2222222...2222222 + yyyyyyyyyy + 1111111...1111111 + xxxxxxxxxx
假设 111...111/222...222 部分（当然这些不是实际字符）的长度为 92 个字符，那么您不需要剩余的内容 xxxxx... 和yyyyy... 在那之后，因为无论如何你都无法用有限的 k 价值到达他们。所以对于你的问题，
的顺序
x[i] = 2222222...2222222 + yyyyyyyyyy + 1111111...1111111 + xxxxxxxxxx
与
相同
x[i] = 2222222...2222222
够高i.
现在剩下的问题是 calculate/select 在计算 x[24] 甚至 x[80] 时应该使用 111..111 或 222...222 的哪个序列.最有可能的是 odd/even 检查你在哪里写了这样的东西：“当 n 是偶数时，使用 x[10]，否则使用 x[11]”。
¹) 检查是否存在任何差一错误，92 个字符的阈值可能不在索引 11.
处
有一个解决方案适用于任何 k，它是一个 int，不包含昂贵的串联操作，具有 O(1) 内存和 O(log(k)) 时间1.
前缀和奇偶校验
该算法使用@Progman 在他们的回答中所做的观察，即如果 a < b 和 a 和 b 具有相同的 parity，则 x[a] 是 x[b] 的前缀（这是根据 x[n-2] 是 x[n] 的前缀这一事实得出的结论）。这意味着我们不需要计算序列中的n项，我们只需要找到j，我定义为最小的数字，使得x[j]的长度为大于 k，并且 j 与 n 具有相同的奇偶校验。
比如n = 12345和k = 1，那么我们只需要计算到x[3] = 101，因为我们知道x[3]是[=33的前缀=] 因为 3 和 12345 都是奇数。所以答案是0.
进入 O(1) 记忆
用于避免存储长序列的零和一的方法如下：
不用计算x
首先注意单词的长度x[n]等于fib[n] 其中fib是斐波那契数列。因此，该方法不是计算 x 中的字符串并索引到 x[n] 以查找是 return 1 还是 0，而是使用 x[n] = x[n-2] + x[n-1]。您可以通过比较 k 与 x[n-2] 的长度（其中 x[n-2] 的长度）来计算 x[n][k] 是 x[n-2] 还是 x[n-1]是 fib[n-2]）。这样比较之后，就知道x[n][k]等于x[n-2][k]还是x[n-1][k-fib[n-2]]了。然后，我们根据需要将 n 设置为 n-1 或 n-2，并根据需要将 k 保持不变或设置为 k-fib[n-2] 来重复此过程。重复此操作直到 n == 0 或 n == 1，此时 k 将为 0，因此 x[n][k] 等于 x[0][0] = 0 或 x[1][0] = 1, 根据定义.
无需存储fib
计算中不需要x，只需要fib，这样可以避免存储长长的数字序列，但是我们肯定需要存储到fib[j]的所有斐波那契数列为了执行上一段中定义的步骤？不我们没有！这是因为我们先找到了j，内存中只保留了fib[i-1]和fib[i]。然后我们重新排列方程以找到 fib[n-2] = fib[n] - fib[n-1]，并使用它回溯斐波那契数列以找到 x[n][k].
实施
既然我已经解释了算法，下面是一个 Java 实现：
首先我们定义一个Fibclass来封装斐波那契数列，使代码更整洁。 （如果您需要坚持一个文件，您可以将其移动到内部 class。）
class Fib {
private long a = 0;
private long b = 1;
private int index = 0;
void advance() {
long sum = a + b;
a = b;
b = sum;
index++;
}
void backtrack() {
long diff = b - a;
b = a;
a = diff;
index--;
}
long getPreviousValue() {
return a;
}
long getCurrentValue() {
return b;
}
int getIndex() {
return index;
}
}
那么，实际的算法：
public class Main {
public static int fibNK(int n, int k) {
Fib fib = new Fib();
// if n is odd, go to the next fib so that fib.getIndex() is 1
// this ensures that n and fib.getIndex() are either both even or both odd
if (n % 2 == 1) {
fib.advance();
}
// find the first fibonacci number greater than k that is still even/odd
while (k >= fib.getCurrentValue()) {
// x+2 is even if x is even, so advance twice
fib.advance();
fib.advance();
}
// now to find character k of the word:
// if we're looking at the first or second fibonacci word, "0" or "1",
// then the character at index k must be 0 or 1
while (fib.getIndex() > 1) {
// only fib[i] and fib[i-1] are stored, but fib[i-2] is needed, so backtrack
fib.backtrack();
// we are trying to find fibWord[i][k]
// fibWord[i][k] = fibWord[i-2] + fibWord[i-1]
// if k >= fibWord[i-2].length, then the target character is in the second part of the word, fibWord[i-1]
if (k >= fib.getPreviousValue()) {
// specifically, if k >= fib[i-2], then fibWord[i][k]==fibWord[i-1][k-fibWord[i-2].length]
k -= fib.getPreviousValue();
} else {
// otherwise, fibWord[i][k]==fibWord[i-2][k], so another backtrack is needed
fib.backtrack();
}
}
// return either 0 or 1
return fib.getIndex();
}
public static void main(String[] args) {
// test the algorithm by using to print the first few words in `x`, one letter at a time
Fib fib = new Fib();
for (int n = 0; n < 8; n++) {
for (int k = 0; k < fib.getCurrentValue(); k++) {
System.out.print(fibNK(n, k));
}
System.out.println();
fib.advance();
}
}
}
去BigInteger或者回家
O(log(k)) 时间复杂度意味着它运行得非常快，即使对于非常大的 k 值也是如此。如果您希望 k 的值大于 Integer.MAX_VALUE（相当于 n 的值大于 45），您可以将 k 更改为 long 但这可能会导致计算斐波那契数时出现溢出错误，因此您需要将一些变量更改为 BigIntegers，尽管这会稍微增加时间和 space 复杂度。
1斐波那契数列有一个exponential lower bound，所以x[n]的长度大于(3/2)**n，也就是说O(log(k)) 需要计算斐波那契数以找到大于 k 的一个。第二阶段然后执行相同数量的“回溯”操作以返回到 x[0] 或 x[1]，这是一个额外的 O(log(k)) 时间，导致总共 O(log(k))。
我正在尝试解决这个作业：
令x[0] =0； x[1] =1; x[i] = x[i-2] + x[i-1]
找到单词 x[n] 的第 k 个字符，看它是“0”还是“1”，边界为 1 <= k < n <= 93
例如，对于序列 0110110101101，我们有
x[0] = 0
x[1] = 1
x[2] = 01
x[3] = 101
x[4] = 01101
x[5] = 10101101
当我测试 n = 44 及更高时，IDE 抛出 OutOfMemoryError java 堆 space。我知道我正在做的方式会存储序列的第 n 个单词、第 n-1 个单词和第 n-2 个单词，这会占用大量内存，但我想不出更好的方法。
在论文的一些草稿工作之后，我还看到要找到 n = 3 之后的第 n 个单词，while 循环只需要 运行 n-2 次但没有运气实现
我还尝试将每个单词存储在一个字符串 ArrayList 中并使用递归进行，但效率更低
如有任何提示，我们将不胜感激
这是我的代码
import java.util.Scanner;
public class BinarySequence {
public static void main(String[] args) {
Scanner read = new Scanner(System.in);
int t = read.nextInt(); //number of test to run
while (t>0){
String s0 = "0";
String s1 = "1";
int n = read.nextInt(); //nth fibonacci word
int k = read.nextInt(); // kth char of the word
System.out.println(fib(s0,s1,n-1).charAt(k-1));
t--;
}
}
private static String fib(String s0,String s1, int n) {
String ans ="";
if(n==0)
return s0;
else if(n==1)
return s1;
else {
while(n>=0){
ans = s0+s1;
s0=s1;
s1=ans;
n--;
}
return ans;
}
}
}
输入k被限制在1和92之间，所以为了计算序列字符串你只需要前92个字符。但是，对于每个不同的 x[i] 值，字符串的开头都会发生变化。对于第一个 11¹ x[i] 值，字符串取决于 x[i-1] 和 x[i-2] 的完整值，但是 after/at 第一个 x[i] 值取决于 x[i-2] 已经足够长，x[i-1] 的值不再重要，因为它在结果的末尾连接。 x[i-1] 和 x[i-2] 对于较大索引的值可以显示为：
x[i-1] = 1111111...1111111 + xxxxxxxxxx
x[i-2] = 2222222...2222222 + yyyyyyyyyy
x[i] = 2222222...2222222 + yyyyyyyyyy + 1111111...1111111 + xxxxxxxxxx
假设 111...111/222...222 部分（当然这些不是实际字符）的长度为 92 个字符，那么您不需要剩余的内容 xxxxx... 和yyyyy... 在那之后，因为无论如何你都无法用有限的 k 价值到达他们。所以对于你的问题，
x[i] = 2222222...2222222 + yyyyyyyyyy + 1111111...1111111 + xxxxxxxxxx
与
相同x[i] = 2222222...2222222
够高i.
现在剩下的问题是 calculate/select 在计算 x[24] 甚至 x[80] 时应该使用 111..111 或 222...222 的哪个序列.最有可能的是 odd/even 检查你在哪里写了这样的东西：“当 n 是偶数时，使用 x[10]，否则使用 x[11]”。
¹) 检查是否存在任何差一错误，92 个字符的阈值可能不在索引 11.
有一个解决方案适用于任何 k，它是一个 int，不包含昂贵的串联操作，具有 O(1) 内存和 O(log(k)) 时间1.
前缀和奇偶校验
该算法使用@Progman 在他们的回答中所做的观察，即如果 a < b 和 a 和 b 具有相同的 parity，则 x[a] 是 x[b] 的前缀（这是根据 x[n-2] 是 x[n] 的前缀这一事实得出的结论）。这意味着我们不需要计算序列中的n项，我们只需要找到j，我定义为最小的数字，使得x[j]的长度为大于 k，并且 j 与 n 具有相同的奇偶校验。
比如n = 12345和k = 1，那么我们只需要计算到x[3] = 101，因为我们知道x[3]是[=33的前缀=] 因为 3 和 12345 都是奇数。所以答案是0.
进入 O(1) 记忆
用于避免存储长序列的零和一的方法如下：
不用计算x
首先注意单词的长度x[n]等于fib[n] 其中fib是斐波那契数列。因此，该方法不是计算 x 中的字符串并索引到 x[n] 以查找是 return 1 还是 0，而是使用 x[n] = x[n-2] + x[n-1]。您可以通过比较 k 与 x[n-2] 的长度（其中 x[n-2] 的长度）来计算 x[n][k] 是 x[n-2] 还是 x[n-1]是 fib[n-2]）。这样比较之后，就知道x[n][k]等于x[n-2][k]还是x[n-1][k-fib[n-2]]了。然后，我们根据需要将 n 设置为 n-1 或 n-2，并根据需要将 k 保持不变或设置为 k-fib[n-2] 来重复此过程。重复此操作直到 n == 0 或 n == 1，此时 k 将为 0，因此 x[n][k] 等于 x[0][0] = 0 或 x[1][0] = 1, 根据定义.
无需存储fib
计算中不需要x，只需要fib，这样可以避免存储长长的数字序列，但是我们肯定需要存储到fib[j]的所有斐波那契数列为了执行上一段中定义的步骤？不我们没有！这是因为我们先找到了j，内存中只保留了fib[i-1]和fib[i]。然后我们重新排列方程以找到 fib[n-2] = fib[n] - fib[n-1]，并使用它回溯斐波那契数列以找到 x[n][k].
实施
既然我已经解释了算法，下面是一个 Java 实现：
首先我们定义一个Fibclass来封装斐波那契数列，使代码更整洁。 （如果您需要坚持一个文件，您可以将其移动到内部 class。）
class Fib {
private long a = 0;
private long b = 1;
private int index = 0;
void advance() {
long sum = a + b;
a = b;
b = sum;
index++;
}
void backtrack() {
long diff = b - a;
b = a;
a = diff;
index--;
}
long getPreviousValue() {
return a;
}
long getCurrentValue() {
return b;
}
int getIndex() {
return index;
}
}
那么，实际的算法：
public class Main {
public static int fibNK(int n, int k) {
Fib fib = new Fib();
// if n is odd, go to the next fib so that fib.getIndex() is 1
// this ensures that n and fib.getIndex() are either both even or both odd
if (n % 2 == 1) {
fib.advance();
}
// find the first fibonacci number greater than k that is still even/odd
while (k >= fib.getCurrentValue()) {
// x+2 is even if x is even, so advance twice
fib.advance();
fib.advance();
}
// now to find character k of the word:
// if we're looking at the first or second fibonacci word, "0" or "1",
// then the character at index k must be 0 or 1
while (fib.getIndex() > 1) {
// only fib[i] and fib[i-1] are stored, but fib[i-2] is needed, so backtrack
fib.backtrack();
// we are trying to find fibWord[i][k]
// fibWord[i][k] = fibWord[i-2] + fibWord[i-1]
// if k >= fibWord[i-2].length, then the target character is in the second part of the word, fibWord[i-1]
if (k >= fib.getPreviousValue()) {
// specifically, if k >= fib[i-2], then fibWord[i][k]==fibWord[i-1][k-fibWord[i-2].length]
k -= fib.getPreviousValue();
} else {
// otherwise, fibWord[i][k]==fibWord[i-2][k], so another backtrack is needed
fib.backtrack();
}
}
// return either 0 or 1
return fib.getIndex();
}
public static void main(String[] args) {
// test the algorithm by using to print the first few words in `x`, one letter at a time
Fib fib = new Fib();
for (int n = 0; n < 8; n++) {
for (int k = 0; k < fib.getCurrentValue(); k++) {
System.out.print(fibNK(n, k));
}
System.out.println();
fib.advance();
}
}
}
去BigInteger或者回家
O(log(k)) 时间复杂度意味着它运行得非常快，即使对于非常大的 k 值也是如此。如果您希望 k 的值大于 Integer.MAX_VALUE（相当于 n 的值大于 45），您可以将 k 更改为 long 但这可能会导致计算斐波那契数时出现溢出错误，因此您需要将一些变量更改为 BigIntegers，尽管这会稍微增加时间和 space 复杂度。
1斐波那契数列有一个exponential lower bound，所以x[n]的长度大于(3/2)**n，也就是说O(log(k)) 需要计算斐波那契数以找到大于 k 的一个。第二阶段然后执行相同数量的“回溯”操作以返回到 x[0] 或 x[1]，这是一个额外的 O(log(k)) 时间，导致总共 O(log(k))。