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

139

Ää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. Janne Ahonen E R O A A

      Taas 2 lasta jää vaille ehjää perhettä!
      Kotimaiset julkkisjuorut
      172
      3580

    2. Tekisi niin mieli laittaa sulle viestiä

      En vaan ole varma ollaanko siihen vielä valmiita, vaikka halua löytyykin täältä suunnalta, ja ikävää, ja kaikkea muuta m
      Ikävä
      85
      1598

    3. Miksi ihmeessä?

      Erika Vikman diskattiin, ei osallistu Euroviisuihin – tilalle Gettomasa ja paluun tekevä Cheek
      Ateismi
      26
      1317

    4. Ootko huomannut miten

      pursuat joka puolelta. Sille joka luulee itsestään liikoja 🫵🙋🏻‍♂️
      Ikävä
      158
      1242

    5. Pitääkö penkeillä hypätä Martina?

      Eivätkö puistonpenkit ole istumista varten.Ei niitä kannata liata hyppäämällä koskaa likaantuvat eikä siellä kukaan niit
      Kotimaiset julkkisjuorut
      194
      1023

    6. Erika Vikman diskattiin, tilalle Gettomasa ja paluun tekevä Cheek

      Erika Vikman diskattiin, ei osallistu Euroviisuihin – tilalle Gettomasa ja paluun tekevä Cheek https://www.rumba.fi/uut
      Maailman menoa
      16
      993

    7. Kerropa ESA miten kävi tuomioiden

      Osaako ESA kertoa miten haukkumasi kunnanhallituksen kävi.
      Puolanka
      35
      981

    8. Kuinka kauan

      Olet ollut kaivattuusi ihastunut/rakastunut? Tajusitko tunteesi heti, vai syventyivätkö ne hitaasti?
      Ikävä
      69
      903

    9. Maikkarin tentti: Orpo jälleen rauhallinen ja erittäin hyvä, myös Purra oli hyvä

      Lindtman ja Kaikkonen oli kohtalaisia, sen sijaan punavihreät Koskela ja Virta olivat taas heikkoja. Ja vastustavat jalk
      Maailman menoa
      95
      839

    10. Se olisi ihan

      Napinpainalluksen päässä. Ei vaatisi paljon
      Ikävä
      62
      765
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt