Екі лшемді массивтерді диагоналдара атысты деу алгоритмдері
Екі лшемді массивтерді деуді типтік алгоритмдері. «Кбік» дісімен срыптау
Екі лшемді массивтерді деуді шарты трде мынадай ш топа блуге болады:
- Массивті тгел деу;
- атарлар бойынша немесе баандар бойынша жекелей деу;
- Диагоналдара атысты деу.
Келтірілген топтарды райсысын жеке арастырайы.
Массивті тгел деу
| 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-лермен келесі суреттегідей етіп толтыру керек: