Работа с массивами и матрицами в языке программирования
© К. Поляков, 2009-2013
А12 (повышенный уровень, время – 5 мин)
Тема: Работа с массивами и матрицами в языке программирования1.
Что нужно знать:
работу цикла for (цикла с переменной)
массив – это набор однотипных элементов, имеющих общее имя и расположенных в памяти рядом
для обращения к элементу массива используют квадратные скобки, запись A[i] обозначает элемент массива A с номером (индексом) i
матрица (двухмерный массив) – это прямоугольная таблица однотипных элементов
если матрица имеет имя A, то обращение A[i,k] обозначает элемент, расположенный на пересечении строки i и столбца k
элементы, у которых номера строки и столбца совпадают, расположены на главной диагонали2
A[1,1]
A[2,2]
A[3,3]
A[4,4]
выше главной диагонали расположены элементы, у которых номер строки меньше номера столбца:
A[1,2]
A[1,3]
A[1,4]
A[2,3]
A[2,4]
A[3,4]
ниже главной диагонали расположены элементы, у которых номер строки больше номера столбца:
-
A[2,1]
A[3,1]
A[3,2]
A[4,1]
A[4,2]
A[4,3]
Ещё пример задания:
В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Ниже представлен фрагмент программы, записанный на разных языках программирования, в котором значения элементов сначала задаются, а затем меняются.
for i:=0 to 9 do
A[i]:=9-i;
for i:=0 to 4 do begin
k:=A[i];
A[i]:=A[9-i];
A[9-i]:=k;
end;
Чему будут равны элементы этого массива после выполнения фрагмента программы?
1) 9 8 7 6 5 4 3 2 1 0
2) 0 1 2 3 4 5 6 7 8 9
3) 9 8 7 6 5 5 6 7 8 9
4) 0 1 2 3 4 4 3 2 1 0
Решение:
выясним, как заполняется массив в первом цикле
for i:=0 to 9 do
A[i]:=9-i;
здесь элемент A[0] равен 9, элемент A[1]=8 и т.д. до A[9]=0
рассмотрим второй цикл, в котором операторы
k:=A[i];
A[i]:=A[9-i];
A[9-i]:=k;
меняют местами элементы A[i] и A[9-i]
второй цикл выполняется всего 5 раз, то есть останавливается ровно на половине массива
for i:=0 to 4 do begin
...
end;
таким образом в нем меняются элементы A[0]A]9], A[1]A]8], A[2]A]7], A[3]A]6] и A[4]A]5]
в результате массив оказывается «развернут» наоборот, элемент A[0] (он был равен 9) стал последним, следующий (A[1]=8) – предпоследним и т.д., то есть получили
0 1 2 3 4 5 6 7 8 9
Ответ: 2.
Ещё пример задания:
Дан фрагмент программы, обрабатывающей двухмерный массив A размера n×n.
k := 1;
for i:=1 to n do begin
c := A[i,i];
A[i,i] := A[k,i];
A[k,i] := c;
end
Представим массив в виде квадратной таблицы, в которой для элемента массива A[i,j] величина i является номером строки, а величина j – номером столбца, в котором расположен элемент. Тогда данный алгоритм меняет местами
1) два столбца в таблице
2) две строки в таблице
3) элементы диагонали и k-ой строки таблицы
4) элементы диагонали и k-го столбца таблицы
Решение:
сначала разберемся, что происходит внутри цикла; легко проверить (хотя бы ручной прокруткой, если вы сразу не узнали стандартный алгоритм), что операторы
c := A[i,i];
A[i,i] := A[k,i];
A[k,i] := c;
меняют местами значения A[i,i] и A[k,i], используя переменную c в качестве вспомогательной ячейки;
элемент матрицы A[i,i], у которого номера строки и столбца одинаковые, стоит на главной диагонали; элемент A[k,i] стоит в том же столбце i, но в строке с номером k; это значит, что в столбце i меняются местами элемент на главной диагонали и элемент в строке k
i
k
A[k,i]
i
A[i,i]
так как эти операторы находятся в цикле, где переменная i принимает последовательно все значения от 1 до n, обмен выполняется для всех столбцов матрицы; то есть, все элементы главной диагонали меняются с соответствующими элементами строки k
перед циклом стоит оператор присваивания k := 1;, а после него переменная k не меняется; поэтому в программе элементы главной диагонали обмениваются с первой строкой
таким образом, правильный ответ – 3.
-
Возможные ловушки и проблемы:
сложность этой задачи в том, что все действия нужно «прокручивать в уме» (или на бумаге), не используя компьютер для отладки
главная проблема – не перепутать столбцы и строки; номер строки – это (по соглашению) первый индекс элемента матрицы, а номер столбца – второй
-
Совет:
чтобы понять, что делает программа, часто бывает полезно сделать ручную прокрутку на матрице небольшого размера, например, 3 на 3 или 4 на 4.
если матрица небольшая (скажем, 5 на 5) можно (а иногда и нужно) вообще сделать все вычисления вручную и посмотреть, что получится
Еще пример задания:
Значения двух массивов A[1..100] и B[1..100] задаются с помощью следующего фрагмента программы:
for n:=1 to 100 do
A[n] := (n-80)*(n-80);
for n:=1 to 100 do
B[101-n] := A[n];
Какой элемент массива B будет наибольшим?
1) B[1] 2) B[21] 3) B[80] 4) B[100]
Решение:
здесь два цикла, в первом из них заполняется массив А, во втором – массив В
в элемент массива A[n] записывается квадрат числа n-80; все элементы массива А неотрицательны (как квадраты чисел)
посмотрим чему равны некоторые элементы массива А:
A[1] = (1–80)2 = (–79)2 = 792 A[2] = (2–80)2 = (–78)2 = 782
...
A[80] = (80–80)2 = (0)2 = 0 A[81] = (81–80)2 = (1)2 = 1
...
A[99] = (99–80)2 = 192 A[100] = (100–80)2 = 202
таким образом, при увеличении n от 1 до 80 значение A[n] уменьшается от 792 до нуля, а потом (для n > 80) возрастает до 202
отсюда следует, что максимальное значение в массиве A – это A[1] = 792
во втором цикле для всех номеров n от 1 до 100 выполняется оператор
B[101-n] := A[n];
который просто переписывает элементы массива A в массив В, «развертывая» массив в обратном порядке (элемент A[1] будет записан в B[100], а A[100] – в B[1])
A[1], наибольший элемент массива А, будет записан в B[100], поэтому B[100] – наибольший элемент в массиве В
таким образом, правильный ответ – 4.
Еще пример задания:
Значения элементов двухмерного массива A[1..10,1..10] задаются с помощью следующего фрагмента программы:
for i:=1 to 10 do
for k:=1 to 10 do
if i > k then
A[i,k] := 1
else A[i,k] := 0;
Чему равна сумма элементов массива после выполнения этого фрагмента программы?
1) 45 2) 50 3) 90 4) 100
Решение:
в программе есть вложенный цикл, в котором переменная i обозначает строку, а k – столбец матрицы
элементы, для которых i=k – это главная диагональ матрицы, поэтому элементы, для которых i > k (только они будут равны 1), находятся под главной диагональю
в первой строке единичных элементов нет, во второй есть один такой элемент, в третьей – 2, в последней (10-ой) их 9, поэтому сумма элементов массива равна
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
таким образом, правильный ответ – 1.
при большом размере массива (например, 100 на 100) суммирование может оказаться трудоемким, поэтому лучше вспомнить формулу для вычисления суммы элементов арифметической прогрессии (именно такая прогрессия у нас, с шагом 1):

где




если приведенная выше формула прочно забыта, можно попытаться сгруппировать слагаемые в пары с равной суммой (как сделал, будучи школьником, великий математик К.Ф. Гаусс), например:

Еще пример задания:
Значения элементов двухмерного массива A[1..10,1..10] сначала равны 5. Затем выполняется следующий фрагмент программы:
for i:=1 to 5 do
for j:=1 to 4 do begin
A[i,j]:=A[i,j]+5; { 1 }
A[j,i]:=A[j,i]+5; { 2 }
end;
Сколько элементов массива будут равны 10?
1) 8 2) 16 3) 24 4) 0
Решение (вариант 1, анализ алгоритма):
1
2
3
4
5
6
7
1
2
3
4
5
6
7
внутри цикла в операторе, отмеченном цифрой 1 в комментарии, в записи A[i,j] переменная i – это строка, а j – столбец, поэтому по одному разу обрабатываются все элементы массива, выделенные зеленым цветом:
1
2
3
4
5
6
7
1
2
3
4
5
6
7
теперь рассмотрим второй оператор внутри цикла: в записи A[j,i] переменная i – это столбец, а j – строка, поэтому по одному разу обрабатываются (увеличиваются на 5 ) все элементы массива, выделенные рамкой красного цвета на рисунке справа
теперь хорошо видно, что левый верхний угол массива (квадрат 4 на 4, синяя область) попадает в обе области, то есть, эти 16 элементов будут дважды увеличены на 5: они станут равны 15 после выполнения программы
элементы, попавшие в зеленый и красный «хвостики» обрабатываются (увеличиваются на 5) по одному разу, поэтому они-то и будут равны 10
всего таких элементов – 8 штук
таким образом, правильный ответ – 1.
Решение (вариант 2, прокрутка небольшого массива):
понятно, что в программе захватывается только левый верхний угол массива, остальные элементы не меняются
сократим размер циклов так, чтобы можно было легко выполнить программу вручную; при этом нужно сохранить важное свойство: внутренний цикл должен содержать на 1 шаг меньше, чем внешний:
for i:=1 to 3 do
for j:=1 to 2 do begin
A[i,j]:=A[i,j]+5; { 1 }
A[j,i]:=A[j,i]+5; { 2 }
end;
выполняя вручную этот вложенный цикл, получаем
1
2
3
4
5
1
15
15
10
5
5
2
15
15
10
5
5
3
10
10
5
5
5
4
5
5
5
5
5
5
5
5
5
5
5
видим, что в самом углу получился квадрат 2 на 2 (по количеству шагов внутреннего цикла), в котором все элементы равны 15; по сторонам этого квадрата стоят 4 элемента, равные 10, их количество равно удвоенной стороне квадрата
в исходном варианте внутренний цикл выполняется 4 раза, поэтому угловой квадрат будет иметь размер 4 на 4; тогда 8 элементов, граничащих с его сторонами, будут равны 10
таким образом, правильный ответ – 1.
-
Возможные проблемы:
упрощая задачу, нельзя потерять ее существенные свойства: например, здесь было важно, что внутренний цикл содержит на 1 шаг меньше, чем внешний
страница 1страница 2страница 3
скачать
Другие похожие работы: