Кірістірілген матрицалар дісі

Екі лшемді масив элементтерін оу баыты (тртібі) иындыы аса жоары есептерді (мысалы, "Сиырлы шаршы" жне "Улама дастарханы" сияты есептерді) шешу кезінде олданылуы ммкін. "Улама дастарханы" есебін шешу барысында алдыы таырыптарда арастырылан «Эратосфен торы» алгоритмі олданылады. Жмыс рамындаы мысалдарды барлыында екі лшемді массивтерді деуді типтік алгоритмдері олданылады.

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

1-мысал. лшемдері NxN болатын квадрат матрицаны 8.1-суреттегідей етіп толтыру керек (натурал сандар матрица элементтерін оу ретін крсетеді):

Сурет 8.1-Квадрат матрицаны толтыру тртібі

Шешу идеясы: берілген матрицаны ойша трт ішкі ішкі матрицаа блеміз (8.2-сурет). Оларды райсысында осымша диагональды толтырамыз:

Сурет 8.2-Бастапы матрицаны ішкі матрицалара блу

Нтижесінде, k-ны мні 1-ден n-ге дейін згереді:

for k=1 to n for i=1 to k a (i,k-i+1)= … next inext k

Бейсиктегі бадарламасы: input "n="; ndim a(n,n)x=1for k=1 to n for i=1 to k a (i,k-i+1)= x x=x+1 next inext krem=========for i=1 to n for j=1 to n print a (i,j); next j printnext i

Паскальдаы бадарламасы: const m=10;var a: array [1..m, 1..m] of byte; x, n, k, i: integer;begin writeln ('n='); readln (n); x:=1; for k:=1 to n do for i:=1 to k do begin a [i,k-i+1]:=x; x:=x+1; end; for i:=1 to n do begin for j:=1 to n do write (a [i,j]); writeln; end;end.

2-мысал: Матрицаны 8.1-кестедегідей етіп толтыру керек.

8.1-кесте

Шешу идеясы: Берілген матрицаны «ойша» 8.3-суреттегідей етіп ішкі матрицалара блейік:

Сурет 8.3-Квадрат матрицаны ішкі матрицалара блу

Бейсикте:

Input "n="; nDim a(n,n)for k=1 to n\2+1 for i=k to n-k+1 for j=k to n-k+1 a (i,j)= k next j next inext krem=====шыару======for i=1 to n for j=1 to n print a (i,j); next j printnext i

Паскальда:

const m=10;var a: array [1..m, 1..m] of byte; x, n, k, I, j: integer;begin writeln ('n='); readln (n); for k:=1 to (n div 2 +1) do for i:=k to n-k+1 do for j:=k to n-k+1 do a [i,j]:= k; {=======шыару=========} for i:=1 to n do begin for j:=1 to n do write (a [i,j]); writeln; end;end.

3-мысал. Матрицаны 8.2-кестедегідей етіп толтыру керек.

8.2-кесте

осымша мліметтер: Массивті осылай толтырылуы «Улама дастарханы» деп аталатын есепті сипаттайды. Бл есепте квадрат матрица спираль бойымен толтырылады (толтыру ішінен сырта арай орындалады). Сонан со барлы рама сандар «сызып тасталады» («Эратосфен торы» есебіндегі сияты). з орнында алан жай сандар «Улама дастарханы» деп аталатын ерекше рнекті кескіндейді.

Шешу идеясы: Берілген квадрат матрицаны ішкі матрицалара бліп, оларды периметрі бойынша толтырамыз (8.4-сурет).

Сурет 8.4-Квадрат матрицаны ішкі матрицаа бліп, толтыру

Бейсикте:

input "n="; ndim a (n,n)x=1for k=1 to n\2 for i=k to n-k a(k,i)=x x=x+1 next rem============= for i=k to n-k a(i,n-k+1)=x x=x+1 next rem=============for i=k to n-k a(n-k+1,n-i+1)=x x=x+1 next rem=============for i=k to n-k a(n-i+1,k)=x x=x+1 next inext krem=================for i=1 to n for j=1 to n print a(i,j); next j printnext i

Паскальда:

const m=10;var a: array [1..m, 1..m] of byte; x, n, k, i, j: integer;begin writeln ('n='); readln (n); x:=1; for k:=1 to n div 2 do begin for i:=k to n-k do begin a [k,i]:=x; x:=x+1; end; for i:=k to n-k do begin a [i,n-k+1]:=x; x:=x+1; end for i:=k to n-k do begin a [n-k+1,n-i+1]:=x; x:=x+1; end ; for i:=k to n-k do begin a [n-i+1,k]:=x; x:=x+1; end; end; {=======вывод========} for i:=1 to n do begin for j:=1 to n do write (a[i,j]); writeln; end;end.

4-мысал. Квадрат матрицаны 8.5-суреттегідей етіп толтыру керек.

Сурет 8.5

осымша мліметтер: Информатикада «сиырлы шаршы» деп аталатын классикалы есеп бар («Сиырлы шаршы»-да барлы атарларды, барлы баандарды жне барлы диагоналдарды элементтеріні осындысы зара те болады). Бл есепті трлі тсілдермен шешуге болады. Оларды бірі – «Террас» деп аталатын діс. n х n (n – та сан) лшемді сиырлы шаршы ру шін (2n-1)x(2n-1) лшемді квадрат матрицаны 8.6-суреттегідей етіп толтыру керек:

Сурет 8.6

Сонан со 8.6-муреттегі белгіленген тіктртбрышты сыртындаы «шбрыштарды» тік тртбрыш ішіне 8.3-кестедегідей етіп ауыстырамыз:

8.3-кесте

Алынан матрицадаы барлы атарлардаы жне баандардаы элементтерді осындысы те болады.

Шешу идеясы: Бастапы матрицаны ішкі матрицалара блеміз. рбір ішкі матрицада осымша диагональды толтырамыз:

Сурет 8.7

Шешімі тсінікті. Бадарламасын здері рып крідер.

Кілттік сздер

· «Сиырлы шаршы» - барлы атарларыны, барлы баандарыны жне барлы диагоналдарыны элементтеріні осындысы зара те болатын матрица.

«Террас» дісі – сиырлы шаршыны ру дісі
Эратосфен торы – жай сандарды табу алгоритмі

· Улама дастарханы – жай сандар спираль бойымен толтырылатын квадрат матрица.

Вопросы

· Екі лшемді массивті натурал сандар атырымен алай толыруа болады?

Сырты цикл есептеуіші екі лшемді массивті бірінші индексі ретінде, ал ішкі цикл есептеуіші – екінші индексі ретінде лданылса, онда матрицаны элементтерін оу андай тртіппен іске асырылады? Ал, керісінше бола ше?

Тапсырмалар

· Екі лшемді массивті 8.4-кестедегі лгі бойынша толтыру керек:

8.4-кесте




т.с.с.	...	...	...	...	...	...

· Екі лшемді массивті 8.5-кестедегі лгі бойынша толтыру керек::

8.5-кесте

· Екі лшемді массивті 8.6-кестедегі лгі бойынша толтыру керек::

8.6-кесте