0

私は再帰と動的プログラミングに最初の一歩を踏み出していますが、再帰をモデル化するための部分問題の形成について質問があります。

問題：

公正なコインを 5 回投げて、表が 3 回以上連続しないようにする方法は何通りありますか?

私がそこにたどり着くのを助けるために、いくつかのコメントの多いコード（Rubyが推奨されますが必須ではありません）を立てることができれば。それが問題なら、私は学生ではありません。これは、Project Eulerの問題を修正して、私が理解しやすくするためのものです。再帰式を書くコツをつかむ必要があるだけです。

問題を抽象化して、公平なコインを Y 回投げ、Z 回以上の表が連続しないようにする方法が何通りあるかを考えてみると、それも有益な場合があります。繰り返しますが、このウェブサイトは揺るぎません。

4

6 に答える 6

6

そのための式を簡単に作成できます。

連続して3つのヘッドを持たずにコインを5回フリップする方法の数は、5つのコインフリップの組み合わせの数から少なくとも3つのヘッドが連続している組み合わせを引いた数に等しくなります。この場合：

HHH-- (4 combinations)
THHH- (2 combinations)
TTHHH (1 combination)

組み合わせの総数=2^5=32。そして32-7=25。

Qヘッドを連続せずにコインをN回投げると、合計金額は2 ^ Nになり、少なくともQヘッドがある場合の金額は2 ^（N-Q + 1）-1になります。したがって、一般的な答えは次のとおりです。

Flip(N,Q) = 2^N - 2^(N-Q+1) +1

もちろん、再帰を使用して合計量をシミュレートできます。

flipme: N x N -> N
flipme(flipsleft, maxhead) = flip(flipsleft, maxhead, 0)

flip: N x N x N -> N
flip(flipsleft, maxhead, headcount) ==
  if flipsleft <= 0 then 0
  else if maxhead<=headcount then 0
  else 
    flip(flipsleft - 1, maxhead, headcount+1) + // head
    flip(flipsleft - 1, maxhead, maxhead)       // tail
于 2009-03-20T20:48:27.823 に答える
1

これがRubyでの私の解決策です

def combination(length=5)
  return [[]] if length == 0
  combination(length-1).collect {|c| [:h] + c if c[0..1]!= [:h,:h]}.compact +
  combination(length-1).collect {|c| [:t] + c }
end

puts "There are #{combination.length} ways"

すべての再帰的メソッドは、エンドケースのアーリーアウトから始まります。

return [[]] if length == 0

これは組み合わせの配列を返します。ここで、長さがゼロの唯一の組み合わせは[]

次のビット（簡略化）は...

combination(length-1).collect {|c| [:h] + c } +
combination(length-1).collect {|c| [:t] + c }

だから..これは..私はそれらのそれぞれに：headが追加された希望の長さより1つ短いすべての組み合わせが欲しいです...そしてそれらにテールが追加された1つ短いすべての組み合わせ。

再帰について考える方法は、「n-1の場合を実行する方法があると仮定すると、nの場合をカバーするために何を追加する必要があるか」です。私にとって、それは帰納法による証明のように感じます。

このコードは、指定された長さまでのヘッドとテールのすべての組み合わせを生成します。

：h：h：hを持つものは必要ありません。これは、：h：hがあり、：hを追加している場合にのみ発生します。だから...私if c[0..1] != [:h,:h]は：hの追加を追加nilして、無効な組み合わせを作成しようとしたときに配列の代わりに返されるようにしました。

次に、結果を無視してcompact、結果を無視する必要がありました。nil

于 2009-03-21T23:09:39.537 に答える
1

これは、考えられるすべての 5 ビット シーケンスを取得し、連続する 1 ビットが 3 つある場合 (1 = 頭、0 = 尾と仮定) を削除することの問題ではありませんか?

于 2009-03-20T20:32:46.333 に答える
0

Pythonでそれを行う1つの方法は次のとおりです。

#This will hold all possible combinations of flipping the coins. 
flips = [[]]
for i in range(5):
    #Loop through the existing permutations, and add either 'h' or 't' 
    #to the end. 
    for j in range(len(flips)):
        f = flips[j]
        tails = list(f)
        tails.append('t')
        flips.append(tails)
        f.append('h')

#Now count how many of the permutations match our criteria.
fewEnoughHeadsCount = 0
for flip in flips:
    hCount = 0
    hasTooManyHeads = False
    for c in flip:
        if c == 'h': hCount += 1
        else: hCount = 0
        if hCount >= 3: hasTooManyHeads = True
    if not hasTooManyHeads: fewEnoughHeadsCount += 1

print 'There are %s ways.' % fewEnoughHeadsCount
于 2009-03-20T20:51:44.337 に答える
0

yieldRubyステートメントを使用した再帰的な組み合わせ関数を次に示します。

def combinations(values, n)
  if n.zero?
    yield []
  else
    combinations(values, n - 1) do |combo_tail|
      values.each do |value|
        yield [value] + combo_tail
      end
    end
  end
end

また、正規表現を使用して、連続して 3 つの見出しを解析できます。

def three_heads_in_a_row(s)
  ([/hhh../, /.hhh./, /..hhh/].collect {|pat| pat.match(s)}).any?
end

最後に、次のようなものを使用して答えを取得します。

total_count = 0
filter_count = 0

combinations(["h", "t"], 5) do |combo|
  count += 1
  unless three_heads_in_a_row(combo.join)
      filter_count += 1
  end
end

puts "TOTAL: #{ total_count }"
puts "FILTERED: #{ filter_count }"

それが私がそれをする方法です:)

于 2009-03-21T18:02:47.543 に答える