Простая рекурсивная задача

Question

Я делаю первые шаги в рекурсии и динамическом программировании и задаю вопрос о формировании подзадач для моделирования рекурсии.

Проблема:

Сколько существует разных способов перевернуть честную монету 5 раз и не иметь три или более головы подряд?

Если бы кто-то мог выложить какой-нибудь сильно прокомментированный код (желательно Ruby, но не обязательный), чтобы помочь мне в этом. Я не студент, если это имеет значение, это модификация проблемы Project Euler , чтобы мне было проще ее понять. Мне просто нужно научиться писать формулы рекурсии.

Если вы хотите абстрагировать проблему от того, сколько существует различных способов подбросить справедливую монету Y раз и не иметь Z или более голов подряд, это также может быть полезным. Еще раз спасибо, этот сайт качается.

Answer 1

Вы можете просто создать формулу для этого:

Количество способов перевернуть монету 5 раз, не имея 3 головы подряд, равно количеству комбинаций из 5 монетных монет за вычетом комбинаций, по крайней мере, с тремя головами подряд. В этом случае:

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  

Answer 2

Вот мое решение в 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 }

Итак ... это говорит ... Я хочу, чтобы все комбинации были на одну короче желаемой длины с добавленной к каждой из них головой: ... плюс все комбинации, которые на одну короче с добавленным к ним хвостом.

Способ думать о рекурсии заключается в том, что ... «предполагая, что у меня есть метод для случая n-1 ... что я должен был бы добавить, чтобы он покрыл случай n» ». Для меня это похоже на доказательство по индукции.

Этот код будет генерировать все комбинации голов и хвостов до заданной длины.

Нам не нужны те, которые имеют: h: h: h. Это может произойти только тогда, когда у нас есть: h: h и мы добавляем a: h. Итак ... Я добавил if c[0..1] != [:h,:h] при добавлении: h, чтобы он возвращал nil вместо массива, когда собирался создать недопустимую комбинацию.

Затем мне пришлось compact результат, чтобы игнорировать все результаты, которые просто nil

Answer 3

Разве это не вопрос взятия всех возможных 5-битовых последовательностей и исключения случаев, когда есть три последовательных 1-битных (при условии 1 = головки, 0 = хвосты)?

Answer 4

Вот рекурсивная комбинационная функция, использующая операторы 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 }"

Так вот, как бы я это сделал:)

Answer 5

Вот один из способов сделать это в 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

Answer 6

Это разбивается на:

Сколько существует способов бросить честную монету четыре раза, когда первый бросок был головами +, когда первый бросок был хвостами:

Итак, в 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)