Описание и обработка последовательных файлов.
End.
End
End
Else begin
Else
End
Begin
Begin
for i:=1 to k do
begin s[i]:=1; t[i]:=i+1 end;
for i:=k+1 to n1 do
begin s[i]:=0; t[i]:=i+1 end;
h:=k;
t[1]:=k+1; {t[1] указывает на вершину стека}
m:=0;
while m<>n1 do
for i:=1 to n do write(s[i]); writeln;
{вывод очередного кодового слова}
m:=t[1];
t[1]:=t[m];
t[m]:=m+1; {выбор сына узла ветвления}
if s[m]=1 then
begin if h<>0 then s[h]:=1-s[h]
else s[m-1]:=1-s[m-1];
h:=h+1
begin if h<>1 then s[h-1]:=1-s[h-1]
else s[m-1]:=1-s[m-1];
h:=h-1
end;
s[m]:=1-s[m]; {конец корректировки кодового слова}
if(h=m-1)or(h=0) then h:=h+1
h:=h-s[m-1]; {корректировка h}
{1} t[m-1]:=t[1];
if h=0 then t[1]:=m-1
{2} else t[1]:=h+1
{корректировка стека}
Комментарий. Стек реализуется таким же способом, как в SET4 t[1] указывает на узел в вершине стека, и каждый элемент t[j] в стеке немедленно получает новое значение, как только он исключается из стека. Присваивания {1} и {2} служат для добавления в стек m-1,...,h+1.
Упражнения. 1. Доказать корректность программы SUBSET3.
2. Откорректировать программу так, чтобы она правильно функционировала при k=0.
Литература
1. Ю. В. Матисевич. Десятая проблема Гильберта. М.: Физматлит, 1993
2. В. Липский. Комбинаторика для программистов. Мир, М. 1988.
3. Х Минк. Перманенты. Мир, М. 1982.
4. Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы. Теория и практика. Мир. М. 1980.
Процедурные типы.
В Turbo Pascal процедуры и функции можно рассматривать как некоторые параметры и можно использовать переменные, принимающие значение процедуры или функции. С этой целью вводятся процедурные типы, которые указывают, какой вид подпрограммы (процедуру или функцию) можно использовать в качестве параметра и с какими параметрами должны быть эти подпрограммы.
Объявление процедурного типа похоже на заголовок подпрограммы: пишется слово procedure или function, за которым в круглых скобках записывается список формальных параметров; для функции после списка формальных параметров через двоеточие указывается тип функции. В отличие от заголовка подпрограммы здесь не указывается имя подпрограммы.
Пример.
type
proc1=procedure; {процедура без параметров}
proc2=procedure (var x,y:integer);
{процедура с двумя параметрами-переменными типа integer}
func1=function (x:real):real;
{функция типа real с одним параметром типа real}
Далее можно ввести переменные этих типов:
var
p1 : proc1;
p2 : proc2;
f1 : func1;
После этого процедурным переменным можно присваивать значения конкретных процедур и функций. Как и в во всех других случаях, процедурная переменная и подпрограмма должны быть совместимы для присваивания.
Существует ряд правил использования подпрограмм в качестве процедурной переменной:
- они должны компилироваться с ключом компилятора {$F+} или иметь директиву far для получения полного адреса подпрограмм;
- они не должны быть стандартными процедурами и функциями;
-они не должны объявляться внутри других процедур и функций;
- они не должны быть типа inline или interrupt.
Пример.
{$f+}
procedure swap(var a,b:integer);
var t: integer;
begin t:= a; a:= b; b:= t end;
function tan( angle: real): real
begin tan:= sin(angle)/ cos( angle)
{проверка, что cos( angle)<>0, осуществляется в самой программе}
end;
{$f-}
в этом случае процедурным переменным, введенным ранее, можно присвоить значения:
p2:=swap;
f1:= tan;
а вызовы p2(i,j) и f1(x) эквивалентны соответственно swap(i,j) и tan(x).
Так же как и указатель, процедурная переменная занимает 4 байта памяти, в которых помещается полный адрес подпрограммы (поэтому подпрограммы необходимо компилировать с ключом {$f-}.
Процедурные переменные можно использовать так же, как и переменные других типов: в выражениях ( если эта переменная – функция), в виде оператора ( если эта переменная – процедура), как компонента другой более сложной переменной, как передаваемый в подпрограмму параметр. Идея единства данных и подпрограмм получила дальнейшее развитие в объектно-ориентированном программировании.
Пример. Вычисление интеграла по формуле Симпсона.
Для аппроксимации интеграла
s=
используется сумма конечного числа узловых значений fi.
sk=
(f0+4f1+2f2+4f3+2f4+. . .+4fn-3+2fn-2+4fn-1+fn)
где fi=f(a+i*h), h=(b-a)/n и n=2k. Число узловых точек равно n+1, а h – расстояние между двумя соседними узловыми точками. Значение интеграла s аппроксимируется последовательностью s1, s2,…, которая сходится, если функция ведет себя достаточно хорошо (гладкая) и если арифметические операции выполняются точно.
На каждом шаге число узловых точек удваивается. Конечно, хорошая программа не будет вычислять f(x) 2k раз на каждом k-м шаге, поскольку можно использовать значения fi, полученные на предыдущих шагах. В сумме sk три члена
sk= s
+ s
+ s
которые обозначают суммы в узловых точках с весами 1, 2, 4. Их можно определить с помощью рекуррентных соотношений для к>1:
s=
s
s=s+
s
s=
(f(a+h)+f(a+3h)+…+f(a+(n-1)h))
и начальных значений:
s
=
(f(a)+f(b))
s
=0
s
=
program integral;
const pi=3.141592;
type func1=function (x:real):real;
var ep:real;
{$f+}
function bil(x:real):real;
var a1,a2:real; i:integer;
begin a1:=sin(10*x); a2:=sin(x);if a2=0 then a1:=1 else a1:=a1/a2;
bil:=a1*a1*a1*a1*a1*a1;
end;
function bi(x:real):real;
begin bi:=sin(x) end;
{$f-}
function simpson(a,b:real; f:func1):real;
var i,n:integer;
s,ss,s1,s2,s4,h:real;
begin n:=2;h:=(b-a)*0.5;
s1:=h*(f(a)+f(b)); s2:=0;
s4:=4*h*f(a+h); s:=s1+s2+s4;
repeat ss:=s; n:=2*n; h:=h/2;
s1:=0.5*s1; s2:=0.5*s2+0.25*s4;
s4:=0; i:=1;
repeat s4:=s4+f(a+i*h); i:=i+2
until i>n;
s4:=4*h*s4; s:=s1+s2+s4
until abs(s-ss)<ep;
simpson:=s/3
end{simpson};
begin ep:=0.001;writeln((1/(2*pi))*simpson(0,2*pi,bil));
writeln(simpson(0,pi/2,bi))
end.
Файлом в языке Паскаль называется объект определенного типа – типа файла. Файл состоит из последовательности компонент одного и того же типа может в разное время содержать различное число компонент (возможно и ни одной).
Тип компонент файла может быть любым, но не должен содержать внутри себя других файлов или указателей. (Последнее ограничение связано с тем, что файлы хранятся, как правило, на внешних устройствах, при этом указатели, которые указывают на объекты в основной памяти, теряют смысл после окончания работы программы, в то время как файл может быть сохранен и дольше.)