Массив строк Фибоначчи

Question

У меня есть массив: AB AB BAB ABBAB BABABBAB ... Номер каждого члена массива основывается на числе Фибоначчи. Сложите n-ю строку и n + 1-ю строку вместе, затем получая n + 2-я строка, например. BABABBAB = BAB + ABBAB. Тогда будет ли 10 ^ 16-я буква А или В?

Answer 1

Пусть f[n] будет n th числом Фибоначчи .

Предположим, что мы хотим найти значение в позиции x в строке, полученной конкатенацией f[1], f[2], ..., f[n].

1. Найдите самый низкий k такой, что f[1] + f[2] + ... + f[k] >= x.Таким образом, позиция x принадлежит слову, которое имеет f[k] символов (по крайней мере, в конкатенации, которое оно имеет. Но так как все слова состоят из a и b, мы постараемся свести проблему только к темдва).
2. Чтобы найти положение, соответствующее x в выражении f[k], вычтите f[1] + ... + f[k - 1] из x.
3. , если k = 1, напечатайте a, еслиk = 2 print b, иначе перейти к шагу 4.
4. 1. , если f[k - 2] < x, то позиция, которую мы ищем, находится в слове, соответствующем (с длиной) f[k - 1].Вычтите 1 из k и f[k - 2] из x и перейдите к step 3 .
   2. Иначе, искомая позиция находится в слове, соответствующем f[k - 2],Вычтите 2 из k, оставьте x без изменений и перейдите к шаг 3 .

Это не требует генерации фактических слов, простоих длины, которые являются основными числами Фибоначчи.

Обработанный пример - обратите внимание, что я использую только фактические слова в целях иллюстрации, они не нужны.

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

Объединяя все это, мы получаем: ababbababbabbababbab.Давайте спросим себя, что находится на позиции 10 (это 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'.

Answer 2

пожалуйста, не воспринимайте этот ответ слишком серьезно:

Я никогда не был хорош и математичен, и это звучит так, как будто эта задача должна быть слишком тяжелой, чтобы ее можно было вычислить без странного алгоритма, поэтому мое решение было бы простодогадка.чтобы выбрать между A и B, я бы написал в php очень простую программу для печати первых 15 или 20 "строк":

<?php
$var1 = "B";
$var2 = "A";
for($i=3;$i<=15;$i++){
    $tmp = $var2;
    $var2 = $var1;
    $var1 = $tmp.$var1;
    echo $i." ".$var1."<br>";
}
echo strlen(implode('',explode('B',$var1)));
echo "<br>";
echo strlen(implode('',explode('A',$var1)));
?>

результат показывает, что всегда меньшеA с (38%), чем B с (62%) - так что шанс быть правым при угадывании B не так уж и плох.