Мисюткин. Методичка по алгоритмитизации

Подождите немного. Документ загружается.

Обозначим наименьшее значение величиной min, а его порядковый

номер величиной n_min. Тогда для их поиска воспользуемся следующим

алгоритмом:

1. Зададим min=x

и n_min=1

(тем самым как бы предполагая, что минимальный элемент – это первый).

2. Организуем цикл по i=2,3,…,N внутри которого будем проверять

условие x

<min.

В случае выполнения этого условия делаем замену

min=x

n_min=i

(Таким образом, при выполнении п.2 мы значения всех остальных элементов

сравним с min и в случае нахождения меньшего значения, делаем замену).

Замечание. Подобным образом работает и алгоритм нахождения

максимального (наибольшего) значения – max и его порядкового номера –

n_max. Но в этом случае проверяемое в п.2 условие нужно записать так:

>max.

5.3.4. Алгоритм перестановки

Очень часто возникает задача перестановки найденного минимального

x(n_min) или максимального x(n_max) элемента с другим элементом того же

массива, номер которого задан x(n_sad).

Описание алгоритма перестановки будем иллюстрировать простым

примером: имеются стакан с водой и стакан с молоком; нужно поменять

содержимое стаканов (рис.5.7). Ясно, что для этого понадобиться третий,

пустой стакан.

Для нашей задачи:

 стакан с водой – это x(n_min);

 стакан с молоком – это x(n_sad);

 пустой стакан – дополнительная величина R.

Перелив (перестановку) можно осуществить в три этапа

Рис.5.7. Иллюстрация алгоритма перестановки

В принятых нами обозначениях это запишется следующим образом:

R=x(n_min)

x(n_min)=x(n_sad)

x(n_sad)=R

Замечание 1. В следующих случаях перестановка не нужна или

невозможна:

а) n_min=n_sad – перестановка не нужна, т.к. элемент, с которым нужно

осуществить перестановку и есть минимальный;

б) n_sad= n_min-1 (т.е. перестановка с предыдущим элементом), а n_min=1 -

перестановка невозможна, т.к. нет предыдущего элемента;

в) n_sad=n_min+1 (т.е.перестановка см последующим элементом), а n_min=N

– перестановка невозможна, т.к. нет последующего элемента.

Поэтому, прежде чем делать перестановку нужно проверить одно из

перечисленных условий (какое – зависит от поставленной задачи), чтобы

решить вопрос о ее необходимости или возможности.

Замечание 2. В рассмотренном нами алгоритме перестановки роль

вспомогательной величины R (третьего стакана) может сыграть величина

min.

МолокоВода

x(n_min) x(n_sad)

Тогда перестановка осуществляется в два этапа

Пример 5.3. Найти минимальный элемент и поменять его местами с

предыдущим элементом массива.

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

рис.5.8.

x(n_min=x(n_sad)

x(n_sad)=min

Рис. 5.8. Схема алгоритма примера 5.3

начало

i≤N

Ввод N,

массива x

Вывод

массива x

min=x

n_min=1

i=2

нет

<min

нет

да

min=x

n_min=i

i=i+1

Вывод

min,n_min

n_min

Вывод

"перестановка

невозможна"

R=x(n_max)

x(n_min)=x(n_min-1)

x(n_min-1)=R

Вывод

массива x

да

нет

конец

5.3.4. Алгоритм формирования нового массива из элементов

имеющегося

Пусть имеется массив x, состоящий из N элементов. Необходимо

сформировать новый массив y, в который войдут те элементы массива x, для

которых выполняется некоторое условие, например, только положительные

значения.

Решение. Обозначим через i величину, которая будет являться

индексом у элементов массива x; она же будет показывать, сколько

элементов в нем уже просмотрено. Обозначим через k величину, которая

будет являться индексом у элементов массива Y; она же будет показывать,

сколько элементов в нем уже сформировано. Тогда для решения задачи

применим следующий алгоритм:

1. Зададим значение k=0.

2. Организуем цикл по i=1,2,…,N,

внутри которого будем осуществлять проверку условия попадания x

в новый

массив.

В случае выполнения этого условия выполняем следующие действия:

k=k+1

Пример 5.4. Даны два числовых массива. Сформировать третий массив

из положительных элементов первого массива и отрицательных элементов

обоих массивов.

Решение. Обозначим исходные массивы как A и B, состоящие из N и

M элементов, соответственно. Вновь формируемый массив обозначим через

C. При его формировании описанный выше алгоритм нужно применить

дважды: сначала для массива A, а затем для массива B. Но во втором случае

установку значения k=0 делать не нужно, т.к. числа из массива В будут

дописываться в уже сформированную из элементов массива А часть массива

С. Схема алгоритма приводится на рис.5.9.

Начало

Ввод N,

массива А

Ввод М,

массива В

к =0

i = i+1

нет

Ni 

i=1

нет

да

>0 или A

i<0

k=k+1

Вывод

массива A

Вывод

массива B

Рис.5.9. Схема программы примера 5.4.

к=0

Вывод "массив С

не сформирован"

Конец

нет

да

Вывод

массива С

i=1

i≤M

k=k+1

да

нет

i=i+1

да

нет

5.3.5. Поиск в упорядоченном массиве.

Массив называется упорядоченным по возрастанию, если для любой

соседней пары его элементов выполняется условие

1



Массив называется упорядоченным по убыванию, если для любой

соседней пары его элементов выполняется условие

1



Замечание 1. Термин: упорядоченный по не убыванию означает

выполнение условия

1



, а термин: упорядоченный по не возрастанию

– условие

1



Использование при поиске упорядоченных массивов очень часто

значительно повышает эффективность поиска (за счет сокращения времени),

поскольку в этом случае просматривается не весь массив, а только его часть.

Например, массив содержит упорядоченный по алфавиту (по

возрастанию) список фамилий студентов. По условию задачи нужно выдать

список фамилий, начинающихся с буквы "А". В этом случае, как только в

массиве попадется фамилия, начинающаяся с буквы "Б" поиск можно

завершить; а если бы список не был упорядочен, то пришлось бы

просматривать весь массив. Упорядочивание массива (или другой термин –

сортировка) осуществляется при помощи специальных алгоритмов, которые

рассмотрены в [2].

Пример 5.5. В упорядоченном по не убыванию массиве из чисел найти

количество отрицательных чисел, и определить, есть ли в массиве нули.

Решение. Поскольку массив упорядочен по не убыванию, а искать в

нем нужно только отрицательные числа или нули, то выход из цикла

просмотра возможен в двух случаях: когда весь массив просмотрен (т.е. в

нем все числа отрицательные), или встретилось значение =0. Введем

дополнительную величину t с начальным значением =0, которое изменит его

на 1, если встретится элемент =0. Количество найденных отрицательных

чисел обозначим через К. Схема алгоритма приведена на рис. 5.10. Она

включает в себя проверку введенного массива на упорядоченность по не

убыванию (символы, ограниченные пунктиром).

начало