Захари:
Допустим, вам дано это
рецидив:
r (n) = 2 * r (n-2) + r (n-1); r (1) = r (2)
= 1
Действительно ли это в форме
основная теорема? Если да, то на словах, что
это говорит?
Я думаю, что ваше рекуррентное отношение говорит о том, что для функции «r» с «n» в качестве ее параметра (представляющего общее количество вводимых вами наборов данных), все, что вы получите в n-й позиции набор данных - это выход n-1-й позиции плюс вдвое больше, чем результат n-2-й позиции, без какой-либо рекурсивной работы. Когда вы пытаетесь решить рекуррентное отношение, вы пытаетесь выразить его так, чтобы не было рекурсии.
Однако я не думаю, что это в правильной форме для метода основной теоремы. Ваше утверждение является «линейным рекуррентным отношением второго порядка с постоянными коэффициентами». Судя по всему, согласно моему старому учебнику по дискретной математике, эта форма вам нужна для решения рекуррентного отношения.
Вот форма, которую они дают:
r(n) = a*r(n-1) + b*r(n-2) + f(n)
Для 'a' и 'b' - некоторые константы, а f (n) - некоторая функция от n. В вашем утверждении a = 1, b = 2 и f (n) = 0. Всякий раз, когда f (n) равен нулю, рекуррентное отношение называется «однородным». Итак, ваше выражение лица однородно.
Я не думаю, что вы можете решить гомогенное рекуррентное отношение, используя метод Theoerm метода Master, потому что f (n) = 0. Ни один из случаев для теоремы метода Master не допускает этого, потому что n-to-power-of -все не может быть равным нулю. Я могу ошибаться, потому что я на самом деле не эксперт в этом, но я не думаю, что можно решить гомогенное рекуррентное отношение с помощью Мастер-метода.
Я понимаю, что способ решения однородного рекуррентного отношения состоит в 5 шагах:
1) Сформируйте характеристическое уравнение, которое имеет вид:
x^k - c[1]*x^k-1 - c[2]*x^k-2 - ... - c[k-1]*x - c[k] = 0
Если у вас есть только 2 рекурсивных экземпляра в вашем гомогенном рекуррентном отношении, то вам нужно всего лишь изменить свое уравнение на квадратное уравнение, где
x^2 - a*x - b = 0
Это потому, что рекуррентное отношение вида
r(n) = a*r(n-1) + b*r(n-2)
Может быть переписано как
r(n) - a*r(n-1) - b*r(n-2) = 0
2) После того как ваше рекуррентное отношение переписано как характеристическое уравнение, затем найдите корни (x [1] и x [2]) характеристического уравнения.
3) С вашими корнями ваше решение теперь будет одной из двух форм:
if x[1]!=x[2]
c[1]*x[1]^n + c[2]*x[2]^n
else
c[1]*x[1]^n + n*c[2]*x[2]^n
для случаев, когда n> 2.
4) С новой формой вашего рекурсивного решения вы используете начальные условия (r (1) и r (2)), чтобы найти c [1] и c [2]
Следуя вашему примеру, вот что мы получаем:
1)
r (n) = 1 * r (n-1) + 2 * r (n-2)
=> x ^ 2 - x - 2 = 0
2) Решение для х
x = (-1 +- sqrt(-1^2 - 4(1)(-2)))/2(1)
x[1] = ((-1 + 3)/2) = 1
x[2] = ((-1 - 3)/2) = -2
3) Поскольку x [1]! = X [2], ваше решение имеет вид:
c[1](x[1])^n + c[2](x[2])^n
4) Теперь используйте ваши начальные условия, чтобы найти две константы c [1] и c [2]:
c[1](1)^1 + c[2](-2)^1 = 1
c[1](1)^2 + c[2](-2)^2 = 1
Честно говоря, я не уверен, каковы ваши константы в этой ситуации, я остановился на этом. Я предполагаю, что вам нужно будет вводить числа до тех пор, пока вы не получите значение для c [1] и c [2], которое будет удовлетворять этим двум выражениям. Либо это, либо выполните сокращение строки на матрице C, где C равно:
[ 1 1 | 1 ]
[ 1 2 | 1 ]
Захари:
Повторение, которое описывает в лучшем
способ количество операций сложения
в следующем фрагменте программы
(при вызове с l == 1 и r == n)
int example(A, int l, int r) {
if (l == r)
return 2;
return (A[l] + example(A, l+1, r);
}
Вот значения временной сложности для заданного вами кода, когда r> l:
int example(A, int l, int r) { => T(r) = 0
if (l == r) => T(r) = 1
return 2; => T(r) = 1
return (A[l] + example(A, l+1, r); => T(r) = 1 + T(r-(l+1))
}
Total: T(r) = 3 + T(r-(l+1))
Иначе, когда r == l, тогда T (r) = 2, потому что оператор if и return оба требуют 1 шаг на выполнение.