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

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

Расширение масштаба решаемой задачи. Для выявления простоты в этом случае достаточно проверять делимость не на все числа, меньшие проверяемого числа (пусть даже нечетные), а только на простые числа. Ранее идея могла возникнуть лишь умозрительно, поскольку распеча­тывание всех простых чисел с номерами, меньшими либо равными N. количественно ограничивает задачу. Ее просто не имеет смысла решать при таких N. при которых эффект сокращения проверок не бу­дет сказываться. Развитие идеи сокращения проверок за счет хранения данных приводит к мысли о том, что можно обойтись вообще без деле­ния, заменив его последовательным вычеркиванием составных чисел, как это делается в решете Эрато с фена;

Замена вычисления извлечением значения. При многократном поиске А^х простых чисел для использования (распечатки) запоминание поз­воляет ставить вопрос о том, что, быть может, искомое число уже ранее было найдено, и процесс поискавычисления можно заменить извлечением нужного числа из хранилища;

Прерываниевозобновление вычислительного процесса. Нет необходи­мости запускать повторный поиск простого числа с самого начала, когда найдены некоторые предшествующие ему числа. Можно просто запустить продолжение ранее прерванного процесса.

Из этого видно, что стратегия решения задач существенно зависит от того, какие средства программист предполагает использовать для запоминания.

Применительно к задаче о простых числах первое, что стоит проанали­зировать, — это возможность использования массива как структуры данных языка в качестве хранилища ранее найденных простых чисел.

Эта программа не сложнее Prime_Numbers_1 (внешне она выглядит даже проще, т. к. текст не перегружен комментариями, использованными ранее для разъяснения потоковой обработки, нет нужды в общей части вывода результата, вместо которой инициализируются два первых значения массива и др.) Не следует опасаться неэффективности в связи с тем, что в условии завершения циклаforвыражение обращается к вызову функции (sqrt(i)). Все, что может быть вычислено вне итераций цикла, будет вынесено транслято­ром до цикла. По аналогичным причинам значение переменной с индексом a[j] не будет извлекаться из массива дважды. Несколько сложнее дело обсто­ит с двойным вычислением истинности Prime: во время проверки условия окончания цикла и после цикла. Не всякий транслятор сможет выстроить вычисления так, чтобы исключался повторный счет. Однако, даже если в данной системе программирования такая оптимизация не предусматривает­ся, это не страшно: лишняя проверка условия выполняется вне внутреннего цикла, а потому на эффективности вычислений она практически не скажет­ся, а устранение этой мелочи испортит другие характеристики программы.

Новости

  • 1
  • 2
Prev Next

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

Реклама