Ученици в редица/Олимпиада Л.Ойлер

[drago]

В едно кино, на един ред са седнали [tex]n[/tex] ученици. Седалките и учениците са номерирани от [tex]1[/tex] до [tex]n[/tex], като няма ученик, чийто номер да е същия, като седалката, на която седи. На всяка стъпка учителят може да разменя местата на двама съседни ученици, стига всеки от тях да седи на седалка с номер несъвпадащ с неговия.
Вярно ли е, че винаги е възможно, след известен брой размествания, учителят да подреди учениците, така че номерата им да съвпадат със седалките, където седят.

[pal702004]

Вярно е. Можем да "избутаме" най-големия елемент на последно място (метод на мехурчето) и да сведем задачата до [tex]n-1[/tex] елемента. Трудност можем да срещнем, само ако [tex]A_{max}[/tex] е на позиция [tex]j[/tex], а [tex]A_j[/tex] е на позиция [tex]j+1[/tex].

Код: Избери целия код

j    j+1   j+2
-----------------------
Amax Aj    Ak


Ако [tex]k\ne j+1[/tex], разменяме първо [tex]A_j\leftrightarrow A_k[/tex] и вече можем да избутаме [tex]A_{max}[/tex] с две позиции.
Ако [tex]k=j+1[/tex] избутваме наляво [tex]A_k[/tex], ако можем и т.н, а ако не можем до края, тоест ако до края са подредени [tex]A_t[/tex] на позиция [tex]t+1[/tex], можем спокойно да избутаме максималният елемент най-накрая - тогава всички тези ще си дойдат на мястото.

[pal702004]

Всъщност не е метод на мехурчето. По-скоро е пряка селекция, а реализацията на преместването на на-големият елемент - като при мехурчето...възможно най-тъпият метод за сортиране.

[inveidar]

Тъп, тъп ама метод!

[Гост]

Метод ама тъп.

[drago]

@pal702004: хубаво решение, благодаря!
...А какво общо има методът на мехурчето?... освен някаква визулана прилика ?
Бих искал да видя и друго решение- примерно някакв неконструктивно или с друга идея.
Ето и моето решение- същата идея и реализация, то и това е най-логичната идея, да избуташ някой, чието място е накрая, на мястото му и после пак, и пак,...
http://www.artofproblemsolving.com/Foru ... 2&t=589404

Всъщност, това е от турнира на градовете/а не олимпиада Ойлер, както съм написал/. Съжалявам, но не мога да го поправя! , такава е политиката на този сайт!! и между другото това състезание Ойлер, от което пуснах няколко задачи, не е руското със същото име.