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

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

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

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-кестедегі үлгі бойынша толтыру керек: