Вычисление с замещением

При описании потока операций в неявном виде подразумевалось, что -элементный массив памяти готов к приему выходной последовательности, являющейся результатом вычислений на предыдущем этапе. Этот подход упрощает объяснение и реализуется в программах вычислений приведенных в приложении 1. Однако имеется возможность более рационального использования

памяти ЭВМ. Можно заметить, что в табл. 8.2 и 8.3 массив содержит не только элементы исходной последовательности, но и результаты их перестановки, обеспечивающей экономию числа ячеек памяти ЭВМ, для чего потребуется ряд искусственных приемов. Например, если элемент должен быть размещен на позиции (0,1), то, как обусловлено второй строкой столбца «Перестановка», сначала элемент следует занести на временную позицию. Затем этот элемент может быть размещен на позиции (0,8), что определено 9-й строкой.

Аналогичные приемы предусматриваются в случае, когда результаты выполнения этапа преобразования должны быть возвращены к расположению исходной последовательности. Для каждого элемента на входе блока, реализующего 1-й этап преобразования, потребуются две временные позиции, на входе блока, реализующего 2-й этап - четыре позиции и т.д. В программе вычислений количество позиций, используемых для запоминания элементов массива, равно , а для наиболее эффективного варианта это число просто равно N. Тогда после завершения вычислительного процесса элементы преобразования займут позиции элементов исходной последовательности. Это означает, что будет выполнено стирание исходных данных; естественно, исходные данные всегда могут быть восстановлены в результате дальнейшего преобразования, но в общем случае следует заблаговременно уделить внимание выполнению любых требуемых операций над исходными доследовательностями, таких, как табулирование или графическое построение, если массив памяти ограничен N позициями.

Вычислительная процедура с замещением используется в программах и (приложение 1). В результате освобождения сегментов памяти может осуществляться преобразование и намного более длинных последовательностей данных.