Непейвода Н.Н. Программирование. Раздел 2

Непейвода Н.Н. Программирование. Страница 252

Упорядочивание массива А при заполнении, кроме уже рассмотренно­го пополнения числа элементов А, требует реализовать вставку X внутрь массива А в двух вариантах:

когда А не заполнен и

когда А заполнен.

Вставка в конец незаполненного А есть частный случай первого варианта. При принятой для рассматриваемой задачи стратегии хранения накапливае­мых максимальных элементов потока с помощью массива, а не какойлибо иной структуры данных, оба варианта требуют сдвига части массива (пере­писи) для освобождения места под X. В будущем мы изучим структуры дан­ных, использование которых позволит избежать такой переписи, и именно от них можно ожидать существенного повышения эффективности программы. Однако это уже будут другая стратегия и другие методы программирования, обсуждение которых стоит отдельного разговора. В рассматриваемой ниже программе MN3 используется простейшее из упорядочиваний, связанное с непосредственным заполнением массива из потока.

Для определенности применяется упорядочивание по возрастанию. Чи­тателю предлагается самостоятельно разработать программу, в которой мас­сив А упорядочивается по убыванию, и сравнить эффективность двух реше­ний задачи (есть основания полагать, что качество второго решения окажется несколько выше).

Если i — индекс такого элемента массива А, что A[i] <X, и при k > i все А[к] >X, то

Оптимизационное назначение цикла for — это традиция, восходящая к Algol 60 и даже к языку FORTRAN. В цикле forбольшинства языков програм­мирования, в частности в ряде случаев его употребления в С, можно явно выделять так называемые параметры цикла— переменные, принимающие те значения, при которых должны быть пройдены итерации. Переменные цикла должны рассматриваться и использоваться как связанные переменные данного оператора, то есть (так же, как в логике) как такие переменные, ко­торым не могут быть приданы конкретные значения извне, которые обязаны пробежать все множество, определенное в цикле, в том порядке (а это — отличие от логики), как предписывает цикл.

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета &quot;Ангара-А5В&quot; в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие &quot;Крокодилы&quot;

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама