简单的递归问题

发布于 2024-07-16 03:16:04 字数 429 浏览 12 评论 0原文

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

问题:

有多少种不同的方法 抛一枚公平的硬币 5 次,没有 连续三个或更多头?

如果有人可以提供一些带有大量注释的代码(Ruby 是首选,但不是必需的)来帮助我实现目标。 如果这很重要的话,我不是学生,这是对 Project Euler 问题的修改,使其对我来说非常简单去把握。 我只需要掌握编写递归公式的技巧。

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

I'm taking my first steps into recursion and dynamic programming and have a question about forming subproblems to model the recursion.

Problem:

How many different ways are there to
flip a fair coin 5 times and not have
three or more heads in a row?

If some could put up some heavily commented code (Ruby preferred but not essential) to help me get there. I am not a student if that matters, this is a modification of a Project Euler problem to make it very simple for me to grasp. I just need to get the hang of writing recursion formulas.

If you would like to abstract the problem into how many different ways are there to flip a fair coin Y times and not have Z or more heads in a row, that may be beneficial as well. Thanks again, this website rocks.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

要走干脆点 2024-07-23 03:16:04

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

抛硬币 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  

You can simply create a formula for that:

The number of ways to flip a coin 5 times without having 3 heads in a row is equal to the number of combinations of 5 coin flips minus the combinations with at least three heads in a row. In this case:

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

The total number of combinations = 2^5 = 32. And 32 - 7 = 25.

If we flip a coin N times without Q heads in a row, the total amount is 2^N and the amount with at least Q heads is 2^(N-Q+1)-1. So the general answer is:

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

Of course you can use recursion to simulate the total amount:

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  
姐不稀罕 2024-07-23 03:16:04

这是我在 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 时才会发生这种情况。 所以...我在添加 :h 时添加了 if c[0..1] != [:h,:h] ,这样它将返回 nil当它要进行无效组合时,而不是数组。

然后我必须压缩结果以忽略所有nil结果

Here's my solution in 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"

All recursive methods start with an early out for the end case.

return [[]] if length == 0

This returns an array of combinations, where the only combination of zero length is []

The next bit (simplified) is...

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

So.. this says.. I want all combinations that are one shorter than the desired length with a :head added to each of them... plus all the combinations that are one shorter with a tail added to them.

The way to think about recursion is.. "assuming I had a method to do the n-1 case.. what would I have to add to make it cover the n case". To me it feels like proof by induction.

This code would generate all combinations of heads and tails up to the given length.

We don't want ones that have :h :h :h. That can only happen where we have :h :h and we are adding a :h. So... I put an if c[0..1] != [:h,:h] on the adding of the :h so it will return nil instead of an array when it was about to make an invalid combination.

I then had to compact the result to ignore all results that are just nil

无远思近则忧 2024-07-23 03:16:04

这不是采取所有可能的 5 位序列并删除存在三个连续 1 位的情况(假设 1 = 头,0 = 尾)的问题吗?

Isn't this a matter of taking all possible 5 bit sequences and removing the cases where there are three sequential 1 bits (assuming 1 = heads, 0 = tails)?

落叶缤纷 2024-07-23 03:16:04

这是在 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

Here's one way to do it in 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
美羊羊 2024-07-23 03:16:04

这可以分解为:

当第一次抛掷正面时,有多少种方法将一枚公平的硬币抛四次;当第一次抛掷是反面时,有多少种方法:

所以在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)

This breaks down to:

How many ways are there to flip a fair coin four times when the first flip was heads + when the first flip was tails:

So in 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)
演多会厌 2024-07-23 03:16:04

这是使用 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

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

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

所以这就是我要做的它 :)

Here's a recursive combination function using Ruby yield statements:

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

And you could use regular expressions to parse out three heads in a row:

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

Finally, you would get the answer using something like this:

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

So that's how I would do it :)

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文