Зертханалық жұмыс

жүктеу 1,28 Mb.

бет	23/38
Дата	23.01.2020
өлшемі	1,28 Mb.
	#27192

1 ... 19 20 21 22 23 24 25 26 ... 38

Біз

- реттелген масссивті

- реттелген массивке қалай түрлендіруге болатының көрсетейік (сол элементтерден сияқты). Бұл түрлендіру нәтижесінде алгоритм былай жазылады:
k:=1;
{x массиві k- реттелген болып келеді}
while k < n do begin
| .. k- реттелген массивті 2k-реттелген массивке түрлендіру керек;
| k := 2 * k;
end;
Талап ететін түрлендіру, біз бірнеше рет екі реттелген кесінді ұзындығын

көп рет бір реттелген кесіндіге "тұтастырамыз".

Біріктіру процедурасы

при

кесінділерді біріктірейік

реттелген кесіндіге

(

массивтін басқа бөліктеріне тиіспей).

Ендеше

- реттелген массивті

-реттелген массивке түрлендіру төмендегідей жүзеге асады:

t:=0;
{t қысқаша 2k немесе t = n, x[1]..x[t] болып келеді

2k-реттелген; x массивтін қалдығы өзгермейді}
while t + k < n do begin
| p := t;
| q := t+k;
| ...r := min (t+2*k, n); {min(a,b) - a немесе b минимумы}
| бірігу (p,q,r);
| t := r;
end;
Бірігу – бірігу нәтижесін жазу үшін көмекші массивті қажет етеді, оларды

деп белгілейік.

немесе

арқылы соңғы элементтер жерінің нөмірлерін (бірігуге қауіпі бар),

– соңғы массивке жазылған

элементі. Бірігуде әр қадам сайын екі әрекеттін орнына біреу ғана жасалады істін:
b[s0+1]:=x[p0+1];
p0:=p0+1;
s0:=s0+1;

немесе
b[s0+1]:=x[q0+1];

q0:=q0+1;
s0:=s0+1;

(C тілін жақсы көретіндер

қысқартуын бағалайды немесе

Бірінші әрекет (элементті бірінші кесіндіден алу) бір уақытта екі әрекетті орындағанда шығуы мүмкін:

бірінші кесінді аяқталған жоқ ();
екінші кесінді аяқталды () немесе аяқталған жоқ, бірақта оның ішінде элемент аз болады (екінші кесіндіге қарағанда) и

Екінші әрекет үшін ұқсас. Сонымен мынаны аламыз

p0 := p; q0 := q; s0 := p;
while (p0 <> q) or (q0 <> r) do begin
| if (p0 < q) and ((q0 = r) or ((q0 < r) and
| | (x[p0+1] <= x[q0+1]))) then begin
| | b [s0+1] := x [p0+1];
| | p0 := p0+1;
| | s0 := s0+1;
| end else begin
| | {(q0 <| | (x[p0+1] > r) and ((p0 = q) or ((p0= x[q0+1])))}
| | b [s0+1] := x [q0+1];
| | q0 := q0 + 1;
| | s0 := s0 + 1;
| end;
end;
(Егерде екі кесінді аяқталмаған болса онда таңдалмаған бірінші элементтері тең болып келеді, бұл жағдайда екі әрекетті де қабылдаймыз; бағдарламада біріншісі таңдалған.)

Бірігу нәтижесін қайтадан

– ке жазу керек. (алдын ала ескерту). Егерде кері көбейту бірігу процедурасынан тыс жасалса, онда соңғы кесіндіні жазуға ұмытпаңыз.)

Бағдарлама біріншілік кемшілігі бар: бульдік өрнекті есептеу элементтін жоқ массивтеріне ұсыңылады.

Екінші шешімді өздігінен тап.

жүктеу 1,28 Mb.

Достарыңызбен бөлісу:

1 ... 19 20 21 22 23 24 25 26 ... 38