problema ricorsione semplice

Question

Sto prendendo i primi passi verso la ricorsione e la programmazione dinamica e hanno una domanda di formare sottoproblemi per modellare la ricorsione.

Problema:

  

In quanti modi diversi ci sono per   lanciare una moneta equa 5 volte e non hanno   tre o più teste di fila?

Se qualcuno potrebbe mettere un po 'di codice pesantemente commentato (Rubino preferibile ma non indispensabile) per aiutarmi lì. Io non sono uno studente se quello che conta, si tratta di una modifica di un Project Euler problema di rendere molto semplice per me per cogliere. Ho solo bisogno di ottenere il blocco di scrittura di formule di ricorsività.

Se volete astratto il problema in quanti modi diversi ci sono per capovolgere una fiera volte moneta Y e Z non hanno o più teste di fila, che può essere utile pure. Grazie ancora, questo sito rocce.

Answer 1

Ecco la mia soluzione 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"

Tutti i metodi ricorsivi iniziano con uno dei primi per il caso finale.

return [[]] if length == 0

Questo restituisce una matrice di combinazioni, dove l'unica combinazione di lunghezza zero è []

Il prossimo bit (semplificato) è ...

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

Quindi .. questo dice .. voglio tutte le combinazioni che sono uno più corto della lunghezza desiderata con un: testa aggiunto a ciascuno di loro ... più tutte le combinazioni che sono uno più corto con una coda aggiunto a loro.

Il modo di pensare ricorsione è .. "ipotizzando avevo un metodo per fare il caso n-1 .. cosa dovrei aggiungere per renderlo coprire il caso n". Per me ci si sente come prova per induzione.

Questo codice genererebbe tutte le combinazioni di teste e code fino alla lunghezza data.

Non vogliamo quelli che hanno: h: h: h. Questo può avvenire solo dove abbiamo: h: he stiamo aggiungendo un: h. Quindi ... ho messo un if c[0..1] != [:h,:h] sulla aggiunta del: h in modo che tornerà nil invece di una matrice quando era sul punto di fare una combinazione non valida.

Poi ho dovuto compact il risultato di ignorare tutti i risultati che sono solo <=>

Answer 2

Si può semplicemente creare una formula per questo:

Il numero di modi per capovolgere una moneta 5 volte senza teste 3 in una fila è uguale al numero di combinazioni di 5 lanci della moneta meno le combinazioni con almeno tre teste di fila. In questo caso:

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

Il numero totale di combinazioni = 2 ^ 5 = 32 e 32 -. 7 = 25

Se lanciamo una moneta N volte senza la testa Q in una riga, la somma totale è 2 ^ N e l'importo con almeno teste Q è 2 ^ (N-Q + 1) -1. Quindi la risposta generale è:

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

Naturalmente è possibile utilizzare la ricorsione per simulare l'importo totale:

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 3

Questa non è una questione di prendere tutte le possibili sequenze di bit 5 e rimuovendo i casi in cui vi sono tre sequenziali 1 bit (assumendo 1 = teste, 0 = code)?

Answer 4

Ecco un modo per farlo 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

Answer 5

Questo si rompe a:

Quanti modi ci sono per lanciare una moneta equa quattro momenti in cui il primo flip era teste + quando il primo flip era code:

Quindi, 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)

Answer 6

Ecco una funzione ricorsiva combinazione con le dichiarazioni di 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

E si potrebbe usare le espressioni regolari per analizzare fuori tre teste di fila:

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

Infine, si otterrebbe la risposta utilizzando qualcosa di simile a questo:

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

Ecco come lo farei:)