5

私は中間試験の勉強をしていますが、練習問題の 1 つに次のような質問があります。

入力整数として a>=1 を取る再帰的な疑似アルゴリズム Milk(a) を考えてみましょう。

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 のせいで、再帰関数 MILK(b); への入力に対して m の可能性がどんどん小さくなり、最終的に条件 a = 1; を満たす 1 に達すると思います。したがって、クッキーを食べて、アルゴリズムを終了します。

2) M(a) を、MILK(a) を実行しているときに飲むコップ 1 杯の牛乳の量とします。M(a) の正確な値を決定する

これについては、実行するたびに「a」が入力であり、すべての入力を合計すると合計が得られるため、M(a) = a + a になると思います。

私の答えはどのように見えますか? または、これは完全に間違っています。ありがとうございました！

4

4 に答える 4

2

2 番目の質問については、全確率の法則を使用できます (期待値に変換 - おそらくこれを検索する必要があります)。

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 プログラムで) 試してみると、おそらく帰納法によって証明できる単純なパターンを認識できるはずです。

于 2013-10-15T15:47:08.460 に答える
1

最初の答えは大丈夫です。

しかし、2番目はそうではありません。を考慮してくださいa=1。あなたの答えは 2 杯のグラスまたは牛乳ですが、正解は 0 です。ヒント: いくつかの小さな例を手作業で試して、アルゴリズムで何が起こっているかを感じてみてください。

于 2013-10-15T15:41:17.627 に答える
1

最初の質問では、以下の両方の式が a 未満であり、a が 1 に等しいときに再帰が停止することに注意してください。また、milk() が呼び出された回数について何が観察できますか? 有界ですか？

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

いくつかの値について牛乳を飲む回数を手で計算すると、パターンが表示されます。それは役に立ちます。

乱数の生成により複雑さが増すことに注意してください。ただし、b=1、b=2、b=a/2、または b=a-1 を選択した場合、結果は異なるでしょうか?

あなたの答えは正しいですが、上記は理由を説明するのに役立ちます。

MILK(v) への 2 回の呼び出しで飲み物の数を計算したら、MILK(v) = formula(v) の式を進めることができるはずです。

MILK(3)、MILK(4)、MILK(5)、MILK(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); }
于 2013-10-15T17:11:12.770 に答える
0

ヒント: M(a) の最初のいくつかの値を計算します。閉じた式のアイデアを得る。帰納法で証明します。

次のヒント: 考えてみてください。値は の各選択に依存しますbか?

于 2013-10-15T15:47:49.003 に答える