•  21-08-2019
  •  | 
  •  

質問

私は、再帰と、動的プログラミングに私の最初のステップを取って、再帰をモデル化する部分問題を形成について質問がありますよ。

問題：

  

にありますどのように多くの異なる方法   公正コインを5回反転していません   行の3つの以上のヘッド？

いくつかは、いくつかの多くのコメントコードを置くことができれば、

私はそこに得るのを助けるために（Rubyは好ましいが、必須ではありません）。それが重要な場合、私は、これは私にとって、それは非常に簡単にするプロジェクトオイラーの問題の修正で、学生ではありませんよ把握します。私は、再帰式を書くのこつを取得する必要があります。

あなたは抽象したい場合はどのように多くの異なる方法に問題はそれが同様に有益であるかもしれない、行にZ以上のヘッドを持っているが、公正コインにY回を反転しないようにしています。おかげで再び、このウェブサイトの岩。

役に立ちましたか？

解決

ここに私のソリューションは、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 }

..だからこれは私がして所望の長さより短い1であるすべての組み合わせをしたい...と言う：頭はそれらのそれぞれに追加...プラスそれらに追加尾と短い1であるすべての組み合わせ。

再帰を考える

の方法です..「私はそれがn個のケースをカバーするために追加する必要がありますどのような..私は、n-1の場合を行うための方法を持っていたと仮定し」。私にはそれが誘導による証拠のように感じます。

このコードは、所定の長さまで頭と尾のすべての組み合わせを生成します。

私たちは持っているものを望んでいない：H：H：H。時間：時間と我々は追加されています。私たちが持っているところでのみ発生することができます時間。無効な組み合わせを作ることを約あったとき、それはif c[0..1] != [:h,:h]代わりの配列を返しますので、時間：そう...私はの追加にnilを置きます。

私は、ちょうどcompactされているすべての結果を無視した結果をnilする必要がありました。

他のヒント

あなたは、単にそのための式を作成することができます

の行に3つのヘッドを有することなくコインを5回反転するいくつかの方法は、5コインの組み合わせの数フリップマイナスの行の少なくとも3つのヘッドとの組み合わせに等しいです。この場合：

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

の組み合わせの総数は= 2 ^ 5 = 32および32 - 7 = 25

我々は行のQヘッドことなくコインをn回反転した場合、

、総量は、少なくともQヘッドを2 ^ N及び量は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

これは、すべての可能な5ビット列を取得し、3つの連続する1ビット（1 =ヘッドを仮定し、0 =テール）が存在するケースを除去する事項ではないか

ここではPythonでそれを行うための一つの方法です。

#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

このはに分解します：

第1のフリップフロッが頭だったとき公正コインを4回が反転するどのように多くの方法があります+第1のフリップフロッだったときに尾ます：

だから、Pythonでます：

HEADS = "1"
TAILS = "0"

def threeOrMoreHeadsInARow(bits):
    return "111" in bits

def flip(n = 5, flips = ""):
   if threeOrMoreHeadsInARow(flips):
      return 0
   if n == 0:
      return 1
   return flip(n - 1, flips + HEADS) + flip(n - 1, flips + TAILS)

ここではRubyのyield文を使用して再帰的な組み合わせの機能です。

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 }"

だから、私はそれを行うだろう方法は次のとおりです。）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top