Бақылау сұрақтары. Жаттығулар 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 |
Орытынды
· Біртекті массивтерді сұрыптаудың «Көбікті» әдісі екі көрші элементті салыстыруға негізделген: егер үлкен элемен кішісінің сол жағында болса, онда элементтердің орындары ауыстырылады. Массив элементінің ең үлкені массивтің ең соңына орналасады. Әрі қарай алгоритм бірінші элементтен соңғы элементке дейін қайталанады.
· Массивтің бөліктерін сұрыптауда (Сұрыптаудың шарттары бойынша массив бөліктерін таңдаймыз) сұрыпталатын индекстер ретінде А массивіндегі элементтерді және қосымша В массивіндегі элементтерді аламыз ( онда таңдалатын массивтің бастапқы элементтері сақталады).
Сұрақтар.
· «Көбікті» сұрыптаудың бірінші қадамында не болады?
· «Көбікті» сұрыптау әдісіндегі ішкі циклдың санауын сыртқы циклдың санауына тәуелділігін анықтаңдар?
Тапсырмалар
· Символды жол сандардан және латын әріптерінен тұрады. Олардың әрқайсысы өз орнында қалатындай етіп сандарды кему реті бойынша, әріптерді алфавиттік тәртіп бойынша реттеу керек.
· Натурал сандардан тұратын массив берілген, ондағы жай сандарды өсу ретімен, ал құрама сандарды кему ретімен сұрыптау керек.
· Сөйлемдегі дауысты дыбыстарды алфавит тәртіппен өсу реті бойынша, ал дауыссыз дыбыстарды кему реті бойынша орналастыру керек.
· Сөйлемдегі сөздердің орнын алфавиттік тәртіппен (әрбір сөздегі бірінші әріп бойынша) орналастыру қажет.