0

我正在迈出递归和动态编程的第一步，并且有一个关于形成子问题来建模递归的问题。

问题：

有多少种不同的方法可以将一枚公平的硬币抛 5 次，并且连续出现三个或更多的正面朝上？

如果有人可以提出一些重注释的代码（Ruby 首选但不是必需的）来帮助我到达那里。如果这很重要，我不是学生，这是对Project Euler问题的修改，使我很容易掌握。我只需要掌握编写递归公式的窍门。

如果您想将问题抽象为有多少种不同的方式可以将一枚公平的硬币抛 Y 次，并且连续没有 Z 次或更多正面，那也可能是有益的。再次感谢，这个网站很棒。

4

6 回答 6

6

您可以简单地为此创建一个公式：

抛硬币 5 次且连续 3 次正面朝上的次数等于 5 次抛硬币的组合数减去至少连续 3 次正面朝上的组合数。在这种情况下：

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

组合总数 = 2^5 = 32。而 32 - 7 = 25。

如果我们连续抛硬币 N 次，没有 Q 次正面朝上，总金额为 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

这不是取所有可能的 5 位序列并删除存在三个连续 1 位的情况（假设 1 = 头，0 = 尾）的问题吗？

于 2009-03-20T20:32:46.333 回答
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 ......加上所有短一个并添加一个尾巴的组合。

考虑递归的方法是..“假设我有一种方法来处理 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 回答
0

这分解为：

当第一次是正面时+第一次是反面时，有多少种方法可以将一枚公平的硬币掷四次：

所以在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)
于 2009-03-20T20:47:21.117 回答
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
于 2009-03-20T20:51:44.337 回答
0

yield这是一个使用 Ruby语句的递归组合函数：

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

您可以使用正则表达式连续解析出三个头：

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 回答