简单的递归问题

Question

我正在进行递归和动态编程的第一步,并且有关于形成子问题以模拟递归的问题.

问题:

有多少种不同的方式可以翻转一枚硬币5次,而不是连续三个或更多头？

如果有人可以提出一些评论很多的代码(Ruby首选但不是必需的)来帮助我实现目标.如果重要的话,我不是学生,这是对Euler项目问题的修改,使我很容易理解.我只需要编写递归公式.

如果你想把这个问题抽象成有多少种不同的方式来翻转一枚硬币Y次并且没有连续Z或更多的头,这也可能是有益的.再次感谢,这个网站摇滚.

Answer 1

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

在没有连续3个头的情况下翻转硬币5次的方法的数量等于5个硬币翻转的组合的数量减去连续至少三个头的组合的数量.在这种情况下:

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

组合总数= 2 ^ 5 = 32.并且32 - 7 = 25.

如果我们连续N次掷硬币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