Форум » Рекурсивные процедуры и функции » задание 16, № 78 » Ответить
задание 16, № 78
Yflzf55: Решаю задачу с помощью массива. когда 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
Поляков: Yflzf55 пишет: F(n) = F(n-3) – (n-3), когда n > 1 и не делится на 3. В условии по-другому.
Yflzf55: 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)
Поляков: Yflzf55 пишет: На мой взгляд F(n) = n + F(n+3) эквивалентно F(n) = F(n-3) – (n-3) Нет. Потому что первый случай - это "рекурсия вперед" (с шансом уйти в бесконечность), а второй - "рекурсия назад", которая всегда закончится.
Yflzf55: мое решение: Когда n > 1 и не делится на 3, F(n) бесконечна, Поэтому рассматриваем только те n, которые делятся на 3, и для которых были вычислены F(n/3 – 1) программа имеет сл. вид: [pre2] 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 [/pre2]
полная версия страницы