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?
Sanan osajonojen lukumäärä
3
264
Vastaukset
Varmistukseksi että laskut menee oikein, niin mitä saatte seuraavalle?
"OSAJONOJEN LUKUMÄÄRÄN LASKEMINEN"
(myös välit lasketaan merkeiksi). Itse saan 1545659216.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} - 1Tä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ä.
Luetuimmat keskustelut
Perintovero 100 prosenttiin, työeläkkeet ja maataloustuet pois
Noilla eväillä lähden tasapainottamaan valtiontaloutta ja korjaamaan työntekijöiden palkkakuoppaa nostamatta työnantajie1655481Seksuuaalivinksataneiden toimintaa rahoitetaan valtion varoilla.
Setan toimintaa rahoitetaan valtionavustuksilla, joilla mm kierretään kouluissa haalimassa alaikäisiä mukaan perverssii774875Riikka runnoo: polttoöljyn hinta nousi maaliskuussa 40 prosenttia
Onko irvistelijällä sakset hävinneet, vai miksei osaa leikata polttoaineiden hintaa kansalaisten kukkarolle sopivalle ta343761Purra ryöväsi Marinin Itä.-Suomelle neuvottelemat EU-rahat
Perust vihaavat suomalaisia, mutta eritoten itäsuomalaisia. "Osa kaksikäyttörahoista on alun perin Itä- ja Pohjois-Suom253139Miksi persut hyökkäävät jatkuvasti henkilöitä päin?
Miksei persut yritä lainkaan korjata asioita, vaan koko ajan haukkuvat henkilöitä? Ei tuollaisilla turvanpieksäjillä ole493038Demariskandaali! Eveliina Heinäluoma (sdp) kahmii kaikki Hitas asunnot itselleen!
Heinäluoma on ostanut useita yhteiskunnan tukemia, hintasäännösteltyjä asuntoja itselleen! Ei ihme, että Hitas on ollut1582806Seida Sohrabi: Suomi ei ole rasistinen maa
Seidalta taas täyttä asiaa. Miksi punavihreät naiset eivät pysty samaan - no se ideologia estää. "Meillä on valitettava232645Mökkejä ostellaan nyt ihan hulluna!
Tyypilliset lainamäärät on yli 500 000€ mökkejä ostellessa eli erityisesti tuollaiset miljoonamökit on nyt suomalaisten862643Demarien sanoin kuvaamaton ahneus - Eveliina Heinäluoma vain yksi esimerkki
Mutta näin se on demari-eliitissä aina ollut, käytännössä siis nämä eliittiin kuuluvat ovat puhtaasti porvareita - Marin712366Ranskan vasemmistojohtaja tunnustaa, että väestö on vaihtumassa
ja se on vaan hyvä asia hänen mielestään. Kyseessä siis Ranskan vasemmistojohtaja Jean-Luc Mélenchon jonka puheet järkyt652009