Plusmiinus jonojen lukumäärä

Anonyymi

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.

9

101

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • 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

    1. Suureksi onneksesi on myönnettävä

      Että olen nyt sitten mennyt rakastumaan sinuun. Ei tässä mitään, olen kärsivällinen ❤️
      Ikävä
      85
      1798
    2. Perusmuotoiset TV-lähetykset loppu

      Nyt sanoo useiden HD-muotoistenkin kanavien kohdalla äly-TV, ettei kanava ole käytössä, haluatko poistaa sen? Kanavia
      Apua aloittelijalle
      123
      1220
    3. YLE Äänekosken kaupunginjohtaja saa ankaraa arvostelua

      Kaupungin johtaja saa ankaraa kritiikkiä äkkiväärästä henkilöstöjohtamisestaan. Uusin häirintäilmoitus päivätty 15 kesä
      Äänekoski
      62
      1080
    4. No ei sun asunto eikä mikään

      muukaan sussa ole erikoista. 🤣 köyhä 🤣
      Ikävä
      62
      956
    5. Hyvin. Ikävää nainen,

      Että vainoat ja stalkkaat miestäni.onko tarkoituksesi ehkä saada meidät eroamaan?no,siinä et tule onnistumaan
      Ikävä
      74
      866
    6. Uskomaton tekninen vaaliliitto poimii rusinoita pullasta

      Korni näytösesitelmä menossa kaupunginvaltuustossa. Juhlia ei ole kokouksista tiedossa muilla, kuin monipuolue paikalli
      Pyhäjärvi
      81
      817
    7. Katsoin mies itseäni rehellisesti peiliin

      Ja pakko on myöntää, että rupsahtanut olen 😆. Niin se ikä saavuttaa meidät kaikki.
      Ikävä
      47
      817
    8. Linnasuolla poliisi operaatio

      Kamalaa menoa taas meidän ihanassa kaupungissa. https://www.uutisvuoksi.fi/paikalliset/8646060
      Imatra
      29
      816
    9. Mitä mietit Honey?

      Kulta nainen ❤️❤️
      Ikävä
      57
      810
    10. Martina lähdössä Ibizalle

      Eikä Eskokaan tiennyt matkasta. Nyt ollaan jännän äärellä.
      Kotimaiset julkkisjuorut
      118
      782
    Aihe