Решение задач третьего класса

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

Рассмотрим примеры типичных алгоритмов решения задач этого класса.

Пример 10. Заданы два одномерных массива, содержащие координаты двух векторов в n-мерном пространстве. Нужно найти координаты вектора суммы.

Решение. Из математики известно, что координаты вектора-суммы находятся как суммы соответствующих координат векторов слагаемых. Здесь первая координата первого вектора складывается с первой координатой второго вектора и получается первая координата суммы, вторая со второй и т.д., поэтому здесь несмотря на то, что в работе участвуют три массива, достаточно одного индекса. В фрагменте алгоритма используются следующие обозначения: a,b - массивы координат заданных векторов, c - массив координат вектора-суммы, i - общий индекс массива, n - размерность векторов.

for (i=0; i<n; i++) c[i]=a[i]+b[i];

Пример 11. Заданы два массива. В первом хранятся некоторые числа, второй содержит только нули и единицы. Нужно в третий массив на те же самые места переписать те элементы первого массива, которым во втором массиве соответствуют единицы. Например, для исходных массивов a и b получится результат c. Минус обозначает неопределенное значение.

a={								9}
b={								1}
c={	-	-		-			-	9}

Решение. Здесь массивы также обрабатываются «синхронно», поэтому достаточно одного индекса.

for (i=0; i<n; i++)

if (b[i] = =1) c[i]=a[i];

Пример 12. Переписать из массива а в массив b положительные элементы, прижав их в массиве b к его началу.

Решение. Здесь исходным массивом является массива а, выходным - b. Просматриваем поэлементно исходный массив и, обнаружив положительный элемент, переписываем его в массив b. Здесь нельзя заранее установить формулу, по которой на основе индекса элемента массива а вычисляется соответствующий индекс в массиве b. Задача относится к «асинхронным». Введем разные индексы для массива а (i) и массива b (j). Тогда задача может быть решена так:

j=0; //в массиве b нет пока ни одного элемента

for (i=0; i<n-1; i++)

if (a[i]>0) {

j++; //готовим место для следующего элемента

b[j]=a[i];

}

Заметим, что в конце работы предложенного алгоритма значение j будет равно количеству элементов в массиве b.

Пример 13. Заданы два упорядоченных по возрастанию элементов одномерных массива: a размерности n и b размерности m. Требуется получить третий массив с размерности n+m, который содержал бы все элементы исходных массивов, упорядоченные по возрастанию.

Решение. Алгоритм решения этой задачи известен как «сортировка фон Неймана». Идея алгоритма состоит в следующем. Сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен.

Для массива a будем использовать в качестве индекса переменную i, для массива b - j, для массива c - k. Описанный алгоритм может быть реализован на так:

k=-1; //в новом массиве пока нет элементов

i=1; j=1; //сравнение начинаем с первых элементов

while (i<n && j<m) //пока один из массивов не закончился

if (a[i]<b[j]) //меньший элемент записываем в массив с

{ k++; c[k]=a[i]; i++;}

else { k++; c[k]=b[j]; j++;}

//если массив а не пуст, то дописываем оставшиеся элементы в массив с

while (i<n)

{ k++;

c[k]=a[i];

i++;

}

//если массив b не пуст, то дописываем оставшиеся элементы в массив с

while (j<m)

{ k++;

c[k]=b[j];

j++;

}

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

Пример 14. В заданном одномерном массиве все нулевые элементы переписать в конец массива. Например, для массива a={1,0,2,3,0,4,5,0,0,0,6} должен получиться результат a={1,2,3,4,5,6,0,0,0,0,0}.

Решение. Можно воспользоваться услугами вспомогательного массива, в который вначале перепишем ненулевые элементы (вспомним пример12), оставшуюся часть вспомогательного массива заполним нулями. Чтобы закончить решение, останется переписать содержимое вспомогательного массива в исходный массив. Соответствующий вариант решения приведен ниже. Здесь а - исходный массив, i - индекс массива а, b - вспомогательный массив, j - его индекс. Размерность обоих массивов - n.

j=0; //указывает номер первой свободной позиции в массиве b

//переписываем все ненулевые элементы из b в а

for (i=0; i<n; i++)

if (a[i] != 0) { b[j]=a[i]; j++;}

// заполняем остаток массива b нулями

for (i=j; i< n; i++) b[i]=0;

//переписываем массив b в а

for (i=0; i<n; i++) a[i]= b[i];

Проанализируем полученное решение. Главным его недостатком является использование вспомогательного массива - нерациональное использование оперативной памяти компьютера. Попробуем обойтись без него. В данном случае можно записывать ненулевые элементы в начало исходного массива. Место записи элемента указывает переменная j, которая передвигается по массиву только после записи ненулевого элемента. При найденном нуле значение переменной j не изменяется. Переменная i будет указывать на проверяемый элемент массива. Получается, что для одного массива используются два индекса: индекс i перебирает элементы массива а как входного (исходного), а индекс j - как выходного. В этом алгоритме результат получается сразу в массиве а, не нужно тратить время на переписывание из вспомогательного алгоритма. Соответствующий вариант программы приведен ниже:

j=0;

for (i=0; i<n; i++)

if (a[i] != 0) { a[j]=a[i]; j++;}

for (i=j; i<n; i++) a[i]=0;