Дан массив a[1..n] и число b. Переставить  числа  в массиве  таким  образом, чтобы слева от некоторой границы стояли числа, меньшие или равные b, а справа от границы -  большие  или
равные b.

Решение.

        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;


2009-12-04 • Просмотров [ 978 ]