Автор | Сообщение |
|
Отправлено: 14.05.22 10:08. Заголовок: задание 16, № 78
Решаю задачу с помощью массива. когда n > 1 и не делится на 3: F(n) = n + F(n+3) из этого соотношения получаю F(n+3) = F(n) - n или F(n) = F(n-3) – (n-3) т.е. функция принимает вид: F(n) = n, при n <= 1, F(n) = n + F(n/3–1), когда n > 1 и делится на 3, F(n) = F(n-3) – (n-3), когда n > 1 и не делится на 3. №№ 75-77 по данному алгоритму получились. Что здесь не так? Где ошибка?
|
|
|
Ответов - 4
[только новые]
|
|
|
| Администратор
|
Сообщение: 3538
|
|
Отправлено: 14.05.22 11:38. Заголовок: Yflzf55 пишет: F(n) ..
Yflzf55 пишет: цитата: | F(n) = F(n-3) – (n-3), когда n > 1 и не делится на 3. |
|
В условии по-другому.
|
|
|
|
Отправлено: 14.05.22 15:06. Заголовок: F(n) = n + F(n+3), к..
F(n) = n + F(n+3), когда n > 1 и не делится на 3. отсюда получаю: F(n+3) = F(n) - n или F(n) = F(n-3) – (n-3). Что не так? Не понимаю... На мой взгляд F(n) = n + F(n+3) эквивалентно F(n) = F(n-3) – (n-3)
|
|
|
|
| Администратор
|
Сообщение: 3543
|
|
Отправлено: 17.05.22 13:26. Заголовок: Yflzf55 пишет: На мо..
Yflzf55 пишет: цитата: | На мой взгляд F(n) = n + F(n+3) эквивалентно F(n) = F(n-3) – (n-3) |
|
Нет. Потому что первый случай - это "рекурсия вперед" (с шансом уйти в бесконечность), а второй - "рекурсия назад", которая всегда закончится.
|
|
|
|
Отправлено: 14.05.22 16:13. Заголовок: мое решение: Когда n..
мое решение: Когда n > 1 и не делится на 3, F(n) бесконечна, Поэтому рассматриваем только те n, которые делятся на 3, и для которых были вычислены F(n/3 – 1) программа имеет сл. вид: arr = [0]*20000 arr[0] = 0 arr[1] = 1 arr[3] = 3 n = 4 while True: if n%3 == 0 and arr[n//3-1] > 0: arr[n] = n + arr[n//3-1] if arr[n] > 1000: print(arr[n]) print(n) break n = n + 1
|
|
|
|