Plusmiinus jonojen lukumäärä

Luonnollinen luku n on jonon pituus.
Esim. tapauksessa n=3 sallitut jonot ovat


-
-

Näitä on kolme kappaletta eli vastaus n:n arvolle 3 on 3. Tässä kysytään yleiselle n:n arvolle kaavaa/jotain tapaa laskea tuo arvo.

Kokeilin eri vaihtoehtoja.

Tarkasteltavia lukuja ei kannata missään vaiheessa muuttaa merkkijonoiksi (tulostusta lukuun ottamatta). Luvun bittien tarkastelut voidaan suorittaa siirrettävällä (jako kahdella) maskibitillä paljon nopeammin ja helpommin. On tietysti ihan sama miten tekee, jos n on pieni (alle 30).

Jos tallettaa listaan kaikki aikaisemmat (n-1) luvut ja yrittää katsoa, voiko niihin lisätä (oikealle) yhden bitin lisää, niin muisti loppuu varmasti.

Anonyymi kirjoitti:

Kokeilin eri vaihtoehtoja.

Tarkasteltavia lukuja ei kannata missään vaiheessa muuttaa merkkijonoiksi (tulostusta lukuun ottamatta). Luvun bittien tarkastelut voidaan suorittaa siirrettävällä (jako kahdella) maskibitillä paljon nopeammin ja helpommin. On tietysti ihan sama miten tekee, jos n on pieni (alle 30).

Jos tallettaa listaan kaikki aikaisemmat (n-1) luvut ja yrittää katsoa, voiko niihin lisätä (oikealle) yhden bitin lisää, niin muisti loppuu varmasti.

Lue lisää

Minä saan rekursiivisella ohjelmalla n=100:aan asti laskettua vielä aika hujauksessa.

32 : 368905094
33 : 704436028
34 : 1361071685
35 : 2601536541
36 : 5025323325
37 : 9613417317
38 : 18566096001
39 : 35542816776
40 : 68630167965
41 : 131469237249
...
99 : 4249273324587584375262781614
100 : 8192353731897060343551592766

Kokeilepas laittaa "putkiehtoon" nelosen tilalle 3, niin löytyy OEIkSesta: http://oeis.org/A191519 . Ajattelin voisiko neloselle keksiä myös generoivan funktion, joka kolmoselle on 2/(1-2*x-x^2 sqrt(1-2*x^2-3*x^4)). Kakkosellahan tulee Fibonacci luvut.

Anonyymi kirjoitti:

Minä saan rekursiivisella ohjelmalla n=100:aan asti laskettua vielä aika hujauksessa.

32 : 368905094
33 : 704436028
34 : 1361071685
35 : 2601536541
36 : 5025323325
37 : 9613417317
38 : 18566096001
39 : 35542816776
40 : 68630167965
41 : 131469237249
...
99 : 4249273324587584375262781614
100 : 8192353731897060343551592766

Kokeilepas laittaa "putkiehtoon" nelosen tilalle 3, niin löytyy OEIkSesta: http://oeis.org/A191519 . Ajattelin voisiko neloselle keksiä myös generoivan funktion, joka kolmoselle on 2/(1-2*x-x^2 sqrt(1-2*x^2-3*x^4)). Kakkosellahan tulee Fibonacci luvut.

Lue lisää

Masentavaa! Olin juuri kirjoittamassa miten pääsin pienellä tyhmällä rekursiivisella ohjelmalla alle tunnissa n=39 asti. Samat lukumäärät tuohon asti. Aika lähes tuplantuu joka kerta n:n kasvaessa 1:llä. Kasvatin lukumäärää aina yhdellä kerrallaan, joten aikaa kuluu tietysti valtavasti.

Sinulla on jotain älykkyyttä mukana ohjelmassasi. Pystyt jotenkin kasvattattaamaan lukumäärälaskuria isoilla kerrannaisilla ja niiden kerrannaisilla. Ja aina oikein. Löytyy varmasti jotain jaksollisuutta.

Anonyymi kirjoitti:

Masentavaa! Olin juuri kirjoittamassa miten pääsin pienellä tyhmällä rekursiivisella ohjelmalla alle tunnissa n=39 asti. Samat lukumäärät tuohon asti. Aika lähes tuplantuu joka kerta n:n kasvaessa 1:llä. Kasvatin lukumäärää aina yhdellä kerrallaan, joten aikaa kuluu tietysti valtavasti.

Sinulla on jotain älykkyyttä mukana ohjelmassasi. Pystyt jotenkin kasvattattaamaan lukumäärälaskuria isoilla kerrannaisilla ja niiden kerrannaisilla. Ja aina oikein. Löytyy varmasti jotain jaksollisuutta.

Lue lisää

Tässä koodini (Pythonia): https://pastebin.com/ZuKzuAkb

Ideana on se, että rekursioon otetaan parametreiksi

j = jonon pituus,
a = miinusputken pituus, väliltä 0,...,3
b = alkupään summan pituus (väliltä 0,..,n).

Katsotaan mistä kaikista tiloista (j-1, *, *) tilaan (j,a,b) voidaan päätyä. Jos a>0, niin on voitu tulla (j-1, a-1, b 1):stä lisäämällä jonon perään -1. Jos taas a=0 ja b>0, niin sitten on tultu lisäämällä 1 ja tila, josta on tultu voi olla (j-1, k, b-1) mille tahansa k:n arvolle 0,1,2, tai 3.
Tulosta varten summataan kaikkien mahdollisten tilojen yli.

Tämä on ehkä helpompi ajatella "eteenpäin" eli lähdetään tyhjästä jonosta kasvattamaan sitä. Sitähän voi ajatella solmusta (0,0) lähtevien n-kävelyden määränä suunnatulla verkolla, jossa solmuina on kaikki parit (a,b), a=0,1,2,3, b=(0,1,...,n) ja kaari solmusta (a,b)

1. solmuun (a 1, b-1), jos a<3 ja b>0 (vastaa miinusmerkin lisäämistä jonon perään)
2. solmuun (0, b 1) (vastaa plusmerkin lisäämistä jonon perään).

Kysytty lukumäärä saadaan verkon vierekkäismatriisin n:n potenssin ensimmäisen rivin summana (olettaen että solmu (0,0) indeksoidaan ensimmäiseksi).

Niin se on ehkä vähän kankealta tuntuva termi, mutta jos sanotaan positiivinen, niin nolla ei ole mukana. Sitten taas "positiivinen tai nolla" alkaa olemaan liian pitkä.