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

Приложение 3. Работа с одномерными числовыми массивами 
257 
    то 
     максимальное := а[i] 
  все 
кц 
где 
минимальное
 — минимальное число в массиве. 
Так, например, если известно, что в массиве все элементы неотрицатель-
ные, то можем записать: 
максимальное := 0 
нц для i от 1 до n 
  если a[i] > максимальное 
    то 
     максимальное := а[i] 
  все 
кц 
Задача нахождения минимального элемента решается аналогично. 
П3.42.  Определение индекса максимального элемента массива 
Здесь также алгоритм решения задачи аналогичен алгоритму действий че-
ловека, определяющего номер ячейки с максимальным значением в неко-
торой  одномерной  таблице  с  числами —  сначала  он  запоминает  первое 
число и номер 1, а затем рассматривает второе число. Если оно больше то-
го числа, которое помнил, то запоминает новое число и номер 2 и перехо-
дит к следующему, в противном случае просто переходит к следующему, 
третьему, числу и делает то же самое и т. д. 
Фрагмент программы, в котором решается задача: 
|Начальное присваивание значений искомым величинам 
максимальное := а[1] 
номер_максимального := 1 
нц для i от 2 до n 
  если a[i] > максимальное 
    то 
  |  |Принимаем встреченный элемент в качестве максимальное 
     максимальное := а[i] 
  |  |а его индекс — в качестве номер_максимального 
     номер_максимального := i 
  все 
кц 
|Вывод результата или использование его в расчетах 
... 

Приложения 
258 
Интересно,  что  при  решении  задачи  можно  обойтись  без  использования 
величины 
максимальное
.  В  самом  деле,  если  нам  известно  значение  ин-
декса максимального среди рассмотренных элементов, то мы знаем и зна-
чение соответствующего элемента (оно равно 
a[номер_максимального]
): 
номер_максимального := 1 
нц для i от 2 до n 
  если a[i] > a[номер_максимального] 
    то 
     номер_максимального := i 
  все 
кц 
Красиво, не правда ли? 
Задача  нахождения  индекса  минимального  элемента  решается  аналогич-
ными способами. 
П3.43.  Определение максимального значения среди тех элементов массива, кото-
рые удовлетворяют некоторому условию. 
Для простоты примем, что известен тот факт, что числа, удовлетворяющие 
заданному условию, в исследуемом массиве имеются. 
Особенностью этой задачи является то, что  в качестве начального значе-
ния  искомого  максимума  нельзя  принимать  значение  первого  элемента 
массива,  т. к.  он  может  не  входить  во  множество  элементов,  удовлетво-
ряющих заданному условию. 
Задача решается во многом аналогично задаче П3.41: 
максимальное := Х 
нц для i от 1 до n 
  если <условие> 
    то  |Встретилось число, удовлетворяющее заданному условию 
     |Cравниваем его с величиной максимальное 
     если а[i] > максимальное 
       то 
        максимальное := а[i] 
     все 
  все 
кц 
где 
Х
 —  число,  о котором    заведомо  известно,  что  оно  не  превышает  ми-
нимальное из чисел, для которых определяется максимальное значение. 
Если же такое значение заранее неизвестно, задача несколько усложняет-
ся. Можно поступить так: 
1.  Найти  первое  значение  в  массиве,  удовлетворяющее  заданному  ус- 
ловию. 

Приложение 3. Работа с одномерными числовыми массивами 
259 
2.  Принять его в качестве максимального. 
3.  Рассмотреть оставшиеся элементы и сравнить их с максимальным сре-
ди уже  рассмотренных. 
Соответствующий фрагмент программы: 
|Этап 1 
i := 1 
нц пока <заданное условие не соблюдается> 
  i := i + 1 
кц 
утв Первый элемент массива, удовлетворяющий 
утв заданному условию, найден. 
утв Его индекс равен i 
|Этап 2 
максимальное := а[i] 
|Этап 3 
нц для j от i + 1 до n 
  если a[j] > максимальное 
    то 
     максимальное := a[j] 
  все 
кц 
|Вывод результата или использование его в расчетах 
... 
Можно  также  использовать  величину  логического  типа 
впервые
,  опреде-
ляющую,  впервые  ли  встретилось  в  массиве  число,  удовлетворяющее  за-
данному  условию.  Остальные  особенности  работы  соответствующего 
фрагмента программы описаны в комментариях: 
впервые := да 
нц для i от 1 до n 
  если <условие> 
    то |Встретился элемент массива, 
       |удовлетворяющий заданному условию 
     если впервые            |Если впервые 
       то 
        максимальное := а[i]|Принимаем его в качестве значения 
                            | максимальное 
        впервые := нет      |Следующие такие числа уже будут 
                            |встречаться не впервые 

Приложения 
260 
       иначе                |Если не впервые 
        |сравниваем число с величиной максимальное 
        если а[i] > максимальное 
          то 
           максимальное := а[i] 
        все 
     все 
  все 
кц 
|Вывод результата или использование его в расчетах 
... 
П3.44.  Определение  индекса  максимального  элемента  среди  элементов  массива, 
которые удовлетворяют некоторому условию. 
Если известно, что числа, удовлетворяющие заданному условию, в иссле-
дуемом  массиве  имеются,  задача  решается  аналогично  задачам  П3.41  
и П3.42. 
П3.45.  Подсчет количества элементов, равных максимальному. 
Задача имеет два метода решения. 
Первый метод достаточно очевиден — сначала  найти максимальный эле-
мент  массива  (см. задачу П3.41),  а  затем  подсчитать  количество  элемен-
тов, равных найденному максимальному значению (см. задачу П3.42). Яс-
но, что при этом потребуется пройти по всему массиву дважды. 
Можно также решить задачу за один проход. Идея этого метода заключа-
ется в том, что, кроме значения максимума, помнить также и количество 
элементов,  равных  максимальному  (
кол_макс
).  Если  очередной  элемент 
оказывается  больше  текущего  максимума —  он  принимается  в  качестве 
максимального значения, а величина 
кол_макс
 —  равной 1. Если же оче-
редной элемент не больше максимального, то сравниваем его с максиму-
мом.  Если  они  равны,  то  встретился  еще  один  максимум,  и  значение 
кол_макс
 увеличиваем на 1. 
Соответствующий фрагмент: 
максимальное := а[1] 
кол_макс := 1 
нц для i от 2 до n 
  если a[i] > максимальное 
    то 
     максимальное := а[i] 
    иначе 
     если a[i] > максимальное 

Приложение 3. Работа с одномерными числовыми массивами 
261 
       то 
        кол_макс := кол_макс + 1 
     все 
  все 
кц 
Задача  нахождения  количества  элементов,  равных  минимальному,  может 
быть решена аналогичными способами. 
П3.46.  Нахождение второго по величине максимального элемента. 
Данная  задача  допускает  два  толкования.  Если  рассматривать,  например, 
массив 5 10 22 6 22 20 6 12, то каким должен быть ответ? 
Под "вторым по величине максимальным элементом" можно понимать: 
 
значение элемента массива, который стоял бы на предпоследнем месте, 
если  бы  массив  был  отсортирован  по  неубыванию  (см. задачи   П3.55  
и П3.56). При таком толковании ответ — 22; 
 
значение  элемента  массива,  больше  которого  только  максимальный.  
В этом случае ответ — 20. 
Если в массиве только один максимальный элемент (все остальные мень-
ше),  то  оба  толкования  совпадают,  и  искомые  значения  будут  одними  и 
теми же, в противном случае — нет. 
Рассмотрим оба варианта задачи. 

жүктеу/скачать 7,99 Mb.

Достарыңызбен бөлісу: