Lukujen kerääminen numerojärjestyksessä

Anonyymi

Millainen algoritmi tähän toimisi? Tarkastellaan positiivisia kokonaislukuja 1,...,n. Permutoidaan ne johonkin järjestykseen, ja kirjoitetaan ne vasemmalta oikealle. Aluksi henkilö saa vaihtaa kahden numeron paikan keskenään. Sitten henkilön täytyy kerätä luvut seuraavalla tavalla:

Joka kierroksella henkilö käy läpi numerot vasemmalta oikealle. Aluksi hän menee siihen asti kunnes löytää ykkösen ja kerää tämän talteen. Sitten hän jatkaa etenemistä ja kerää seuraavaksi kakkosen, kolmosen ja niin edelleen, jos ne löytyvät samalla kierroksella. Aina on kuitenkin kerättävä yhtä suurempi kuin edellinen kerätty oli. Kun kierros päättyy, aloitetaan uusi kierros, mennään listan alkuun vasemmalle ja aletaan keräämällä yhtä suurempi luku kuin mitä viimeksi kerättiin.

Miten suunnitellaan algoritmi, joka kertoo, monellako tapaa alussa voidaan vaihtaa kahden alkion paikat, jotta luvut tulee kerättyä mahdollisimman vähillä kierroksilla? Miten monta kierrosta tarvitaan?

12

163

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Anonyymi
    • Anonyymi

      "Aluksi henkilö saa vaihtaa kahden numeron paikan keskenään." ??
      "monellako tapaa alussa voidaan vaihtaa kahden alkion paikat" ???

      Selvitä itsellesi mitä noilla tarkoitat ja kerro sitten asia yksiselitteisesti muille. Älä vaihda termejä kesken kaiken.

      "Permutoidaan ne johonkin järjestykseen". Jos tuota tapaa ei tiedetä, aika hankala suunnitella yhtikäs mitään algoritmeja. Olet lukenut jotain jostakin ja oletata kaikkien tietävän tasan tarkkaan mitä olet tekemässä.

    • Anonyymi
    • Anonyymi

      Lopeta yksinkeskutelu!

    • Ohjelmoi metodi, mikä saa parametrina kaksi kokonaislukua, ja vertailee niitä keskenään, ja palauttaa joko luvuista pienemmän tai suuremman

      public static int max (int x, int y) {
      if (x<y) {
      return y;
      }
      return x;

      Sitten käyt silmukassa läpi kaikki luvut niin kauan, kunnes taulukon edellinen luku on pienempi, kuin seuraava.

      • Anonyymi

        Sataakos heinäkuussakin?


    • En ole meterologi, enkä tiedä tämän vuoden heinäkuun ilmastsota, mutta sinä vuonna, kun kirjoitin tuon kappaleeni "Heinäkuun sateet" -lyriikan, niin oli heinäkuu, ja satoi vettä.

    • Wikipediasta löytyy teoriaa lajittelualgoritemistä:
      https://en.wikipedia.org/wiki/Sorting_algorithm

      Lajittelu on tärkeä tietojenkäsittelyn ja algoritmiikan kannalta oleva asia. Ei ole ollenkaan sama, mitä lajittelualgoritmia käyttää esimerkiksi, kun pitäisi yhdistää tietoja tietttyyn järjestykseen esimerkiksi kahdesta laajasta tietokannasta, tai hakea tietoa valtavasta datamassasta mahdollisimman optimaalisen nopealla ajalla. (Esim. Googlella on maailman suurin tietovarasto käytössä, ja haut ovat todella nopeita. Aika näkyy sekunnin murto-osissa mitattuna tulossivulla.) Puhutaan Algoritmin aikakompleksisuudesta.

      • Anonyymi

        Lajttelu on historiaa. Silloin kun minä opiskelin kymmeniä vuosia sitten, kaikki oli vielä ihan tarpeellista ja viisaat kuluttivat aikaa erilaisten teorioden kehittelyyn.

        Nykyisin suurimmatkin käytännön tietokannat ovat mitättömiä kapasiteettiin verrattuna. Toista oli ennen kun muistia oli kilotavu ja reikä- ja magneettinauhat ja reikäkortit olivat hitaita ja niiden käsittelyyn vaadittiin paljon ihmistyövoimaa.


    • Anonyymi

      Ensimmäisen tehtävän tauluthan oli:
      [6, 1, 4, 10, 7, 2, 3, 9, 5, 8]

      Ja väitän ellei joku toisin todista että pienin kierrosmäärä on 6 joka saavutettiin vaihtamalla taulujen 4 ja 8 paikat, niin että ratkaisemaan lähdettiin tässä järjestyksessä olevia tauluja:
      [6, 1, 8, 10, 7, 2, 3, 9, 5, 4]

      Kierros 1: kerätyt taulut: 1, 2
      Kierros 2: kerätyt taulut: 3, 4
      Kierros 3: kerätyt taulut: 5
      Kierros 4: kerätyt taulut: 6, 7
      Kierros 5: kerätyt taulut: 8, 9
      Kierros 6: kerätyt taulut: 10

      Tehtävän ratkaisussa käytin apuna noin 40 rivistä Python Scriptiä. Mitään Algoritmejä tai aikakompleksisuuden opiskelua tai tuntemusta ei ratkaisua hakiessa tarvittu.

      • Anonyymi

        Toisen tehtävän tauluthan oli (50kpl):
        [38, 42, 43, 27, 41, 20, 33, 6, 47, 45, 34, 11, 19, 7, 24, 23, 35, 29, 50, 5, 17, 15, 2, 26, 49, 8, 31, 36, 1, 21, 3, 39, 22, 37, 46, 13, 40, 14, 25, 44, 16, 18, 12, 10, 30, 48, 32, 9, 4, 28]

        Ja väitän ellei joku toisin todista että pienin kierrosmäärä on 24 joka saavutettiin vaihtamalla taulujen 42 ja 19 paikat, niin että ratkaisemaan lähdettiin tässä järjestyksessä olevia tauluja:
        [38, (19), 43, 27, 41, 20, 33, 6, 47, 45, 34, 11, (42), 7, 24, 23, 35, 29, 50, 5, 17, 15, 2, 26, 49, 8, 31, 36, 1, 21, 3, 39, 22, 37, 46, 13, 40, 14, 25, 44, 16, 18, 12, 10, 30, 48, 32, 9, 4, 28]


        Kierros 1: kerätyt taulut: 1
        Kierros 2: kerätyt taulut: 2, 3, 4
        Kierros 3: kerätyt taulut: 5
        Kierros 4: kerätyt taulut: 6, 7, 8, 9
        Kierros 5: kerätyt taulut: 10
        Kierros 6: kerätyt taulut: 11, 12
        Kierros 7: kerätyt taulut: 13, 14
        Kierros 8: kerätyt taulut: 15, 16
        Kierros 9: kerätyt taulut: 17, 18
        Kierros 10: kerätyt taulut: 19, 20, 21, 22
        Kierros 11: kerätyt taulut: 23
        Kierros 12: kerätyt taulut: 24, 25
        Kierros 13: kerätyt taulut: 26
        Kierros 14: kerätyt taulut: 27, 28
        Kierros 15: kerätyt taulut: 29, 30
        Kierros 16: kerätyt taulut: 31, 32
        Kierros 17: kerätyt taulut: 33, 34, 35, 36, 37
        Kierros 18: kerätyt taulut: 38, 39, 40
        Kierros 19: kerätyt taulut: 41, 42
        Kierros 20: kerätyt taulut: 43, 44
        Kierros 21: kerätyt taulut: 45, 46
        Kierros 22: kerätyt taulut: 47, 48
        Kierros 23: kerätyt taulut: 49
        Kierros 24: kerätyt taulut: 50

        Samaan tulokseen tultiin kahdeksalla (8) eri rivillä. Tässä listattu tuli vastaan ensimäisenä.


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

    Luetuimmat keskustelut

    1. Riikka runnoo: datakeskuksille tulee UUSI yritystuki

      "Suomen valtio erikseen tukee esimerkiksi kryptovaluuttaan tai aikuisviihteeseen tai muuhun keskittyviä datakeskuksia.",
      Maailman menoa
      17
      5093
    2. Elikkä Riikka Purra ei kannusta Suomea edes euroviisuissa

      Sellaista on persujen "isänmaallisuus", oma kansa viimeiseksi ja ulkomaalaiset ensimmäisiksi. https://www.iltalehti.fi/
      Maailman menoa
      101
      2321
    3. Mitä kirjainta haluaisit

      rakastella juuri nyt?
      Ikävä
      135
      2008
    4. Riikka: 3 euron bensa, Ruotsi: bensavero jopa alle EU-minimin

      Eipä vaan suomalainen autoilija saa kaikkien rakastamalta Riikalta sympatiaa. Ruotsissa on eri meininki, siellä diskutee
      Maailman menoa
      48
      1878
    5. Victoria-tytär, 16, vertaa Martina Aitolehteä ja Esko Eerikäistä: "Iskä on enemmän..."

      Martina Aitolehti ja Esko Eerikäinen ovat ex-pari ja heillä on yksi yhteinen tytär, Victoria. Eerikäinen oli Huomenta Su
      Kotimaiset julkkisjuorut
      117
      1680
    6. "UKRAINA HYÖKKÄÄ LATVIAN ÖLJYVARASTOON JA JUNAAN"!!!

      "MATKUSTAJAJUNA SAI UKRAINALAISLENNOKEISTA VAKAVIA VAURIOITA"!!!
      Maailman menoa
      55
      1276
    7. Hilma Hallo-ahon kuvat julki - kiistää SSK ryhmän nimen merkityksen

      Eduskunnan puhemies Jussi Halla-ahon tyttären ympärille on noussut skandaali. Lehdistö sai selville Hilma Hallo-ahon kuu
      Perussuomalaiset
      117
      947
    8. Sofia Belorf rehellisenä suhteen alusta Jeff-miljonäärirakkaaseen: "Hän ei..."

      Sofia Belórfin elämä on tapetilla Sofia Bling Bling Dubai -realityssä. Näyttävien puitteiden rinnalla Belórf avaa elämää
      Kotimaiset julkkisjuorut
      48
      851
    9. Äänestän seuraavissa eduskuntavaaleissa persuja.

      Persut on ainoa puolue, joka aidosti vastustaa islamisaatiota Suomessa.
      Maailman menoa
      303
      831
    10. Kaupungin yt

      Honkolan tai hietaman koulu suljetaan. Säästölistalle on nostettu muun muassa Honkolan tai Hietaman koulun toiminnan l
      Äänekoski
      24
      664
    Aihe