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

жүктеу 1,28 Mb.

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

1 ... 10 11 12 13 14 15 16 17 ... 38

3 Тапсырма

саннын барлық орын ауыстырымдарын басыңыз (

ұзындылығының реттілігін, оған 1 санының әр қайсысы бір рет кіреді).

Шешім. Өзгертулерді массиве

массивінде сақтаймыз және лексикографикалық тәртіпте тереміз. (

ауыстырылымы бірінші, ал

соңғы болады). Келесі ауыстырылымға көшуде алгоритмі құрастыруда сұрақ туындайды: қай жағдайда алдағыларды өзгертпегенде

ауыстырылымын арттыруға болады ма? Жауабы: егер де келесі мүшелерден аз болса (

нөмірлері бар мүшелер көп). Біз көбірек

–ны анықтауымыз керек. Ол

. Одан кейін

ең төменгі мүмкіндікпен арттыру керек.

арасынан, ...,

–ден көп ең төменгі санды табу керек.

- пен ауыстырғанда, сандарды

нөмірлермен орналастырамыз, ...,

ауыстырылым ең төмен болу керек, яғни өсу тәртібінде.

Келесі ауысымға көшу алгоритмы.

{ <> }
k:=n-1;
{ x[k+1] >...> x[n]}төмендегі,k оң жақтағы реттілік
while x[k] > x[k+1] do begin
| k:=k-1;
end;
{x[k] < x[k+1] > ... > x[n]}
t:=k+1;
{t <=n, кесіндінің барлық мүшелері x[k+1] > ... > x[t] көп x[k]}
while (t < n) and (x[t+1] > x[k]) do begin
| t:=t+1;
end;
{x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]}
... x[k] и x[t] ауыстыру
{x[k+1] > ... > x[n]}
... x[k+1] ... x[n] кері тәртіпте орналастыру
Ескерту. Бағдарламада бізге таныс дефект бар: егер

, онда

анықталмаған.

Келесі ауыстырылымға модифицирланған алгоритмды көшіруде, ол өзі аталған ауыстырылым ақырғы емес екенін тексеріп отыру керек.

жүктеу 1,28 Mb.

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

1 ... 10 11 12 13 14 15 16 17 ... 38