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

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

Бросается в глаза то, что исходное задание А (аналог строки 1.1. в про­грамме М11) можно описать как перепись (разумеется, без повторений) на­чала входного потока, а поиск убираемого элемента (см. строку 1.2) — с помощью просмотра А и поиска в нем минимума. При переписи приходится ввести индекс заполненности А (в дальнейшем он обозначается 1_), который растет, когда место в А еще не исчерпано (Ь< ЛГ). Если N невелико, вопрос о цене разделения переписи без повторений и просмотра не возникает, и вполне приемлемо решение, когда работа с А организуется прямо, циклом с проверками каждого элемента массива:

Однако с ростом ТУ эффективность программы будет падать изза того, что приходится просматривать все большее и большее количество чисел. Возни­кает желание улучшить просмотр, а заодно и перепись. Это можно сделать при специальной организации А: использовать упорядочивание при запол­нении.

Идея упорядочивания весьма продуктивна, а потому ее обсуждение будет проведено специально. Здесь же хотелось бы оценить первоначальный план с другой стороны: оправдана ли предварительная перепись? При вниматель­ном рассмотрении становится ясно, что заполнение А можно программно совместить с просмотром и поиском убираемого элемента. Для этого надо использовать индекс заполненности Ь как границу просмотра. Программа МЫЗ, реализующая эту идею, приводится ниже.

При ростеNпрограмма MN2 все еще будет неэффективной изза увеличения накладных расходов на полный просмотр массива А. Как уже отмечалось, это можно поправить за счет упорядочивания массива. Предварительно от­метим, что формулировка решаемой задачи не совсем точна: она оставляет свободу разработчику в выборе того, в какой последовательности надо вы­водить полученные результаты. Если это безразлично, то решение вопроса, использовать упорядочивание или нет, разработчик программы вправе моти­вировать только логикой построения алгоритма и оценкой эффективности. В противном случае, когда требуется вывести результат в том или ином порядке (для определенности — по возрастанию), необходимость упорядо­чивания диктуется условием задачи. И тогда возможное решение, связанное с дополнительным упорядочиванием массива А после завершения работы с потоком, становится совершенно неприемлемым: оно приведет к заведомой неэффективности программы.

Новости

  • 1
  • 2
Prev Next

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

Реклама