Бақылау сұрақтары. Жаттығулар NxM өлшемді матрицаның әр қатарындағы минимум элементтердің ең үлкенін және

• Екі өлшемді массивті өңдеу алгоритмінде i және j циклдік параметрлерінің орнын ауыстырса не болады?
• Бас диагоналдағы элементтердің индекстерінің тәуелділігі қандай? Қосымша диагоналда ше?

Жаттығулар

• NxM өлшемді матрицаның әр қатарындағы минимум элементтердің ең үлкенін және әр бағанындағы максимум элементтердің ең кішісін табу керек.
• 7.2-суретте көрсетілгендей етіп квадрат матрицаларды толтырыңдар:

Сурет 7.2 – Квадрат матрицаларды толтыруға тапсырмалар

 

Көбік» әдісімен сұрыптау

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

 

Жұмыс мақсаты: танысқан типтік алгоритмдері қолдану арқылы классикалық есептерді шығару.

 

Сұрыптауды берілген массив элементтерін өсу реті бойынша сұрыптау арқылы қарастырамыз. Мысалы, 5, 8, 4, 9, 3 массивін сұрыптайық:

Сурет 4.1- «Көбікті» сұрыптау

 

Паскальда программаны орындау:	C/C++-те программаны орындау:
for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:= a[i+1]; a[i+1]:=x; end;	for (j=n; j>=2; j--) for (i=1; i<=j-1; i++) if (a[i]>a[i+1]) { x=a[i]; a[i]=a[i+1]; a[i+1]=x; }

Сұрыптау әдістерін қолдануға мысалдар

Мысал. Кез-келген сандар қатары берілген. Олардың арасына "<" және ">" символдарын қою арқылы ретімен орналастыру керек («ара тәріздес» тізбек).

Есепті шешу идеясы: Алдымен сандар қатарын сұрыптап алып, сосын бірінші элементтен бастап әрбір жұптың орнын ауыстырамыз.

var a: array [1..100] of integer; i,j,n,x:integer;begin writeln ('элементтер саны: '); readln (n); for i:= 1 to n do begin writeln ('a[',i,']='); readln (a[i]); end; {=====сұрыптау==========} for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:= a[i+1]; a[i+1]:=x; end; for i:=1 to 5 do write(a[i]:3); writeln; j:=1; {====әрбір жұптың орындарын ауыстырамыз====} for i:=1 to (n div 2) do {тек циклдың қайталану санын анықтайды} begin x:=a[j]; a[j]:= a[j+1]; a[j+1]:=x; j:=j+2; end; for i:=1 to n do write(a[i]:4);end.

Тест:

Берілгені:	5, 2, 1, 8, 0, 67, 100
Сұрыпталғаны:	0, 1, 2, 5, 8, 67, 100
Нәтижесі:	0, 2, 1, 8, 5, 100, 67

2-мысал. Сандар тізбегінен қатар келген сандардың ішкі тізбегін анықтау керек.

Есепті шешу идеясы: сандар қатарын сұрыптаймыз. Массив элементтерін екі көрші элементті салыстыра отырып өңдейміз: егер олардың айырмашылығы бірге тең болмаса, онда экранға жаңа тізбекті шығарып бастаймыз.

var a: array [1..100] of integer; i,j,n,x: integer;begin writeln ('элементтер саны:'); readln (n); for i:= 1 to n do begin write('a[',i,']=');readln (a[i]); end; {===== массивті сұрыптау=============} for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i:= a[i+1]; a[i+1]:=x; end; {===қатар орналасқан тізбектерді шығару===} write (a[1]); for i:= 2 to n do begin if (a[i]-a[i-1]) <> 1 then writeln; write (a[i]:3); end;end.

Тест:

Берілгені:	N=10 2, 1, 5, 3, 7, 8, 6, 12, 9, 11
Нәтижесі:	1, 2, 3 5, 6, 7, 8, 9 11, 12

3-мысал. Сандар тізбегіндегі қатар келген сандардың ең ұзын тізбегін тауып, оларды шығару керек.

Есепті шешу идеясы: Сандар қатарын сұрыптаймыз. Екі көрші элементті салыстыра отырып, массивті өңдейміз: егер олардың айырмасы 1-ге тең болса, онда келесі сан осы тізбекке қосылады. k шамасы арқылы оның ұзындығын анықтаймыз. Максимум элементті табудың типтік алгоритмін қолданып, ең ұзын тізбекті анықтаймыз.

var a: array [1..10] of integer; max,k,number,i,j,n,x: integer;begin writeln ('элементтер саны:'); readln (n); for i:= 1 to n do begin write('a[',i,']='); readln (a[i]); end; {=====массивті сұрыптау================} for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:= a[i+1]; a[i+1]:=x; end; {===ең ұзын тізбекті анықтау===} max:=0; k:=1; for i:=1 to n-1 do begin if a[i+1]-a[i]=1 then k:=k+1 else k:=1; if k>max then begin max:=k; number:=i+1; end; end; writeln('Ең ұзын тізбек элементтерінің саны=', max); writeln('Ең ұзын тізбек:'); for i:=(number-max+1) to number do write(a[i]:3);end.

Тест:

Берілгені:	N=10 2, 1, 5, 3, 7, 8, 6, 12, 9, 11
Нәтижесі:	Max=5 5, 6, 7, 8,9

4-мысал: Берілген сөйлемдегі сөздердің орнын ондағы әріп санының өсу ретімен ауыстыру керек.

Есепті шешу идеясы: Сөйлемдегі сөздерді бөліп алудың типтік алгоритімін қолданып, әрбір сөзді массив элементіне орналастырып жазамыз. Сонан соң, сөздер массивін ондағы сөздің ұзындығы бойынша сұрыптаймыз.

var b:array[1..10] of string; a,a1,a2,x: string; n,i,j,k: integer;begin writeln ('Сөйлемді ендір:'); readln (a); n:=length (a); k:=0; for i:=1 to n do if copy(a,i,1)=' ' then k:=k+1; k:=k+1; j:=1; for i:=1 to n do if copy(a,i,1)=' ' then j:=j+1 else b[j]:=b[j]+copy(a,i,1); {===== массивті сұрыптау ==============} for j:=k downto 2 do for i:=1 to j-1 do if length (b[i])>length (b[i+1]) then begin x:=b[i]; b[i]:= b[i+1]; b[i+1]:=x; end; { ==============================} for i:=1 to k do writeln (b[i]);end.

Тест:

Берілгені:	Менің сүйікті пәнім - информатика
Нәтижесі:	- Менің пәнім сүйікті информатика

Сұрыптау есептерінің ішінде массив элементтерінің бір бөлігін өсу ретімен және екінші бөлігін кему ретімен сұрыптау қажеттілігі жиі кездеседі.

Мысал. Массив бөліктерін сұрыптау керек. Оң және теріс элементтері бар А массиві берілсін делік (4.2-сурет). Массивтің оң элементтері өсу реті бойынша сұрыпталып, ал теріс элементтерін өз орнында қалдыру керек.

Сурет 4.2

 

Есепті шешу идеясы:

· Қосымша В массивін енгіземіз және оған А массивіндегі оң элементтерді жазамыз (4.3-сурет):

В

Сурет 4.3

Содан соң массивті өңдеудің типтік алгоритімін қолдану арқылы, A массивінің элементтерінің индексі ретінде В массивінің элементтерін қолданамыз. Бұл есептің шығарылуын бөлек типтік алгоритм ретінде қарастыруға болады.

const m=10;var a, b: array [1..m] of integer; i, j, n, x, k: integer;begin writeln('Элементтер саны:'); readln(n); for i:=1 to n do begin write('a[',i,']='); readln(a[i]); end; j:=1; k:=0; for i:=1 to n do if a[i]>0 then begin b[j]:=i; j:=j+1; k:=k+1; end; for j:=k downto 2 do for i:=1 to j-1 do if a[b[i]]>a[b[i+1]] then begin x:=a[b[i]]; a[b[i]]:=a[b[i+1]]; a[b[i+1]]:=x; end; for i:=1 to n do write (a[i],' ');end.

Тест:

Берілгені:	N=9 -3, 5, -1, 3, 6, -8, 2, -1, -3
Нәтижесі:	-3, 2, -1, 3, 5, -8, 6, -1, -3

Орытынды

· Біртекті массивтерді сұрыптаудың «Көбікті» әдісі екі көрші элементті салыстыруға негізделген: егер үлкен элемен кішісінің сол жағында болса, онда элементтердің орындары ауыстырылады. Массив элементінің ең үлкені массивтің ең соңына орналасады. Әрі қарай алгоритм бірінші элементтен соңғы элементке дейін қайталанады.

· Массивтің бөліктерін сұрыптауда (Сұрыптаудың шарттары бойынша массив бөліктерін таңдаймыз) сұрыпталатын индекстер ретінде А массивіндегі элементтерді және қосымша В массивіндегі элементтерді аламыз (онда таңдалатын массивтің бастапқы элементтері сақталады).

Сұрақтар.

· «Көбікті» сұрыптаудың бірінші қадамында не болады?

· «Көбікті» сұрыптау әдісіндегі ішкі циклдың санауын сыртқы циклдың санауына тәуелділігін анықтаңдар?

Тапсырмалар

· Символды жол сандардан және латын әріптерінен тұрады. Олардың әрқайсысы өз орнында қалатындай етіп сандарды кему реті бойынша, әріптерді алфавиттік тәртіп бойынша реттеу керек.

· Натурал сандардан тұратын массив берілген, ондағы жай сандарды өсу ретімен, ал құрама сандарды кему ретімен сұрыптау керек.

· Сөйлемдегі дауысты дыбыстарды алфавит тәртіппен өсу реті бойынша, ал дауыссыз дыбыстарды кему реті бойынша орналастыру керек.

· Сөйлемдегі сөздердің орнын алфавиттік тәртіппен (әрбір сөздегі бірінші әріп бойынша) орналастыру қажет.