13

Steven S. Skiena による Algorithm Design Manual を読んでいます。私は宝くじの問題について読んでいる最初の章にいます. Skiena は、勝利を保証するための最適なチケット数の最初の解決策が間違っていたと主張しています。彼の次の最終的な解決策がどのように正しいのかわかりませんか?

図 1.11で彼は次のように述べてい{1,2,3,4,5}ます。なぜ他の数字がそこにないのか混乱していますか？たとえば、当選番号が、、、などの場合はどうなるでしょうか? チケットを組み合わせることは明らかにできませんが、これはどのように説明できますか? 宝くじでは、当選番号が 3 と 5 の場合、何らかの順序で 3 と 5 が含まれているチケットを 1 枚持っている必要があります。誰か説明してくれませんか？{1,2,3}{1, 4, 5}(3,4)(2,4)(2,5)(3,5)

4

2 に答える 2

18

例では

  • n = 5 - サイキックからの数字
  • j = 3 - n からの当選番号の数
  • k = 3 - チケットのスロット数
  • l = 2 - 賞品を獲得するために必要な試合数

このケースを単純にするのは、チケットのすべての数字が 1 から 5 の間でなければならないという事実です。これは、j=k であるためです。つまり、1 から 5 の間の当選番号の数が、チケットのスロットの数と一致します。

チケット {1, 2, 3} と {1, 4, 5} を取ります。これは実際に一致する {3, 5} を見逃していることを意味しますが、番号 {3, 5} がチケットにある場合、チケットの他の番号はセット {1, 2, 4} からのものでなければなりません。1 の場合はマッチ 3 が最初のチケットでピッキングされ、2 の場合は同じ、5 の場合は 2 番目のチケットがそれをキャッチします。

于 2013-10-20T19:25:00.760 に答える