blocks|key|2118398|text|这不就是取所有可能的5位序列，并删除有三个顺序1位(假设1=正面，0=尾部)的情况吗？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2118399|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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)?

blocks|key|588692|text|具体如下：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|588693|当第一次抛硬币是正面%2B当第一次抛硬币是反面时，有多少种方法可以将一枚公平的硬币抛四次：|588694|所以在python中：|588695|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+%2B+HEADS)+%2B+flip(n+-+1,+flips+%2B+TAILS)|code-block|syntax|javascript|588696|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|O|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|P|8|@]|9|@]|A|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

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:

<pre><code>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)
</code></pre>

blocks|key|828668|text|您可以简单地为此创建一个公式：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|828669|将硬币抛5次而不连续3个头的方法数等于5枚硬币翻转减去一排至少3个头组合的组合数。在这种情况下：|828670|HHH--+(4+combinations)
THHH-+(2+combinations)
TTHHH+(1+combination)|code-block|syntax|javascript|828671|组合总数=+2%5E5+=+32。32+-7=+25。|828672|如果我们连续抛硬币N次而没有Q头，则总金额为2%5EN，而至少Q头数为2%5E(N%2B1)-1。因此，一般的答案是：|828673|Flip(N,Q)+=+2%5EN+-+2%5E(N-Q%2B1)+%2B1|828674|当然，您可以使用递归来模拟总量：|828675|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%2B1)+%2B+//+head
++++flip(flipsleft+-+1,+maxhead,+maxhead)+++++++//+tail++|828676|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|V|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|W|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|X|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|Y|8|@]|9|@]|A|$]]|$1|M|3|N|5|F|7|Z|8|@]|9|@]|A|$G|H]]|$1|O|3|P|5|6|7|10|8|@]|9|@]|A|$]]|$1|Q|3|R|5|F|7|11|8|@]|9|@]|A|$G|H]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

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:

<pre><code>HHH-- (4 combinations)
THHH- (2 combinations)
TTHHH (1 combination)
</code></pre>

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:

<pre><code>Flip(N,Q) = 2^N - 2^(N-Q+1) +1
</code></pre>

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

<pre><code>flipme: N x N -&gt; N
flipme(flipsleft, maxhead) = flip(flipsleft, maxhead, 0)

flip: N x N x N -&gt; N
flip(flipsleft, maxhead, headcount) ==
 if flipsleft &lt;= 0 then 0
 else if maxhead&lt;=headcount then 0
 else 
 flip(flipsleft - 1, maxhead, headcount+1) + // head
 flip(flipsleft - 1, maxhead, maxhead) // tail 
</code></pre>

blocks|key|588764|text|这里有一种在Python中实现它的方法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|588765|#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+%2B=+1
++++++++else:+hCount+=+0
++++++++if+hCount+>=+3:+hasTooManyHeads+=+True
++++if+not+hasTooManyHeads:+fewEnoughHeadsCount+%2B=+1

print+'There+are+%25s+ways.'+%25+fewEnoughHeadsCount|code-block|syntax|javascript|588766|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here's one way to do it in Python: 

<pre><code>#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 &gt;= 3: hasTooManyHeads = True
 if not hasTooManyHeads: fewEnoughHeadsCount += 1

print 'There are %s ways.' % fewEnoughHeadsCount
</code></pre>

blocks|key|588792|text|下面是一个使用Ruby+yield语句的递归组合函数：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|588793|def+combinations(values,+n)
++if+n.zero?
++++yield+[]
++else
++++combinations(values,+n+-+1)+do+%7Ccombo_tail%7C
++++++values.each+do+%7Cvalue%7C
++++++++yield+[value]+%2B+combo_tail
++++++end
++++end
++end
end|code-block|syntax|javascript|588794|您可以使用正则表达式来连续解析出三个头部：|588795|def+three_heads_in_a_row(s)
++([/hhh../,+/.hhh./,+/..hhh/].collect+{%7Cpat%7C+pat.match(s)}).any?
end|588796|最后，您可以使用这样的方法得到答案：|588797|total_count+=+0
filter_count+=+0

combinations(["h",+"t"],+5)+do+%7Ccombo%7C
++count+%2B=+1
++unless+three_heads_in_a_row(combo.join)
++++++filter_count+%2B=+1
++end
end

puts+"TOTAL:+#{+total_count+}"
puts+"FILTERED:+#{+filter_count+}"|588798|所以我会这样做:)|588799|entityMap^0|C|5|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|Z|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|10|8|@]|D|@]|E|$]]|$1|M|3|N|5|H|7|11|8|@]|D|@]|E|$I|J]]|$1|O|3|P|5|6|7|12|8|@]|D|@]|E|$]]|$1|Q|3|R|5|H|7|13|8|@]|D|@]|E|$I|J]]|$1|S|3|T|5|6|7|14|8|@]|D|@]|E|$]]|$1|U|3|-4|5|6|7|15|8|@]|D|@]|E|$]]]|V|$]]

Here's a recursive combination function using Ruby <code>yield</code> statements:

<pre><code>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
</code></pre>

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

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

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

<pre><code>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 }"
</code></pre>

So that's how I would do it :)

blocks|key|828589|text|这是我在Ruby中的解决方案|type|unstyled|depth|inlineStyleRanges|entityRanges|data|828590|def+combination(length=5)
++return+[[]]+if+length+==+0
++combination(length-1).collect+{%7Cc%7C+[:h]+%2B+c+if+c[0..1]!=+[:h,:h]}.compact+%2B
++combination(length-1).collect+{%7Cc%7C+[:t]+%2B+c+}
end

puts+"There+are+#{combination.length}+ways"|code-block|syntax|javascript|828591|所有递归方法都以结束情况的早期输出开始。|828592|return+[[]]+if+length+==+0|828593|这将返回一个组合数组，其中唯一的零长度组合是[]。|offset|length|style|CODE|828594|下一段(简化)是..。|828595|combination(length-1).collect+{%7Cc%7C+[:h]+%2B+c+}+%2B
combination(length-1).collect+{%7Cc%7C+[:t]+%2B+c+}|828596|所以..。这上面说..。我希望所有的组合都比期望的长度短一个，并在每个组合中添加一个:head+.加上所有的组合，这是一个较短的尾巴添加到他们。|828597|考虑递归的方法是..。“假设我有一种方法来处理n-1的情况.我需要添加什么才能使它涵盖n个情况”。对我来说，这就像是通过归纳来证明。|828598|此代码将生成在给定长度范围内的所有正面和尾部组合。|828599|我们不想要有:h+:h+:h。这只能发生在我们有:h+:h的地方，而我们正在添加a+:h。所以.我在添加:h时添加了一个if+c[0..1]+!=+[:h,:h]，这样当它准备进行无效的组合时，它将返回nil而不是数组。|828600|然后，我不得不对结果进行compact，以忽略所有只是nil的结果。|828601|entityMap^0|0|0|0|0|M|2|0|0|0|0|0|0|1O|L|2T|3|0|C|7|R|3|0^^$0|@$1|2|3|4|5|6|7|16|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|17|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|18|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|19|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|1A|8|@$M|1B|N|1C|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1D|8|@]|9|@]|A|$]]|$1|S|3|T|5|D|7|1E|8|@]|9|@]|A|$E|F]]|$1|U|3|V|5|6|7|1F|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1G|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|1H|8|@]|9|@]|A|$]]|$1|10|3|11|5|6|7|1I|8|@$M|1J|N|1K|O|P]|$M|1L|N|1M|O|P]]|9|@]|A|$]]|$1|12|3|13|5|6|7|1N|8|@$M|1O|N|1P|O|P]|$M|1Q|N|1R|O|P]]|9|@]|A|$]]|$1|14|3|-4|5|6|7|1S|8|@]|9|@]|A|$]]]|15|$]]

Here's my solution in Ruby

<pre><code>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"
</code></pre>

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

<pre><code>return [[]] if length == 0
</code></pre>

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

The next bit (simplified) is...

<pre><code>combination(length-1).collect {|c| [:h] + c } +
combination(length-1).collect {|c| [:t] + c }
</code></pre>

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 <code>if c[0..1] != [:h,:h]</code> on the adding of the :h so it will return <code>nil</code> instead of an array when it was about to make an invalid combination. 

I then had to <code>compact</code> the result to ignore all results that are just <code>nil</code>

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

Problem:

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

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 <a href="http://projecteuler.net/" rel="nofollow noreferrer">Project Euler</a> 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.

Simple recursion problem

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我的第一步是递归和动态规划，并且有一个关于形成子问题来建模递归的问题。问题：有多少种不同的方式来抛一个公平的硬币5次，而不是有三个或更多的头在一起？如果有些人能提供一些注释较多的代码(Ruby更喜欢但不是必需的)来帮助我实现这个目标。我不是一个学生，如果这重要，这是一个修改的问题，使它非常简单的我掌握。我只需要掌握编写...

问简单递归问题
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问简单递归问题EN