Екі өлшемді массивтерді диагоналдарға қатысты өңдеу алгоритмдері
Екі өлшемді массивтерді өңдеудің типтік алгоритмдері. «Көбік» әдісімен сұрыптау
Екі өлшемді массивтерді өңдеуді шарты түрде мынадай үш топқа бөлуге болады:
- Массивті түгел өңдеу;
- Қатарлар бойынша немесе бағандар бойынша жекелей өңдеу;
- Диагоналдарға қатысты өңдеу.
Келтірілген топтардың әрқайсысын жеке қарастырайық.
Массивті түгел өңдеу
| 7.1-кесте | ||
| Типтік алгоритм | Бейсик тілінде | Паскаль тілінде |
| Толтыру (екі өлшемді массив элементтерін айналу тәртібі - солдан оңға қарай қатар бойынша) | …for i=1 to nfor j=1 to minput x(i,j)next jnext i | …for i:=1 to n dofor j:=1 to m do readln (x[i,j]);… |
| Шығару | …for i=1 to nfor j=1 to mprint x(i,j);" ";next jprint next i | …for i:=1 to n dobeginfor j:=1 to m dowrite (x[i,j], ' ');writeln;end; |
| Қосынды, көбейтінді | …p=1for i=1 to nfor j=1 to ms=s+x(i,j)p=p*x(i,j)next jnext i | …s:=0; p:=1;for i:=1 to n dofor j:=1 to m dobegins:=s+x[i,j];p:=p*x[i,j];end; |
| Максимум (минимум) элемент | …max=x(1,1)min=x(1,1)for i=1 to nfor j=1 to mif x(i,j)>max then max=x(i,j)if x(i,j)<min then min=x(i,j)next j,i | …max:=x[1,1];min:=x[1,1];for i:=1 to n dofor j:=1 to m dobeginif x[i,j]>max then max:=x[i,j];if x[i,j]<min then min:=x[i,j];end |
| Шарт бойынша таңдау (іздеу) | for i=1 to nfor j=1 to mif {шарт} then {оператор}next jnext i | …for i:=1 to n dofor j:=1 to m doif {шарт} then { оператор }… |
Массивті оның қатарлары бойынша өңдеу алгоритмдері:
| 7.2-кесте | ||
| Типтік алгоритм | Бейсик тілінде | Паскаль тілінде |
| Әр қатардағы элементтердің қосындысы | …for i=1 to nfor j=1 to ms(i)=s(i)+x(i,j)next jnext irem-----------for i=1 to nprint s(i);" ";next | …for i:=1 to n dos[i]:=0;for i:=1 to n dofor j:=1 to m dos[i]:=s[i]+x[i,j];for i:=1 to n dowrite (s[i]);… |
| Әр қатардағы элементтердің көбейтіндісі | for i=1 to np(i)=1nextrem---------for i=1 to nfor j=1 to mp(i)=p(i)*x(i,j)next jnext ifor i=1 to nprint p(i);" ";next | for i:=1 to n dop[i]:=1;for i:=1 to n dofor j:=1 to m dop[i]:=p[i]*x[i,j];for i:=1 to n dowrite (p[i]); |
| Әр қатардағы максимум (минимум) элемент | for i= 1 to nmax(i)=x(i,1)min(i)=x(i,1)nextfor i=1 to nfor j=1 to mif x(i,j)>max(i) then max(i)=x(i,j)if x(i,j)<min(i) then min(i)=x(i,j)next j,ifor i=1 to nprint max(i);" ";;nextprint for i=1 to nprint min(i);" ";;next | …for i:= 1 to n dobeginmax[i]:=x[i,1];min[i]:=x[i,1]; end;for i:=1 to n dofor j:=1 to m dobeginif x[i,j]>max[i] then max[i]:=x[i,j];if x[i,j]<min[i] then min[i]:=x[i,j]; end;for i:=1 to n dowrite (max[i]);writeln;for i:=1 to n dowrite (min[i]);… |
| Әр қатардағы шарт бойынша таңдау (іздеу) | …for i=1 to nfor j=1 to mif {шарт} then {rez(i)=…}next jnext ifor i=1 to nprint rez(i);" ";next | …for i:= 1 to n dobeginrez[i]:=0; end;for i:=1 to n dofor j:=1 to m doif {шарт} then < rez[i]:=… >;for i:=1 to n dowrite (rez[i]); |
Массивті оның бағандары бойынша өңдеу алгоритмдері:
| 7.3-кесте | ||
| Типтік алгоритм | Бейсик тілінде | Паскаль тілінде |
| Әр бағандағы элементтердің қосындысы | for j=1 to mfor i=1 to ns(j)=s(j)+x(i,j)next inext jfor j=1 to mprint s(j)next | …for j:=1 to m do s[j]:=0;for j:=1 to m dofor i:=1 to n dos[j]:=s[j]+x[i,j];for j:=1 to m do write (s[j]); |
| Әр бағандағы элементтердің көбейтіндісі | for j=1 to mp(j)=1nextfor j=1 to mfor i=1 to np(j)=p(j)*x(i,j)next inext jfor j=1 to mprint p(j)next | …for j:=1 to m do p[j]:=1;for j:=1 to m dofor i:=1 to n dop[j]:=p[j]*x[i,j];for j:=1 to m do write (p[j]);… |
| Әр бағандағы максимум (минимум) элемент | for j= 1 to mmax(j)=x(i,1)nextfor j=1 to mfor i=1 to nif x(i,j)>max(j) then max(j)=x(i,j)next i,jfor j=1 to mprint max(j);" ";next printfor j=1 to mprint min(j);" ";next | for j:= 1 to m dobeginmax[j]:=x[i,1];min[j]:=x[i,1]; end;for j:=1 to m dofor i:=1 to n dobeginif x[i,j]>max[j] then max[j]:=x[i,j]if x[i,j]<min[j] then min[j]:=x[i,j] end;for j:=1 to m dowrite (max[j]);writeln;for j:=1 to m dowrite (min[j]); |
| Әр бағандағы шарт бойынша таңдау (іздеу) | for j=1 to mfor i=1 to nif {усл.} then {rez(i)=…}next inext jfor j=1 to mprint rez(j);" ";next | …for j:= 1 to m dorez[j]:=0;for j:=1 to m dofor i:=1 to n doif {усл.} then {rez[i]:=…};for j:=1 to m dowrite (rez[j]); |
Екі өлшемді массивтерді диагоналдарға қатысты өңдеу алгоритмдері
Егер екі өлшемді массивте қатарлар мен бағандар саны бірдей болса, оны квадрат массив деп атайды. Квадрат массивтерге арналған тиіптік алгоритмдер оны диагоналдарға қатысты өңдеуге мүмкіндік береді. Қосымша диагонал элементтерінің индекстері 1-зертханалық жұмыстағы 1-ші тәуелділік бойынша оп-оңай анықталады (элемент қатарының нөмірі өседі, ал баған нөмірі кемиді).
Сурет 7.1-Квадрат массивтің диагоналдары
Бас диагонал. Келесі кестеде квадрат массивтің бас диагоналына қатысты типтік алгоритмдер келтірілген:
| 7.4-кесте | ||
| Типтік алгоритм | Бейсик тілінде | Паскаль тілінде |
| Бас диагоналдағы элементтер қосындысы | for i=1 to ns=s+x(i,i)next i | s:=0;for i:=1 to n dos:=s+x[i,i]; |
| Бас диагоналдан жоғары орналасқан элементтер қосындысы | …for i=1 to nfor j=1 to nif i<j then s=s+x(i,j)next j, i… | …s:=0;for i:=1 to n dofor j:=1 to n doif i<j then s:=s+x[i,j];… |
| Бас диагоналдан төмен орналасқан элементтер қосындысы | for i=1 to nfor j=1 to nif i>j then s=s+x(i,j)next j i | s:=0;for i:=1 to n dofor j:=1 to n doif i>j then s:=s+x[i,j]; |
Қосымша диагонал. Келесі кестеде квадрат массивтің қосымша диагоналына қатысты типтік алгоритмдер келтірілген:
| 7.5-кесте | ||
| Типтік алгоритм | Бейсик тілінде | Паскаль тілінде |
| Қосымша диагоналдағы элементтер қосындысы | for i=1 to ns=s+x(i, n-i+1)next i | s:=0;for i:=1 to n dos:=s+x[i, n-i+1]; |
| Қосымша диагоналдан жоғары орналасқан элементтер қосындысы | …for i=1 to nfor j=1 to nif (i<n-j+1) then s=s+x(i,j)next j, i | s:=0;for i:=1 to n dofor j:=1 to n doif (i<n-j+1) then s:=s+x[i,j]; |
| Қосымша диагоналдан төмен орналасқан элементтер қосындысы | for i=1 to nfor j=1 to nif (i>n-j+1) then s=s+x(i,j)next j, i | s:=0;for i:=1 to n dofor j:=1 to n doif (i>n-j+1) then s:=s+x[i,j]; |
Квадрат матрицаны диагоналдарға қатысты өңдеу (тиімді айналым)
Квадрат массивті оның диагодалдарына қатысты өңдеудің жоғарыда келтірілген алгоритмдері аса тиімді емес. Өйткені, оларда массивтің барлық элементтері қарастырылады. Элементтерді қарастыру санын азайту арқылы алгоритмнің тиімділігін едәуір арттыруға болады. Ол үшін ішкі циклдағы басқарушы айнымалының бастапқы немесе соңғы мәнінің сыртқы цикл есептеуішінің мәніне тәуелділігін ендіру керек.
Тиімді тәсілді пайдаланып квадрат матрицаларды диагоналдарына қатысты өңдеу алгоритм-деріне мысалдар келтірейік.
1-мысал. Квадрат массивтің элементтерін 1-лермен келесі суреттегідей етіп толтыру керек: