Стандартные приёмы программирования

42

Стадарные приемы программирования.

Урок 3. Переработка массивов на месте

Сравните свои решения подготовительных задач к этому уроку (см. «Квант» № 11, Урок 2) с приведенными здесь. Варианты a) — это правильные решения, варианты b) — это типичные ошибки (программы не дают желаемого результата), варианты θ) работать будут, и все же их нельзя признать приемыми.

Так же, как на прошлом уроке, давайте посмотрим, что общего в условиях задач.

Главным общим моментом является то, что результат должен получаться на том же месте, где находится исходные данные. Тепер посмотрит на расчетные формулы в условиях задач (читатель простит употребление программыского знака «присваивание» вместе математического знака «равно», оно здесь естественно) и сравните расчетные формулы с решениями б); эти решения — «дословные» переводы формулы на языке программирования. Мы столкнулись с той же проблемой, что и на прошых уроках: разницы в правильах разговора на языке математики и языке программирования.

Когда математик пишет формулу трансопроизводия матрицы, то есть отражения ее элементов относительно диагонали (для всех i, j a’ij := aji) он, по видимому, имеет в виду, что по команде «Алле-оп!» все элементы матрицы разом подпрыгнут вверх и тут же все разом опустятся на свои места, но уже с измененными значениями. Но ЭВМ не может делать все сразу*, процесс обработки данных производит в пространстве и во времени: сначала обрабатывается один элемент, затем друг и т. д. И к тому времени, когда начинается обработка i-го элемента, для которого нужно строение k-го элемента, k-й элемент

*) Некоторые современные ЭВМ уже научились и этоomy, но в языке пакель также возможности не отражены.

Решения подготовительных задач

a) Задание 1 (среднее арифметическое и среднее геометрическое)
for i:=1 to n do
begin d:=a[i];
a[i] := (a[i] + b[i])/2;
b[i] := sqrt(db[i])
end;
Более быстрый вариант:
for i:=1 to n do
begin ai:=a[i]; bi:=b[i];
a[i] := (ai+bi)/2;
b[i] := sqrt(aibi)
end;

b) Задание 2 (деление на диагональной элемент)
for i:=1 to n do
begin d:=a[i,i];
for j:=1 to n do
a[i,j] := a[i,j]/d;
end;

Задание 3 (транспроизводение)
for i:=1 to n-1 do
for j:=i+1 to n do
begin d:=a[i,j];
a[i,j] := a[j,i];
a[j,i] := d
end;

for i:=1 to n do
for j:=1 to n do
a[i,j] := a[j,i];
второе решение:
for i:=1 to n do
for j:=1 to n do
begin d:=a[i,j];
a[i,j] := a[j,i];
a[j,i] := d
end;

43

уже может успешить новое значение. Аналогично, мы привыкли, что математический фразу «для всех $i$ при $i \in M$» мы переводим на язык программирования циклом с параметром $i$, пробегающим множество $M$. Чаще всего этот перевод правильный, но бывают и исключания, одним из которых часто является переработка массивов на месте. Посмотрите на второе решение $6$) задачи 3 и попробуйте понять, что сделает программа и почему в результате ее работы матрица останется в неизменном виде.

Итак, стало понятно, что если один из элементов переработываемого на месте массива нужен для вычисления нового значения другого элемента, то его надо как-то сохранить. Простейшее решение — снять копию с исходного массива и записать результат в другой место — на практике часто не годится. Программиру задачу больших размеров (или задачу не очень больших размеров, но на ЭВМ с небольшой памяти), вы можете столкнуться с ситуацией, когда массив занимает почти всю память и на копию просто нет места. В этом и заключается недостаток вариантов $b$): при больших размерах массивов программе не хватит памяти. Однако, как показывают варианты $a$), необходимо в копировании массива нет: в полне можно обойти одним дополнительным элементом (в программах — это переменная с именем $d$) для сохранения значения, необходимого для вычисления нескольких новых значений.

Теперь можно сделать окончательные выводы.

$\theta)$
for $i:=1$ to $n$ do
begin $c[i]:=a[i]$;
$a[i]:=(a[i]+b[i])/2$;
$b[i]:=sqrt(c[i]*b[i])$
end;

for $i:=1$ to $n$ do
begin $d[i]:=a[i,i]$;
for $j:=1$ to $n$ do
$a[i,j]:=a[i,j]/d[i]$;
end;

for $i:=1$ to $n$ do
for $j:=1$ to $n$ do
$c[j,i]:=a[i,j]$;
for $i:=1$ to $n$ do
for $j:=1$ to $n$ do
$a[i,j]:=c[i,j]$;

1. При переработке массивов на месте необходимо приниматьеры к сохранению значений элементов, нужных при последующих вычислениях. Как правило, для этого достаточно ОДНОГО вспомогательного элемента.

В крайнем случае, когда одного элемента явно мало, можно взять массив меньше размерности (например, одномерный массив вместе матрицы). Разумеется, былоют случаи, когда массив на месте обработать нельзя, и тогда приходим к копию.

2. Если элементы обработываются не в порядке их расположения в массиве, то циклы перебор элементов массива следует организовать специальным образом.

Например, в задаче 3 одновременно обработываются пары элементов, симметричные относительно диагонали, поэтому организация цикла отличается от «дословного» перевода математической формулы.

Посмотрим теперь, почему начинающие программы не видят ошибки в вариантах — это переменная с именем $d$) для сохранения значения, необходимого для вычисления нескольких новых значений.

Проверим, например, вариант $b$) задачи 1. Для этого возьмем небольшие массивы, скажем $a=(2,3,4)$, $b=(5,6,7)$, и прокрутим программу $n=3$, $i=1$, $a[1]=(2+5)/2=3,5$, $b[1]=\sqrt{2\cdot5}=\sqrt{10}$ и т. д. Это и есть та самая типичная ошибка: мы сделали то, что сами хотим от ЭВМ, а не то, что сделает ЭВМ на самом деле!

Правильная прокрутка выполняется так: а) выписывает таблица всех действующих в проверяемом формате и идентификаторов и их значений, б) на каждом шаге старое значение зачеркивается и заменяется новым.

Прокрутим tot же пример:

$$\begin{array}{c} n \\ 3 \\ a_1=(a_1+b_1)/2=3.5 \\ 1 \\ 3.5 \\ b_1=\sqrt{a_1b_1}=\sqrt{(3.5)\times5}=\sqrt{17.5} \\ (2,3,4) \\ b(5,6,7) \end{array}$$

Ошибка стала видна на первом же шаге.

И, наконец, последний вопрос: не ухудшается ли программа по скорости при