Keskustelu: Ohjelmointikysymykset: C++ pino (kombinatoriikkaa)

Olisikohan jollain neuvoa, että pääsisi alkuun.. Sovellukselle annetaan numerot 1-5 jossain järjestyksessä (esim. 4,3,5,2,1), jonka jälkeen sovellus tarkistaa pystytäänkö se muodostaa pinon avulla lukujonosta 1,2,3,4,5..

Mitä tarkoittaa "pinon avulla"? Missä muualla ohjelma saa säilyttää tietoa kuin pinossa?

4,3,5,2,1 ............1,2,3,4,5
           | |
           | |
           | |
           | |
           |_|
(kuva esittää pinoa)

eli tuossa esim. kuvassa oikealta tulee lukujonosta numero kerrallaan pinoon ja sitten vasemmalle muodostetaan haluttu lukujono jos pystytään.

eli 1 , 2 , 3 ja 4 pinoon jolloin saadaan 4 ja sen jälkeen 3 nostettua pinosta vasemmalle ja sitten 5 pinoon --> 5, 2 ja 1 vasemmalle jolloin sovelluksen pitäisi ilmoittaa, että haluttu lukujono pystytään muodostamaan.

jos selvensi yhtään..

Tuohan on lopulta aika helppoa. Laitat lukujonon merkkejä pinoon yksitellen kunnes pinon päällä on halutun järjestyksen ensimmäinen merkki. Otat tämän merkin pois ja tarkistat onko seuraavaksi tarvittava merkki jo pinossa. Jos se on pinossa eikä se ole päällimmäinen, on tehtävä mahdoton (jos se on päällimmäinen poistat sen merkin ja siirryt etsimään seuraavaa). Jos se taas ei ole pinossa, lisäät lukujonon seuraavia merkkejä taas pinoon kunnes tulee vastaan se seuraava merkki ja toistat näitä askelia kunnes pino on tyhjä tai tulee vastaan mahdoton tilanne.

Tuo nyt ei ole kovin tehokas algoritmi O(n²), mutta luultavasti riittävä.

Jos tuo lähtötilanne on aina järjestyksessä olevat numerot niin tuon pystyy tekemään O(n) ajassa, koska voidaan helposti tarkistaa onko tarvittava merkki jo pinossa (pienempi kuin pinon päällimmäinen).

Toimisiko ihan niin, että pinoon laitetaan lukuja yksi kerrallaan ja aina jos pinon päällä on seuraava kombinaatioon tarvittava luku, se otetaan pois? Jos kaikki luvut on laitettu pinoon ja siitä ei saa mitään pois mutta kombinaatio ei ole valmis, tehtävä on mahdoton. Tässä toteutuksessa ei tarvitse välittää, mitä pinoon on laitettu aiemmin.

paljon kiitoksia avusta.

sain neuvoista vähän aivoja liikkeelle, eiköhän se nyt onnistu.