Определение отдельных букв строк Фибоначчи? - PullRequest
Новая
       1

Определение отдельных букв строк Фибоначчи?

8 голосов
/ 04 февраля 2011

Строки Фибоначчи определяются следующим образом:

  • Первая строка Фибоначчи "a"
  • Вторая строка Фибоначчи "bc"
  • The (n + 2) ая строка Фибоначчи - это конкатенация двух предыдущих строк Фибоначчи.

Например, первые несколько строк Фибоначчи: 

a
bc
abc
bcabc
abcbcabc

Цель - получитьстрока и смещение, чтобы определить, какой символ находится в этом смещении.Более формально:

Ввод: Два целых числа, разделенных пробелом - K и P (0 9 ), (

9 ), где K - номер строки Фибоначчи, а P - номер позиции в строке.

Вывод: Требуемый символ для соответствующего теста: "a", "b" или "c".Если P больше k-й строки (K ≤ 10 9 ), необходимо получить «Нет решения»

Пример:

ввод: 18 58

вывод: 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;
}

Это правильно?Как бы вы сделали?

Ответы [ 5 ]

14 голосов
/ 31 августа 2011

Вы можете решить эту проблему, не вычисляя явно ни одну из строк, и это, вероятно, лучший способ решения проблемы.В конце концов, если вас попросят вычислить 50-ю строку Фибоначчи, вам почти наверняка не хватит памяти;F (50) равно 12 586 269 025, поэтому вам понадобится более 12 ГБ памяти только для ее удержания!

Интуиция, лежащая в основе решения, заключается в том, что каждая строка строк Фибоначчи состоит из символов предыдущих строкВы можете преобразовать пару (строка, смещение) в другую пару (строка ', смещение'), где новая строка всегда для строки Фибоначчи меньшего размера, чем та, с которой вы начали.Если вы повторите это достаточно много раз, в конечном итоге вы вернетесь к строкам Фибоначчи либо для строки 0, либо для строки 1, и в этом случае ответ может быть немедленно считан.

Чтобы заставить этот алгоритм работать, мынужно установить несколько фактов.Во-первых, давайте определим ряд Фибоначчи с нулевой индексацией;то есть последовательность равна 

F(0)   = 0
F(1)   = 1
F(n+2) = F(n) + F(n + 1)

. Учитывая это, мы знаем, что в n-й строке (с одним индексом) строк Фибоначчи содержится всего F (n + 1) символов.Вы можете увидеть это быстро по индукции:

  • Строка 1 имеет длину 1 = F (2) = F (1 + 1)
  • Строка 2 имеет длину 2 = F (3)= F (2 + 1).
  • Для некоторой строки n + 2 длина этой строки определяется как Size (n) + Size (n + 1) = F (n + 1) + F (n + 2) = F (n + 3) = F ((n + 2) + 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) часть.Так как мы ищем седьмой символ этой строки, это означает, что мы ищем 7 - F (4) = 7 - 3 = 4-й символ R (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));
}

Теперь, конечно, есть проблема с реализацией, как написано здесь.Поскольку индекс строки может варьироваться до 10 9 , мы не можем вычислить Fibonacci(row) во всех случаях;Миллиардное число Фибоначчи слишком велико, чтобы его представлять!

К счастью, мы можем обойти это. Если вы посмотрите на таблицу чисел Фибоначчи, то обнаружите, что F (45) = 1 134 903 170, что больше 10 9 (и не меньшее число Фибоначчи больше этого). Более того, поскольку мы знаем, что индекс, который нас интересует, также не должен превышать одного миллиарда, если мы находимся в строке 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 --;
       }
    }
}

Я еще не проверял это; Перефразируя Дона Кнута, я просто доказал, что это правильно. :-) Но я надеюсь, что это поможет ответить на ваш вопрос. Мне очень понравилась эта проблема!

1 голос
/ 04 февраля 2011

Я полагаю, что ваша общая идея должна быть в порядке, но я не понимаю, как ваш код будет справляться с большими значениями K, потому что числа станут огромными быстро, и даже с большими целочисленными библиотеками это может занять практически навсегда точно вычислить Фибоначчи (10 ^ 9).

К счастью, вас спрашивают только о первых 10 ^ 9 символах. Строка достигнет такого количества символов уже на 44-й строке (f (44) = 1134903170).

И если я не ошибаюсь, с этого момента первые 10 ^ 9 символов будут просто чередоваться между префиксами строк 44 и 45 и, следовательно, в псевдокоде: 

def solution(K, P):
   if K > 45:
       if K % 2 == 0:
           return solution(44, P)
       else:
           return solution(45, P)
   #solution for smaller values of K here
0 голосов
/ 04 мая 2018

Я сделал еще один пример, в котором каждому соответствующему числу рядов Фибоначчи соответствует буква в алфавите. Итак, для 1 - это a, для 2 - это b, для 3 - это c, для 5 - это e ... и т.д .: 

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string a = "abcdefghijklmnopqrstuvwxyz"; //the alphabet
    string a1 = a.substr(0,0); string a2 = a.substr(1,1); string nexT = a.substr(0,0);

    nexT = a1 + a2;

   while(nexT.length() <= a.length())
    {
        //cout << nexT.length() << ", ";             //show me the Fibonacci numbers
        cout << a.substr(nexT.length()-1,1) << ", "; //show me the Fibonacci letters
        a1 = a2;
        a2 = nexT;
        nexT = a1 + a2;
    }
    return 0;
}

Выход: a, b, c, e, h, m, u,

0 голосов
/ 04 февраля 2011

Я бы вычислил K-ю строку Фибоначчи, а затем получил бы ее P-й символ. Примерно так: 

#include <iostream>
#include <string>
#include <vector>

std::string FibonacciString(unsigned int k)
{
    std::vector<char> buffer;
    buffer.push_back('a');
    buffer.push_back('b');
    buffer.push_back('c');

    unsigned int curr = 1;
    unsigned int next = 2;

    while (k --)
    {
        buffer.insert(
            buffer.end(),
            buffer.begin(),
            buffer.end());

        buffer.erase(
            buffer.begin(),
            buffer.begin() + curr);

        unsigned int prev = curr;
        curr = next;
        next = prev + next;
    }

    return std::string(
        buffer.begin(),
        buffer.begin() + curr);
}

int main(int argc, char** argv)
{
    unsigned int k, p;
    std::cin >> k >> p;

    -- p;
    -- k;

    std::string fiboK = FibonacciString(k);
    if (p > fiboK.size())
        std::cout << "No solution";
    else
        std::cout << fiboK[p];
    std::cout << std::endl;
    return 0;
}

Он использует больше памяти, чем ваша версия, поскольку он должен хранить как N-ю, так и (N + 1) -ю строку Фибоначчи в каждый момент времени Однако, поскольку он действительно близок к определению, он работает для каждого значения.

Кажется, у вашего алгоритма есть проблема, когда k велико, а p мало. Тест fib_num[k] < p будет разыменовывать элемент вне диапазона массива с k = 30 и p = 1, не так ли?

0 голосов
/ 04 февраля 2011

Я нашел это.Я не проводил предварительную проверку (получал размер k -ой строки фибоначчи для проверки p againt), потому что если проверка прошла успешно, вам все равно придется ее вычислять.Конечно, как только k станет большим, вы можете столкнуться с проблемой переполнения (длина строки фибоначчи является экспоненциальной функцией индекса n ...). 

#include <iostream>
#include <string>

using namespace std;

string fibo(unsigned int n)
{
    if (n == 0)
        return "a";
    else if (n == 1)
        return "bc";
    else
        return fibo(n - 2) + fibo(n - 1);

}

int main()
{
    unsigned int k, p;
    cin >> k >> p;
    --k;
    --p;
    string fiboK = fibo(k);
    if (p > fiboK.size())
        cout << "No solution" << endl;
    else
        cout << fiboK[p] << endl;
    return 0;
}

РЕДАКТИРОВАТЬ:Хорошо, теперь я вижу вашу точку зрения, т.е. проверяем, в какой части k -ой строки p находится (то есть в строке k - 2 или k - 1, и обновляем p при необходимости).Конечно, это хороший способ сделать это, так как, как я говорил выше, мое наивное решение взорвется слишком быстро.

Ваш путь выглядит правильно для меня с точки зрения алгоритма (экономит память и сложность).

...