Добавлен: 18.06.2023
Просмотров: 161
Скачиваний: 6
СОДЕРЖАНИЕ
ГЛАВА1. ИЗУЧЕНИЕ ОСНОВНЫХ СЕМАНТИК ЯЗЫКА
1.2.3 ОПЕРАТОР БЕЗУСЛОВНОГО ПЕРЕХОДА
1.3.1.3 ПОЛЬЗОВАТЕЛЬСКИЙ ПЕРЕЧИСЛЯЕМЫЙ ТИП
ГЛАВА 2. ОСНОВНЫЕ АЛГОРИТМЫ ЯЗЫКА
2.3 МЕТОД ЛОГИЧЕСКОЙ ПЕРЕСТАНОВКИ ЭЛЕМЕНТОВ
2.4 МЕТОДЫ СОРТИРОВКИ МАССИВОВ
Function agorner(var a,base:integer):string
Var s:string;
I,tmp,count:integer;
Begin
Tmp:=a;
Count:=0;
While (tmp div Base>0)begin tmp:=tmp div Base; inc(count); end;
For i:=0 to count do
Begin
If (a mod Base<=9) then s[count-i+1]:=chr(a mod Base +48) else s[count-i+1]:=chr(a mod Base +65);
End;
Agorner:=s;
End;
У обратной функции горнера уже квадратичная сложность, поэтому считается, что это не самый лучший алгоритм перевода из десятичной системы в другую, однако, в случае вырожденности основания в какую-то степень двойки данный факт может быть частично невелирован с помощью логических операций, а так же безопасность, которую гарантирует этот метод опережает схожие методы. [8]
2.3 МЕТОД ЛОГИЧЕСКОЙ ПЕРЕСТАНОВКИ ЭЛЕМЕНТОВ
Данный метод является наиболее быстрым и безопасным методом для перестановки двух переменных
Program swap;
Var a,b:integer;
Begin
A:=9;
B:=5;
A:=a xor b;
B:=a xor b;
A:= a xor b;
End.
У алгоритма постоянная сложность и он не расходует дополнительной памяти, а также полностью безопасен. [2]
2.4 МЕТОДЫ СОРТИРОВКИ МАССИВОВ
Очень часто в программе требуется отсортировать массив, существует целая масса способов сделать это, каждый из которых показывает хорошие показатели в определённых условиях. Далее будут рассмотрены только два стандартных алгоритма: самый быстрый и простой в написании и чья сложность возрастает с наименьшей скоростью (однако, это не значит, что он является самым лучшим). [5] Под самым быстрым и простым в написании имеется в виду метод сортировки пузырьком. Своё название он получил благодаря идеи, что в нём заложена –при сравнении двух элементов самый лёгкий (меньший) идёт наверх, а тяжёлый (больший) вниз (определение верха и низа у массива считается тонкостью реализации…), поэтому, в худшем случае сложность этого алгоритма –квадратичная. [1] Предположим у нас есть массив M[1..N], тогда реализация будет:
begin
for j:=1 to N-1 do
for i:=1 to N-j do
if M[i] > M[i+1] then
swap(M[i],M[i+1])
end;
Преимущество данного алгоритма –скорость реализация. В большинстве проектов (особенно небольших) оптимизация – это отдельный этап разработки, который наступает уже после релиза исходного продукта, поэтому скорость написания и сложность понимания алгоритмов также считаются важными показателями. [9] В случае же, когда данных действительно много, или же просто нет необходимости в выборе подходящего под конкретную задачу алгоритма, обычно предпочитают пользоваться методом «быстрой сортировки», поскольку сложность алгоритма в этом случае логарифмическая, что является наименьшей среди прочих. [6]
procedure quicksort(var mas: array[1..n] of integer; first, last: integer);
var f, l, mid, count: integer;
begin
f:=first;
l:=last;
mid:=mas[(f+l) div 2];
repeat
while mas[f]<mid do inc(f);
while mas[l]>mid do dec(l);
if f<=l then
begin
count:=mas[f];
mas[f]:=mas[l];
mas[l]:=count;
inc(f);
dec(l);
end;
until f>l;
if first<l then quicksort(A, first, l);
if f<last then quicksort(A, f, last);
end;
На практике, программисты порой даже не думают о том, какую именно сортировку им использовать, а используют одну из указанных двух, особенно это актуально с учётом постоянно растущих мощностей вычисления и улучшения алгоритмов работы минификаторов данных. [3]
Последний алгоритм, который будет рассмотрен –это возведение числа в степень. Стандартные методы возведения числа в степень работают недостаточно эффективно, а соответствующей перегрузки нет в стандарте pascal, поэтому обычно пользуются следующим математическим приёмом:
X^y=exp(ln(X) * Y)
С математической точки зрения, это работает, поскольку при взятии экспоненты от натурального логарифма получается логарифмическое выражение, а по свойству логарифма степень выражения можно вынести в множитель логарифма. Через эту логику реализовано возведение в степень в других языках программирования. [1]
Данных алгоритмов обычно оказывается достаточно для комфортной работы на языке программирования pascal, и хотя само по себе программирование как область научного знания приводит практически любую задачу к набору стандартных алгоритмов, которые были бы эффективны в рамках данного языка и чья алгоритмическая сложность была бы минимальна и я бы соврал, если бы сказал, что мы разобрали хотя бы сколько-нибудь ощутимую часть от всех стандартных алгоритмов –всё-таки в прикладном программировании чаще всего предпочитают опираться на совсем базовые алгоритмы или библиотечные функции, чтобы создать свою собственную реализацию какой-то задачи. И я точно могу сказать, что приведённых алгоритмов обычно оказывается достаточно для собственных реализаций. [5]
ГЛАВА 3. РАЗРАБОТКА ПРИКЛАДНЫХ ПРОГРАММ В СРЕДЕ FREE PASCAL
Итак, чтобы проиллюстрировать, что приведённых теоретических сведений достаточно, чтобы чувствовать себя программистом, способным реализовывать прикладные задачи будут решены некоторые прикладные задачи. Под прикладными имеются в виду задачи, которые могли бы быть частью какой-то большой программы или которые являлись самодостаточными проектами в очень локальном промежутке. [7] Примером таких программ может служить методы реализующие логику длинной арифметики (без учёта оптимизаций), хотя такую программу сложно назвать прикладной, поскольку существуют специальные библиотеки, которые реализуют длинную арифметику, всё-таки может случиться так, что её необходимо будет реализовать с нуля. Итак, под длинной арифметикой понимают случаи, когда исходное число слишком велико, чтобы поместиться в стандартный контейнер и над таким числом необходимо провести стандартные математические операции (сложение, вычитание, умножение и деление). [4] Поскольку стандартные контейнеры недостаточно велики для хранения таких длинных чисел, то придётся написать с нуля и структурный вид контейнера числа и операции чтения и записи числа, ну и само собой всю арифметику.
Const MaxDig=1000;
Osn=10000;
Type Tlong=Array[0..MaxDig] Of Integer;
Одним из вариантов хранения такого числа является массив, каждый элемент которого –одна цифра такого числа, само собой для компактности (нам всё равно необходимо реализовывать арифметику с нуля) основание системы счисления должно быть максимально большим. [6] Несложно математически показать, что оно должно быть максимальной степенью двойки для максимальной эффективности по памяти (по скорости такое решение неочевидно, однако, если брать в расчёт «оптимальность дальнейших реализуемых алгоритмов», тогда нет никакой разницы в какой системе счисления хранить числа), которая не превышает заданного типа, однако, это сильно усложняет программу, (а мы не гонимся за эффективностью), поэтому для простоты возьмём просто степень числа 10. [8] Также для оптимизации, в 0 элементе будем хранить фактическую длину числа,а само число будет располагаться в обратном порядке. Далее необходимо реализовать функцию чтения:
Procedure ReadLong(Var A:Tlong);
Var ch:char;i:Integer;
Begin
FillChar(A,SizeOf(A) , 0) ;
Read(ch);
While Not(ch In ['0'..'9']) Do Read(ch);
{пропуск не цифр во входном файле}
While ch In ['0'..'9'] Do Begin
For i:=A[0] DownTo 1 Do Begin
A[i+l]:=A[i+l]+(LongInt(A[i])*10) Div Osn;
A[i]:=(LongInt(A[i])*10) Mod Osn;
End;
A[1]:=A[l]+Ord(ch)-Ord('0' ) ;
If A[A[0]+1]>0 Then Inc(A[0]);
Read(ch) ;
End;
End;
И сразу же функцию записи, с учётом особенности хранения числа:
Procedure WriteLong(Const A:Tlong);
Var ls,s:String;
i:Integer;
Begin
Str (Osn Div 10,Is) ;
Write(A[A[0]];{выводим старшие цифры числа}
For i:=A[0]-l DownTo 1 Do Begin
Str(A[i],s) ;
While Length(s)<Length(Is) Do s:='0'+s;
{дополняем незначащими нулями}
Write (s) ;
End;
Writein;
End;
Теперь, когда у нас есть все необходимые обслуживающие функции, можно приступить к непосредственной реализации арифметики. [10] Не будем мудрить в плане алгоритмов (для достаточно эффективных алгоритмов можно обратиться к книге алгоритмические приёмы программирования, там в разделе описания алгоритмов для целочисленной арифметики можно найти множество эффективных алгоритмов, которые и легли в основу реализаций специализированных библиотек), мы же будем реализовывать алгоритм «в лоб» -реализация алгоритмов арифметики столбиком, прямиком со школьной скамьи.
Procedure SumLongTwo(A,B:Nlong; Var C:Tlong);
Var i,k:Integer;
Begin
FillChar(C,SizeOf (C),0) ;
If A[0]>B[0] Then k:=A[0] Else k:=B[0];
For i:=l To k Do
Begin С [i+1]:=(C[i]+A[i]+B[i]) Div Osn;
C[i]:=(C[i]+A[i]+B[i]) Mod Osn;
End;
If C[k+l]=0 Then C[0]:=k Else C[0]:=k+l;
End;
Далее нам потребуются функции сравнения двух чисел, приведём одну из возможных реализаций:
Function Eq(A,B:TLong):Boolean;
Var i:Integer;
Begin
Eq:=False;
If A[0]OB[0] Then Exit
Else Begin
i:=l;
While (i<=A[0]) And (A[i]=B[i]-) Do Inc(i);
Eq:==(i=A[0]+l) ;
End;
End;
Function More(A,B:Tlong):Boolean;
Var i:Integer;
Begin If A[0]<B[0] Then More:=False
Else If A[0]>B[0] Then More:=True
Else Begin
i : =A [ 0 ] ;
While (i>0) And (A[i]=B[i]) Do Dec(i);
If i=0 Then More:=False
Else If A[i]>B[i] Then More:=True
Else More:=False;
End;
End;
Function Less(A,B:Tlong):Boolean;{A<B}
Begin
Less:=Not(More(A,B) Or Eq(A,B));
End;
Function More_Eq(A,B:Tlong):Boolean;
Begin
More_Eq:=More(A,B) Or Eq(A,B);
End;
Function Less_Eq (A, B:Tlong) : Boolean;
Begin
Less_Eq:-Not(More(A,B)) ;
End;
На практике, в программировании часто удобно пользоваться приёмом, что при сравнении двух чисел выдаётся число (а не булевая переменная), которая и отражает результат сравнения. Реализуем такую, с учётом сдвига чисел.
Function More(Const А, В: Tlong;
Const sdvig: Integer): Byte;
Var i: Integer;
Begin
If A[0]>(B[0]+sdvig) Then More:=0
Else If A[0]<(B[0]+sdvig) Then More:=l
Else Begin
i:=A[0];
While (i>sdvig) And
(A[i]=B[i-sdvig]) Do Dec(i);
If i=sdvig Then Begin
More:=0;
For i:=l To sdvig Do If A[i]>0 Then Exit;
More:=2;
End
Else More:=Byte(A[i]<B[i-sdvig]) ;
End;
End;
Перейдём к умножению двух длинных чисел.
Procedure Mul(Const A: TLong;Const К:
Longlnt;Var С: TLong) ;
Var i: Integer;
{результат - значение переменной С}
Begin
FillChar (С, SizeOf (С), 0) ;
If K=0 Then Inc(С[0]){умножение на ноль}
Else Begin
For i:==l To A[0] Do Begin
C[i+l]:=(LongInt(A[i])*K+C[i]) Div Osn;
C[i]:=(LongInt(A[i])*K +C[i]) Mod Osn;
End;
If C[A[0]+1]>0 Then C[0]:=A[0]+1
Else C[0]:=A[0] ;
End;
End;
Реализуем вычитание двух чисел:
Procedure Sub (Var A: TLong;
Const B: TLong;
Const sp: Integer);
Var i,j: Integer;
Begin
For i:=l To B[0] Do Begin Dec(A[i+sp], B[i]);
j:=i;
while (A[j+sp]<0) and (j<=A[0}) Do
Begin
Inc(A[j+sp], Osn) ;
Dec(A[j+sp+l]);Inc(j) ;
end;
End;
i : =A [ 0 ] ;
While (i>l) And (A[i]=0) Do Dec(i);
A[0]:=i;
End;
И наконец самое сложное – реализация деления двух длинных чисел, которое также будет реализовано через «алгоритм столбика». [2] Сам алгоритм можно разбить на 2 этапа: подбор очередной цифры, которая пойдёт частное и получение очередного числа – делимого. Разобьём эти 2 этапа на функции:
Function FindBin(Var Ost: Tlong;Const В:
TLong;Const sp: Integer): Longint;
Var Down, Up: Word;
C: TLong;
Begin
Down:=0;Up:=0sn;
While Up-l>Down Do Begin
Mul(В, (Up+Down) Div 2, С);
Case More(Ost, C, sp) Of
0: Down:=(Down+Up) Div 2;
1: Up:== (Up+Down) Div 2;
2: Begin Up:=(Up+Down) Div 2;
Down:=Up; End;
End;
End;
Mul(B, (Up+Down) Div 2, C);
If More (Ost.C,0)=0 Then Sub(Ost, C, sp)
Else begin Sub (C,Ost,sp); Ost:=C;
end;
FindBin:=(Up+Down) Div 2;
End;
Procedure MakeDel(Const А, В: TLong;
Var Res, Ost: TLong);
Var sp: Integer;
Begin
Ost:=A;
sp : =А [ 0 ] -В [ 0 ] ;
If More(А, В, sp)=l Then Dec(sp);
Res [0]:=sp+l;
While sp>=0 Do Begin
Res [sp+1]:=FindBin(Ost, B, sp);
Dec(sp) ;
End;
End;
Вот мы и получили полный набор инструментариев для реализации длинной арифметики. Как видно, нами активно использовались вещи, описанные в предыдущих главах, что лишь очередной раз подтверждает их пользу. [6]
Реализуем ещё одну программу, которая также может являться частью какой-то более большой программы: предположим в каком-то фрагменте нам стало необходимо найти определитель матрицы. [3] Реализуем программу, которая выполняет это:
program opred;
uses crt;
const n=3;
type
Tmatr=array [1..n,1..n] of real;
var a:Tmatr;
det:real;
procedure Per(k,n:integer;var a:Tmatr; var p:integer);
var i,j:integer;z:real;
begin
z:=a[k,k];i:=k;p:=0;
for j:=k+1 to n do
begin
if abs(a[j,k])>z then
begin
z:=abs(a[j,k]);i:=j;
p:=p+1;
end;
end;
if i>k then for j:=k to n do
begin
z:=a[i,j];a[i,j]:=a[k,j];a[k,j]:=z;
end;
end;
function znak(p:integer):integer;
begin
if p mod 2=0 then
znak:=1 else znak:=-1;
end;
procedure opr(n:integer;var a:Tmatr;var det:real);
var k,i,j,p:integer;
r:real;
begin
det:=1;
for k:=1 to n do
begin
if a[k,k]=0 then per(k,n,a,p);
det:=znak(p)*det*a[k,k];
for j:=k+1 to n do
begin
r:=a[j,k]/a[k,k];
for i:=k to n do
begin
a[j,i]:=a[j,i]-r*a[k,i];
end;
end;
end;
end;
В программе используется вырожденный случай, когда необходимо найти определитель матрицы 3x3, однако этот алгоритм достаточно мощный, чтобы работать с матрицами больших размерностей. [1]