Название: Алгоритмическое мышление при решении задач (Шамшев А. Б.)

Жанр: Информационные системы и технологии

Просмотров: 1389


Задача 3: найти индекс максимального четного значения в массиве.

Рассуждения:

1. Надо найти максимальное четное значение в массиве. Казалось бы очевидно, что результат – индекс одного из элементов массива. Но это не так.

Для конкретики рассмотрим массив из четырех элементов – {1,3,5,7}. В   нем   нет   четного   элемента   вообще,   и   как   следствие,   задача нахождения максимального четного значения не имеет смысла. Тогда логично предположить, что эту ситуацию (когда нет четных элементов

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

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

в качестве ответа, который сигнализирует о том, что четного элемента нет, выберем -1. Потому что -1 как индекс элемента – не корректное значение.

2.  Возьмем конкретные данные для того, что бы лучше понять алгоритм работы. Пусть массив имеет название data и содержит данные (1,5,4,1,7,9,2), т. е. шесть элементов. Как человек ищет максимальное из

четных чисел?

В начале он берет первое четное значение, которое встречается в массиве. В данном случае это четыре. Потом сравнивает все четные элементы,  которые  находятся  после  четверки,  с  этим  элементом.

В случае необходимости изменяют текущий результат.

3.  Запишем алгоритм в псевдокоде

 

Найти первое четное значение в массиве

Сравнить найденное значение со всеми оставшимися четными элементами

НачалоЦикла

Если тек. элемент массива больше результата, то

НачалоЕсли

Запомнить текущий элемент как результат.

ОкончаниеЕсли

ОкончаниеЦикла

 

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

5.  Поэтому улучшим псевдокодовое решение.

 

Инициализировать результат значением -1.

Просматривать весь массив

НачалоЦикла

Если текущий элемент четный, то

НачалоЕсли

В результат записать текущую позицию

Прервать цикл

ОкончаниеЕсли

ОкончаниеЦикла

Если просмотрели весь массив и не нашли четного элемента, то началоЕсли

вернуть как результат -1.

окончаниеЕсли.

Сравнить найденное значение со всеми оставшимися четными элементами

НачалоЦикла

Если тек. элемент массива больше результата, то

НачалоЕсли

Запомнить текущий элемент как результат.

ОкончаниеЕсли ОкончаниеЦикла Вернуть результат.

 

6.  В виде кодов данный алгоритм материализуется следующим образом:

public int getMaxEvenIndex(int[] data) {

int res = -1;

for (int i = 0; i < data.Length; i++) {

if (data[i] \% 2 == 0) {

res = i;

break;

}

}

if (res == -1) {

return -1;

}

for (int i = res + 1; i < data.Length; i++) {

if ((data[i] \% 2 == 0) && (data[i] > data[res])) {

res = i;

}

}

return res;

}