Как можно ускорить выполнение рекурсивного кода на C++?

Какие слова нужно перевести с этой картинки, содержащей задачу?
  • 21 апреля 2024 г. 12:20
Ответы на вопрос 2
Для ускорения выполнения рекурсивного кода на C++ можно применить следующие методы:

1. Оптимизация базовых случаев: убедитесь, что базовые случаи рекурсии реализованы эффективно и без лишних условий.
2. Мемоизация: храните результаты выполненных вычислений и используйте их при повторных вызовах функции.
3. Использование итеративных алгоритмов: в некоторых случаях рекурсивный алгоритм может быть заменен на итеративный, что может ускорить выполнение.
4. Переход к хвостовой рекурсии: оптимизация рекурсивной функции таким образом, чтобы все рекурсивные вызовы были в конце функции, что позволяет оптимизатору компилятора сократить использование памяти и ускорить выполнение.

Слова на картинке:
1. initiative
2. ysibaya
3. grasp
4. partition
5. ambiguous
Можно попробовать сделать микрооптимизации: функция F реализуется одним циклом (делите, пока делится на 10, потом берите последнюю цифру). S тоже можно считать циклом, а не рекурсией. 

Но скорее всего, этого не хватит. Это решение за O(q*log(q)). Ограничения на числа в условии не видно, но если там что-то порядка 2000000000, то ваша программа будет считать несколько секунд.

Надо хорошенько подумать и применить математическую хитрость. Надо как-то считать числа в интервале p...q пачками, а не каждое отдельно.

Что такое функция F? Это последняя ненулевая цифра в числе. Давайте вместо суммы значений F счиатать, сколько чисел из интервала дадут вот такое вот значение? Ну просто по последней цифре сложно сказать, сколько там чисел, а вот если еще зафиксировать количество пропущенных в конце нулей, то уже становится понятно, как подсчитать это. Вот допустим, вы считаете последнюю цифру d и там должно быть 3 нуля. Тогда вы ищети числа вида "xxxd000". Или их можно представить в виде d*1000+x*10000 для произвольного неотрицательного x. И вот вам надо подсчитать сколько таких чисел в интервале [p,q]. Ну решите 2 уравнения: d*1000+x*10000 >= p и d*1000+x*10000 <= q

Таким образом вы за несколько арифметических действий и одну проверку можете подсчитать, сколько чисел вида "xxxd000" будут в интервале. Осталось циклом перебрать d от 1 до 9 и количество нулей от 0 до длины q. И вот у вас решение за O(log(q)).
Похожие вопросы