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

жүктеу 1,28 Mb.

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

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

4 Тапсырма

Барлық

-элементтері жиындар мен жиын асты болып саналсын

.

Шешім.

нөлдер мен n ұзындық бірліктерінің әр жиынтығын реттілікпен ұсынамыз (ұсынудың басқа да түрін кешірек қарастырамыз).

Осындай реттіліктерді лексикографиялық түрде белгілейміз. (жоғарыда қар.) есепті шешудің тиімді түрі – барлық ауыстырылымдарды бұрынғыдай іріктеу болып келеді, ал сосын олардың арасынан

бірлігін таңдаймыз, ал қалғанын тиімді емес деп санаймыз (

бірліктерінің ауыстырылымдар саны басқа да ауыстырылымдар санынан төмен болуы мүмкін). Біз кезекті ауыстырылым алу үшін

қызметіндегі тәртібін талап ететін алгоритм іздестіру керек. Қандай жағдайда

- ауыстырылым мүшесін арттыру керек, алғашқыны ауыстырмағанда? Егерде

ден

ауысса, онда жалпы бірліктер санын сақтау үшін

оң жағынан

-ді

-ге ауыстыру керек. Сол үшін

бірліктер оң жағынан болу керек. Егер де біз келесі ретке көшсек, онда

нөл оң жақтан бірінші болу керек, одан кейін бірліктер тұру керек.

бірінші тұрғаның біз көріп тұрмыз (

бірінші емес екенін).

Сонымен

–дан

көпті іздестіру қажет.

–тен кейін бірнеше бірліктер тұруы мүмкін, ал одан кейін бірнеше нөлдер.

–ті 1-ге ауыстырғанда, одан кейін келе жатқан бірліктерді сақтау керек және де ол біздің тәртіп ретінен ең төмен реттілікте болу керек. Ең бірінші нөлдер ал сосын бірліктер тұру керек. Не шығатының көрейік:
бірінші реттілік 0...01...1 (n-k нөлдер, k бірліктер)

соңғы реттілік 1...10...0 (k бірліктер, n-k нөлдер)

х[1]...x[n] келесі реттілігінен алгоритмге көшу:

s := n - 1;while not ((x[s]=0) and (x[s+1]=1)) do begin

| s := s - 1;

end;

{s - мүше, 1-ден 0 –ге өзгертіуі мүмкін }

num:=0;

for k := s to n do begin

| num := num + x[k];

end;

{num – бірліктер саны x[s]...x[n], нөлдер саны

тең (ұзындық – бірліктер саны), яғни (n-s+1) - num}

x[s]:=1;

for k := s+1 to n-num+1 do begin

| x[k] := 0;

end;

{ num-1 бірлігін сонында орналыстыру керек}

for k := n-num+2 to n do begin

| x[k]:=1;

end;

Жиынтықты көрсетудің басқа да түрі – олардың элементтерін есептеу. Әр жиынтық бір ғана мағынасы болу керек, элементтерді өсу тәртібінде есептейік. Мынадай есепке келеміз.

Лексикографиялық тәртіпте

санынан

ұзындығының барлық өсу реттілігін атап шығу керек. (Мысалы:

болғанда аламыз 12 13 14 15 23 24 25 34 35 45.)

жүктеу 1,28 Mb.

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

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