Как я использую Основную теорему для описания рекурсии?

Ваш метод, записанный в коде с помощью рекурсивной функции, был бы похож на это:

function r(int n) 
{
  if (n == 2) return 1;
  if (n == 1) return 1;
  return 2 * r(n-2) + r(n-1);  // I guess we're assuming n > 2
}

Я не уверен, каково "повторение", но рекурсивная функция является просто той, которая называет себя.

Для рекурсивных функций нужен пункт Escape (некоторый нерекурсивный случай - например, "если n == 1 возврат 1") для предотвращения Ошибки переполнения стека (т.е. функция вызвана так, что интерпретатор исчерпывает память или другие ресурсы),

Простая программа, которая реализовала бы, который будет похож:

public int r(int input) {
    if (input == 1 || input == 2) {
        return 1;
    } else {
        return 2 * r(input - 2) + r(input -1)
    }
}

Необходимо было бы также удостовериться, что вход не собирается вызывать бесконечную рекурсию, например, если вход вначале был меньше чем 1. Если это не допустимый случай, то возвратите ошибку, если это допустимо, то возвратите соответствующее значение.

«Я не совсем уверен, что такое« повторение »

Определение« рекуррентного отношения »- это последовательность чисел,« домен которой представляет собой некоторый бесконечный набор целых чисел и диапазон которых представляет собой набор действительных чисел ". С дополнительным условием, что функция, описывающая эту последовательность, «определяет один член последовательности в терминах предыдущего».

И цель их решения, я думаю, состоит в том, чтобы перейти от рекурсивного определения к определению, которое нет. Скажем, если бы у вас были T (0) = 2 и T (n) = 2 + T (n-1) для всех n> 0, вам пришлось бы перейти от выражения «T (n) = 2 + T (n -1) "такому как" 2n + 2 ".

источники: 1) «Дискретная математика с теорией графов - второе издание», Эдгар Г. Гудэр и Майкл М. Парментер. 2) «Компьютерные алгоритмы C ++» Эллиса Хоровица, Сартаджа Сахни и Сангутевара Раджасекарана.

Захари:

Допустим, вам дано это повторение:

r (n) = 2 * r (n-2) + r (n-1); г (1) = г (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) равно нулю, рекуррентное отношение называется «однородным». Итак, ваше выражение лица однородно.

Я не думаю, что вы можете решить гомогенное рекуррентное отношение, используя Теорему мастер-метода, потому что f (n) = 0. Ни один из случаев теоремы об основном методе не допускает этого, потому что n-в-степени-из -ничего не может равняться нулю.Я могу ошибаться, потому что на самом деле я не эксперт в этом, но я не знаю, что можно решить однородное рекуррентное отношение с помощью основного метода.

Я считаю, что способ решения однородного рекуррентного отношения состоит из 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) г (п) = 1 * г (п-1) + 2 * г (п-2) => x ^ 2 - x - 2 = 0

2) Решение относительно x

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 ] 

Zachary:

Повторение, которое описывает наилучшим образом способ количество операций сложения в следующем фрагменте программы (при вызове с 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 шаг на выполнение.