Sanan osajonojen lukumäärä

minkkilaukku

Sanan osajono on siitä järjestyksessä poimittujen kirjaimien muodostama sana. Esim. sanalla "KISSA" on osajonot (24 kpl)

['', 'A', 'I', 'IA', 'IS', 'ISA', 'ISS', 'ISSA', 'K', 'KA', 'KI', 'KIA', 'KIS', 'KISA', 'KISS', 'KISSA', 'KS', 'KSA', 'KSS', 'KSSA', 'S', 'SA', 'SS', 'SSA']

Nyt kysytään algoritmiä (tai löytyykö jopa jotain kaavaa) jolla laskea näiden määrä annetulle sanalle.

Tutkitaan sitten tapausta jossa sana on n:n pituinen binäärijono.

Esim. jonolla "01101" on osajonot (18 kpl)

['', '0', '00', '001', '01', '010', '0101', '011', '0110', '01101', '0111', '1', '10', '101', '11', '110', '1101', '111']

Mikä on suurin määrä osajonoja mitä n-binäärijonolla voi olla?
Mikä on keskiarvo?

3

212

Äänestä

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • minkkilaukku

      Varmistukseksi että laskut menee oikein, niin mitä saatte seuraavalle?

      "OSAJONOJEN LUKUMÄÄRÄN LASKEMINEN"

      (myös välit lasketaan merkeiksi). Itse saan 1545659216.

    • minkkilaukku

      Ratkaisu: https://membolicsythod.home.blog/2020/02/29/sanan-osajonojen-lukumaara/

      Lisäkysymyksen ensimmäisen kohdan vastaus on f_{n 2} - 1, missä f_k on k:s Fibonacci luku.
      Suurin määrää saadaan selvästikin alternoivalla binäärijonolla, sillä aina kannattaa hypätä lähemmäksi, jotta saadaan enemmän kävelyjä (ja mikäli kaksi samaa merkkiä on peräkkäin aiheuttaa tämä toisen yli hyppäämisen edeltävästä merkistä (ja lähtö on -1 eli tyhjä, niin vaikka se olisi heti alussa, niin haittaa tulee)).
      Alternoivia on kaksi 0101.... ja 1010.... Näille osajonojen määrä, merkataan sitä a(n), on selvästi yhtäsuuri, sillä toinen saadaan toisesta muuttamalla ykköset nolliksi ja nollat ykkösiksi.

      Lasketaan nyt sanan 0101.... (päättyy joko 0 tai 1 riippuen n:n pariteetista) osajonot.
      Induktioaskel kaavan todistuksessa menee samaan tyyliin kuin mikä viimeksikin oli missä ratkaisuun tuli Fibonacci luvut. Jaetaan osajonot kolmeen luokkaan:
      - tyhjä jono
      - 0:lla alkavat
      - 1:llä alkavat

      Jos osajono v alkaa nollalla, niin silloin loppu eli v[1:] on 101... (pituus n-1):n osajono, induktio-oletuksen mukaan näitä on f_{n 1}-1.
      Jos alkaa ykkösellä, niin v[1:] taas on 010... (pituus n-2):n osajono, sillä ensimmäistä nollaa ei ole voitu käyttää, sillä alkoi ykkösellä ja niinkuin tuossa edelläkin se ensimmäinen ykkönen on voitu käyttää tai sitten ei, mutta se loppu on sen lopun osajono joka tapauksessa käytettiin se ensimmäinen ykkönen ekaan paaluun tai myöhemmin. Näitä on f_n - 1.
      Siis yhteensä

      a(n)
      = 1 a_{n-1} a_{n-2}
      = 1 f_{n 1} - 1 f_n - 1
      = f_{n 2} - 1

      • minkkilaukku

        Tämä jono, kun muuten on täällä: https://oeis.org/A000071 ja siellä on yksi muoto, että mistä tuo tulee: "Number of 001-avoiding binary words of length n - 3", niin onko tuo jotenkin kombinatorisesti nähtävissä tuosta suoraan, kun vähän samaltahan tuo kuulostaa, että kahta nollaa ei tule peräkkäin ja sitten ykköstä. Jos merkataan uudella binäärijonolla sitä indeksien osajonoa, josta osajono muodostetaan niin että 0 merkkaa että ei tule mukaan ja 1 että tulee mukaan, niin olisiko se siitä jotenkin nähtävissä?

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

    Takaisin ylös

    Luetuimmat keskustelut

    1. Saisinpa halata sinua joka päivä

      ja kertoa miten paljon sinusta välitän. Vaikka olisi jommalla kummalla huono päivä, väsynyt päivä tai kiireinen päivä, a
      Ikävä
      63
      6956

    2. Nykymiehet odottaa, että nainen lähestyy?

      Perus luonnonlaki menee päinvastoin! Oletko nähnyt luontodokkaria jossa naaraat juoksee uroksien perässä??? 🦁🫎🦍🐒🦦�
      Ikävä
      232
      5773

    3. Me työeläkeläiset äänestämme SDP:tä

      SDP on luonut koko työeläkejärjestelmän, jonka hedelmistä saamme nyt nauttia. Kansaneläkelaitos on Maalaisliiton tekele,
      Maailman menoa
      71
      4536

    4. Kolmen tuiki tavallisen demariahdistelijan nimet julki

      Nyt tiedetään ketkä kolme oli niissä niin tavanomaisissa demarin jokapäiväisissä askareissa avustajia ahdistelemassa. K
      Maailman menoa
      106
      3782

    5. Sannahan laski sähkön ALV:n 10 prosenttiin, Riikka runnoi 25,5 %:iin

      Tässäkin nähdään kumpi on Suomen kansan puolella, ja kumpi omaa vastaan. Putinistipersuille Suomen kansa tulee aina vii
      Maailman menoa
      73
      2941

    6. Eikö tunnukin kamalalta, kun en

      anna periksi vaikka parhaasi olet tehnyt antaaksesi täystyrmäyksen? Ja kyllähän minä monta iskua olen saanut ja maannut
      Ikävä
      66
      2907

    7. Kansalaispalkka ja maksuton joukkoliikenne

      Noilla pienillä parannuksilla saadaan Suomesta taas hitusen parempi paikka peruskansalaiselle, joka elää ekologisesti ja
      Maailman menoa
      118
      2613

    8. SDP:n selitykset ontuu pahasti - "On käsitelty heti, mutta kukaan ei tiedä"

      Kokoomuslaiset pistää taas demareita nippuun. Tuppuraisen mukaan mukaan SDP:n useat ahdistelutapaukset on käsitelty het
      Maailman menoa
      24
      2069

    9. Antti Lindtman: "Ainahan kaikenlaisia huhuja liikkuu"

      Näin hän siis vastaa SDP:n häirintäkohuun, väistelee vastuutaan Juttuhan on niin, että Lindtman ja Tuppurainen on tasan
      Maailman menoa
      62
      1927

    10. Muistattekos kun kaupassa piti pyytää tavarat myyjältä

      Edes kahvipakettia ei saanut itse valita, vaan myyjä nouti sen hyllystä tiskille. Jos osti jauhelihaa, niin se jauhettii
      Maailman menoa
      255
      1831
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt