1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

2. Punaiset ja siniset helmet rivissä

Pieniä reikiä on rivissä numeroituna vasemmalta alkaen parilliseen lukuun N asti. Reikiin on asetettu N kappaletta helmiä. Helmistä X kappaletta on punaisia ja loput ovat sinisiä. Kussakin reiässä on vain yksi helmi.

Robotti voi vaihtaa minkä tahansa kahden helmen paikkaa. Kahden helmen paikan vaihtaminen tulkitaan yhdeksi operaatioksi.

Robotin halutaan lajittelevan helmet siten, että kaikki punaiset helmet ovat vasemmalla alkaen paikasta 1 ja kaikki siniset helmet ovat oikealla heti punaisten helmien jälkeen.

Alla olevassa tilanteessa lajitteluun tarvitaan neljä operaatiota.

Esimerkkikuva

Lajittelussa huonoin mahdollinen alkutilanne on, kun mahdollisimman moni punainen helmi ei ole oikealla paikallaan.

Kuinka monta operaatiota robotin tarvitsee lajittelussa tehdä, jos alkutilanne on huonoin mahdollinen?

Valitse oikea vastaus:

Muista painaa vastaa-painiketta, muuten vastaus ei tallennu lainkaan.