Binäärijonon kahden peräkkäisen lukumäärät

Anonyymi-ap

Lasketaan n-pituisesta H,T-jonosta kuinka monta kertaa siinä esiintyy HH, HT, TH ja TT. Siis katsotaan kaikkia kahden peräkkäisen merkin palasia (näitä on n-1). Esim jonossa

HTTHHHTHT

määrät ovat:
HH: 2, HT: 3, TH: 2, TT: 1


Merkitään f(a,b,c,d):llä niiden H,T-jonojen lukumäärää joissa määrät ovat HH: a, HT:b, TH: c, TT: d. Laske

f(8, 5, 4, 2)
f(29, 24, 25, 21)
f(276, 249, 250, 224) (Ilmoita vastaus modulo M = 10^9 + 7)

Määritellään sitten g(n, a) niiden n:n pituisten H,T-jonojen lukumäärää, joissa esiintyy a kappaletta HH:ta. Laske mod M

g(24, 12)
g(100, 34)
g(10^100, 13)

3

152

Äänestä

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Anonyymi

      Kysy TVH:lta! Ne tietää. Tuskinpa muita kiinnostaa.

    • Anonyymi

      Vastaus:

      f(a,b,c,d) =
      [b=c➕1]( (a➕b-1) C a * (c➕d)Cd ➕ [b=c] (a➕b) C a * (c➕d-1)Cd ➕ (a➕b-1) C a * (c➕d-1)Cd )) ➕ [b=c-1] ((a➕b-1) C a * (c➕d-1)Cd ))

      Eli riippuen siitä onko b=c tai c -1, niin otetaan pienillä muutoksilla kahden binomikertoimen tulon summa. Kaipa tuon voisi kirjoittaa lyhyemminkin muodostamalla binomikertoimen sisäosat Iversonin sulkeella [b=?].

      Toinen kohta:

      g(n, a) = [z^a] sum (([[1,z], [z,z]])^n)[0]

      (tässä hakasulje tarkoittaa kertoimen ottoa)

      Laskenta kannattaa tehdä modulo z^(a 1) ja tietenkin jo lähtöjään polynomi Z/ZM -kertoiminen kun tuossa modulossa lasketaan.

    Ketjusta on poistettu 1 sääntöjenvastaista viestiä.

    Takaisin ylös

    Luetuimmat keskustelut

    1. Poliisi: Kymmenhenkinen pohjalaisperhe ollut vuoden kateissa kansainvälinen etsintäkuulutus Poliis

      Poliisi: Kymmenhenkinen pohjalaisperhe ollut vuoden kateissa – kansainvälinen etsintäkuulutus Poliisi pyytää yleisön apu
      Maailman menoa
      272
      2410

    2. Tässä totuus jälleensyntymisestä - voit yllättyä

      Jumalasta syntyminen Raamatussa ei tässä Joh. 3:3. ole alkukielen mukaan ollenkaan sanaa uudestisyntyminen, vaan pelkä
      Jälleensyntyminen
      299
      1289

    3. Mitään järkeä?

      Että ollaan erillään? Kummankin pää on kovilla.
      Ikävä
      108
      1201

    4. En kadu sitä, että kohtasin hänet

      mutta kadun sitä, että aloin kirjoittamaan tänne palstalle. Jollain tasolla se saa vain asiat enemmän solmuun ja tekee n
      Ikävä
      83
      1201

    5. Oisko mitenkään mahdollisesti ihan pikkuisen ikävä..

      ...edes ihan pikkuisen pikkuisen ikävä sulla mua??.. Että miettisit vaikka vähän missähän se nyt on ja oiskohan hauska n
      Ikävä
      58
      1145

    6. Noniin rakas

      Annetaanko pikkuhiljaa jo olla, niin ehkä säilyy vienot hymyt kohdatessa. En edelleenkään halua sulle tai kenellekään mi
      Ikävä
      81
      1096

    7. Lapuan sanomissa käy rytinä

      Pistivät sitten päätoimittajan pihalle
      Lapua
      44
      962

    8. Helena Koivu : Ja kohta mennään taas

      Kohta kohtalon päivä lähestyy kuinka käy Helena Koivulle ? Kenen puolella olet? Jos vastauksesi on Helenan niin voisi
      Kotimaiset julkkisjuorut
      67
      897

    9. Au pair -työ Thaimaassa herättää kiivasta keskustelua somessa: "4cm torakoita, huumeita, tauteja..."

      Au pairit -sarjan uusi kausi herättää keskustelua Suomi24 Keskustelupalvelussa. Mielipiteitä ladataan puolesta ja vastaa
      Tv-sarjat
      22
      860

    10. Oot ihana

      Toivottavasti nähdään sattumalta jonain kesäpäivänä♥️🥺🫂
      Ikävä
      33
      767
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt