Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 163

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 157 158 159 160 161 162 < 163 > 164 165 166 167 168 169 .. 316 >> Следующая

• чебными целевыми установками. Здесь имеется ввиду возмо ность использования реения начинаими программистами, для которх более развитые средства программирования целесообразно изучать по мере освоения базовх средств программирования.
В программе использу тся вспомогательне процедуры: InpW, организу -
460
ГЛАВА 8. ПОДПРОГРАММЫ
щая ввод входного потока с текущим контролем, ClearQueue, очищающая очередь и распечатывающая ее содержимое, и InpHandle, выполняющая все действия, связанне с обработкой очередного входного числа.
Программа 8.6.3
program WWW;
uses Crt, IntQueue;
const MaxW = 15;
var InpEl, CurW: Integer;
procedure InpW; begin repeat
Read (InpEl);
Writeln (Ошибка: слишком большой вес.', ' Повторите ввод'); until InpEl <= MaxW end;
procedure ClearQueue; begin
while StateQueue <> Empty do Write ( GetElQueue,''); end;
procedure InpHandle;{ Обрабатывает InpEl, корректирует CurW}
var S, Sn, R : Integer; begin
S := CurW + InpEl; if S < MaxW
then begin CurW:= S; PutElQueue ( InpEl );
end else
if S = MaxW
8.6. TURBOPASCAL
461
then begin
ClearQueue; Write (InpEl,''); Write ('(', S, ')'); CurW := 0;
end
else { S > MaxW- возможен обмен } begin
while StateQueue <> Empty do begin R := GetElQueue; Sn:= S - R;
if ( Sn > MaxW) or ( Sn <= CurW) then { Отказ от обмена }
Write ( R, ' ' )
else begin
Write ( InpEl, ' ' );
if Sn = MaxW then { Оптимизация }
ClearQueue; {Завершение обмена}
InpEl := R;
CurW := Sn
end end;
Write ( '(', CurW, ') '); CurW:= InpEl; PutElQueue ( InpEl )
end
end;
begin
CurW := 0;
Writeln ('Поток входных значений:'); while not eoln do begin
InpW; InpHandle; end; ClearQueue; Writeln ( '(', CurW, ') ' );
462
8.
repeat until KeyPressed end.
Решение данной задачи, вообще говоря, может базироваться не только на использовании IntQueue. Так, для задерки поступаих элементов вполне правомерна стековая дисциплина хранения данных. Чтобы реализовать эту стратеги , мо но чисто механически заменить в программе WWW вызовы подпрограмм модуля IntQueue на вызовы подпрограмм подходящего модуля работы со стеком (разумеется, со сменой используемого модуля). Новое реение будет отличаться от приведенного лиь порядком установки контейнеров (съедения рыб котом). Читател настоятельно рекомендуется убедиться в этом.
Анализ предложенного решения и сопоставление его с только что упомянутым решением показывает, что сам по себе факт использования очереди или стека не влияет на эффективность программ . ровень эффективности будет зависеть от качества реализаций этих двух структур даннх. Как очередь, так и стек обеспечива т правильну дисциплину обраения к памяти для организации поиска кандидатов на обмен, что, собственно говоря, и есть причина использования линии задержки в данной программе. Выбор между стеком и очередь для данной задачи вполне произволен. ледует однако заметить, что очередь позволяет ' почти' сохранять в вводе порядок, в котором вводятся элементы данных, тогда как стек делает его ' почти' произвольным. Может быть, это обстоятельство склонит программиста в пользу очереди?
С точки зрения демонстрации модуляризации уместно заметить, что смена одного модуля (IntQueue) на другой (работа со стеком или с очередь , базируейся на списковой организации) практически не приводит к из-менени алгоритма. С точность до имен процедур реение сохраняется.
о это достигнуто благодаря тому, что модулем IntQueue на уровень использования вынесены только необходимые возможности, никак не завязанные на реализаци . оддерка разделения контекстов язком программирования обеспечила заиту от употребления реализационно-зависимых средств.
сво очередь, именно это обстоятельство позволяет провести анализ различных вариантов организации памяти.
Задания для самопроверки
1. В случае, когда у нас заранее известное количество очередей, можно эффективно организовать работу, воспользовавшись секциями initialization
8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ
463
и finalization модуля. Проделайте это для случая, когда в программе всего одна очередь.
2. Реализовать стратегию кота, механически заменив в программе WWW использование модуля IntQueue на использование некоторого модуля для работы со стеком и вызовы подпрограмм модуля IntQueue на вызовы подпрограмм модуля работ со стеком.
3. Чем новое решение будет отличаться от приведенного в тексте?
§ 8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ
Методы составления рекурсивных алгоритмов занимают заметное место среди средств, которми пользу тся программисты в своей работе. В то е время, их освоение требует определеннх навков, которые базиру тся на понимании процессов вычислений в целом. Главная цель настоящего раздела в том, чтобы обеспечить возможность на практике ознакомиться с рекурсией, сопоставить рекурсивность с другими, в некотором смысле родственными понятиями, в перву очередь, с итеративность . В соответствии с этой цель м не будем здесь обсу дать рекурси как метод программирования. Этому посвящена глава в части III.
Если алгоритм построен таким образом, что в ходе его работ возмо но повторение некоторых действий посредством обращения к самому себе (т. е. обраение к вчислениям, описаннм этим алгоритмом), то такой алгоритм называется рекурсивным.
Предыдущая << 1 .. 157 158 159 160 161 162 < 163 > 164 165 166 167 168 169 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100