Методическое пособие для подготовки к государственному экзамену по информатике для студентов специальности «Прикладная математика»

m_i+1= max(m_i,a_i)= while not eof() do

 m_i, m_{i } a_i if ms:= {a_i: i [1..k]} s₀=0 s:=0; read(eps);

k=min {i: abs(a_i)

s_i+1= s_i+a_i while not eof() and go do

begin read(a);

if abs(a)>=eps

then s:=s+a else go:=false

end

Общую теорию приближения числовых функций суммами (теорию рядов) - ищи в курсе мат. анализа.

b_i+1=b_ix+a_i while not eof() do

(схема Горнера) begin read(a); b:=b*x+a end

Замечательный - и достаточно редкий - случай наилучшего решения проблемы заданными средствами (здесь - с наименьшим количеством вычисления арифметических операций)

Задача. Вычисление значения комплексного многочлена a степени Deg(a). Спецификация-постусловие (неявно, предполагает знание типа "арифметика комплексных чисел"): y(a,x):={a_i*xⁱ:i[1..Deg(a)]}, xComplex, i[1,Deg(a)](a_iComplex).

1. 
   Решаем задачу в терминах ее постановки (спецификации). Объявляем имена нужных пользовательских типы и процедур.
   

tIndex=? ; {номера коэффициентов}

tComplex=?; {комплексные числа}

tComplexPolynom=? {комплексные многочлены}

procedure SetZero(var c:tComplex); {c:=0} ?

function Degree(p:tPolynom):tIndex; {определить степень полинома}?

function Element(p:tPolynom,i:tIndex):tComplex;{определить значение коэффициента}?

procedure Mult(a,b:tComplex;var c:tComplex); {c:=a  b} ?

var

i, {его номер}

DegA:tIndex; {степень полинома}

begin

DegA:=Degree(Polynom);

for i:=1 to DegA do

begin

end; {for}

end; {procedure PolynomValue }

Выделены операторы типа "арифметика комплексных чисел" - или, в более программистской терминологии, "подзадачи"

2. 
   Даем фактическое определение пользовательских объектов - желательно такое, чтобы обеспечить наиболее эффективное вычисление основного алгоритма (при восходящем программировании, наоборот, реализация типов управляет их логикой). Если такое определение тривиально, можно, исходя из соображений эффективности, сразу подставить значение (а именно - модифицированное тело, см. далее) в исходный текст.
   

tIndex=1..100; {строго говоря - ограничиваем постановку}

tComplex=record x,y:real end;

tComplexPolynom=record Coefficient:array[tIndex] of tComplex; Degree:tIndex end;

procedure SetZero(c:tComplex); begin c.x:=0;c.y=0 end;

{function Degree(p:tPolynom):tIndex; = p.Degree }

{function Element(p:tPolynom,i:tIndex):tComplex;=p.Coefficient[i] }

procedure Mult(a,b:tComplex;c:tComplex);

begin

c.x:=a.x*b.x-a.y*b.y;

c.y:= a.x*b.y+a.y*b.x;

end;

var

i:tIndex; {номер коэффициента}

{DegA:tIndex; = Polynom.Degree }

begin

for i:=1 to Polynom.Degree do Mult(y, Polynom.Coefficient[i],y);{y:=y*x+a_i;}

end; {PolynomValue }

Выделена реализация операторов языка спецификации. Понятно, реализовали полином "псевдодинамическим" массивом (а не, скажем файлом или списком) для того, чтобы быстрее и компактнее вычислить функции Degree и Element. Несмотря на то, что пришлось фактически ограничить постановку исходной задачи.

1. 
   Избавление от конфликта (коллизии) имен. В случае совпадения имен формальных параметров и имен локальных объектов с именами глобальных объектов - замени их на новые, уже не несовпадающие.
   
2. 
   Формальная семантика параметров-значений. Перед телом процедуры проставь операторы присваивания V:=E, V - имя формального параметра, E - соответствующее ему в обращении выражение (фактический параметр-значение)
   
3. 
   Формальная семантика параметров-переменных. Замени в тексте процедуры все вхождения имен параметров на соответствующие им при обращении имена переменных (фактический параметр-переменная).
   

{спецификация: found:=x a   i [1..LenA] (x=a_i) }

procedure poisk(x:T;A:tArray;LenA:tIndex; var found:boolean);

var i:tIndex;

begin

found:=false; i:=1;

end;
Построим обращение для poisk(2*i,X,10,b)  ?

1. 
   (Избавление от коллизии имен)
   

2. 
   (Присваивание значений параметров-значений)
   

3. 
   (Замена имен параметров-переменных)
   
4. 
   x1:=2*i; a:=x;LenA:=10; b:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then b:=true else inc(i1)
   

procedure poisk(x:T;A:tArray; var found:boolean);

{found:=i[1..LenA](x=a_i)}

{var i:tIndex; - сэкономили память!}

begin

found:=false; while (LenA>=0) and not found do if A[i]=x then found:=true else dec(Len)