Как рассчитать n-й символ слова Фибоначчи? - PullRequest
Новая
       9

Как рассчитать n-й символ слова Фибоначчи?

1 голос
/ 21 марта 2019

Проблема состоит в том, чтобы найти n-й символ первой строки (в последовательности слов Фибоначчи), длина которой больше заданной длины.

Пример: 

A = 1415926535  
B = 8979323846  
Find F(n) for n = 35  
The first few terms of  are:  
1415926535,  
8979323846,  
1415926535 8979323846,  
8979323846 1415926535 8979323846,  
1415926535 8979323846 8979323846 1415926535 8979323846

Здесь пятая строка первая содержит более 35 символов, поэтому F (35) = 35-й символ, то есть 9 - это ответ.

Я пытался использовать массив структур, определенных как 

typedef struct obj
{
    struct obj *one;
    struct obj *two;
    char len[101]; //Given maximum length 100
    char string;
} OBJ;
OBJ result[300]; //Given that n < 2^100 which means around 250 lines max. 

//Here i denotes line number.
result[1].string = 'a';
strcpy(result[1].len, len_a);
result[2].string = 'b';
strcpy(result[2].len, len_b);
int i = 3;
while (1)
{
    result[i].one = &result[i - 2];
    result[i].two = &result[i - 1];
    strcpy(result[i].len, addStrings(result[i - 1].len, result[i-2].len));
    if (compareStrings(result[i].len, char_n) >= 0)
        break;
    i++;
}  
while (1)
{
    if (solution->string == 'a')
    {
        n = strtoull(char_n, &end, 10);
        return a[n - 1];
    }
    if (solution->string == 'b')
    {
        n = strtoull(char_n, &end, 10);
        return b[n - 1];
    }
    if (compareStrings(solution->one->len, char_n) >= 0)
    { 
        solution = solution->one;
        i -= 2;
    }
    else
    {
        char_n = subStrings(char_n, solution->one->len); 
        //n = n-len(one)
        solution = solution->two;
        i -= 1;
    }
}

где указатель один содержит указатель на второй последний элемент, указатель два - указатель на последний элемент, длина - длина строки. Здесь len - строка для обработки чисел больше 2 ^ 64. Функции сложения и вычитания определены и работают во всех случаях, которые я пробовал. Полный код здесь: [Вторая попытка] [4]

Сбой около 9 тестов. Я все еще что-то упускаю?

...