Комбинация циклов с параметром и с условием

1. Дана матрица A(N,N). Переменной В присвоить значение, равное количеству строк матрицы А, содержащих хотя бы одну нулевую компоненту.

2. Дана матрица B(N,N). Получить вектор A(N), компоненты которого находятся по правилу: A _i равно первому по порядку положительному элементу в i -ой строке матрицы (если таких элементов в строке нет, то принять A _i = –1).

3. В заданной матрице A(N,M) найти количество строк, не содержащих отрицательных чисел.

4. Дана матрица A(N,M). Построить вектор B(N), элементы B _i которого равны единице, если элементы i - ой строки образуют упорядоченную по убыванию или по возрастанию последовательность, и нулю во всех остальных случаях.

5. Подсчитать количество различных (не повторяющихся) чисел, встречающихся в заданном целочисленном массиве A(N).

6. Подсчитать количество различных (не повторяющихся) чисел, встречающихся в заданной целочисленной матрице A(N,M).

Приложение. Методы сортировки массивов

МЕТОД ПРЯМОГО ВКЛЮЧЕHИЯ

Идея алгоритма состоит в следующем. Элементы массива просматриваются по одному, и каждый следующий элемент из числа еще неупорядоченных вставляется в подходящее место среди ранее упорядоченных элементов. Очевидно, что на N-ом шаге упорядоченными окажутся ровно N элементов.

 

 

Пример.

Пусть задано 8 чисел: 27, 412, 71, 81, 59, 14, 273, 87. На каждом шаге берем очередной элемент и сравниваем его поочередно с ранее упорядоченными, пока не встретится больший данного. В таблице звездочкой отмечена граница упорядоченных элементов.

 

Итеpация	Массив
нач.сост.	027 412 071 081 059 014 273 087
	027* 412 071 081 059 014 273 087
	027 412* 071 081 059 014 273 087
	027 071 412* 081 059 014 273 087
	027 071 081 412* 059 014 273 087
	027 059 071 081 412* 014 273 087
	014 027 059 071 081 412* 273 087
	014 027 059 071 081 273 412* 087
	014 027 059 071 081 087 273 412*

 

МЕТОД ПРЯМОГО ВЫБОРА (ЛИНЕЙНОЙ СОРТИРОВКИ)

Пусть задан массив из N чисел. Для сортировки массивов метод предусматривает последовательность шагов, на каждом из которых из массива выбирается и ставится на свое место один элемент.

а) Находим в массиве наименьший элемент.

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

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

 

Пример.

Для приведенного выше массива из 8 чисел последовательность сортировки описывается следующей таблицей (звездочка – граница отсортированной части).

 

Итеpация	Массив
нач.сост.	27 412 71 81 59 14 273 87
	14* 412 71 81 59 27 273 87
	14 27* 71 81 59 412 273 87
	14 27 59* 81 71 412 273 87
	14 27 59 71* 81 412 273 87
	14 27 59 71 81* 412 273 87
	14 27 59 71 81 87* 273 412
	14 27 59 71 81 87 273* 412
	14 27 59 71 81 87 273 412*

 

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

 

МЕТОД ПУЗЫРЬКА (ПРЯМОГО ОБМЕHА)

Метод пузырька получил свое название благодаря тому, что на каждом шаге наименьший из неупорядоченных элемент "всплывает" к левому краю. Идея метода основана на том, что в упорядоченном массиве каждое значение находится в правильном положении относительно непосредственно следующего за ним. Этот факт является основой метода прямого обмена, основанного на сравнении соседних элементов.

 

Метод реализуется следующим алгоритмом:

а) На первом шаге все элементы массива, начиная с последнего, сравниваются с предшествующим. Если элемент a[j] оказывается меньше, чем элемент a[j-1], то элементы меняются местами. Далее элемент, стоящий теперь на (j-1)-ом месте, сравнивается с элементом a[j-2] и т.д. После завершения первого шага можно гарантировать, что наименьший элемент массива будет самым первым (помещен в самый левый край массива).

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

Пример.

При сортировке методом пузырька последовательность шагов будет следующей.

Итеpация	Массив
нач.сост.	27 412 71 81 59 14 273 87
	14* 27 412 71 81 59 87 273
	14 27* 59 412 71 81 87 273
	14 27 59* 71 412 81 87 273
	14 27 59 71* 81 412 87 273
	14 27 59 71 81* 87 412 273
	14 27 59 71 81 87* 273 412
	14 27 59 71 81 87 273* 412

 

На первом шаге последовательно выполняются следующие перестановки: 87<-->273, 14<-->59, 14<-->81, 14<-->71, 14<-->412, 14<-->27.

На втором шаге значение 59 последовательно меняется местами с 81, 71 и 412.

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

Метод прямого обмена работает тем эффективнее, чем правильней расположены элементы в исходном состоянии массива. Не существует способа, который бы позволил предсказать, за сколько проходов N элементов будут полностью отсортированы. Если массив упорядочен с самого начала, то потребуется всего один проход. Если элементы расположены в обратном порядке (по убыванию), то N проходов.

Список использованной литературы

1. Фаронов В.В. Delphi 3. Учебный курс. М.: «Нолидж», 1998. 400 с.

2. Галисеев Г.В. Программирование в среде Delphi 8 for.NET. М.: Издательский дом «Вильямс», 2004. 304 с.

3. Павловская Т.А. Паскаль. Программирование на языке высокого уровня. СПб.: Питер, 2003. 393 с.

4. Абрамов С.А. Задачи по программированию. М.: Наука, 1988. 224 с.