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

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

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

Еще один важный вопрос, в связи с программой Рпте_1\1итЬег8_2, о том, почему выбрана проверка простоты числа г в данном порядке. Исходные условия для организации проверки минимальны: наличие множества най­денных простых чисел, не превосходящих г. Никаких предположений об упорядоченности этого множества нет. Да и не нужны они, если речь идет о математической задаче. Способ порождения этого множества таков, что его элементы появляются в соответствии с последовательностью простых чисел. Если бы явно требовался другой порядок, его нужно было бы по­строить. Если же не требуется никакого порядка, то, в частности, можно остановиться на порядке порождения, как целесообразно для решаемой за­дачи, поскольку вероятность делимости числа на малые числа выше, чем на большие. Это наблюдение использовано в программе Рпте_1\1итЬег8_2 при выборе порядка итераций проверочного цикла:

Данный порядок оказывается согласованным с решением о хранении раз­ностей вместо значений простых чисел. В самом деле, он предполагает последовательный перебор простых чисел от меньшего к большему. При хранении разностей именно такой перебор можно реализовать за одно сло­жение.

Рпте_1ЧитЬег8_2 не учитывает возможности перехода на новые позиции рассмотрения решаемой задачи, связанные с долговременным хранением результатов счета. И замена вычисления извлечением значения, и механизм прерываниявозобновления вычислительного процесса ограничены лишь те­ми случаями, когда программу можно встроить в использующую программу (например, с циклическими запросами) лишь как текст. Но и в этом случае применение Рпте_1ЧитЬег8_2 не приведет к экономии счета: все простые числа будут повторно вычисляться, а не извлекаться. Соответствующая мо­дификация Рпте_1\1итЬег8_2 представлена следующей программой.

Новости

  • 1
  • 2
Prev Next

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

Реклама