50
Стадартные приемы программирования
Урок 4. Синхронная и асинхронная обработка массивов
Если вам не удалось найти общность и различия в условиях задач, попробуйте ответить на вопрос: с какими элементами массивов будет идти работа, скажем, на 5-м шаге работы алгоритма (шагом считаем обработку одного элемента в любом массиве)? В 3-й и 4-й задаче ответ на этот вопрос прост: на 5-м шаге обработываются 5-e элементы в массивах A и B (3-я задача), 5-й элемент в массиве B и 10-й элемент в массиве A (4-я задача). Что же касается первых двух задач, то на 5-м шаге обработывается 5-й элемент того массива, по которым мы отсчитываем шаги, но про другие массивы мы ничего сказаить не можем (за исключением того, что обработывается элемент с большим, чем в данном массиве, или меньшим номером). Это и есть ключевой момент: в задачах 3 и 4 массивы обработываются синхронно (то есть имеется явная, аналогическая связь между номерами обработываемых элементов в разных массивах; в задачах 1 и 2 между номерами обработываемых элементов в каждой паре массивов нельзя указать связь, не зависящую от конкретных массивов, которое можно выразить формулой, связывающей только эти номера и какие-тоCONSTANTЫ. Поэтому можно сказать, что в задачах 1 и 2 массивы обработываются синхронно,
Теперь рассмотрим приведенные решения. Все решения правильны, но не все одинаково хорошего. Задание 3 и 4, по-видимому, не вызывали трудности, однокретию, однокретию и легкости его понимания. Поскольку в задачах 3 и 4 массивы обработываются синхронно,
достаточно иметь один индекс для обработки всех синхронно обработываемых массивов.
В 1-й и 2-й задачах массивы обработываются синхронно, поэтому попытка обойти один индекс заранее обречена на неудачу:
при асинхронной обработке массивов для каждой из асинхронно обработываемых массивов необходимо свой индекс (см. решения 1a, 16, 2a, 26).
В принципие, конечно, можно вместе ввести, например, счетчики, фикси-
рующее отставление одного индекса от другого (см. решения 2в), но это не упрощает программу, а только нарушает единобразие обработки массивов.
Рассмотрим подробнее решения 1a и 16. В основе этих решения лежат 2 стратегических отличиях исходных подхода. Первое решение можно прокомментировать так: «Выполняем m+n шагов переписывания в массив C. На каждом шаге, если массив A и B еще не исчерпаны, то переписываем текущий минимальный элемент, иначе — элемент из еще не исчерпанного массива». Второе решение соответствует подходу «Переписываем текущий минимальный элемент пока не исчерпается один из массивов. Затем дописываем оставшийся массив». Оба подхода в целом равновервины, хотя программа 26 будет выполняться быстрее.
Теперь сравним решения 2a и 26. Формально решение 26 правильно, однако в аналогичных ситуациях здесь применены два технических отличиях подхода: i нумерует первый свободный элемент массива и изменяется после переписывания, а k нумерует
51
Задча 1
i:=1; j:=1; k:=1;
while (i<=n) AND (j<=m) do
begin if a[i]<b[j]
then begin
c[k]:=a[i]; i:=i+1 end
else begin
c[k]:=b[j]; j:=j+1 end;
k:=k+1
end;
if j<=m then for j:=j to m do
begin c[k]:=b[j];
k:=k+1 end
else for i:=i to n do
begin c[k]:=a[i];
k:=k+1 end;
Задча 2
j:=1; k:=0;
for i:=1 to n do
begin
if a[i]>0 then begin nol[j]:=a[i];
j:=j+1 end;
if a[i]<0 then begin k:=k+1;
otrp[k]:=a[i] end
end;
nol[j]:=0; otrp[k+1]:=0;
Задча 4 (Копирование)
j:=2; for i:=1 to n do
begin b[i]:=a[j]; j:=j+2 end;
последний запятый элемент и изменяется до переписывания. В более сложных случаях такой разновой в обработке сходных ситуаций может повлечь ошибку, и в любом случае он не способствует легкости понимания программы. В технических вопросах каждый программист должен иметь любые технические приемы и не изменять им без достоинных оснований, тогда больше творческих сил остатется на решение стратегических вопросов.
В программе 2a по два раза повторяются одинаковые строки. Это можно избежать путем, показанным в программе 2в. Хотя формальное решение 2в правильно, но эллюпотребляя «фитами» типа передачи управления внутри условия половного оператора не следует, а современная теория не рекомендуется пользоваться оператором перехода вообще. Отметим, что обычно один оператор if, записав условия переписи из A, например, так:
if ((i<=n) AND (j<=m) AND
(a[j]<b[j])) OR (i>n) then
нельзя, так как даже при невыполненении условия i<=n ЭВМ все равно может проверить вычисление выражения a[i]<b[j], попытавшись обработать несуществующий элемент a[n+1].
КонтROLное задание
4.1. Выбросить из текста (массива символов) пробелы и «сжать» текст, сdwину
Задча 1
i:=1; j:=1;
for k:=1 to m+n do
begin if i>n then goto 2;
if j>m then goto 1;
if a[i]<b[j]
then 1: begin c[k]:=a[i];
i:=i+1 end
else 2: begin c[k]:=b[j];
j:=j+1 end
end;
Задча 2
j:=0; k:=0;
for i:=1 to n do
begin
if a[i]>0 then begin nol[i-j]:=a[i];
k:=k+1 end;
if a[i]<0 then begin otrp[i-k]:=a[i];
j:=j+1 end;
if a[i]=0 then begin k:=k+1; j:=j+1 end
end;
nol[i-j]:=0; otrp[i-k]:=a[i];
оставшиеся символы к левому краю. Обработку проверости без дополнительного массива.
4.2. (Сборка по массе). Дано 2 массива равной длины и пустой массив. Элементы 2-го массива (масси) имеют значения истин/a ложь. Значение ложь i-го элемента масси делает невидимым (массирует) i-e значение исходного массива. Собраты видимые (отмеченные значением истин/a массей) элементы первого массива в третьий массив, прижав их к левому краю и заполнив остаток третього массива нулями. (Обратите внимание, что 2 массива здесь будут обработаться синхронно, а третья — асинхронно по отношению к первым двум.)
4.3. (Разборка по массе). Дан массив, маска и пустой массив. Первые несколько элементов исходного массива разослать в те элементы пустого массива, которые отмещены в массе значением истин/a остальные элементы заполнить нулями.
4.4. (Повышенной сложности.) В массив могут быть несколько массивных элементов. За один просмотр массива выписать в другой массив номера всех массивных элементов исходного массива.
Подготовительные задачи к уроку 5
- Вывести на печать таблицу значений функции y=x² при x изменяющей от a до b с шагом h.
- Найти среднее арифметическое элементов массива.
- Дан массив действительных чисел. Найти в нем число, равное заданному: получить номер этого числа или нуль, если такого числа нет.
Л. Ф. Штерибер