https://www.ohjelmointiputka.net/oppaat/opas.
def kaanna(mjono):
uusi = ""
for merkki in mjono:
uusi = merkki + uusi
return uusi
while True:
sana = input("Anna sana: ")
if sana == "":
break
print("Toisinpäin: " + kaanna(sana))Missä toi kääntää ton sanan? Onko tuo jokin ohjelmiin sisäänrakennettu komento? Jäikö mulla jotain tärkeää välistä?
(Mod. huom: muista käyttää kooditageja koodin merkkaamiseen!)
Tuossahan se kaanna-funktio on määritelty ihan ensimmäiseksi.
Mieti, mitä kaanna-funktiossa tapahtuu. Mitä merkkejä käydään läpi ja missä järjestyksessä? Mihin ne merkit laitetaan ja missä järjestyksessä? Eli kyllä, jos tässä on epäselvää, kannattaa kerrata oppaasta aiemmat osat (for-silmukka ja merkkijonot). Jos asia on vaikea hahmottaa, suorita ohjelmaa itse ja kirjoita vaikka paperille eri muuttujien sisältöjä.
Jokainen ”komento” tai rakenne tuosta ohjelmasta pitäisi jo ymmärtää, joten pitäisi myös nähdä, että mitään yllättävää sisäänrakennettua taikuutta ei tapahdu.
Älkääs nyt hoputtako, että pitäisi osata ja siellähän se on, jos ei löydä, niin ei löydä. Olen nyt toista viikkoa tässä touhussa mukana, kun pari vuotta sitten kävin nettikurssin aiheesta.
Virittelin omaan "ohjelmaan" ensin noita yksinkertaisia juttuja, ne onnistui, ja nyt yritän sieventää röpellykseni deffeihin.
Muistaakseni silloin pari vuotta takaperin juttu jäi juuri siihen, kun piti noita juttuja, jotka ei auennut kerrasta, etsiä erilaisia selityksiä eri kielillä, jolloin itse aihe unohtui, mitä piti opetella.
”Pitäisi osata” tarkoittaa tässä yhteydessä sitä, että kaikki tähän liittyvät asiat on kerrottu oppaassa aikaisemmin eli mitään uusia yllätyksiä koodissa ei ole.
Onko koodissa jokin erityinen kohta, jota et ymmärrä? Millaiseen tulokseen päädyt, jos alat käsin paperilla miettiä tuota kaanna-funktion kulkua vaikka merkkijonolla "ABC"?
Tee suorituksesta vaikka taulukko:
rivi | uusi | merkki | mjono 1 | | | "ABC" 2 | "" | | "ABC" 3 | "" | "A" | "ABC" ... (lisää rivejä tähän, kun silmukka etenee) ... 5 | "CBA" | "C" | "ABC"
Avainsana on järjestys.
Metabolix kirjoitti:
(04.06.2021 12:11:17): ”Pitäisi osata” tarkoittaa tässä yhteydessä...
Juu, kyllä toi aika hyvin selkeni siis tähän vaiheeseen, missä olen. Kiitos tuosta vinkistä. Ei ole aina ihan varmaa just tosta, et mitä tietoa täytyy olla pohjalla, et voi alkaa käydä läpi jotain tiettyä asiaa. Ei siis ole tuo ulkomuisti mulla niin hyvä, et menis kuin vettä vain.
Toi mjono ja merkki löytyi kyl hyvin, mut kaipa se oli tuo uusi = "", missä tipuin kärryiltä. Tai en ole ihan varma.
Sain tehtyä nyt tuollaisen simppelin deffin ilman argumenttia. Tässä, kun yrittää ajatella yhtä aikaa, kun tekee, et oppis, niin pää on välillä aika kovilla. :D
HTML5 kirjoitti:
Avainsana on järjestys.
Siksi koodaaminen varmaan kiehtoo. Sillä voi luoda järjestystä, kun pään sisässä on kaaosjärjestys.
Mieti, mitä eroa on koodilla A + B ja B + A, kun molemmat ovat merkkijonoja.
HTML5 kirjoitti:
Mieti, mitä eroa on koodilla
A + BjaB + A, kun molemmat ovat merkkijonoja.
A + B
Rivi | Merkki | mjono tai Rivi | Merkki | mjono
1 | B | AB 1 | + | A+B
2 | A | AB 2 | B | A+B
-3 | A | A+Bja
B + A Rivi | Merkki | mjono 1 | A | BA 2 | B | BA
Osuinko lähelle?
HTML5 kirjoitti:
Mieti, mitä eroa on koodilla
A + BjaB + A, kun molemmat ovat merkkijonoja.
A + B Rivi | Merkki | mjono 1 | B | AB 2 | A | AB
Tai
Rivi | Merkki | mjono 1 | + | A+B 2 | B | A+B -3 | A | A+B
ja
B + A Rivi | Merkki | mjono 1 | A | BA 2 | B | BA
Osuinko lähelle?
"A"+"B"="AB"
"B"+"A"="BA"
Näyttää, että Vanutyyny ei nyt ymmärtänyt kysymystä eikä oikein tätä taulukkomerkintää myöskään. Taulukossani rivi-kohtaan oli tarkoitus merkitä koodin rivinumero sitä mukaa, kun ajat tuota alkuperäistä koodia paperilla ja mietit sen toimintaa; rivillä 3 on for-sana ja rivillä 4 on uutta merkkijonoa muokkaava lauseke, ja näitä siis toistetaan tietyllä tavalla. Käyttäjä HTML5 taas kehotti miettimään, mitä eroa on koodilla A+B ja B+A: jos vaikka A sisältää tekstin "kis" ja B sisältää tekstin "a", niin A+B on "kisa" ja B+A on "akis". Syy, miksi tätä käskettiin miettiä, on tuossa alkuperäisessä koodissa, joka kääntää tekstin: siinä käydään merkit läpi järjestyksessä mutta lisätään ne aina uuden tekstin alkuun (eikä loppuun), ja sen takia tuloksena on käännetty teksti. Ja juuri tuon takia myös kehotin kokeilemaan omassa päässä ja paperilla, mitä koodissa tapahtuu.
Käy algoritmi läpi vaikka sitten kynällä ja paperilla, josset kaksirivistä koodia muuten ymmärrä. Koodi on jo itsessään niin yksinkertainen, että sen toiminta pitäisi ymmärtää silmämääräisesti. Jos näin ei ole, niin hyvin vaikea sitä on foorumillakaan purkaa auki sen paremmin.
Tämä on sikäli kiinnostava algoritmi, että rekursio voi olla jopa helpompi ymmärtää.
def käännä(s):
if len(s) < 2:
return s
else:
return käännä(s[1:]) + s[0]Pythonissa on kätevää merkkijonoa kun se käsittelee taulukkona, ja taulukon alkio indeksi viittaa merkkijonon merkkiin. Tämän taulukkona käsittelyn seurauksesta voidaan tehdä johtopäätös, että taulukon voi palauttaa käänteisenä, Pythonissa on aika tehokkaat taulukon käsittelyominaisuudet.
def kaanna(sana):
return sana[::-1]
print(kaanna("saippuakauppias"))Tuo on paras, mihin olen päätynyt kun ohjelmoin Pythonilla Palindromikonetta.
Tuloste
saippuakauppias
Saatuani huomautus-palaute viestin täällä Ohjelmointiputkassa yksityisviestin ylläpitäjältä, että voisin mahdollisesti olla poikkoilematta aiheessa niin paljon, niin nyt avasin uuden ketjun kun mainitsin tuossa tämän säikeen vastauksessani palindromikoneen tuon mekkijonon kääntämisen yhteydessä.
pythonissa voisi olla kätevää, jos saisi tuossa input-metodissa vaikka toisen syoteparametrin keinoin tallennettua käyttäjän syotteen muuttujaan. Lisäksi tein havainnon, että do-while toistorakennetta ei taida python tarjota ollenkaan.
Suora linkki jatkoa tälle keskustelulle vähän sivu-urille jatkettaessa
Metabolix kirjoitti:
Tämä on sikäli kiinnostava algoritmi, että rekursio voi olla jopa helpompi ymmärtää.
def käännä(s): if len(s) < 2: return s else: return käännä(s[1:]) + s[0]
Ei tuo nyt niin kaukaa haettua ole, ratkeaa tuo kääntäminen rekursiivisenakin ongelmana, mutta entä sitten ratkeamisaika verrattuna tuohon minun esitykseen, kestääko se vertailun.
Käsittääkseni pythonissa taulukonkäsittely käyttää quicksorttia, tai jos ei lajittelua ole, pelkkä arvon hakeminen taulukosta, joka on vain käänteisenä aina seuraavan alkion sisällon hakeminen taulukosta tuossa esittämässäni metodissa, niin sitten suoritusaika on vakioaikainen, joka on nopeampi, kuin rekursiivisen metodin, jossa käsittääkseni parhaimmillaan päädytään (n (log) n) -suoritusajan suhteen.
pythonissa tosiaan sovelletaan tuota Timsort, joka on jonkinlainen variantti quicksortista, siitäkin on täällä ohjelmointiputkassa en muista oliko peräti minun avaamani keskustelu, tai tiedustelin tuosta Timsort-metodista, niin tuli esille tuo quicksort joku mainitsi sen. Quicksortin ratkeavuusaika on sama, mitä tuossa rekursiivisessa ratkaisussa (n (log) n), niin aikakomplesisuuden suhteen kun ne on samat, jos tuossa jotain lajittelua olisi vakioaikaisen seuraavan arvon tulostamisen ulostuloon sijaan, joka on tosiaan vakioaikainen suoritusaika, niin sittenhän olisi ihan makukysymys, jos haluaa rekursiolla ratkaista tuon.
Vakioaika on kaikilla syotekoon määrillä joka tapauksessa nopeampi, kuin tuo rekursio, kun syotteena merkkijonon pituus on tarkasteltavana näiden kahden algoritmin vertailu aina yhtä pitkillä merkkijonoilla.
Jere Sumell kirjoitti:
Metabolix kirjoitti:
Tämä on sikäli kiinnostava algoritmi, että rekursio voi olla jopa helpompi ymmärtää.
def käännä(s): if len(s) < 2: return s else: return käännä(s[1:]) + s[0]Ei tuo nyt niin kaukaa haettua ole, ratkeaa tuo kääntäminen rekursiivisenakin ongelmana, mutta entä sitten ratkeamisaika verrattuna tuohon minun esitykseen, kestääko se vertailun.
Jos suoritusaika on tärkeä, niin oma versiosi on muuten isoilla syötteillä ja isolla syötemäärällä potentiaalisesti melko hidas!
Merkkijonoilla touhutessa kun otat siivun merkkijonosta niin otat aina käytännössä kopion alkuperäisestä merkkijonosta. Vähemmän elegantin näköinen ja vähän pitempi toteutus mikä käyttää kahta indeksi muuttujaa ja tekee vertailun paikallaan on varmasti paljon nopeampi.
Taulukonkäsittely selityksesi on aika "mielenkiintoinen" ...
Mikä jalski mielestäsi on tuon esitykseni suooritusajan ratkeavuusaika?
Jos tuossa merkkijonon siivuttamisessa kopioinnissa puhutaan expotentiaalisesta ajasta, niin siinä tapauksessahan se on hitaampi, ja ruo Metabolixin rekursio-ratkaisu pesee omani mennen tullen.
Käytännön tasolla tuskin simppelissä palindromikoneessa, jossa kysytään ihmiskäyttäjältä jotain syötettä, niin ainakin valta-osa syötteistä on sitä koko luokkaa, että melkein sama kumpaa ratkaisua käyttää, jos tosiaan aika olisi kriittinen määre tässä tapauksessa. Käytännössä näin ei varmaan ole missään olosuhteissa, vaikka tuo olisi ajossa sovellettuna kaupalliseen sovellukseen vaikka ajossa jossain palindromipalvelussa jossain päin maailmaa virtuaalipalvelimella, niin varmaan ihan yhdenkin prosessorin vuokraamisella ei käy kukkaron päälle tuo laskentatehon lisäinvestointien tarve, kun sitä ei ole.
jalski kirjoitti:
Taulukonkäsittely selityksesi on aika "mielenkiintoinen" ...
Ehkä Python-sivistyksessäni on under-the-hood -osastolla aukko. Valaise minua, ja voitko vääntää rautalangasta, miten tuo taulukon käsittely etenee vaihe vaiheelta, kun Python tulkki tulkitsee koodia. Voi ollakin, että olet oikeassa, että tosiaan siivuttamisessa olisi tuo kopiointi-mekanismi, mutta en ole asiasta niin paljon ottanut selvää, joten nyt sinä voisit kertoa.
Varmaan, jos on olemassa jokin hyvin matalan tason Python-debuggeri olemassa, voisi asiaa selvittää itsekin, mutta en ole koskaan debugannut Python-koodia ja varmaan Python 3:n oletusdebuggerilla ei selviä asia.
Javasta tiedän, että siinähän on tuo kopiointi, kun liittää kaksi merkkijonoa + -operaattorilla yhteen, niin Java kopioi ja syntyy uusi String, jossa on kopiot, eikä se ole mikään resurssitehokas tapa käsitellä stringejä Javassa.
Vielä MUOKKAUS-LISÄYS
vertailu (x > y) suoritusaika on vakioaikainen.
Rekursiossa, kun tehdään kerrallaan kahden alkion vvertailua, niin mihin aikakokoluokkaan päädytään, kun kahden alkion suuruuden vertailua toistetaan n-kertaa. Siitähän se ratkeaa. Päätykö siinä tuohon n log n, mitä aluksi epäilin rekursion ajan määreen suhteen suorituksen kokoluokaksi. Vai onko se n^2 vai mitä se on?
Jere Sumell kirjoitti:
Pythonissa on kätevää – – että taulukon voi palauttaa käänteisenä,
Joo, mutta tuon merkinnän ymmärtäminen vaatii erityistä ennakkotietoa Pythonista, kun taas silmukka ja rekursio ovat ymmärrettäviä yleisellä ohjelmointikokemuksella.
Jere Sumell kirjoitti:
Voi ollakin, että olet oikeassa, että tosiaan siivuttamisessa olisi tuo kopiointi-mekanismi,
Kyllä siinä nimenomaan kopioidaan, käännä-funktiohan palauttaa käännetyn tekstin. Siitä ei pääse mihinkään, että tekstin kääntämistä varten joutuu joko muokkaamaan alkuperäistä dataa (ei onnistu Pythonin merkkijonoilla) tai luomaan datasta uuden käännetyn kopion.
Tietysti esittämäni rekursio on tässä ajallisesti erityisen huono, kun tekstiä katkaistaan moneen kertaan ja Pythonin funktiokutsutkin ovat hitaita. Tarkoitus olikin esittää tyyliä eikä nopeutta.
Toisaalta sitten vaikkapa palindromin tarkastamiseen ei tarvita ollenkaan käännettyä tekstiä, vaan alkuperäistä tekstiä voi vertailla merkki kerrallaan lähtien samaan aikaan alusta ja lopusta.
Jere Sumell kirjoitti:
Rekursiossa, kun tehdään kerrallaan kahden alkion vvertailua, niin mihin aikakokoluokkaan päädytään, kun kahden alkion suuruuden vertailua toistetaan n-kertaa. Siitähän se ratkeaa. Päätykö siinä tuohon n log n, mitä aluksi epäilin rekursion ajan määreen suhteen suorituksen kokoluokaksi. Vai onko se n^2 vai mitä se on?
Ei aavistustakaan, mistä algoritmista nyt edes selität, kun tässä keskustelussa ei ole mitään listan alkioita vertailtu. Rekursio ei myöskään tekniikkana johda tiettyyn aikavaativuusluokkaan.
Esittämäni kääntämisfunktio on O(N²) siitä syystä, että joka merkin kohdalla luodaan kopio merkkijonon loppuosasta. Toisaalta jos funktion toteuttaisi indeksillä, aikavaativuudeksi tulisi O(N).
def kaanna(s, i = 0):
if i >= len(s):
return ""
else:
return kaanna(s, i+1) + s[i]Näennäisen hyvästä luokituksesta huolimatta funktiokutsut rajoittavat käytännön nopeutta (ja myös käännettävän merkkijonon pituutta, koska rekursion syvyyttä Pythonissa on rajoitettu).
Metabolix kirjoitti:
Tämä on sikäli kiinnostava algoritmi, että rekursio voi olla jopa helpompi ymmärtää.
def käännä(s): if len(s) < 2: return s else: return käännä(s[1:]) + s[0]
Jere Sumell kirjoitti:
(05.06.2021 17:10:47): Pythonissa on kätevää merkkijonoa kun se...
No noissahan se lukee silmien edessä. Kyllä tässä opiskeluvaiheessa on hyvä nähdä asiat vaihe vaiheelta, kun ei ole opettajaa luokan edessä kertomassa, että mitä tapahtuu.
Ton :: tajusin tosta ekasta. :)
Ja juu kaikille, kiitos vastauksista. Opiskelen tosissaan ensin logiikan, eli lieliopin ja sitten voidaan jutella lisää noista ajoista, eli tyylistä.
Vaiks mun kone veti nää kyl ihan niin nopeesti, vaikka testailin tosi pitkillä sanoilla näitä. ;)
Vanutyyny kirjoitti:
Vaiks mun kone veti nää kyl ihan niin nopeesti, vaikka testailin tosi pitkillä sanoilla näitä. ;)
Käytännössä ihmisen syöttämä merkkijono tässä merkkijonon kääntämis-algoritmissä, missä puhutaan siitä algoritmin syötekoosta, niin on joka tapauksessa pieni kooltaan.
Nykyaikaiset mikrotietokoneet omaavat jo koti-oloissakin paljon vaativimpienkin algoritmien suorittamiseen, jotka vaativat paljon laskentatehoa, niin monesta tehtävästä nämä ihan kotiläppäritkin suoriutuvat ihan siedettävässä ajassa, jos nyt ajattelet vaikka jotain paljon laskentatehoa vaativia uusia PC-pelejä esimerkiksi ja ääritapauksena jokin Bitcoin-louhintakin, sitäkin voi kotikoneella harrastaa jollain lailla, nVidian uusimmassakin näytönohjaimessa ihan hyvä laskentateho, vaikka louhisi pelkästään sillä, mutta prosessoritkin ovat jo nykyään melko tehokkaita kotiläppäreissä ja kotikonettakin ihan mielekästä käyttää vähän vaativampienkin algoritmien suorittamiseen, sieltä toisesta päästä, mikä ei ole mahdollista nykyaikaisella mikrotietokoneella, on jokin sellaisen shakkitietokone, joka kävisi joka siirron jälkeen läpi 100% sen pelitilanne-analyysin, ja tekisi parhaan mahdollisen siirron joka siirron jälkeen. Siihen ei kykene välttämättä supertietokoneetkaan vielä, täytyy odottaa lopullista kvanttihyppyä, niin siinä kohtaa ihminen häviää 100% varmuudella tietokoneelle shakissa melko varmasti.
Vielä sellainen lisäys, kun puhuin vähän sekoittaen edellisessä postauksessani, että vältytään väärinymmärryksiltä:
Tietokoneen prosessorin laskentateholla ole mitään merkitystä puhuttaessa algoritmin aikakompleksisuudesta, vaan jos algoritmi todetaan hitaaksi isolla syotekoolla, on sen suorittaminen verrattain hidasta myos sama mikä kvanttitietokone olisi sitä suorittamassa.
Shakkitietokoneen ohjelmointi on kokonaan toinen keskustelusäikeen aloituksen aihe, joten ei mennä tässä siihen, mutta sama mikä algoritmi on kyseessä, kannattaa tavallisesti ajatella myos sen aikavaativuutta, jos ongelma on algoritmisesti ratkeava kelvollinen ongelma, joissain kelvottomissa ongelmissa tai jossain tiettyyn tarkoitukseen suunnitelluista algoritmeistä voi tinkiä joistain vaatimuksista. Yleensä tinkiminen esimerkiksi ajasta sitten muistivaatimukset nousee tai jokin muu resurssin tarve.
Idea algoritmistä on tuhansia vuosia vanha, ja valta-osan ihmisen reaalimaailman ongelmista on sellaisia, jotka eivät ole algoritmisesti ratkeavia, eli lähestulkoonkaan kaikkeen ei kykene tietokoneella ohjelmoimaan ongelman ratkaisevaa algoritmiä.
Jere Sumell kirjoitti:
Jos algoritmi todetaan hitaaksi isolla syotekoolla, on sen suorittaminen verrattain hidasta myos sama mikä kvanttitietokone olisi sitä suorittamassa.
Älä sotke kvanttitietokoneita tähän. Kvanttitietokone ei ole nopea tietokone vaan idealtaan täysin erilainen laite. Sillä voisi ratkaista joitain ongelmia, joihin ei ole tavallisessa laskennassa tehokasta ratkaisua edes supertietokoneella, ja toisaalta se sopisi huonosti perinteiseen laskentaan. Toki teknisesti kvanttitietokoneelle pitäisi myös laatia eri algoritmi, joten pilkkua viilaamalla olet sattumalta oikeassa.
Yleensä kuitenkin pysytään perinteisessä laskennassa ja sanotaan, että hidas algoritmi on verrattain hidas myös supertietokoneella.
Metabolix kirjoitti:
... joten pilkkua viilaamalla olet sattumalta oikeassa.
"sattumalta". Ehkä käsitykseni kvanttitietokoneesta on vajavainen, oikeastaan sen mitä olen siihen perehtynyt, niin se tarjoaa mm. huiman laskentatehon mitä olen lukenut siitä. Tästä syystä vedin kvanttitietokoneen tähän keskusteluun.
Sovitaan siten, että pysytään nykyaikaisissa mikrotietokoneissa ja supertietokoneissa ja perinteisessä laskennassa siinä mielessä, kuin me sen tänä päivänä ymmärrämme.
Aihe on jo aika vanha, joten et voi enää vastata siihen.