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

203

Ää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. Arman Alizadin viesti puna-aktivisteille: "Pitäkää lärvinne nytkin kiinni"

      Arman Alizad kritisoi vasemmiston kaksinaismoralismia. Iranissa syntynyt suosikkijuontaja Arman Alizad pakeni perheensä
      Maailman menoa
      246
      4071

    2. Minja Koskela nostanut vasemmistoliiton kannatuksen ennätykseen

      Koskela valittiin puolueen johtoon lokakuussa 2024, ja silloin Ylen kysely antoi puolueelle 9,3 prosentin kannatuksen.
      Maailman menoa
      128
      2343

    3. Antti johtaa Petteriä jo 7,1 prosenttiyksiköllä

      Tällä menolla sdp menee kokoomuksesta kierroksella ohi jo tällä vaalikaudella. https://yle.fi/a/74-20213575
      Maailman menoa
      82
      2006

    4. Harmi nainen kun

      olet niin elähtäneen näköinen. Miestä et koskaan löydä itelles. j
      Ikävä
      141
      1491

    5. Hotelli kainuu

      Mietityttää, hotelli Kainuussa, se, että asiakkaat voivat valita ketä saa olla ja ketä ei, Illan aikana asiakkaina!
      Kuhmo
      39
      968

    6. Seuraavakin hallitus joutuu leikkaamaan

      Sitähän tämä hallitus nyt höpöttää, kun itse on ajanut tilanteen katastrofaaliseksi. Orpon hallitus lähti suurin puhein
      Maailman menoa
      129
      958

    7. Mistä kehon osasta

      Pidät minussa eniten?
      Ikävä
      77
      949

    8. Ovatko vastasyntyneet vauvat syntisiä?

      Se ihmisten keksimä järjetön perisynti, jos ovat!
      Luterilaisuus
      334
      881

    9. Pitäis vaan lopettaa

      Sinun kanssa yhteydenpito. Alkaa vaan haluamaan enemmän ja tuskin lopulta mikään kohtaisi. Ja ikävä vaan kasvaa ja lähei
      Ikävä
      8
      867

    10. J. Rinta-Joupilla jättimäinen veropetosvyyhti

      Seinäjoen keskustan kiinteismiljonäärit olleet jo pitkään ahtaalla ja liittykö J. Rinta-Jouppikin rintamaan? https://yl
      Seinäjoki
      62
      790
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt