Д. М. Златопольский Санкт-Петербург «бхв-петербург» 2011 удк



Pdf көрінісі
бет260/271
Дата04.02.2022
өлшемі7,99 Mb.
#24830
1   ...   256   257   258   259   260   261   262   263   ...   271
Байланысты:
Златопольский Сборник задач по прогр

Вариант  2.  Нахождение элемента  массива,  больше  которого  только  мак-
симальный. 
Здесь  сначала  рассмотрим  случай,  когда  диапазон  значений  элементов 
массива известен. 
В  качестве  начальных  значений  величин 
максимум1
  и 
максимум2
 
(см. ранее)  принимаем  число,  которое  заведомо меньше  нижней  границы 
диапазона значений элементов массива (например, при диапазоне от –1000 
до 1000 — число –1001): 
максимум1 := -1001 
максимум2 := -1001 
Рассматриваем все элементы массива и проверяем каждое из них сначала 
на первый, а затем на второй  максимум: 
нц для i от 1 до n 
  если a[i] > максимум1 
    |Встретился элемент, больший максимум
    то 
     |Бывший первый максимум станет вторым 
     максимум2 := максимум1 
     |Первым максимумом станет встреченный элемент 
     максимум1 := а[i] 


Приложение 3. Работа с одномерными числовыми массивами 
263 
    иначе 
     |Очередной элемент не больше максимум1. 
     |В этом случае сравниваем его со значением максимум
     если a[i] < максимум1 и a[i] > максимум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] 
  иначе |Он больше первого максимума 
   |В качестве второго максимума принимаем значение максимум
   максимум2 := максимум1 
   |а в качестве первого максимума - встреченный элемент 
   максимум1 := а[i] 
   |Именно в такой последовательности 
все 
После этого рассматриваем остальные элементы массива: 
нц для j от i + 1 до n 
  если a[j] > максимум1 
    |Встретился элемент, больший максимум
    то 
     |Бывший первый максимум станет вторым 
     максимум2 := максимум1 
     |Первым максимумом станет встреченный элемент 
     максимум1 := а[j] 
    иначе 
     |Очередной элемент не больше максимум1. 
     |В этом случае 
     |сравниваем его со значением максимум
     если a[j] < максимум1 и a[j] > максимум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 < максимум1 


Приложения 
266 
     то 
      максимум2 := а[i] 
     иначе 
      максимум2 := максимум1 
      максимум1 := а[i] 
   все 
    |Рассматриваем остальные элементы массива: 
   нц для j от i + 1 до n 
    ... (см. выше) 
   кц 
   вывод нс, "Второй максимум равен ", максимум2 
все 
 
П3.47.  Определение места, которое заданное число М должно занимать в масси-
ве, упорядоченном по возрастанию (рис. П3.1), при сохранении его упоря-
доченности (известно, что число M меньше последнего элемента массива). 
 



12 
20 
24 
31 
45 
50 
53 
М = 15 


Достарыңызбен бөлісу:
1   ...   256   257   258   259   260   261   262   263   ...   271




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет