ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 76263
Темы:    [ Одномерные массивы ]
[ Сортировка ]
Сложность: 2
Классы:
В корзину
Прислать комментарий

Условие

Та же задача, но требуется, чтобы сначала шли элементы, меньшие b, затем равные b, а лишь затем большие b.

Решение

Теперь потребуются три границы: до первой будут идти элементы, меньшие b, от первой до второй — равные b, затем неизвестно какие до третьей, а после третьей — большие b. (Более симметричное решение использовало бы четыре границы, но вряд ли игра стоит свеч.) В качестве очередного рассматриваемого элемента берём элемент справа от средней границы.

     l:=0; m:=0; r:=n;
     {инвариант: a[1..l]<b; a[l+1..m]=b; a[r+1]..a[n]>b}
     while m <> r do begin
     | if a[m+1]=b then begin
     | | m:=m+1;
     | end else if a[m+1]>b then begin
     | | ..обменять a[m+1] и a[r]
     | | r:=r-1;
     | end else begin {a[m+1]<b}
     | | ..обменять a[m+1] и a[l+1]
     | | l:=l+1; m:=m+1;
     | end;
     end;

Источники и прецеденты использования

книга
Автор А.Шень
Название Программирование: теоремы и задачи
Издательство МЦНМО
Издание второе
Год издания 2004
глава
Номер 1
Название Переменные, выражения, присваивания
параграф
Номер 2
Название Массивы
задача
Номер 1.2.32

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .