Dubenėlių konvejeris

Taškai: 9

Įmonė gamina 6 skirtingų dubenėlių rinkinius. Dubenėliai slenka konvejerio juosta vienas paskui kitą iš kairės į dešinę.
Visi 6 skirtingi rinkinio dubenėliai keliauja konvejeriu kartu, tačiau jie sudėti atsitiktine tvarka. Prieš pakuojant dubenėliai turi būti išrikiuoti nuo mažiausio iki didžiausio.
Dubenėlius rikiuoja įmonės darbuotojai, sustoję palei konvejerį. Dubenėlių rinkiniui slenkant pro darbuotoją, šis apkeičia dubenėlių poras, išsidėsčiusius neteisinga tvarka. Pasižiūrėkite, kaip sudėstomas dubenėlių rinkinys, kol praslenka pro vieną darbuotoją:

Kiek darbuotojų reikia norint išrikiuoti pateiktą dubenėlių rinkinį teisinga tvarka?

Paaiškinimas

Automatinis duomenų apdorojimas vyksta daug lengviau, jei duomenys išdėstomi pagal tam tikrus kriterijus – išrikiuojami. Informatikoje daug pastangų dedama ieškant vis naujų, vis geresnių rikiavimo algoritmų. Užduotyje aprašytas dubenėlių rikiavimo metodas vadinamas burbulinio rikiavimo metodu. Šis rikiavimo algoritmas daug kartų tikrina objektų sąrašą ir kaskart apkeičia gretimus objektus, išsidėsčiusius neteisinga tvarka. Sąrašas laikomas išrikiuotu, kai nebereikia nieko keisti tikrinant visą sąrašą.

Burbulinis rikiavimas, palyginti su kitais, yra gana lengvai suprantamas rikiavimo algoritmas, tačiau jis nėra labai veiksmingas. Norint išrikiuoti 1000 daiktų burbulinio rikiavimo metodu teks atlikti maždaug pusę milijono žingsnių. Geresni rikiavimo algoritmai atliktų maždaug tik 10000 žingsnių.

Atsakymas

Iš klausimo matyti, kad pirminė dubenėlių rinkinio išdėstymo tvarka: 5 6 3 2 4 1.
Prisiminkime, kad gretimi dubenėliai vienas su kitu apkeičiami iš dešinės į kairę.

Dubenėliams praslinkus pro pirmąjį darbuotoją išsidėstymas toks: 1 5 6 3 2 4 (1-asis dubenėlis apkeistas 5 kartus).
Dubenėliams praslinkus pro antrąjį darbuotoją išsidėstymas toks: 1 2 5 6 3 4 (2-asis dubenėlis apkeistas 3 kartus).
Dubenėliams praslinkus pro trečiąjį darbuotoją išsidėstymas toks: 1 2 3 5 6 4 (3-iasis dubenėlis apkeistas 2 kartus).
Dubenėliams praslinkus pro ketvirtąjį darbuotoją išsidėstymas toks: 1 2 3 4 5 6 (4-asis dubenėlis apkeistas 2 kartus).

Interaktyvi užduotis

 

 
Informacija atnaujinta 2015-12-03 07:50:57