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

@vwodzz · Регистрация: 19.11.2020

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

Задача.
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следую-
щими соотношениями:
F(n) = n, если n ≥ 10 000,
F(n) = n/6 + F(n/6 + 2), если n < 10 000 и n делится на 6,
F(n) = n + F(n + 2) , если n < 10 000 и n не делится на 6
Чему равно значение выражения F(264) – F(7)?

1 Решить задачу вручную (аналитически).
2 Решить задачу с помощью рекурсии
3 Решить задачу динамически (с помощью списка или без него)

@amogus_007 · 04.06.2023, 19:08

1. Решение задачи вручную (аналитически):

Для решения данной задачи вручную, нужно последовательно применить указанные соотношения до тех пор, пока не достигнем базового случая (n ≥ 10 000).

F(264) – F(7) можно вычислить следующим образом:

F(7) = 7 + F(7 + 2) = 7 + F(9)
F(9) = 9/6 + F(9/6 + 2) = 9/6 + F(3)
F(3) = 3 + F(3 + 2) = 3 + F(5)
F(5) = 5 + F(5 + 2) = 5 + F(7)

Таким образом, F(7) = 7 + 9/6 + 3 + 5 + F(7) + F(9) + F(3) + F(5).
Получаем уравнение: F(7) = 24 + F(7) + F(9).
Решаем его: F(7) = 12 + F(9).

Теперь вычислим F(264):

F(264) = 264/6 + F(264/6 + 2) = 264/6 + F(44)
F(44) = 44 + F(44 + 2) = 44 + F(46)
F(46) = 46 + F(46 + 2) = 46 + F(48)
F(48) = 48 + F(48 + 2) = 48 + F(50)

Таким образом, F(264) = 264/6 + 44 + 46 + 48 + F(50).

Теперь вычислим значение выражения F(264) – F(7):

F(264) – F(7) = (264/6 + 44 + 46 + 48 + F(50)) - (12 + F(9))
= (264/6 + 44 + 46 + 48 + F(50)) - (12 + 9/6 + 3 + 5 + F(7) + F(9))
= 264/6 + 44 + 46 + 48 + F(50) - 12 - 9/6 - 3 - 5 - F(7) - F(9)
= 264/6 - 9/6 + 44 + 46 + 48 + F(50) - 12 - 3 - 5 - F(7) - F(9)
= 255/6 + 44 + 46 + 48 + F(50) - 12 - 3 - 5 - F(7) - F(9)
= 42.5 + 44 + 46 + 48 + F(50) - 12 - 3 - 5 - F(7) - F(9)
= 233.5 + F(50) - F(7) - F(9)

Значение выражения F(264) – F(7) равно 233.5 + F(50) - F(7) - F(9). Теперь мы можем перейти к решени

ю задачи с помощью рекурсии или динамического программирования.

2. Решение задачи с помощью рекурсии:

Python
1
2
3
4
5
6
7
8
9
10
def calculate_F(n):
    if n >= 10000:
        return n
    elif n % 6 == 0:
        return n / 6 + calculate_F(n / 6 + 2)
    else:
        return n + calculate_F(n + 2)
 
result = calculate_F(264) - calculate_F(7)
print(result)

В данном решении используется рекурсивная функция `calculate_F`, которая вычисляет значение функции F(n) в соответствии с заданными соотношениями. Результатом вычисления выражения F(264) – F(7) является значение переменной `result`.

3. Решение задачи динамически:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def calculate_F(n):
    if n >= 10000:
        return n
 
    dp = [0] * (n + 1)
    dp[0] = 0
 
    for i in range(1, n + 1):
        if i % 6 == 0:
            dp[i] = i / 6 + dp[i // 6 + 2]
        else:
            dp[i] = i + dp[i + 2]
 
    return dp[n]
 
result = calculate_F(264) - calculate_F(7)
print(result)

В данном решении используется динамическое программирование с использованием списка `dp`. Значение функции F(n) для каждого n вычисляется один раз и сохраняется в списке `dp`. Результатом вычисления выражения F(264) – F(7) является значение переменной `result`.

@thyrex · 04.06.2023, 23:53

amogus_007, как давно 9 стало делиться нацело на 6, а 48 перестало делиться на 6? Или это Вам ИИ такое решение подсказал?

@eaa · 05.06.2023, 07:27

vwodzz, а рекурсия это разве не динамическое программирование?

Новые блоги и статьи Все статьи Все блоги /
1С: Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .
Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .

@vwodzz 0 / 0 / 0 Регистрация: 19.11.2020 Сообщений: 15

	Алгоритм вычисления значения функции f(n) 24.05.2023, 19:46. Показов 2483. Ответов 3 Метки нет (Все метки) Задача. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следую- щими соотношениями: F(n) = n, если n ≥ 10 000, F(n) = n/6 + F(n/6 + 2), если n < 10 000 и n делится на 6, F(n) = n + F(n + 2) , если n < 10 000 и n не делится на 6 Чему равно значение выражения F(264) – F(7)? 1 Решить задачу вручную (аналитически). 2 Решить задачу с помощью рекурсии 3 Решить задачу динамически (с помощью списка или без него) Миниатюры 0

@thyrex 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	04.06.2023, 23:53
	amogus_007, как давно 9 стало делиться нацело на 6, а 48 перестало делиться на 6? Или это Вам ИИ такое решение подсказал? 3

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	05.06.2023, 07:27
	vwodzz, а рекурсия это разве не динамическое программирование? 1