Алгоритм вычисления значения функции F(n)

@monc63 · Регистрация: 17.07.2023

Студворк — интернет-сервис помощи студентам

Доброго времени суток. Решаю вот это заданиеhttps://education.yandex.ru/eg... ca4f7e0d07 На плюсах, вот код.

C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include<big_integer.hpp>
using namespace std;
big_integer F(big_integer n) {
    if (n <= 1000) return n.pow(n*n);
    if (n > 1000) return n + 2 * F(n - 2) + 6 * F(n - 6);
}
int main()
{
    std::cout << F(20024) - 2 * F(20022) - 3 * F(20020) + 18 * F(20014);
}

Но выдает вот такое сообщение Необработанное исключение по адресу 0x0014F319 в EG16_Yandex.exe: 0xC00000FD: Stack overflow (параметры: 0x00000001, 0x00602FA4). Судя по все ошибка по памяти. Как можно ее решить? Помогите пожалуйста)).

Verevkin · 11.01.2025, 10:58

Не нравится мне это. Надо звать математика, чтоб попробовал преобразовать как-то это аналитически. А то не только стека может не хватить, а ваще - памяти.
Значения функции для n = 1...25 выглядят так:

Алгоритм вычисления значения функции F(n)

@gunslinger · 11.01.2025, 11:39

Аналитическое решение (там же есть видео и текстовая подсказка с описанием общего алгоритма, хотя и без них можно догадаться):

Code
1
2
3
4
5
6
7
8
9
F(20024) = 20024 + 2 * F(20022) + 6 * F(20018)
2 * F(20022) = 40044 + 4 * F(20020) + 12 * F(20016)
3 * F(20020) = 60060 + 6 * F(20018) + 18 * F(20014)
18 * F(20014) = 360252 + 36 * F(20012) + 108 * F(20008)
 
20024 + 2 * F(20022) + 6 * F(20018) - 40044 - 4 * F(20020) - 12 * F(20016) -
60060 - 6 * F(20018) - 18 * F(20014) + 360252 + 36 * F(20012) + 108 * F(20008) = 
280172 + 2 * F(20022) - 4 * F(20020) - 12 * F(20016) - 18 * F(20014) + 36 * F(20012) + 108 * F(20008) =
320216 - 18 * F(20014) + 36 * F(20012) + 108 * F(20008) = -40036

Ответ (правильный): -40036

Остальные похожие задания делаются (скорей всего) аналогично.

@monc63 · 11.01.2025, 14:51 **[ТС]**

Значит такие выражение кодом можно не делать. Хотя, интересно было бы реализовать, особенно на С++

@gunslinger · 11.01.2025, 17:23

Такие выражения нужно пытаться сократить (если получится). Напрямую сразу писать код - никакой памяти может не хватить, как уже было сказано выше.
Суть задания (скорей всего) не в написании кода по готовым формулам, а в шевелении извилинами.
Код на крайний случай, если других вариантов нет (или они не работают).

Для этой задачи:

Вариант решения 1

Чтобы решить задание, надо расписывать значения функции F(n) с конца, от тех значений n, которые нужны для вычисления выражения. Это помогает быстрее упростить выражение и избежать лишних вычислений.

1. Изучи условия задачи и выбери начальную точку
Определи, какие значения функции нужно найти, чтобы вычислить выражение. Например, если требуется вычислить F(54) − F(50), имеет смысл начать с F(54) и последовательно двигаться назад, чтобы выразить значения F(53), F(52) и так далее, пока не станет понятно, как они взаимодействуют.

2. Последовательно вычисли значения функции от нужного n назад
Начни с самого большого n, которое нужно для выражения, и последовательно двигайся к меньшим значениям. Для каждого n используй соответствующее правило, чтобы выразить F(n) через предыдущее значение. В процессе можно увидеть, что часть выражений упрощается или сокращается.

3. Выяви закономерности и сокращения в выражении
Постепенно можно заметить, что некоторые слагаемые или множители сокращаются. Это помогает быстрее прийти к окончательному числу или к упрощённому виду выражения.

4. Подставь конечные значения и вычисли ответ
Когда все нужные значения функции для выражения найдены, подставь их и упрости результат, чтобы получить окончательное число.

@Pphantom · 11.01.2025, 17:38

Сообщение от gunslinger

Напрямую сразу писать код - никакой памяти может не хватить, как уже было сказано выше.

Ну вообще-то можно и сразу код писать, вопрос в том, какой.

В каком месте задания сказано, что это нужно ваять на C++ (да и на любом другом языке общего назначения), а не в какой-нибудь системе компьютерной алгебры?

Потому что вот такое, например, поделие на Maxima выдает ответ сразу же:

Code
1
2
F(n):=if n>20000 then n+2*F(n-2)+6*F(n-6) else x$
expand(F(20024)-2*F(20022)-3*F(20020)+18*F(20014));

@gunslinger · 11.01.2025, 17:44

Как вариант. Я об этом думал (смутно), но проверить "руки не дошли".

@Alex1126 · 11.01.2025, 18:05

Ну если раскрыть F(20024) то член 2F(20022) сокращается. Тоже самое и с 3F(20020). Далее они уже между собой сокращаться будут

@monc63 · 11.01.2025, 18:21 **[ТС]**

Спасибо, я о такой программе и не знал.

@gunslinger · 11.01.2025, 18:24

Кстати, да. Я сложным путем пошел, а можно гораздо проще (если лучше смотреть).

Code
1
2
3
F(20024) = 20024 + 2 * F(20022) + 6 * F(20018)
3 * F(20020) = 60060 + 6 * F(20018) + 18 * F(20014)
F(20024) - 2 * F(20022) - 3 * F(20020) + 18 * F(20014) = -40036

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

Verevkin Злостный нарушитель 10359 / 5774 / 1274 Регистрация: 12.03.2015 Сообщений: 26,686
	11.01.2025, 10:58
	Не нравится мне это. Надо звать математика, чтоб попробовал преобразовать как-то это аналитически. А то не только стека может не хватить, а ваще - памяти. Значения функции для n = 1...25 выглядят так: 0

@monc63 1 / 1 / 0 Регистрация: 17.07.2023 Сообщений: 36
	11.01.2025, 14:51 [ТС]
	Значит такие выражение кодом можно не делать. Хотя, интересно было бы реализовать, особенно на С++ 0

@gunslinger place status here 3190 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,023
	11.01.2025, 17:44
	Как вариант. Я об этом думал (смутно), но проверить "руки не дошли". 0

@Alex1126 431 / 153 / 28 Регистрация: 12.12.2020 Сообщений: 1,239
	11.01.2025, 18:05
	Ну если раскрыть F(20024) то член 2F(20022) сокращается. Тоже самое и с 3F(20020). Далее они уже между собой сокращаться будут 1

@monc63 1 / 1 / 0 Регистрация: 17.07.2023 Сообщений: 36
	11.01.2025, 18:21 [ТС]
	Спасибо, я о такой программе и не знал. 0