Рекурсивная функция псевдокода

Я готовлюсь к среднему семестру, и в одном из практических вопросов задается следующий вопрос:

Рассмотрим рекурсивный псевдоалгоритм Milk (a), который принимает на вход целое число a> = 1.

MILK(a)
    if a = 1;
    then eat cookie;
    else drink glass of milk;
       select a random integer b with 1 <= b <= a-1
       MILK(b);
       MILK(a-b);
    endif

1) Объясните, почему для любого целого числа a> = 1 алгоритм MILK (a) завершается

Я думаю, что для этого из-за n-1 возможность для m становится все меньше и меньше для ввода в рекурсивную функцию MILK (b);, в конечном итоге достигая 1, что удовлетворяет условию a = 1; поэтому съедает cookie и таким образом завершает работу алгоритма.

2) Пусть M (a) будет количеством стаканов молока, которое вы выпиваете при использовании МОЛОКА (a). Определите точное значение M (a)

Для этого я предполагаю, что это будет M (a) = a + a, поскольку каждый раз, когда вы запускаете его, 'a' является входом, и сложение каждого ввода вместе даст вам общий результат.

Как выглядят мои ответы? Или это совершенно неверно. Спасибо!


recursion algorithm pseudocode
person pyramid    schedule 15.10.2013    source источник
comment
точное значение M(a)? Или ожидаемое значение?   -  person phimuemue    schedule 15.10.2013

Ответы (4)


arrow_upward
2
arrow_downward

Для второго вопроса вы можете использовать закон полной вероятности (переведенный в ожидаемые значения - вам, возможно, придется искать это).

M(a) обозначает количество очков (как вы предложили), E() - ожидаемая ценность чего-либо. Тогда этот закон полной вероятности дает:

E(M(a)) = sum(E(M(a) | b=i) * Pr(b=i), i=1..a-1) =
        = ... =
        = 1/(a-1) * (1+sum(E(M(i)+M(a-i), i=1..a-1)))

Насколько я понял, базовый случай M(1)=0 выполняется.

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

person phimuemue    schedule 15.10.2013

arrow_upward
1
arrow_downward

Первый ответ - нормально.

Второго, однако, нет. Рассмотрим a=1. Ваш ответ - два стакана или молоко, тогда как правильный ответ - ноль. Подсказка: попробуйте вручную проработать несколько небольших примеров, чтобы понять, что происходит в алгоритме.

person NPE    schedule 15.10.2013
comment
Спасибо, но могу ли я сказать в B (n) = n + n - 1 (общее количество нс). Так, например, если это 2, это будет 2 + 2-2, так как n в конечном итоге достигнет 1? Извините, если мой ответ немного сбивает с толку. - person pyramid; 15.10.2013
comment
@pyramid Откуда взялся B (n)? Это то же самое, что M (a)? - person Mashmagar; 15.10.2013
comment
О да, извините, я посмотрел не на тот вопрос. B (n) совпадает с M (a). Я имел ввиду M (a) = a + a -1 - person pyramid; 16.10.2013

arrow_upward
1
arrow_downward

В качестве первого вопроса обратите внимание на то, что оба приведенных ниже выражения меньше a, и рекурсия останавливается, когда a равно 1, и что вы можете заметить относительно того, сколько раз вызывается milk ()? Это ограничено?

b < a
a-b < a
MILK(1) returns (no recursion)

Определите количество порций молока вручную для пары значений, вы увидите закономерность. Это поможет.

Обратите внимание, что генерация случайных чисел добавляет сложности, но спросите себя, отличается ли результат, если вы выберете b = 1, b = 2, b = a / 2 или b = a-1?

Ваш ответ правильный, но приведенное выше должно помочь вам объяснить ваши рассуждения.

После того, как вы подсчитали количество напитков для пары звонков в МОЛОКО (v), вы сможете разработать формулу для МОЛОКО (v) = формула (v).

Попробуйте МОЛОКО (3), МОЛОКО (4), МОЛОКО (5), МОЛОКО (9),

Обратите внимание, что Ruby может выразить ваш алгоритм с небольшим добавлением синтаксиса,

rdm = Random.new
def milk(a)
    if(a==1) then
        print "eat cookie\n";
    else
        print "drink milk\n";
        b = Random.rand(1..a-1)
        print "rand (1,#{a-1}) #{b}\n";
        milk(b)
        milk(a-b)
    end
end
ARGV.each { |argi| milk(argi.to_i); }
person ChuckCottrill    schedule 15.10.2013

arrow_upward
0
arrow_downward

Подсказка: вычислите несколько первых значений M (a). Получите представление о формуле в закрытой форме. Докажите по индукции.

Следующий совет: подумайте, зависит ли значение от каждого выбора b?

person chill    schedule 15.10.2013