Условие
Дан массив
a[1..n] и число
b. Переставить числа
в массиве таким образом, чтобы слева от некоторой границы
стояли числа, меньшие или равные
b, а справа от
границы — большие или равные
b. Число действий
порядка
n.
Решение
l:=0; r:=n;
{инвариант: a[1]..a[l]<=b; a[r+1]..a[n]>=b}
while l <> r do begin
| if a[l+1] <= b then begin
| | l:=l+1;
| end else if a[r] >=b then begin
| | r:=r-1;
| end else begin {a[l+1]>b; a[r]<b}
| | ..поменять a[l+1] и a[r]
| | l:=l+1; r:=r-1;
| end;
end;
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
2 |
|
Название |
Массивы |
|
задача |
|
Номер |
1.2.31 |
