Понятие алгоритма. Свойства. Способы представления алгоритма
Алгоритм - последовательность действий, приводящая к решению задачи.
Свойства:
| 1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов. 2. Определенность. Каждое правило алгоритма должно быть четким, однозначным. 3. Результативность. Алгоритм должен приводить к решению за конечное число шагов. 4. Массовость. Алгоритм должен быть применим для некоторого класса задач, различающихся лишь исходными данными. 5. Правильность. Алгоритм правильный, если его выполнение дает правильные результаты решения поставленной задачи. | |
Формы представления алгоритма
· Словесная форма
· Графическая форма
· Псевдокод
· Алгоритмический язык
Типы вычислительных процессов
Виды вычислительных процессов
· Линейный вычислительный процесс: вычислительный процесс, в котором каждое действие выполняется один раз, применяются операции ввода, вывода и вычисления.
· Разветвляющийся вычислительный процесс: вычислительный процесс, в котором решение задачи зависит от выбора определенного условия
· Циклический вычислительный процесс: вычислительный процесс, в котором участок программы должен повторяться несколько раз
Типы разветвляющихся вычислительных процессов
· Альтернатива (разветвляющийся вычислительный процесс, в котором решение задачи зависит от проверки определенного условия; в зависимости от этого выполняется либо серия действий 1, либо серия действий 2)
· Обход (разветвляющийся вычислительный процесс, в котором действие выполняется, если условие истина, в противном случае ничего не выполняется)
· Вывод (разветвляющийся вычислительный процесс, в котором необходимо выполнить последовательно несколько логических сравнений)
Циклические вычислительные процессы
Циклические вычислительные процессы – это процессы, в которых участок программы должен повториться несколько раз. Бывает 2 видов:
· С неизвестным числом повторений (while, repeat)
· С известным числом повторений (for)
Оператор WHILE…DO
Цикл while используется в том случае, если некоторую последовательность действий надо выполнить несколько раз. Причем число повторений при разработке программы неизвестно и может быть определено только во время работы программы. Типичными примерами использования этого цикла является вычисление с заданной точностью, поиск в массиве или в файле. В общем виде цикл while записывается следующим образом:
While <условие> do
Begin
…
End;
Инструкция выполнения:
Вычисление значения условия.
Если условие ложное, ничего не выполняется, на этом выполнение инструкции завершается.
Если условие истинное, то условие выполняется и далее выполняются инструкции тела цикла, далее идет проверка условия и так до тех пор пока условие не станет ложны
Для того чтобы инструкции цикла были выполнены хотя бы 1 раз, необходимо чтобы перед выполнением инструкции значение выражения условия было истинно.
Для того чтобы цикл завершился, необходимо чтобы последовательность инструкций влияла на значение выражения условия.
Оператор REPEAT…UNTIL
Цикл repeat используется в том случае, когда необходимо выполнить повторные вычисления и число повторений во время разработки программы неизвестно.
Общая схема:
Repeat <инструкции>
Until <условие>
Выполняется следующим образом:
Сначала выполняются инструкции цикла.
Затем вычисляется значение условия. Если условие ложно, то инструкции цикла выполняются еще раз.
Если условие цикла истина, то выполнение цикла прекращается.
Инструкции цикла выполняются как минимум 1 раз. Для того чтобы цикл завершился, необходимо, чтобы инструкции цикла изменяли значение переменных входящих в условие.
Оператор FOR…DO
Оператор цикла с перечислением применяется, когда число выполнения тела цикла известно еще до начала его выполнения. Он имеет следующий общий вид:
for <параметр цикла>:= <нач. знач.> to <кон. знач.> do <тело цикла>
Оператор тела цикла выполняется до тех пор, пока не будут перебраны все значения параметра цикла.
Типы данных
· Числовой тип данных делится на целый и вещественный тип данных:
o Целочисленные типы данных представляют собой значения, которые могут использоваться в арифметических выражениях и занимать в памяти от одного до четырех байт.
В языке Турбо Паскаль определено пять целых типов:
– Shortint (диапазон представления от -128 до 127, 1 байт);
– Integer (диапазон представления от -32767 до 32768, 2 байта);
– Longint (диапазон представления от -2147483648 до 2147483647, 4 байта);
– Byte (диапазон представления от 0 до 255, 1 байт), – Word (диапазон представления от 0 до 65535, 2 байта).
Над данными целого типа определены следующие арифметические операции: «+», «-»,«*»,«/»,div, mod.
Над данными целого типа определены следующие операции отношения: «=», «<>»,«>»,«<», «>=», «<=».
Для целых чисел определены следующие стандартные функции:
– Odd(x) – возвращает результат логического типа: для четного аргумента – false, а для нечетного – true;
– Succ(x) – возвращает следующее целое число (х+1);
– Pred(x) – возвращает предыдущее целое число (х-1);
– Ord(x) – возвращает аргумент x;
– Abs(x) – возвращает модуль х;
– Srq(x) – возвращает квадрат числа х;
– Sqrt(x) – возвращает значение корня числа х;
– Exp(x) – возвращает е в степени х (экспоненту), результат вещественного типа;
– Sin(x) – возвращает синус х, результат вещественного типа;
– Cos(x) – возвращает косинус х, результат вещественного типа;
– Ln(x) – возвращает натуральный логарифм х, результат вещественного типа;
– Dec(x, i) – уменьшает значение х на i, если i не задано, то на 1;
– Inc(x, i) – увеличивает значение х на i, если i не задано, то на 1
o Вещественный тип данных
Вещественные типы данных применяются для описания вещественных данных с плавающей или с фиксированной точкой, описывается как real. Вещественное число записывается и храниться в памяти компьютера в виде x=mb^n, где m-мантиса, b-основание представленного числа с плавающей точкой, n-порядок. Real занимает 6 байт памяти, диапазон представления чисел m до 12 чисел, n от -38 до 38. Операция деления свойственна только вещественному типу данных.
· Символьный тип данных
Символьные типы применяются для описания данных, значением которых является буква, цифра, знак препинания и другие символы. Существуют два фундаментальных символьных типа данных: AnsiChar и WideChar. Данные типа AnsiChar занимают один байт памяти и кодируют один из 256 возможных символов расширенной кодовой таблицы ANSI, в то время как данные типа WideChar занимают два байта памяти и кодируют один из 65536 символов кодовой таблицы Unicode.
· Логический тип данных
Задается как перечислимый тип данных, состоящий из 2 значений true/false. Описывается как Boolean, занимает 1 байт памяти. Для работы с таким типом данных применяются логические операции not/or/and. К логическим типам данных возможно применение операций сравнения false<true. Результат любой логический операции имеет тип данных Boolean.
· Строковый тип данных
Задает конечное упорядоченное множество символов, количество символов допустимое в языке.
Всего 255 символов, каждый символ имеет свой код:
0-31: коды управления устройствами.
49-57: цифры.
Операции:
Chr(x): символьное представление соответствующее коду х
Ord(c):код символа с
Функции и процедуры работы со строковым типом данных
1. LengTh(Str)
В качестве параметра функции передается строка Str, а результат функции целый тип данных который равен длине строк.
2. Concat(Str1,[Str2,Str3,...,StrN])
Функция выполняет слияние строк, которые передаются в качестве параметра, их может быть N количество. Это более эффективная функция чем операция “+”.
3. Copy(Str, Index, Count)
Функция копирует строку из строки Str, начиная с позиции Index в количестве Count символов.
4. Delete(Str,Index,Count)
В процедуре из строки-параметра Str, удаляется подстрока длинной Count символов, начиная с символа под номером Index в строке Str.
5. Insert(source, Str)
Процедура Insert ипспользуется для вставки строки Source в строку Str, начиная с символа index строки Str.
6. Pos(SubStr,Str)
Функция ищет подстроку SubStr в строке S. Результат функции будет номер первой позиции подстроки SubStr в исходной строке Str. Если подстрока не найдена функция возвратит 0.
· Множества
Множества – наборы однотипных, логически связанных друг с другом объектов.
Использование в программировании множеств дает следующие преимущества:
· Упрощение оператора if
· Увеличение наглядности программ и понимания алгоритма решения задач.
· Экономия памяти, времени компиляции и выполнения
Одной из причин редкого применения является относительно низкая скорость выполнения операций с множествами.
Типы данных:
char, byte.
Элементами множества являются только положительные числа.
Способ объявления:
Type <имя типа>=set of <тип множества>;
Var <идентификатор>:<имя типа>;
Операции над множествами:
· Объединение (+)
· Пересечение (*)
· Разность (-)
Сравнение множеств:
· 2 множества равны, если каждый элемент множества А является элементом множества В, и наоборот; А=В
· Множество А есть подмножество множества В, если каждый элемент А присутствует в В
· Принадлежность множеству х in A
Процедуры:
Include – включает новый элемент в множество
Exclude – исключает элемент из множества
Старшинство множественных операций:
1. *
2. +, -
3. =,<,>,in,<=,>=
Перечислимые и ограниченные типы данных
Перечислимый тип данных задается списком констант, которые могут принимать переменные этого типа. Каждый объект имеет свое имя.
Числа, логические и символьные константы не могут являться объектами перечислимого типа данных.
Применение перечислимого типа данных повышает наглядность программы и дает возможность автоматически контролировать допустимость значений переменных. Перечислимый тип задается в виде перечисления в строго определенном порядке и количестве всех значений, которые могут принимать данные.
Каждая константа имеет свой порядковый номер, счет начинается с 0.
Операции:
Pred -переход на пред. элемент
Succ - переход на следующий элемент
Ord - порядок элемента
Вводить и выводить на внешние устройства значение перечислимых типов недопустимо.
Ограниченный тип данных:
Множество значений стандартных, скалярных типов данных и перечисление скалярных типов упорядоченно и конечно. Если необходимо сузить диапазон значений, то осуществляется наложение ограничений на перечислимый скалярный или стандартный называемый базовым.
· Массивы
Массив – структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип.
Доступ к каждому элементу массива осуществляется путем индексирования элементов массива. Нумерация элементов начинается с 1.
Существует 2 вида массивов:
o Одномерные
Заполнение массива:
var
s:array [0..4] of integer;
Begin
Randomize;
For i:=0 to 4 do
Begin
S[i]:=random(100)-50;
Memo1.lines.add(inttostr(s[i]));
End;
Первое вхождение заданного элемента в массиве:
var
s:array [0..4] of integer;
Begin
For i:=0 to 4 do
If s[i]=p then
Begin
K:=I;
Break;
End;
Включение элементов в заданную позицию массива:
var
s:array [0..4] of integer;
k:integer;
Begin
K:=2;
For i:=4 downto (k-1) do
Begin
S[i+1]:=s[i];//все элементы начиная с k сдвигаем вправо
S[k]:=10;
End;
Исключение элемента из массива:
var
s:array [0..n] of integer;
k:integer;
Begin
K:=2;
For i:=k to (n-1) do
Begin
S[i]:=s[i+1];//все элементы начиная с k сдвигаем влево
S[k]:=0;
End;
Сортировка элементов:
1. Метод пузырька
Первый элемент массива сравнивается с последовательно со всеми оставшимися элементами. Если очередной элемент меньше чем первый, то эти элементы переставляются местами. Сравнение продолжается до тех пор, пока не сравним каждый элемент друг с другом.
For i:=1 to (n-1) do
For j:=j+1 to n do
If a[i]>a[j] then
Begin
P:=a[i];
A[i]:=a[j];
A[j]:=p;
End;
2. Метод простого выбора
На первое место становится самый минимальный элемент. На второе минимальный из всех оставшихся и так до предпоследнего элемента.
For i:=1 to (n-1) do
Begin
Min:=a[i];
Nmin:=I;
For j:=i+1 to n do
If min>a[j] then
Begin
min:=a[j];
nmin:=j;
End;
P:=a[i];
A[i]:=min;
A[nmin]:=p;
End;
3. Метод вставки
Второй элемент массива переставляется в порядке возрастания с первым элементом массива. Третий элемент вставляется в уже отсортированную часть массива а1, а2, не нарушая упорядоченности. Повторяем действия до последнего элемента массива.
For I:=2 to 5 do
Begin
M:=A[i];
J:=1;
While m>a[j] do
Begin
Inc(j);
End;
For k:=(i-1) down to j do A[k+1]:=a[k];
A[j]:=m;
End;
o Двумерные
I - строка
J – столбец
Заполнение массива:
var
s:array [1..3,1..3] of integer;
I,j:integer;
Begin
Randomize;
For i:=1 to 3 do
For j:=1 to 3 do
Begin
S[I,j]:=random(100)-50;
Memo1.lines.add(inttostr(s[I,j]));
End;
Суммирование элементов каждой строки:
var
a:array [1..3,1..3] of integer;
I,j:integer;
Sum: array [1..3] of integer;
Begin
For i:=1 to n do
Sum [i]:=0;
For i:=1 to 3 do
For j;=1 to 3 do
Sum [j]:=sum[i]+a[I,j];//для суммы столбцов Sum [j]:=sum[i]+a[j,i]
End;
Максимальный элемент каждой строки:
var
a:array [1..3,1..3] of integer;
I,j:integer;
max: array [1..3] of integer;
Begin
For i:=1 to n do
Begin
Max[i]:=a[I,1];
For j:=2 to 3 do
If a[I,j]>max[i] then max[i]:=a[I,j];
End;
Перестановка i-той и j-той строк матрицы
1) var
a:array [1..3,1..3] of integer;
I,j:integer;
Begin
K:=1;
M:=2;
For j:=1 to 3 do
Begin
P:=a[k,j];
A[k,j]:=a[m,j];
A[m,j]:=p;
End;
2) С использованием вспомогательного массива
Вначале все элементы 1 строки сохраняются в массиве, потом их заменяют на элементы 2 строки, а элементы 2 строки заменяют на вспомогательный массив.
Begin
K:=1;
M:=2;
For j:=1 to 3 do
C[j]:=a[k,j];
For j:=1 to 3 do
a[k,j]:=a[m,j];
For j:=1 to 3 do
a[m,j]:= C[j];
end;
Включение k-той строки в матрицу
Все строки начиная с k-той сдвинуть на одну строку назад (начать с последней и идти до k). Далее элементам k-той строки присвоить значение вектора с (одномерный массив).
Const
n=10;
Var
A:array [1..n,1..n] of integer;
I,j:integer;
Begin
K:=2;
For i:=3 downto k do
For j:=1 to 3 do
A[i+1,j]:=a[I,j];
For j:=1 to 3 do
A[k,j]:=c[j];
End;
Удаление k-той строки из матрицы
Все строки начиная с позиции k+1 необходимо переместить вверх на 1 строку.
Begin
K:=1;
For i:=k to (n-1) do //от k-той строки до количества строк-1
For j:=1 to n do
A[I,j]:=a[i+1,j];
End;
Для сортировки двумерного массива нужно добавить еще один цикл, позволяющий перебирать строки или столбцы.
· Файлы
Файл – поименованная область на диске, содержащая логически связанную совокупность данных.
Типы:
1. Текстовые
Совокупность строк переменной длины.
Переменная длина строк определяется наличием маркеров, обозначающих конец строки.
Определение конца строки:
EOLn(<файловая переменная>);
Для записи в файл используются write и writeln.
Чтение производится read и readln. По оператору read из файла выбирается столько символов, сколько указанно в текущем string, принадлежащем списку вывода.
По оператору readln из файла последовательно считываются строки и присваиваются string из списка. Если выбранная строка больше чем длина string, то она обрезается до его длины
2. Типизированные
Все компоненты файла должны быть одного типа.
Чтение компоненты через read. Запись – write.
Чтение компонент типизированного файла можно осуществлять, как последовательно, так и прямым методом доступа.
Последовательный доступ – доступ возможен путем перебора все предыдущих.
Прямой доступ – доступ сразу к указанному компоненту.
Процедуры:
Seek (<файловая переменная>, номер компоненты); - прямой доступ
Seek (<файловая переменная>,+1) – переход на следующую запись
Seek(<файловая переменная>,-1) – переход на предыдущую запись
Filepos (<файловая переменная>) – определить номер текущей компоненты
Rename (<файловая переменная>,’новое имя’)- переименование файла
Filesize(<файловая переменная>) – размер файла
Erase(<файловая переменная>) – удаление файла
3. Не типизированные
Объявление:
Var
<файловая переменная>:textfile;
<файловая переменная>:file of <тип>; //в качестве типа могут быть базовый тип и структурный тип – запись.
<файловая переменная>:file;
Доступ к файлу:
Необходимо привести в соответствие файловую переменную и файл. Это производится при помощи процедуры:
Assignfile(<файловая переменная>,’путь к файлу’);
Если путь не указан, то запись или считывание осуществляется в текущем директории.
Инициализация и завершение работы с файлом:
Прежде чем начать работу с файлом необходимо выполнить операции по работе с устройством на котором хранится или будет храниться файл:
1. При создании необходимо выделить область памяти на устройстве и запомнить имя файла и адрес заданной области.
2. При работе с уже существующим файлом необходимо по имени файла найти области памяти этого файла и установить указатель устройства на начало файла.
Инициализация происходит при помощи команд:
Reset (<файловая переменная>); //открытие существующего файла
Rewrite (<файловая переменная>); //создание или перезапись файла
Append (<файловая переменная>); //открытие файла для записи в конец
После работы с файлом его необходимо закрыть. При закрытии ОС подсчитывает размер файла и запоминает его.
Закрытие осуществляется при помощи процедуры:
Closefile (<файловая переменная>);
Конец файла определяется при помощи процедуры:
Eof (<файловая переменная>);
Обработка файла:
While not (eof (<файловая переменная>)) do
Begin
…
End;
Считывание данных из файла и запись их в файл:
Read (<файловая переменная>, <список вывода>); //считывает строку и оставляет указатель в конце строки
Readln (<файловая переменная>,<список вывода>); //считывает строку и оставляет указатель на следующей строке
Write (<файловая переменная>, <строка>, ‘разделитель’); //запись в файл подряд
Writeln (<файловая переменная>, <строка>) //запись в файл с новой строки
· Записи
Запись представляет собой совокупность ограниченного числа логически связанных компонент, принадлежащих разным типам.
Компоненты записи называются полями, каждая из которых определяется именем.
Чтобы обратиться к отдельной компоненте записи, необходимо задать имя записи и через точку указать имя нужного поля.
Объявление:
Type
Student=record; //имя записи
Fio=string[30];
Group=string[5];
End;
Var
S:student;
S2:array [1..100] of student;
F:file of student;
Доступ:
s.Fio:=’Иванов’;
Графика
В Delphi имеются классы существенно упрощающие использование графических средств:
· TCanvas – контекст изображения
· TFont - шрифт
· TPen – перо
· TBrush – заливка
Связанные с этими классами объекты при необходимости создаются автоматически для всех визуальных компонент, однако не все классы доступны у определенных визуальных компонент.
Для работы с изображениями используются:
· TPicture – контейнер для изображений
· TIcon - значок
· TBitmap – растровые изображения
· TMetafile - метафайл
· TImage – базовый класс для графических объектов изображения
Рисование:
Поверхность рисования представляет собой объект класса TCanvas, который называется холстом.
Любая поверхность рисования включает в себя шрифт, перо и заливку. Перо и заливка используются для прорисовки фигур, а шрифт – для управления атрибутами текста.
При выполнении графических операций используется текущий указатель – указатель позиции. Он представляет собой маркер определяющий позицию на поверхности рисования, начиная с которой выполняется следующая графическая операция.
Текущая позиция определяется горизонтальной (х) и вертикальной (у) координатами.
По умолчанию начало системы координат находится в левом верхнем углу поверхности рисования, отсчет координат осуществляется в пикселах.
Для перемещения указателя используется:
MoveTo (x:integer;y:integer); //указатель перемещается в позицию с координатами х,у.
Рисование геометрических фигур:
· Arc (x1,y1,x2,y2,x3,y3,x4,y4: integer) – рисование дуги
· Ellipse (x1,y1,x2,y2:integer) – эллипс с заполнением
· LineTo (x,y:integer)- линия от указателя до точки
· Rectangle (x1,y1,x2,y2: integer) – заполненный прямоугольник
· Pie (x1,y1,x2,y2,x3,y3,x4,y4:integer) – замкнутая фигура с закругленным верхом
· FillRect (const rect:integer) – прямоугольник с заполнением
· FrameRect (const rect:integer) – незаполненный прямоугольник
· Polygon (const point: array of point) – многоугольник с заполнением
· PolyLine (const point: array of point) – незаполненный многоугольник
Процедура CopyRect (Dest:TRect; Canvas: TCanvas; Source:TRect) копирует прямоугольную область, размеры которой заданы параметром Source из исходной поверхности, заданной параметром Canvas, в прямоугольную область Dest.
Адресатом операции является поверхность, для которой была вызвана процедура.
Если исходная и результирующая поверхности имеют разные размеры, то копируемый образ масштабируется под размеры области Dest, т. е результирующей поверхности.
Свойство ClipRect определяет границы области поверхности рисования в пределах которой осуществляется прорисовка. Часть изображения выходящая за пределы этого прямоугольника отсекается и не выводится.
Это свойство используется для ускорения процесса отображения. По умолчанию границы отсечения установлены по размерам поверхности коспонента.
Draw (x,y:integer; Graphic:TGraphic); - процедура вывода изображения на поверхность рисования, в которой х,у – левый верхний угол начала вывода, а параметр Graphic задает выводимое изображение.
Занимаемая изображением область зависит от размера изображения. Если рисунок не входит, то применяется процедура StrechDraw(), в которой для изображения задается прямоугольная область.
Свойство LoadFromFile используется для загрузки изображения в переменную.
Установка параметра шрифта:
· Name – имя шрифта
· Style – стиль (bold – жирный, underline – нижнее подчеркивание, italic – курсив)
· Size - размер
· Color – цвет
Свойства TPen:
· Style – стиль рисования
o psSolid – сплошная прорисовка
o psDash - штрихи
o psDot - пунктир
o psClear – невидимая линия
· Width - размер пера
· Mode –как перо при рисовании линий взаимодействует с имеющимися линиями
o pmBlack – всегда черный
o pmWhite – всегда белый
o pmNop – не изменяется
o pmNot – инверсия при повторном рисовании
o pmCopy – совпадение с цветом, указанным в свойстве Color
o pmNotCopy – инверсия цвета пера
Свойства Brush (кисть):
· Style - стили
o bsSolid – сплошная заливка
o bsClear – нет заливки
o bsGorizontal – горизонтальные линии
o bsVertical – параллельные вертикальные линии
o bsfDiagonal – диагональные линии направленные вверх
o bsbDiagonal - диагональные линии направленные вниз
o bsGross – прямая решетка
o bsDiagGross – диагональная решетка
· BitMap – изображение в качестве стиля кисти
Последовательность дейтвий при создании анимации:
1) Вывести объект на экран
2) Подождать
3) Стереть объект с экрана
4) Вывести объект с некоторым смещением
Процедуры и функции
Процедуры и функции – подпрограммы.
Применяются, когда при решении задач когда некоторую совокупность команд необходимо повторять в программе несколько раз.
Программа состоит из 3 частей:
1) Имя – procedure …
2) Декларативная часть – var …
3) Процедурная – begin … end;
Данные объявленные в основной программе называются глобальными. Используются в любых подпрограммах.
Данные объявленные в подпрограмме называются локальными. Используются только в одной подпрограмме.
Функции:
· Синтаксис:
Function <имя>: <тип функции>;
Var …
Begin
…
End;
Функция всегда возвращает значение, предназначена для вычисления
· Вызов в программе
<Имя функции> (<имя параметра>:<тип>);
· Для возврата значения в основную программу необходимо в конце тела функции имени функции присвоить вычисляемое значение.
Процедуры:
· Синтаксис:
Procedure <имя процедуры> (var <параметр>:<тип>); // var ставится перед тем параметром, который будет изменятся в теле процедуры
Begin
…
End;
· Передача параметров осуществляется двумя способами:
o По ссылке
o По значению
В подпрограмму пересылается копия значения переменной.
Если необходимо, чтобы значение переменной в процедуре менялось, то необходимо осуществить передачу данных по ссылке путем указания слова var перед передаваемым формальным параметром