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

 

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

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

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

В настояем разделе приводится пример программы с рекурсивными процедурами, который предлагается для самостоятельного анализа. рограмма предназначена для распечатки всех последовательностей, составляемых из символов "1", "2" и "3", среди которых знаком "+" помечаются удовлетворя-
ие некотрому услови , которое Вам предстоит выяснить самим. ля реения задачи вбран рекурсивнй алгоритм, но это не означает, что ее нельзя реить без использования рекурсии. Программа 8.7.4
program SEQ;
const NN = 100;
K = 5;
Ms = '3';
MaxNstr = 23; var i, N : Integer;
S : packed array [ 1 .. NN ] of Char; sim: packed array [1..K] of Char;
8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ
473
M, Nseq, MaxNseq, Nstr: Integer;
procedure Init; begin
for i := 1 to N do
S [i] := '1'; M := N; end; { Init }
function Next: Boolean; begin
if S [ M ] = Ms then if M > 1 then begin S[M]:= '1';
M := M - 1; Next := Next; M := M + 1
end
else Next := false
else begin S[M]:= Succ (S[M]); Next := true end end; {Next}
procedure Inpt;
var ch : Char; begin
Writeln ('Введите проверяемую строку'); N := 0;
repeat Read ( ch ); N := N + 1; S [ N ] := ch
until ( N >= NN ) or ( ch = #13 ); N := N - 1 end; { Inpt }
function Good1 (ib, ie : Integer): Boolean; var i, l: Integer;
gl : Boolean; function Eq (i, j, l: Integer): Boolean; var imax : Integer; r : Boolean;
begin
l := l - 1;
474
8.
imax := i + l;
r := (l >= 0 ) and (imax <= N ) and (j + l <= N ); while r and (i <= imax) do begin
r := S [i] = S [j]; i := i + 1; j := j + 1; end; Eq := r end; { Eq} begin
if ib + 1 = ie
then Good1 := TRUE else if Good1 (ib, ie -1 ) then begin
gl := true; l := (ie - ib ) div 2; while gl and ( l > 0 ) do begin
gl := not Eq (ie-l-l, ie-l, l); l := l - 1 end; Good1 := gl
end
else Good1 := false end; { Good1 }
begin { Главная программа }
Write ('Введите длину последовательностей '); Readln ( N ); Init;
Nstr:= 0; Nseq := 0; MaxNseq := 80 div ( N + 2 ); repeat
if Good1 (1,N) then Write ('+') else Write (' '); for i := 1 to N do Write ( S [ i ]); Write (''); Nseq := Nseq + 1; if Nseq >= MaxNseq then begin Nseq := 0; Nstr := Nstr + 1; Writeln
8.8. ПРОЦЕДУРЫ В РАЗНЫХ МОДЕЛЯХ ВЫЧИСЛЕНИЙ
475
end;
if Nstr >= MaxNstr then begin Nstr := 0; Readln end until not Next; Writeln; end.
§ 8.8. ПРОЦЕДУРЫ В РАЗНЫХ МОДЕЛЯХ ВЫЧИСЛЕНИЙ
ри обсу дении подпрограмм, представленном в настояей главе, были подробно рассмотрены все аспекты работы с ними как с операционными единицами программы и единицами декомпозиции. В целом это рассмотрение ограничивалось лиь стилем структурного программирования, в рамках которого, собственно говоря, понятие процедур и приобрело современное содерание. Если е взглянуть на это понятие ире, попытаться распространить его на другие стили, то окажется, что некоторые из рассмотренных выше положений нуждаются в корректировке. Причина тому очевидна: стили, относяиеся к другим моделям вчислений, вкладыва т свое содерание как в операционне, так и в декомпозиционные аспекты автономно рассматриваемых подпрограмм.
Даже самое близкое к структурному стилю программирование от состояний приводит к несколько отличному от устоявшегося понятию процедуры. Этому случа оказывается противопоказана рекурсия. самом деле, с точки зрения модели вчислений программирование от состояний есть конеч-нй автомат, которому не ну ны понятия экземпляров процедур, локального контекста и др., тогда как для структурного понимания процедур они необходимы. То, что это действительно так, подтверждается ранними языками программирования Fortran IV и Basic, которые в большей степени, чем все их наследники, соответству т данному стил . редписываемые в них механизм реализации подпрограмм явно указыва т на то, что о рекурсивности здесь речи нет.24 В Basic стиль программирования от состояний поддерживается наиболее последовательно: нет не только рекурсии, но и само понятие
24 Отсутствие рекурсивности в ранних языках часто объясняют неразвитостью методов трансляции, необходимостью работать в очень жестких ресурсных ограничениях и другими подобными мотивами. Однако есть контрпример: язык LISP, рекурсивные механизмы которого органичны для функционального стиля. Это один из самых старых языков программирования, применявшийся в тех же самых жестких условиях. В этом контексте следует отметить Algol 60, разработчики которого пусть не во всем, пусть лишь на уровне идей, но уже понимали, что потребуется не только программирование от состояний, но и значительно
476
8.
процедуры подменено командами GOSUB и RETURN, которые выполняются, соответственно, как переход по метке с запоминанием адреса возврата и как переход по этому запомненному адресу. С точностью до использования специальнх регистров это именно то, что делается в обчном ассемблерном коде.
Различное отноение двух родственнх стилей к рекурсии мо но считать следствием различий в трактовке структуры информационного пространства программы (см. § 3.3). Процедурность в программировании от состояний исходит из того, что информационное пространство является обим для всех подзадач, из реений которых складвается реение основной задачи. тс да следует, что в данном случае утвердение о том, что процедура выполняется в каком-то контексте, в первом приближении становится тривиальным — все программные единицы вычисляются в одном и том же контек-сте.25 Как было показано, в структурном программировании ситуация иная.
Предыдущая << 1 .. 161 162 163 164 165 166 < 167 > 168 169 170 171 172 173 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100