Kuinka monta n:n pituista jonoa plus ykkösistä ja miinus ykkösistä voidaan muodostaa siten että jonon alkupään summa pysyy aina epänegatiivisena SEKÄ jonossa ei ole neljää -1:tä peräkkäin?
Esim.
- -- --- -
on tällainen mutta
- --
ei ole, sillä alkupään - -- summa menee negatiiviseksi.
Myöskään
- ----
ei kelpaa, sillä siinä on neljä -:ta peräkkäin.
Plusmiinus jonojen lukumäärä
Anonyymi
9
151
Vastaukset
- Anonyymi
Mikä ihmeen n?
- Anonyymi
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.
- Anonyymi
Oletetaan merkkijonojen olevan binäärilukuja. Nolla vastaa miinus-merkkiä ja ykkönen plus-merkkiä. Esim n:n arvolla 6 saadaan 20 merkkijonoa:
101010
101011
101100
101101
101110
101111
110010
110011
110100
110101
110110
110111
111000
111001
111010
111011
111100
111101
111110
111111
Ja muilla n:n arvoilla:
n c
1: 1
2: 2
3: 3
4: 6
5: 10
6: 20
7: 35
8: 69
9: 124
10: 243
11: 444
12: 867
13: 1602
14: 3120
15: 5811
16: 11296
17: 21163
18: 41081
19: 77312
20: 149913
21: 283123
22: 548524
23: 1038854
24: 2011296
25: 3817941
26: 7387651
27: 14050106
28: 27174054
29: 51762136
30: 100073139
31 190876629
32 368905094
Tarkkaa lukumäärää ei voi esittää yksinkertaisen kaavan muodossa. Kaksi epämatemaattista keksittyä ehtoa. Toinen toistaan parempia ja nopeampia tapoja löytyy rajattomasti. Isoilla n:n arvoilla tehtävä muuttuu käytännössä mahdottomaksi laskea.- Anonyymi
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
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.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
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.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
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.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).
- Anonyymi
Kaikkea oppii, kun vanhaksi elää, sanotaan.
Lukiossa 55 vuotta sitten ei kukaan tiennyt mitään epänegatiivisista luvuista.- Anonyymi
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ä.
Ketjusta on poistettu 1 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Kiky-maksuista valehtelu persujen törkein vaalipetos
Perusduunarina koen pahimmaksi persujen vaalipetokseksi "työmies" Putkosen lupaaman työntekijöiltä perittävien kiky-maks655716Persujen kannatusromahdus ilahduttaa
Siin' ei hyvä häviä. Luotto parempaan tulevasuuteen alkaa taas palautua.243927Onko Sdp:n romahdus pienpuolueeksi alkanut?
Mikään puolue ei kykene selviytymään loputtomasti, jos sitä repii jatkuvasti sisäiset ristiriidat ja kyvyttömyys päättää773500- 1132936
En malta odottaa, että Lindtman pääsee suhmuroimaan pääministerinä
kun pitää sopeuttaa 10 miljardin edestä, ja eläkkeisiinkin voidaan puuttua Antin mielestä. (Demarien kannattajissa suuri642437Totuus sattui demareihin, vaativat asiallisen jutun poistoon
ja oli vielä suosittu, mutta kun demarit tarpeeksi valittivat, niin poistettiin. Raukkamaista toimintaa. Eli siis juttu401815Mikä ihmeen v&v megastore?
Tulee Pohjoisväylälle. Mitä siellä myydään? Keski-uudessamaassa juttua.11348En selvinnyt ilman naarmuja
Vaikka ehkä kuvittelin sen olevan ilmoitusluonteinen asia, jonka jälkeen kaikki palaa entiselleen ja ilma puhdistuu. Naa131325Pitkän päivän ilta
Tarina elämättömästä miehestä, jonka elämän täytti velvollisuudentunto. Pikkutarkka, huolellinen, hyvällä katsottu, miel681234Miksi kastetaan luterilaisia ?
Tiesitkö että helluntailaiset ja jehovantodistajat kastavat luterilaisia saadaksen uusia maksavia jäseniä ? Tätä hellunt1801071