Б1. Алгоритм и его св-ва.
Алгоритм-последовательность действий однозначно определяющих процесс решения задач.
Свойства:
1. Наличие вв. и выв. Алгор. должен иметь входные и выходные данные, состав, типы и диапазоны возможных значений, которые перед разработкой алгоритма следует однозначно определить.
2. Детерминированность (определённость) заключается в том, что каждое действие алгор-а должно быть точно и однозначно определено.
3. Конечность (разрешимость, результативность или финитность) заключается в том, что работа алгор. должна заканчиваться после выполнения конечного числа действий.
4. Массовость заключается в возможности решения задачи с различными вариантами наборов исходных данных.
5.Эффективность заключается в том, что алгор. должен быть “хорош” с точки зрения некоторых критериев: продолжительность работы, требуемый объём памяти и др.
Б2. Формы представлен. алг.
1. Словесное описание. Представление алгор. с помощью литерат-ого или профессионального языка.
2. Блок-схема. Составляется на основе ГОСТа 19.701-90, алгор. представляется в граф. форме, где действие над данными изображается в виде геометр. блоков с поясняющими надписями, а последовательность действий указывается соединительными линиями.
3.Запись на языке программирования Программа на алгор. языке – это запись алгор. с использованием операций выбранного языка программирования.
Б3.Линейные(1) и разветвлённые(2) структуры алгоритмов.
1. Линейный алгор. предполагает последовательное выполнение действий по одному разу.
2. Разветвлённые алгор. содержат альтернативные действия процесса обработки данных, состав которых зависит от результатов предыдущих операций
Б4.Циклические структуры алгор-ов. Составные части цикла.
Разновидности циклических структур.
Циклические алгор. многократно используют часть действий для формирования результата решения задачи.
Составные части:
Р – рабочая часть цикла (тело).
П – подготовка цикла. Задание начальных значений для вычислений.
Л – логический анализ на завершение (продолжение) цикла.
ПИ – подготовка информации к следующему шагу.
Разновидности циклических структур:
1.Циклы с предусловием.
2.Циклы с постусловием.
Характер управления:
1.Циклы с заданным числом повторений (с параметром), для которых можно указать: начальное, конечное значения и приращение.
2.Итерационные циклы число повторений которых не известно и проверка на окончание происходит не по параметру, а, чаще всего, по достижению заданной точности.
Б15.Условный оператор(1). Оператор перехода(2).
2):Операторы в программе обычно выполняются в том порядке, в котором они записаны. Оператор перехода прерывает естественный порядок выполнения программ и указывает, что дальнейшее её выполнение должно продолжаться, начиная с оператора, помеченного этой меткой.
Goto……метка
Каждая метка должна быть объявлена в разделе описания меток.
Б5. Порядок разработки программного обеспечения.
1.Постановка задачи.
2.Определение метода решения задачи.
3.Формализация постановки задачи. Определение обозначения переменных, констант и результатов, с помощью введённых значений записывается соотношение между данными.
4.Разработка, выбор или адаптация формального решения задачи.
5.Разработка состава и структуры исходных данных и результатов.
6.Разработка алгор. решения задачи.
7.Разработка программы на заданном языке по составленному алгор.(исходный модуль .pas).
8.Компиляция – преобразование исходного текста программы в машинный код определённого формата(объектный код .obj).
9.Компоновка – к полученному объектному коду добавляются коды библиотечных процедур (sin, cos, …) из библиотеки TURBO.TPL. В результате компоновки формируется загрузочный модуль с расширением .ехе пригодный для выполнения.
10.Подготовка контрольных примеров для проверки правильности работы программы.
11.Тестирование программы (проверка правильности работы программы).
12.Подготовка документации на разработанную программу.
Б6. Алфавит(1),синтаксис(2),семантика(3) и словарь языка ПАСКАЛЬ(4).
1), 2), 3):Алгоритмический язык состоит из алфавита, правил составления текста (синтаксиса) и правил понимания смыслового содержания текста (семантика).
Алфавит – зафиксированный набор символов из которых может состоять текст.
Синтаксис – правило записи слов, выражений, операторов и др. языковых конструкций на данном языке.
Семантика – определённое смысловое содержание отдельных языковых конструкций.
Минимальные единицы языка, имеющие самостоятельный смысл, называются лексемами: словарь, комментарии, знаки операций, разделители и символьные строчки.
4):1.Ключевые слова, введённые разработчиками языка, - это ограниченный набор слов, который имеет фиксированное обозначение и определённый смысл: PROGRAM, BEGIN, READLN, WRITELN.
2.Идентификаторы – имена (названия), построенные по определённым правилам слова, предназначенные для обозначения (идентификации) констант, переменных, типов данных, процедур и т.п., определённых программистом.
3.Числа делятся на целые и вещественны; целые же в свою очередь на десятичные и шестнадцатеричные, а вещественны – на числа с фиксированной точкой и на числа с плавающей точкой.
Лексемы:
Комментарий – фрагменты текста поясняющего характера, записанного с использованием допустимых слов и ограниченного скобками: (**), {}.
Знаки операций: простые (+, -, *, /) и составные (:=, >=, =).
Разделители – для отделения лексем друг от друга ( ; , ).
Символьные строки – последовательность символов, заключённых в апострофах.
Б7.Синтаксические диаграммы, как форма описания синтаксиса языка ПАСКАЛЬ.
Графический способ формального определения лексических единиц языка.
1. – терминальный символ.
2 - не терминальный символ.
3 дуги.
цифра
Б8.Структура программы.
Раздел описаний:
Program Pr1………… .заголовок программы
Uses………спецификация внешних модулей
Label………………………… раздел меток
Const…………… раздел описания констант
Type…………………………… раздел типов
Var…………………….…раздел переменных
Procedure………раздел процедур и функций
Function……… раздел процедур и функций
Begin…………….начало исполняемой части
… …….……….раздел операторов
End……………………………………… end
Операторы, константы и переменные:
Операторы – синтаксические конструкции, предназначенные, как для записи алгор. действий по преобразованию данных, так и для задания порядка выполнения других действий.
Константы – элементы данных, которые задаются в начале программы и не изменяются в процессе её выполнения.
Переменные – программный объект, который способен принимать различные значения, в соответствии с типом.
Б9.Стандартные типы данных: целый тип(1).
Стандартные типы данных:
- целый;
- вещественный;
- логический;
- символьный.
Тип данных задаёт область значений, которую могут принимать переменные данного типа, множество операций над этими значениями и внутр. представляет ЭВМ.
1):Представление в ЭВМ.
Целые числа представлены в ЭВМ с помощью двоичных чисел. Двоичные числа, состоящие из N бит можно представить двумя способами:
1.N бит без знака; 2.N бит со знаком.
Диапазоны:
1) 00…0(min)(N) 11…1(max)(N)=0 2^N-1
2)-0 0(N) +11…1(N-1)=-2^(N-1)…2^(N-1)-1
Б10.Логический тип данных.
Boolean.
True
False 1 байт
Логические функции, таблица истинности.
OR……логическое сложение (дизъюнкция)
XOR….исключение “или” (сумма по mod2)
AND…логическ. умножение (конъюнкция)
NOT………………….отрицание (инверсия)
Б11.Вещественный тип данных.
Представление:
Вещественные числа представляются внутри ЭВМ в полулогарифмической форме, состоящей из мантиссы и экспоненты, мантисса содержит значащие цифровые разряды, а экспонента задаёт числовой диапазон.
Действия со всеми типами данных, кроме real, могут быть выполнены специальными сопроцессорами, чтобы его подключить надо дать дерриктиву компьютера.{$N+}
Преобразование веществ. в целые.
TRUNC(X) – выделение целой части.
ROUND(X) – округление.
Выделение частей числа.
INT(X) – целая часть числа.
FRAC(X) – выделение дробной части.
Если при выводе вещественного числа не задан формат, то число выводится в следующем виде:
Х.ХХХХХХХХХХЕ(+-)dd (>0)
-X.XXXXXXXXXXE(+-)dd (Б14.Программирование линейных алгоритмов на языке ПАСКАЛЬ.
Оператор присвоения используется для присвоения переменной нового значения.
Составной оператор – группа операторов, заключающихся в операторные скобки (Begin End).
Написать про read и write.
Б16.Оператор выбора (варианта).
Используется в тех случаях, когда в зависимости от какого-либо выражения выбрать один из нескольких путей (кол-во путей не ограничено).
Пример:
Program nedellja;
Var w:byte; {номер дня недели}
Begin writeln(‘введите номер дня недели’);
Readln(n);
Case n of
1:writeln(‘пон.’);
2:writeln(‘втор.’);
3:writeln(‘ср.’);
4:writeln(‘четв.’);
5:writeln(‘пятн.’);
6:writeln(‘субб.’);
7:writeln(‘вос.’);
else writeln(‘Такого дня нет’); end {case}
end.
Б17.Оператор цикла с предусловием.
WHILE логическое выражение DO оператор
Б18.Оператор цикла с постусловием.
REPEA оператор UNTIL логическое выражение
Б19.Оператор цикла с параметром (с заданным числом повторений).
to (+1)
FOR имя := выр.1 выр.2 Dо оператор
downto (-1)
1.Цикл for не выполняется ни разу, если начальное значение (выр.1) > (для downto 2.Начальное и конечное значения управляющей переменной не должны изменяться внутри цикла.
3.Последнее значение управляющей переменной не определено после нормального выхода из цикла.
4.Нельзя задать шаг, отличный от 1 или -1.
Б20.Нестандартные типы данных: перечисляемый(1) и интервальный(2) типы.
1): - упорядоченная последовательность имён.
I вар.
Type
Wremja= (vesna, leto, osen, zima);
Svetofor= (krasn, gelt, zel);
Var
Sezon: wremja;
Svet: svetofor;
II вар.
Var
Sezon: (vesna(0), leto(1), osen(2), zima(3));
Svet: (krasn(0), gelt(1), zel(2));
Упорядоченная последовательность значений нумеруется!!!
Операции:
1.Отношения (=,,,>=,=leto zel ---false
2.Стандартные функции.
SUCC(X) – последующий;
Succ(gelt) --- zel;
PRED(X) – предыдущий;
Pred(osen) --- leto;
ORD(X) – номер.
Ord(zima) --- 3.
2):Отрезок любого скалярного типа, кроме real.
Константа . . Константа
Type
M=5…10; {базовый целый}
Bukva=’а’ .’я’; {базовый char}
Скалярный тип, на котором строится отрезок, называется базовым.
Zifra=’0’…’9’;
Var a, b: M; b: bukva; a: zifra;
Б22.Строковые типы данных. Char.
Строка – последовательность символов кодовой таблицы ПК.
Определение констант и переменных строкового типа.
String…[…константа (max длина строки)…]
Type
Stroka=string[20]; {или var S2: string[20]}
Var S2: stroke;
Доступ к отдельному символу может быть получен с помощью индекса.
S2= ‘программа’; S2[4]=‘г’; S2[0]=9;
Операции над строками.
1.Операция отношения (=, Строки сравниваются посимвольно, слева направо.
При обнаружении первого не совпадающего символа принимается решение 0 > 2.Операция сцепление.
a:= ‘семестр’; b:= ‘первый’; c:= ‘второй’;
b+a - ‘первый семестр’; c+a - ‘второй --||--‘
3.Стандартные процедуры и функции.
Delet(st{string},pos,n{byte}) – из строки st, с позиции pos удаляется n символов.
Insert(S1,S2{string},pos{byte}) – вставка S1 в S2 с позиции pos.
Str(V{real},St{string}) – преобразование числового значения V в строку St.
Val(St{string},V{real},C{byte}) –преобразование строки St в число V, C=0, если нет ошибки.
Copy(St{string},pos,n{byte}) – выделение из строки St, с позиции pos, n символов.
Length(St{string}) – определение длины строки.
Pos(S1,S2{string}) – обнаружение первого появления строки S1 в строке S2.
Concat(St1,St2,…) – Сцепление строк, равноценное знаку “+”.
Ввод(1) и вывод(2) строк.
(1)При вводе строк иметь ввиду: так как пробел тоже символ, то конец строки – клавиша “ввод”.
(2)При выводе в списке выводимых данных можно использовать выражение и формат, при использовании формата стока выравнивается по правому краю.
Б23.Организация подпрог. Процедуры. Описание процедур и обращение к ним.
(1)Подпрограмма – относительно самостоятельный фрагмент программы оформленный особым образом и снабжённый именем.
При решении многих задач возникает необходимость одни и те же последовательности операторов для различных данных. При этом для уменьшения размеров программ целесообразно выделить эти операторы в отдельную подпрограмму. Кроме того использование подпрог. позволяет реализовать принцип структурного программирования.
(2)Процедуры используются в тех случаях, когда необходимо получить один или несколько результатов.
(3)Описание процедур происходит в разделе описание процедур и функций.
Procedure…имя .список формальных параметров…;…блок…;
Формальные параметры – это те объекты, над которыми описаны действия в процедуре и которые заменяются фактическими параметрами при обращении к ней. Параметры:
1.Значения (копия значения);
2.Перемещения (передача адреса);
3.Процедуры;
4.Функции.
1.Определяют исходные данные для работы процедуры, которые не желательно изменять в процессе её выполнения.
2.Определяют, как правило, выходные данные процедуры, которые передаются в основную программу.
Фактические параметры должны соответствовать формальным параметрам по количеству, типу и месту расположения.
Б21.Структурированные типы данных: массивы.
Структурированные типы данных составляются из других типов данных, т.е. имеют в своём составе некоторые компоненты.
Массив – группа данных одинакового типа, имеющая одно имя.
Индекс – обозначение порядкового номера элемента.
Элемент массива – индексированная переменная.
Массив М1 (одномерный, вектор); М[1], М[2],…
Массив М2 (двумерный, матрица); М[1,1], М[1,2], М[2,1], М[2,2].
Описание массива.
Array[ .тип индекса .] of .тип элемента
Для ввода и вывода используются циклы.
Пример!!!
Б24.Функции. Описание функций и обращение к ним.
В результате выполнения некоторых операций вычисляется одно единственное значение, присваиваемое имени функции.
Обращение к ф-ии ,как и к стандартным ф-ям, осуществляется из выражения, в котором в качестве операнда записывается имя ф-ии и фактические параметры.
После выполнения ф-ии вычисленные значения присваиваются имени ф-ии и передаётся выражение.
Function Fun(a, b: real): real;
…end; {fun}
…y:=Fun(x, 2); writeln(fun(k, l));
if fun(m, n) > 0 then…
Б25.Рекурсивные процедуры и ф-ии.
При использовании проц. и ф-ий встречается обращения их к самим себе, называемое рекурсивным.
Рекурсия возможна благодаря тому, что при вызове процедуры динамически создаются новые локальные переменные.
X^n=1(если n=0); X^n=X*X^(n-1)(если n >0);
n!=1(если n=0); n!=n*(n-1)!(если n > 0). Пример!!!
Б26.Записи. Описание записей. Оператор присоединения (а).
Данные типа запись представляют собой совокупность логически связанных элем-ов различного типа, которые называются полями.
Для обращения к полю записи используется составное имя, в котором необходимо указать путь от вершины до нужного поля.
Ввод, вывод и др. операции над записью выполняются для отдельных полей, в соответствии с их типами.
(а)Позволяет сократить текст программы за счёт исключения повторяющихся частей: имён полей, записей.
With .имя поля, имя записи(,) .do .оператор
Б27.Записи с вариантной частью(1).
Case имя сектора (:) тип of конст. (,)
(:) ( список полей )
Б28.Множества.
Множества – ограниченный, не упорядоченный набор различных элементов базового типа.
Set…of…порядковый тип
Z:=[0,2 4,8]; b:=[‘a’ ‘d’, ‘k’];
g:=[Penza, Moscow].
Элементы множества не упорядочены, поэтому:
[1,3,7]=[3,7,1]=[1,7,3,1,3,7];
a:=[3 6,8 10]; b:=[2 5,8 9];
a*b---[3 5,8]; a+b---[1 6,8 10];
a - [4,6,8]---[1,3,5,10];
Реализовать вычисление первых простых чисел до заданного n методом “решета Эратосфена”; n=15.
ISH=[2,3,4,5,6,7,8,9,10,11,12,13,14,15];REZ[?]
m=2 REZ[2]
m=3 REZ[2,3]
m=5 REZ[2,3,5]
m=7 REZ[2,3,5,7]
m=11 REZ[2,3,5,7,11]
m=13 REZ[2,3,5,7,11,13]
Б29.Файл. Стандартные процедуры работы с ф. Не типизированные ф.(а)
Файл – именованная область памяти на внешнем носителе, предназначенная для хранения данных.
Упорядоченная совокупность произвольного числа однотипных компонент с последовательным методом доступа.
В отличии от массивов в файлах место каждого элемента не определено индексом, число элем. не задано, каждая компонента файла становится доступной, только после перебора всех предшествующих компонент.
Для доступа к записи файла используется текущий указатель, который в начале работы с файлом должен указывать на начальную запись, имеющую № 0. При выполнении операции текущий указатель автоматически перемещается.
Типы файлов:
1.Типизированные – записи которых имеют жёсткую структуру, типа record.
2.Текстовые – состоящие из символов и строковых структур.
3.Нетипизированные – файлы без какой-либо структуры.
Процедуры и ф-ии для всех типов ф-ов.
1.Assign(имя файла,‘имя системного ф.’) устанавливает связь между переменной файлового типа в ПАСКАЛЬ-программе и конкретными физическими файлами на магнитных носителях.
Assign(f, ‘A:\file.dat’);
2.Reset(имя файла) – подготовка к чтению;
Rewrite(имя файла) – подготовка к записи;
3.Read(F) – чтение из файла F
Write(F) – запись в файл F
4.Eof(F) – достигнут ли конец файла при записи?
5.Uose(F) – закрытие файла.
6.Erase(F) – стирание файла.
7.Rename(F, ‘STR’) – переименование.
8.Truncate(F) – усечение файла по текущему положению указателя
9.Файлы параметров процедур могут передаваться по ссылке.
(а)Не типизированными файлами является последовательность байтов без какой-либо структуры. В них можно на примитивном уровне очень быстро и эффективно реализовать доступ к блокам, содержащим требуемое число байтов.
Особенности исполнения стандартных процедур и функций.
Rewrite(F, lblock); Reset(F, lnlock);
Lblock – размер передаваемого блока в байтах (по умолч. 128 байт).
Filesize, Filepos, Seek – используют компоненты длиной lblock каждый.
Blockread(F, buf, nmax, n) – из F в buf считывается максисум nmax блоков; n – фактически прочитано.
Б30.Текстовые файлы.
Текстовые файлы отличаются от типизированных следующими признаками:
1.Их элементами являются символы.
2.Их текстовые строки делятся с помощью метода конца строки, генерируемых при нажатии клавиши ENTER.
3.Спомощью процедуры readln метод строки считывается с помощью writeln метода конца строки.
4.При чтении из файла и записи в файл данные преобразуются автоматически.
Стандартные процедуры и функции для текстовых файлов:
Eoln(F) – конец строки;
Read(f, x1, x2,…xn) – чтение из f в x1…xn;
Write(f, x1,x2,…xn) – запись в f из х1…хn;
Append(f) – открыть текстовый файл для дополнения.
Б40.Графические проц. и ф-ии для работы с графическими примитивами типа “линия”.
Line(x1,y1,x2,y2{integer}) – вычерчивается отрезок прямой от (х1, у1) до (х2, у2)
LineTo(x,y) – от текущей позиции курсора до (x,y);
LineRel(dx,dy) – от текущей позиции курсора до ((x+dx),(y+dy));
MoveTo(x,y) – курсор устанавливается в точку (x,y);
MoveRel(dx,dy) - курсор устанавливается в точку ((x+dx),(y+dy));
PutPixel(x,y,Color) – закрашивает точку (x,y) в цвет Color.
Б41.Графические проц. и ф-ии для работы с дугами и геометрическими фигурами.
Arc(x,y{integer},w1,w2,r{word}) – из центра с координатами (x,y) вычерчивается дуга с радиусом r, от угла w1 до угла w2.
Circle(x,y,r) – окружность.
Rectangle(x1,y1,x2,y2) – прямоугольник.
DrawPoly(n,x,y) – контур многоугольника, где n – число вершин; array[1 n+1,1 2] of integer.