Я работаю над функцией для вычисления чисел Фибоначчи и возврата младшей цифры этого числа на C++. Я обнаружил, что в C++ самым большим типом данных является __uint128_t, что дает мне 16 байт для работы. Я написал перегрузку для обработки потоковой передачи __uint128_t. Это вычислит до 186-го числа Фибоначчи, а затем переполнится до 187. Мне нужно подняться намного выше 186. Это моя функция:
__uint128_t get_fibonacci_last_digit_fast (int n)
{
__uint128_t f[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n + 1; i++)
{
f[i] = f[i - 1] + f[i -2];
}
return f[n] % 10;
}
Мне известна библиотека boost и другие библиотеки, которые помогают обрабатывать большие данные на C++, но эта функция предназначена для задания, которое необходимо отправить автооценщику, у которого эти библиотеки не установлены. Существуют только стандартные библиотеки C++, поэтому мой код не компилируется при отправке с этими библиотеками. Я рассматриваю возможность создания типа данных для решения этой проблемы. Мы будем очень признательны за любые указания и помощь в продвижении вперед.
«Последовательность Фибоначчи — это ряд чисел, где каждое число представляет собой сумму двух предыдущих чисел». -- возможно, я ошибаюсь, но такое ощущение, что вам не нужны полные числа: вас не волнуют старшие цифры...
Если вас беспокоит только единичная цифра, вы можете применить по модулю к каждому f[i]
. И вам больше не нужен «большой» шрифт.
Зачем вы вычисляете все число, если вам нужна только последняя цифра? Просто используйте обычный int
и на каждом шаге обрезайте все цифры, кроме последней, например. f[i] = (f[i-1] + f[i-2]) % 10;
Вы будете выполнять намного больше %
операций, но целочисленная точность больше не будет проблемой.
Доступ к f[n]
недействителен и выполняется дважды (последняя итерация цикла и оператор возврата).
Кроме того, здесь нет необходимости в массиве; все, что вам нужно, это два последних значения. sum = f0 + f1; f0 = f1; f1 = sum;
.
Существуют только стандартные библиотеки C++. Однако имейте в виду, что автооценщик, похоже, принимает нестандартные типы C++, такие как __uint128_t
, и нестандартный синтаксис C++, например __uint128_t f[n]
. Итак, ваш автооценщик не такой стандарт C++, как вы думаете.
Также укажите один язык. Вы используете C
или C++
?
Пожалуйста, не отмечайте несвязанные языки.
«Я обнаружил, что в C++ самым большим типом данных является __uint128_t». Вам следует изменить «в C++» на «в реализации C++, которую я использую» (и, возможно, указать свой компилятор/инструментарий), поскольку __uint128_t
не стандартный C++. (Двойное подчеркивание 🔁 подразумевает это.) Стандарт C++ гарантирует только целые числа длиной не менее 8 байт (long long
).
В стандартном C++ самые большие целочисленные типы (long long
, unsigned long long
и (C++11 и более поздние версии) типы фиксированной ширины, такие как std::uint64_t
, std::uint_least64_t
) гарантированно будут только 64-битными. (Они могут быть больше, но размеры определяются реализацией, и нет никакой гарантии, что какой-либо целочисленный тип будет больше 64 бит). Вместо того, чтобы пытаться найти (нестандартный) больший тип, я предлагаю вам работать со стандартным контейнером стандартного типа (например, std::vector<unsigned long long>
) и реализовывать нужные вам операции таким образом, чтобы не зависеть от размера целочисленного типа.
Ни одно упражнение «вернуть результат по модулю некоторого числа» не должно быть решено простым применением %
к результату тривиального решения. Смысл этого упражнения обычно в том, чтобы вы выучили (или запомнили) это (a + b) % m == ((a % m) + (b % m)) % m
, поэтому вам понадобится только одна цифра каждого числа в серии; понимая, что вам не нужно хранить более двух последних номеров; и обнаружив, что последняя цифра является периодической.
Если вы знаете, что такое __uint128_t, но не знаете, что такое бигнум, вы держите рукоять стрелы не за тот конец.
Спасибо всем за помощь. Большинство комментариев были очень полезными и информативными. Спасибо.
Если вам нужна только последняя цифра, вы можете использовать точку Пизано:
#include <iostream>
int get_last_digit(unsigned long long n)
{
n %= 60;
if (n <= 1)
return n;
int prev = 0;
int curr = 1;
for (int i = 2; i <= n; ++i)
{
int next = (prev + curr) % 10;
prev = curr;
curr = next;
}
return curr;
}
int main()
{
unsigned long long n = 10000000000008989ULL;
std::cout << get_last_digit(n) << "\n";
}
9
0, 1
:0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, ..., 0, 1
0, 1
повторяется после 60 номеров. Следовательно, мы можем использовать предварительно вычисленный массив, чтобы эффективно получить последнюю цифру для n
по модулю 60 за O(1)
временную сложность:#include <iostream>
int get_last_digit(unsigned long long n)
{
const int pisano[60] = {
0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1,
5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6,
5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1};
return pisano[n % 60];
}
int main()
{
unsigned long long n = 10000000000008989ULL;
std::cout << get_last_digit(n) << "\n";
return 0;
}
Спасибо. Это было очень полезно. Узнал новое из статьи в Википедии. Спасибо.
Небольшое примечание: вы используете VLA (массив переменной длины), который не является частью стандарта C++.