inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ プログラミング 期待値は再帰的に計算することができます。例えば、N=4、M=2なら、 0 ／ ＼ 1 2 ／ 3となりますが、各プロセスを殺すと、0を殺すと全て殺せて、残りは、 1: 0 2: 0 3: 0 ＼ ／ ／ ＼ 2 1 1 2 ／ 3となります。これらのプロセスツリーに対する期待値を計算して平均を取って1を足せば元のツリーに対する期待値が出ます。 これをざっくり組んでみました。ツリーのデータ構造は、そのプロセスに親と子を書いておきます。殺すときは親の子リストから消すだけです。 def create_process(a, i, k, N, M): if k < N: n = min(M, N - k… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F20101113%2Fp1" title="プロセスを全て殺すには何回かかるか（2） - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-11-13 00:00:00 rich https://inamori.hateblo.jp/entry/20101113/p1 1.0 100%