Д. М. Златопольский Санкт-Петербург «бхв-петербург» 2011 удк
жүктеу/скачать 7,99 Mb. Pdf көрінісі
|
Златопольский Сборник задач по прогр
| Вариант 2. Нахождение элемента массива, больше которого только мак-
симальный. Здесь сначала рассмотрим случай, когда диапазон значений элементов массива известен. В качестве начальных значений величин максимум1 и максимум2 (см. ранее) принимаем число, которое заведомо меньше нижней границы диапазона значений элементов массива (например, при диапазоне от –1000 до 1000 — число –1001): максимум1 := -1001 максимум2 := -1001 Рассматриваем все элементы массива и проверяем каждое из них сначала на первый, а затем на второй максимум: нц для i от 1 до n если a[i] > максимум1 |Встретился элемент, больший максимум1 то |Бывший первый максимум станет вторым максимум2 := максимум1 |Первым максимумом станет встреченный элемент максимум1 := а[i] Приложение 3. Работа с одномерными числовыми массивами 263 иначе |Очередной элемент не больше максимум1. |В этом случае сравниваем его со значением максимум2 если a[i] < максимум1 и a[i] > максимум2 |Встретился элемент, меньший максимум1 |и больший максимум2 то |Принимаем его в качестве нового значения максимум2 максимум2 := а[i] |Значение максимум1 не меняется все все кц Фрагмент программы, относящийся к выводу ответа, оформляется так: если максимум2 = -1001 |Второй максимум не встретился то вывод нс, "Нет такого значения в массиве " иначе вывод нс, "Второй максимум равен ", максимум2 все Ясно, что второго максимума в принятом толковании может не быть толь- ко тогда, когда все элементы массива равны. Теперь обсудим случай, когда диапазон значений элементов массива неиз- вестен. В таком случае сначала найдем два первых различных элемента массива и примем больший из них — в качестве начального значения величины максимум1 , а меньший — величины максимум2 : |В качестве первого максимума условно |принимаем первый элемент массива максимум1 := а[1] |Ищем отличающийся от него элемент i := 2 нц пока a[i] = максимум1 i := i + 1 кц |Такой элемент найден. |Если он меньше первого максимума если максимум2 < максимум1 Приложения 264 то |Принимаем его в качестве второго максимума максимум2 := а[i] иначе |Он больше первого максимума |В качестве второго максимума принимаем значение максимум1 максимум2 := максимум1 |а в качестве первого максимума - встреченный элемент максимум1 := а[i] |Именно в такой последовательности все После этого рассматриваем остальные элементы массива: нц для j от i + 1 до n если a[j] > максимум1 |Встретился элемент, больший максимум1 то |Бывший первый максимум станет вторым максимум2 := максимум1 |Первым максимумом станет встреченный элемент максимум1 := а[j] иначе |Очередной элемент не больше максимум1. |В этом случае |сравниваем его со значением максимум2 если a[j] < максимум1 и a[j] > максимум2 |Встретился элемент, меньший максимум1 |и больший максимум2 то |Принимаем его в качестве нового значения максимум2 максимум2 := а[i] |Значение максимум1 не меняется все все кц вывод нс, "Второй максимум равен ", максимум2 Можно также после нахождения двух первых различных элементов не уточнять, какой из них больше, а проверку начинать с найденного элемента: |В качестве первого максимума условно |принимаем первый элемент массива максимум1 := а[1] Приложение 3. Работа с одномерными числовыми массивами 265 |Ищем отличающийся от него элемент i := 2 нц пока a[i] = максимум1 i := i + 1 кц |Такой элемент найден. |Условно принимаем его в качестве второго максимума максимум2 := а[i] |После этого рассматриваем остальные элементы массива: нц для j от i до n если a[j] > максимум1 ... (см. ранее) все кц вывод нс, "Второй максимум равен ", максимум2 Если же допускается, что все элементы массива могут быть равны, про- грамма несколько усложняется. Как и ранее, ищем два первых различных элемента массива: |В качестве первого максимума условно |принимаем первый элемент массива максимум1 := а[1] |Ищем отличающийся от него элемент i := 2 нц пока i < n и a[i] = максимум1 i := i + 1 кц Приведенный оператор цикла прекратит работать на последнем элементе массива или раньше — когда встретится элемент, отличающийся от зна- чения максимум1 . Если текущий элемент также равен максимум1 , то это значит, что все элементы массива одинаковые, и искомого второго макси- мума в массиве нет, в противном случае дальнейшие действия аналогичны рассмотренному до этого варианту: если а[i] = максимум1 то вывод нс, "Нет такого значения в массиве " иначе |Элемент, отличающийся от максимум1, найден. |Уточняем значения максимум1 и максимум2 если максимум2 < максимум1 Приложения 266 то максимум2 := а[i] иначе максимум2 := максимум1 максимум1 := а[i] все |Рассматриваем остальные элементы массива: нц для j от i + 1 до n ... (см. выше) кц вывод нс, "Второй максимум равен ", максимум2 все П3.47. Определение места, которое заданное число М должно занимать в масси- ве, упорядоченном по возрастанию (рис. П3.1), при сохранении его упоря- доченности (известно, что число M меньше последнего элемента массива). 2 4 5 12 20 24 31 45 50 53 М = 15 жүктеу/скачать 7,99 Mb. Достарыңызбен бөлісу:
|