Рассмотрим следующее отношение повторения.Поиск закрытой формы для рекурсивной функции
T(n) = 5 if n <= 2
T(n-1) + n otherwise
Закрытая форма раствор для T(n) является
Я получил решение как n(n+1)/2 + 7 для всех значений. Но на моем университетском экзамене они дали решение n(n+1)/2 + 2. Однако это решение не заканчивается на 5 для значений n<2. Может ли кто-нибудь объяснить это?
Решим это; первым давайте расширим телескопические суммы:
T(k) = T(k)
T(k + 1) = T(k) + k + 1
T(k + 2) = T(k + 1) + k + 2 = T(k) + k + 1 + k + 2
...
T(k + m) = T(k) + k + 1 + k + 2 + ... + k + m =
= T(k) + mk + 1 + 2 + ... + m =
= T(k) + mk + (1 + m) * m/2
...
Теперь у нас есть
T(k + m) = T(k) + mk + (1 + m) * m/2
Пусть k = 2:
T(m + 2) = T(2) + 2m + (1 + m) * m/2 = 5 + 2m + (1 + m) * m/2
Наконец, m + 2 = n или m = n - 2:
T(n) = 5 + 2 * (n - 2) + (n - 1) * (n - 2)/2 = n * (n + 1)/2 + 2
Мы
T(n) = n * (n + 1)/2 + 2 when n > 2
T(n) = 5 when n <= 2
Когда вы рассматриваете решение закрытой формы, можем ли мы добавить исключения, что T (n) недействителен при n <2. Функция T (n) должна прерываться при всех значениях без каких-либо исключений. Разве это не означает, что закрытая форма ...? Если мы добавим исключения, что при n <2, T (n) даст другой результат ... тогда как мы можем назвать это замкнутым решением формы? –
@ Y.Surya Narayana: как вы можете видеть, мы начинаем с * расширения * серии: 'T (k) = ... T (k + 1) = ...' поэтому душа является истиной, начиная с некоторых ' k'. Затем мы явно помещаем 'k = 2', который является минимальным индексом, который мы использовали, поэтому решение верно для индексов больше, чем' 2': 'T (n) = n * (n + 1)/2 + 2, когда n > 2': мы не вычислили 'T (2)', но взяли его. –
В качестве простого нестрогую рассуждения упражнения, мы знали, что T(n) = T(n-1) + n дает сумму первых n цифр: S(n) = n * (n + 1)/2
Теперь, когда n=2, S(2) = 3, поэтому значение 5 является фактически прирост на 5 - S(2) = 2. Таким образом, мы могли бы сказать:
T(n) = S(n) + (5 - S(2)) for n >=2
или
T(n) = S(n) + 2 for n >= 2
T(n) = 5 for n <= 2
Обратите внимание, что в n=2, два отношения идентичны.
n (n + 1)/2 + 2 не является решением заданных уравнений. Что объяснить? –
@PaulHankin проверил его, 'n (n + 1)/2 + 2' работает для всех значений в диапазоне 2-50. Не работает для 'n = 1', но кроме этого это определенно решение. – Paul
Я голосую, чтобы закрыть этот вопрос как не по теме, потому что это чистый математический вопрос, а не вопрос программирования. –