Как найти рекуррентное уравнение (для этого псевдокода)? - PullRequest
Новая
       81

Как найти рекуррентное уравнение (для этого псевдокода)?

0 голосов
/ 27 сентября 2018

Мне было поручено найти ответы на приведенные ниже вопросы, но, честно говоря, я совершенно не знаю, с чего начать.Я не ищу прямые ответы за слово (хотя они были бы оценены), а скорее как я могу найти / получить их.Я понимаю рекурсию, я просто не понимаю, как найти уравнение рекурсии.

a.) Дайте рекурсию для ожидаемого времени работы RANDOM.

b.) Дайте точную рекурсиюуравнение для ожидаемого числа рекурсивных вызовов, выполненных вызовом RANDOM (n).

c.) Дайте точное уравнение повторения для ожидаемого числа повторений выполнения операторов строки 14 во всех вызываемыхСЛУЧАЙНО (n), рекурсивно или нет.

Псевдокод:

Функция СЛУЧАЙНО (u)

  1. если u = 1, то

  2. return (1)

  3. else

  4. назначить x = 0 с вероятностью 1/2,или

  5. назначить x = 1 с вероятностью 1/3, или

  6. назначить x = 2 с вероятностью 1/6

  7. если x = 0, то

  8. возврат (RANDOM (u-1) + RANDOM (u-2))

  9. end-if

  10. если x = 1, то

  11. return (RANDOM (u) + 2 * RANDOM (u-1))

  12. end-if

  13. если x = 2, то

  14. возврат (3 * RANDOM (u) + RANDOM (u) + 3)

  15. end-if

  16. end-if

end-RANDOM

1 Ответ

0 голосов
/ 27 сентября 2018

Прежде всего важно отметить, что, поскольку вопросы задают время выполнения / нет.вызовов , коэффициенты перед рекурсивными вызовами RANDOM не имеют значения (поскольку ни один из ответов не зависит от фактического возвращаемого значения).

Кроме того, поскольку вопросы задают ожидаемыеколичества, вы можете смешивать соответствующие рекурсивные вызовы вероятностно.

a)

Начиная довольно легко.Вероятностное смешивание функций: 

T(u) = [1/2] * [T(u-1) + T(u-2)] + 
       [1/3] * [T(u)   + T(u-1)] + 
       [1/6] * [T(u)   + T(u)  ]        // + constant amount of work

b)

То же, что и раньше, но не забудьте добавить по одному для каждого вызова: 

N(u) = [1/2] * [N(u-1) + N(u-2) + 2] +
       [1/3] * [N(u)   + N(u-1) + 2] +
       [1/6] * [N(u)   + N(u)   + 2]    // no constants here

в)

Это хитрее двух других.Кажется противоречивым, что вопрос требует «[все вызовы RANDOM (u)], рекурсивные или нет», но только те, которые в строке 14 являются рекурсивными ...

В любом случаеигнорируя эту незначительную деталь, важно отметить, что вызов RANDOM(u) в строке 11 также может производить требуемые рекурсивные вызовы, не влияя на сам общий счет.Адаптируя вышесказанное: 

R(u) = [1/3] * [R(u)           ] +     // don't add 1 here
       [1/6] * [R(u) + R(u) + 2]       // add 2 as before

Обратите внимание, что этот вопрос, вероятно, предполагает, что вы переставите все термины T(u), N(u), R(u) в LHS.Я оставлю это вам, поскольку это тривиально.

...