斐波那契字符串数组 [英] Fibonacci string array

问题描述

我有一个数组：AB AB BAB ABBAB BABABBAB ...阵列的每个术语的数量是基座上的斐波number.Put第n串和n + 1个串在一起，然后制备N + 2个字符串，eg.BABABBAB = BAB + ABBAB。 然后是10 ^ 16个字母是A还是B？

解决方案

让 F [N] 是 N 日 Fibonacci数。

假设我们要查找的字符串通过连接 F获得的位置 X 值[1]，F [2]，.. 。，F [N] 。

1. 找到最低 K ，使得 F [1] + F [2] + ... + F [K]＆GT; = X 。所以位置 X 属于字有 F [K] 字符（至少在它的连接。但由于所有单词从由一个和 B ，我们会尽量减少的问题，只是这两种）。
2. 要找到这个词对应于位置x F [K] ，减 F [1] + ... + F [K - 1]。从 X
3. 如果 K = 1 打印 A ，如果 K = 2 打印 B ，否则到步骤4。
4. 1. 如果 F〔K - 2]其中， X ，那我们要找的位置对应于（长度） F字[K - 1] 。减去1 K 和 F〔K - 2] 从 X 并转至第3步
   2. 否则，我们正在寻找的位置对应于 F字[K - 2] 。从 K 减去2，离开 X 不变，并转至第3步

这并不需要产生实际的话，只是它们的长度，这是基本的斐波那契数。

样例 - 注意，我只使用实际字说明目的，他们不需要

  N·[N]对应的字
1 1一
2 1b中
3 2 AB
4 3 BAB
5 abbab
6 8 bababbab
 

连接所有这些问题，我们得到： ababbababbabbababbab 。让我们问自己什么是在位置 10 （这是 B ）。

  1。 F [1] + F [2] + F [3] + F [4] + F [5]≥= 10，所以K = 5
2. X = 10中，f [1] + F [2] + F [3] + F [4] = 7，所以从x中减去7，得到X = 3
3'。 k不是1或2，则跳过此。
4'。 F〔K  -  2 = 3] = 2;的X. K = 4，X = 1
3''。还是无视这一点。
4''F〔K  -  2 = 2] = 1＆GT; = X。 K = 2中，x = 1
3'''。 K = 2，打印B。
 

I have an array: A B AB BAB ABBAB BABABBAB ... The number of each term of the array is base on the Fibonacci number.Put the n-th string and the n+1-th string together, then producing the n+2-th string,eg.BABABBAB = BAB + ABBAB. Then is the 10^16-th letter is A or B?

解决方案

Let f[n] be the nth fibonacci number.

Assume we want to find the value at position x in the string obtained by concatenating f[1], f[2], ..., f[n].

1. Find the lowest k such that f[1] + f[2] + ... + f[k] >= x. So position x belongs to word that has f[k] characters (at least in the concatenation it does. But since all words are made up from a and b, we'll try to reduce the problem to just those two).
2. To find the position corresponding to x in the term f[k], subtract f[1] + ... + f[k - 1] from x.
3. if k = 1 print a, if k = 2 print b, else go to step 4.

4. 1. if f[k - 2] < x, then the position we're looking for is in the word corresponding to (with length) f[k - 1]. Subtract 1 from k and f[k - 2] from x and go to step 3.
   2. Else, the position we're looking for is in the word corresponding to f[k - 2]. Subtract 2 from k, leave x unchanged and go to step 3.

This doesn't require generating the actual words, just their lengths, which are the basic fibonacci numbers.

Worked example - note that I'm only using the actual words for illustration purposes, they are not needed.

n  f[n]  corresponding word
1  1     a
2  1     b
3  2     ab
4  3     bab
5  5     abbab 
6  8     bababbab

Concatenating all these we get: ababbababbabbababbab. Let's ask ourselves what's at position 10 (it's b).

1. f[1] + f[2] + f[3] + f[4] + f[5] >= 10, so k = 5
2. x = 10, f[1] + f[2] + f[3] + f[4] = 7, so subtract 7 from x, giving x = 3
3'. k isn't 1 or 2, skip this.
4'. f[k - 2 = 3] = 2 < x. k = 4, x = 1
3''. still ignoring this.
4'' f[k - 2 = 2] = 1 >= x. k = 2, x = 1
3'''. k = 2, print 'b'.

这篇关于斐波那契字符串数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！