12.5.Еще пример задания

Значения элементов двухмерного массива 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. 	1	2	3	4	5	6	7
   1
   2
   3
   4
   5
   6
   7

   обратим внимание, что в двойном цикле переменная i изменяется от 1 до 5, а j – от 1 до 4 (на 1 шаг меньше)

2. внутри цикла в операторе, отмеченном цифрой 1 в комментарии, в записи A[i,j] переменная i – это строка, а j – столбец, поэтому по одному разу обрабатываются все элементы массива, выделенные зеленым цветом:

3. 	1	2	3	4	5	6	7
   1
   2
   3
   4
   5
   6
   7

   это значит, что если оставить только один первый оператор внутри цикла, все выделенные элементы увеличиваются на 5 и станут равны 10

4. теперь рассмотрим второй оператор внутри цикла: в записи A[j,i] переменная i – это столбец, а j – строка, поэтому по одному разу обрабатываются (увеличиваются на 5 ) все элементы массива, выделенные рамкой красного цвета на рисунке справа

5. теперь хорошо видно, что левый верхний угол массива (квадрат 4 на 4, синяя область) попадает в обе области, то есть, эти 16 элементов будут дважды увеличены на 5: они станут равны 15 после выполнения программы

6. элементы, попавшие в зеленый и красный «хвостики» обрабатываются (увеличиваются на 5) по одному разу, поэтому они-то и будут равны 10

7. всего таких элементов – 8 штук

8. таким образом, правильный ответ – 1.

Решение (вариант 2, прокрутка небольшого массива):

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. выполняя вручную этот вложенный цикл, получаем

   	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 на 2 (по количеству шагов внутреннего цикла), в котором все элементы равны 15; по сторонам этого квадрата стоят 4 элемента, равные 10, их количество равно удвоенной стороне квадрата

3. в исходном варианте внутренний цикл выполняется 4 раза, поэтому угловой квадрат будет иметь размер 4 на 4; тогда 8 элементов, граничащих с его сторонами, будут равны 10

4. таким образом, правильный ответ – 1.