Основы программирования — Осенний семестр; Михалкович С.С.; 2008; I — различия между версиями

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Основные операторы. Их синтаксис и семантика.)
Строка 95: Строка 95:
 
* ''РБНФ'' (Расширенные БНФ)
 
* ''РБНФ'' (Расширенные БНФ)
  
:'''[]''' — 0 или 1 повторение.  
+
:'''[]''' 0 или 1 повторение.  
:'''{}''' — 0 и более повторений
+
:'''{}''' 0 и более повторений
  
 
<tt>'''Пример.'''</tt>
 
<tt>'''Пример.'''</tt>
Строка 523: Строка 523:
  
 
<small>'''Лекция 9'''</small>
 
<small>'''Лекция 9'''</small>
 
==Процедуры==
 
 
Пример вычисления среднего арифметического и среднего геометрического.
 
 
Синтаксис описания процедуры. Синтаксис вызова процедуры.
 
 
Входно-выходные параметры. Процедура Swap.
 
 
Формальные и фактические параметры. Семантические правила при вызове.
 
 
<H3>Функции</H3>
 
 
Синтаксис. Вызов функции. Переменная Result.
 
 
Примеры: Sign, ReadInteger и т.п., SumN.
 
 
Сравнение с процедурами на примере Sign.
 
 
Нежелательность var-параметров в функциях.
 
 
Стандартные подпрограммы с передачей по ссылке: readln, Inc, Dec.
 
 
<H3>Локальные и глобальные переменные</H3>
 
 
Инициализация глобальных и локальных переменных значениями по умолчанию.
 
 
Понятие пространства имен.
 
 
Глобальные переменные и побочный эффект.
 
 
<small>'''Лекция 10'''</small>
 
 
Понятие области видимости и времени жизни объекта.
 
 
Изменение глобальной переменной как побочный эффект. Нежелательность такого изменения. При необходимости изменения глобальной переменной - передать ее как параметр.
 
 
Принцип локальности: чем локальнее объявлена переменная, тем лучше. Распространение принципа локальности на внутриблочные переменнные: вспомогательные переменные, используемые в блоке алгоритма, следует делать внутриблочными.
 
 
Понятие ссылки как другого имени объекта. Внутренний механизм передачи параметра по ссылке.
 
 
Перегрузка имен подпрограмм (на примере swap).
 
 
<small>'''Лекция 11'''</small>
 
 
Параметры по умолчанию - на примере DoOp(a,b: integer; var res: integer; op: char := '+').
 
 
Предварительное объявление подпрограмм.
 
 
==Процедурные переменные==
 
 
Процедурные переменные как параметры подпрограмм. Функции обратного вызова (callback).
 
 
Пример.
 
<source lang="delphi">
 
procedure DoActions(Act1, Act2, Act3: procedure);
 
begin
 
  Act1;
 
  Act2;
 
  Act3;
 
end;
 
</source>
 
 
Пример. Вычисление определённого интеграла методом прямоугольников - Integral(a,b,N,f)
 
 
Вызов нескольких действий. Операции += и -= для процедурных переменных.
 
 
Оператор exit досрочного завершения подпрограммы
 
 
<small>'''Лекция 12'''</small>
 
==Методы разработки подпрограмм==
 
 
Метод "сверху вниз" и метод "снизу вверх" (на примере таблицы простых чисел).
 
 
Когда эффективен каждый метод:
 
 
* сверху-вниз - когда задача четко поставлена и имеется четкий алгоритм ее решения;
 
* сниз-вверх - когда задача нечетко поставлена. когда решается группа взаимосвязанных задач из дной области, когда в задаче нет четко выделенного главного алгоритма, когда необходимо приступать к решению задачи, попутно уточняя алгоритм.
 
 
<H3>Вызов подпрограммы на этапе выполнения</H3>
 
 
Понятие программного стека.
 
 
Запись активации, ее структура.
 
 
Алгоритм вызова подпрограммы на этапе выполнения.
 
 
<small>'''Лекция 13'''</small>
 
 
Пример, иллюстрирующий алгоритм вызова процедуры.
 
 
Замечания:
 
 
* о накладных расходах, связанных с вызовом маленьких и больших подпрограмм
 
* о проблеме переполнения программного стека при наличии больших локальных переменных и при передаче больших локальных переменных п значению
 
* о проблеме доступа к глобальным переменным
 
 
==Модули==
 
 
Определение
 
 
Структура модуля с разделами интерфейса и реализации.
 
 
Принцип сокрытия информации.
 
 
Преимущества разделения модуля на интерфейс и реализацию.
 
 
<small>'''Лекция 14'''</small>
 
 
Упрощенная структура модуля.
 
 
Разделы инициализации и финализации.
 
 
Схема компиляции программы с модулями.
 
 
Алгоритм поиска имен в модулях. Модуль как пространство имен.
 
 
Системный модуль PABCSystem
 
 
<small>'''Лекция 15'''</small>
 
 
Документирующие комментарии ///
 
 
Библиотеки. Отличие библиотек от модулей. Подключение библиотек в PascalABC.NET.
 
 
Перечислимый и диапазонный типы. Стандартные функции Ord Pred Succ. Стандартные процедуры Inc Dec.
 
 
Использование перечислимого типа в for и case.
 
 
==Массивы==
 
 
Понятие структурированного типа данных.
 
 
Определение массива.
 
 
Описание массивов. Тип массива. Тип индексов массива. Понятие порядкового типа.
 
 
<small>'''Лекция 16'''</small>
 
 
Обращение к элементам массивов.
 
 
Выход за границы диапазона. Контроль выхода в Delphi и PascalABC.NET.
 
 
Динамические массивы. Хранение в памяти.
 
 
Инициализация массивов.
 
 
Присваивание массивов. Сравнение массивов.
 
 
Присваивание a := nil для динамических массивов.
 
 
Цикл foreach.
 
 
Именная и структурная эквивалентность типов.
 
 
<small>'''Лекция 17'''</small>
 
<H3>Массивы как параметры подпрограмм</H3>
 
 
При передаче статического массива должна соблюдаться именная эквивалентность
 
<source lang="delphi">
 
  procedure xxx(a: array [1..100] of integer); // неверно
 
 
  type IArr = array [1..100] of integer;
 
  procedure yyy(a: IArr);
 
</source>
 
Передавать массив по значению крайне неэффективно (т.к.происходит копирование всех элементов на стек). Его следует передавать по ссылке: для этого есть специальное ключевое слово <tt>const</tt>, которое также запрещает изменять данные внутри п/п.
 
<source lang="delphi">
 
 
  procedure zzz(const a: IArr);
 
  procedure sss(var a: IArr);
 
 
</source>
 
Динамический массив
 
можно передавать в виде <tt>array of integer</tt>, т.к. для него определена структурная эквивалентность типов.
 
<source lang="delphi">
 
  procedure ttt(a: array of integer);
 
</source>
 
Передавать массив по ссылке необходимо только если внутри п/п нужно изменить длину массива.
 
Иначе можно передавать по значению, т.к. при вызове п/п на программный стек кладется только адрес участка памяти, хранящего значения элементов массива, а значит все изменения формального массива-параметра внутри п/п меняют соответствующий ему фактический параметр.
 
Массивы как возвращаемые значения функции
 
 
Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.
 
 
<h3>Переменное число параметров подпрограмм</h3>
 
 
П/п можно создавать с переменным количеством параметров.
 
Для этого исп. ключевое слово params.
 
При этом такие параметры, перечисленные через запятую, на этапе выполнения упаковываются в динамический массив, и п/п внутри работает именно с ним.
 
Пар-р params может быть только один и должен находиться последним в списке пар-ов.
 
 
<small>'''Лекция 18'''</small>
 
==Шаблоны подпрограмм==
 
 
Часто требуется выполнять одно и то же действие для разных типов данных.
 
В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
 
 
Выход - шаблоны.
 
 
Пример:
 
 
  procedure Print<T> (array of T);
 
 
В момент вызова п/п происходит:
 
 
* выведение типов шаблона по фактическим параметрам
 
* инстанцирование - подстановка конкретных типов шаблонов и генерация кода подпрограммы с этими конкретными типами.
 
 
Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
 
 
<H3>Задачи на одномерные массивы</H3>
 
 
* инвертирование массива (шаблон)
 
* поиск элемента в массиве - найти и вернуть индекс (шаблон)
 
 
можно с for и break,
 
 
можно и другим способом - с while
 
 
* поиск с барьером (шаблон). Его преимущества
 
* минимальный элемент массива и его индекс
 
* слияние двух упорядоченных массивов в один упорядоченный (барьер)
 
* сдвиг элементов массива влево (шаблон)
 
 
знакомство со значением default(T), Т - тип
 
 
<small>'''Лекция 19'''</small>
 
 
<h3>Задачи на одномерные массивы</h3>
 
 
pas-файл с задачами
 
 
doc-файл
 
 
используется тип IArr =  array [1..size] of integer
 
 
* сдвиг элементов массива вправо (ShiftRight)
 
 
[ два варианта определения граничных значений цикла (от n-1 до 1; от n до 2) ]
 
 
* циклический сдвиг элементов массива вправо (CycleShiftRight)
 
* удаление элемента по заданному индексу (Delete)
 
* вставка элемента по заданному индексу (Insert)
 
 
<H3>Задачи с процедурными переменными в качестве параметров</H3>
 
 
Определяется тип IUnPred = function (x: integer): boolean
 
 
* поиск элемента по заданному условию (Find)
 
* количество элементов, удовлетворяющих условию (Count)
 
* условный минимум (MinElem)
 
* удаление всех элементов, удовлетворяющих условию (DeleteAll)
 
 
'''Примечание.''' Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы
 
 
<small>'''Лекция 20'''</small>
 
==Сортировки==
 
 
* '''Выбором''' (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)
 
 
* '''Пузырьковая'''
 
 
Это самый компактный алгоритм сортировки. Его можно оптимизировать, проверяя случай "холостого" прохода по элементам массива. Т.е. если за проход ни один элемент не изменил позицию, значит массив уже отсортирован и проверять дальше нет смысла.
 
 
* '''Вставками''' (вставка элемента из еще не упорядоченного участка массива в "нужную" позицию отсортированного, для чего сдвиг части элементов вправо и вставка нового в освободившуюся позицию)
 
 
'''Замечание.''' Рассмотренные виды сортировки не являются самыми эффективными.
 
Асимптотическая сложность алгоритмов
 
 
'''Определение.''' Число шагов алгоритма асимптотически равно  Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:
 
 
    c1*f(n) ≤ число шагов ≤ c2*f(n)
 
 
'''Замечание 1.''' Для рассмотренных алгоритмов сортировки асимптотическая сложность = Θ(n<sup>2</sup>).
 
 
'''Замечание 2.''' Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).
 
 
<small>'''Лекция 21'''</small>
 
==Алгоритм бинарного поиска в отсортированном массиве==
 
 
Его асимптотическая сложность - Θ(logn).
 
Двумерные массивы
 
 
Двумерный массив как матрица (соответствие индексов строкам и столбцам)
 
 
Элементы строки. Элементы столбца (рисунки)
 
 
Понятие замороженного индекса
 
 
<H3>Задачи на двумерные массивы</H3>
 
 
* Вывод матрицы
 
** внешний цикл по строкам
 
** если внешним сделать цикл по столбцам будет выведена транспонированная матрица
 
 
* Сумма элементов в j-том столбце
 
 
* Сумма элементов в каждом столбце
 
** использование функции для нахождения суммы в j-ом столбце
 
* Минимальный элемент в каждой строке
 
** в отличие от предыдущей задачи, для реализации не создается дополнительная п/п.
 
 
'''Замечание.''' Решать такие задачи можно и реализуя алгоритм полностью,  и создавая для этого дополнительные п/п. Если задача несложная, то вполне можно пользоваться первым способом, однако если решение не очевидно, лучше выносить часть алгоритма в п/п, иначе код будет очень трудно читать.
 
 
* Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.
 
 
<small>'''Лекция 22'''</small>
 
 
* Поиск элемента в матрице
 
 
если для поиска используется функция, то при нахождении элемента выходить из циклов с помощью exit,
 
 
иначе удобно использовать goto КОНЕЦ_ВНЕШНЕГО_ЦИКЛА
 
 
==Записи==
 
 
<source lang="delphi">
 
type <имя записи>= record
 
  <поля записи>
 
end;
 
</source>
 
 
Поля записей
 
 
Инициализация записей при описании (на примере Student)
 
 
Доступ к полям записей. Точечная нотация.
 
 
'''Замечание.''' Для записей имеет место именная эквивалентность типов.
 
 
Передача записей в п/п (Print(s)). Запись как возвращаемое значение функции (s := ReadStudent;).
 
 
Передавать записи по значению неэффективно, т.к. копируются все поля. Поэтому следуют передавать их по ссылке  (с ключевым словом const - если значения полей не изменяются, и var - если внутри п/п их требуется изменить.
 
 
Оператор with.
 
 
<source lang="delphi">
 
with <переменная типа запись> do
 
begin
 
  <поле>:=<значение>
 
end;
 
</source>
 
 
Оператор удобен, когда нужно выполнить достаточное количество операций с одной и той же переменной (имя этой переменной и точка добавляются неявно перед всеми полями)
 
 
<H3>Методы в записях</H3>
 
 
На примере Student.Print.
 
 
Запись как пространство имен
 
 
Запись выступает для своих полей и методов в качестве модуля (поскольку является набором данных и связанных с ними процедур и функций, оформленных как единое целое).
 
 
Методы работают в некотором окружении, в роли которого выступают поля записи и другие методы.
 
 
Создается окружение при описании переменной типа запись.
 
 
* Сравнение s.Print и Print(s)
 
 
'''s.Print''' - объектно-ориентированный подход, доминирует объект, который сам выполняет над собой действие.
 
 
'''Print(s)''' - процедурно-ориентированный подход, главным является действие, выполняющееся над переменной.
 
 
* Метод Init - инициализатор полей записи.
 
 
<small>'''Лекция 23'''</small>
 
==Создание простейших графических объектов==
 
 
<source lang="delphi">
 
RPoint = record x, y: integer end;
 
RRectangle = record p1,p2: RPoint end;
 
</source>
 
 
Для каждого типа определяются методы Print, Draw, MoveOn
 
 
<H3>Записи как средство упаковки параметров</H3>
 
 
'''Пример.'''
 
Используем определенные типы записей для создания перегруженных версий процедур Rectangle и Line:
 
 
<source lang="delphi">
 
Rectangle(x1,y1, x2,y2: integer)
 
Rectangle(p1,p2: RPoint)
 
Rectangle(r: RRectangle)
 
 
Line(x1,y1, x2,y2: integer)
 
Line(p1,p2: RPoint)
 
Line(r: RRectangle)
 
</source>
 
 
<H3>Переменная типа запись как объект</H3>
 
 
В модуле можно выносить реализацию методов записи в раздел реализации. При этом в разделе интерфейса внутри определения типа запись описываются только заголовки методов, а в разделе реализации перед именем метода необходимо писать <Имя записи>.
 
 
Поля записи как состояние объекта.
 
 
Методы записи как действия, воздействующие на состояние объекта.
 
 
Методы делятся на две категории
 
* меняющие состояние объекта (MoveOn для RPoint)
 
* осуществляющие доступ к состоянию объекта на чтение (Draw для RPoint)
 
 
Сортировка массива записей.
 
 
<small>'''Лекция 24'''</small>
 
==Индексная сортировка==
 
 
Часто физически переставлять элементы массива или вообще невозможно, или долго (в силу достаточно большого размера, например).
 
В этом случае удобно использовать ''перестановку индексов'' вместо перестановки самих элементов.
 
 
Идея заключается в том, чтобы описать '''индексный массив''' index, который взаимооднозначно сопоставляет ''реальным'' индексам элемента ''виртуальные'' таким образом, чтобы относительно ''виртуальных'' массив оказался упорядоченным.
 
 
----
 
 
'''Пример.'''
 
 
Дан массив целых (с реальными индексами):
 
  '''5'''[1]  '''15'''[2]  '''3'''[3]  '''1'''[4]  '''9'''[5]  '''8'''[6]  '''20'''[7]  '''12'''[8]
 
 
А так выглядит отсортированный массив по виртуальным индексам:
 
  '''1'''[1]  '''3'''[2]  '''5'''[3]  '''8'''[4]  '''9'''[5]  '''12'''[6]  '''15'''[7]  '''20'''[8]
 
 
Т.е.
 
  index[1] = 4
 
  index[2] = 3
 
  index[3] = 1
 
  index[4] = 6
 
  index[5] = 5
 
  index[6] = 8
 
  index[7] = 2
 
  index[8] = 7
 
 
----
 
Соответственно, алгоритм сортировки меняется таким образом, что вместо перемены местами самих элементов упорядочиваемого массива меняется '''содержимое элементов index'''.
 
 
Вначале удобно положить элементы index соответствующими '''тождественной''' подстановке (т.е. a[i] = i).
 
<source lang="delphi">
 
type CmpFunc = function (const s1,s2: Student): boolean;
 
 
procedure BubbleIndexStudentSort(const a: StArr; var Index: IArr; n: integer; Cmp: CmpFunc);
 
begin
 
  for var i:=1 to n do
 
    Index[i] := i;
 
  for var i:=n downto 2 do
 
  for var j:=1 to i-1 do
 
    if Cmp(a[Index[j+1]],a[Index[j]]) then
 
      Swap(Index[j+1],Index[j]);
 
end;
 
 
procedure WriteArrByIndex(const a: StArr; const Index: IArr; n: integer);
 
begin
 
  for var i:=1 to n do
 
    writeln(a[Index[i]].name,' ',a[Index[i]].course,' ',a[Index[i]].group);
 
end;
 
</source>
 
 
==Множества==
 
 
Описание множеств. Множества-константы. Пустое множество.
 
 
Операции над множествами:
 
s1+s2 - объединение
 
s1*s2 - пересечение
 
s1-s2 - разность
 
s += s1
 
s -= s1
 
s *= s1
 
s1<s2 - строгое вложение
 
s1<=s2 - нестрогое вложене
 
s1>s2 - строгое вложение
 
s1<=s2 - нестрогое вложене
 
i in s - принадлежность
 
 
Include(s,i);
 
Exclude(s,i);
 
Вывод множеств.
 
 
Цикл foreach по множеству.
 
 
Пример использования множеств: решето Эратосфена.
 
Алгоритм.
 
 
<small>'''Лекция 25'''</small>
 
<H3>Алгоритм Эратосфена</H3>
 
 
Код алгоритма Эратосфена
 
<source lang="delphi">
 
const n = 10000;
 
var primes: set of byte;
 
begin
 
  primes := [2..n];
 
  for var i:=2 to round(sqrt(n)) do
 
  begin
 
    if not (i in primes) then
 
      continue;
 
    var x := 2*i;
 
    while x<=n do
 
    begin
 
      Exclude(primes,x);
 
      x += i;
 
    end;
 
  end;
 
  for var i:=0 to n do
 
    if i in primes then
 
        write(i,' ');
 
end.
 
</source>
 
 
<H3>Статические методы записей</H3>
 
<source lang="delphi">
 
type RRectangle = record
 
  class function EqualSquare(const r1,r2: RRectangle): boolean;
 
  class function CreateRandom: RRectangle;
 
end;
 
</source>
 
 
<H3>Символы</H3>
 
 
Коды символов. Однобайтовые и двухбайтовые кодировки.
 
ASCII - стандарт на символы с кодами 0..127.
 
Unicode.
 
Однобайтовые кодировки: Windows, DOS (CP866), Koi8
 
 
Литеральные константы-символы:
 
#13 - символ возврата "каретки"
 
#10 - символ перехода на следующую строку
 
#9  - символ табуляции
 
 
<H4>Стандартные подпрограммы работы с символами</H4>
 
OrdUnicode(c)
 
ChrUnicode(i)
 
Succ(c)
 
Pred(c)
 
Inc(c,5)
 
Dec(c,5)
 
Ord(c)
 
Chr(i)
 
UpperCase(c)
 
LowerCase(c)
 
 
Для символов с кодами 0..127
 
OrdUnicode(c)=Ord(c)
 
ChrUnicode(i)=Chr(i)
 
 
char - тип, содержащий ряд статических методов:
 
 
char.IsDigit(c)
 
char.IsLetter(c)
 
char.IsLetterOrDigit(c)
 
char.IsLower(c)
 
char.IsUpper(c)
 
char.ToLower(c)
 
char.ToUpper(c)
 
 
<small>'''Лекция 26'''</small>
 
==Строки==
 
 
Тип string
 
 
Отводится память (до 2 Гб), равная длине строки, плюс некоторая дополнительная информация
 
 
Строки - массивы символов, индексируемые с 1: s[i] - i - тый символ строки.
 
var s := 'IT'; // s[1]='I', s[2]='T'
 
 
Операции со строками:
 
 
s1+s2 
 
s1 += s2 
 
s1<s2 
 
...
 
 
<H3>Основные подпрограммы работы со строками</H3>
 
 
'''Length(s)''' - функция, возвращающая длину строки s
 
 
'''SetLength(s,n)''' - процедура, устанавливающая длину строки s равной n
 
 
'''Copy(s,from,len)''' - функция, возвращающая подстроку s с позиции from длины len
 
 
'''Insert(subs,s,form)''' - процедура, вставляющая подстроку subs в строку s с позиции from
 
 
'''Delete(s,from,len)''' - процедура, удаляющая из строки s len символов с позиции from
 
 
'''Pos(subs,s)''' - функция, возвращающая позицию первого вхождения подстроки subs в строку s или 0, если подстрока не найдена
 
 
'''PosEx(subs,s,from=1)''' - функция, возвращающая позицию первого вхождения подстроки subs в строку s, начиная с позиции from, или 0, если подстрока не найдена
 
 
'''TrimLeft(s)''' - функция, возвращающая строку s, в которой удалены все начальные пробелы
 
 
'''TrimRight(s)''' - функция, возвращающая строку s, в которой удалены все заключительные пробелы
 
 
'''Trim(s)''' - функция, возвращающая строку s, в которой удалены все удаляет все начальные и заключительные пробелы
 
 
<h4>Преобразование строка <-> число</h4>
 
 
'''Str(x,s)''' - процедура, преобразующая целое или вещественное выражение x к строковому представлению и записывающая результат в строку s
 
 
'''Val(s,x,errcode)''' - процедура, преобразующая строку s к целому или вещественному значению и записывающая результат в целую или вещественную переменную x. Переменная errcode  - целая; если преобразование невозможно, то в errcode содержится номер первого символа, вызвавшего ошибку
 
 
'''IntToStr(i)''' - функция, преобразующая целое x в строку
 
 
'''StrToInt(s)''' - функция, преобразующая строку s к целому; может генерировать исключение
 
 
'''FloatToStr(i)''' - функция, преобразующая вещественное x в строку
 
 
'''StrToFloat(s)''' - функция, преобразующая строку s к вещественному; может генерировать исключение
 
 
<H3>Некоторые задачи на строки</H3>
 
 
Посимвольная обработка
 
 
* Строка 'ABCD...XYZ'
 
* Сумма всех цифр в строке s
 
 
Использование стандартных подпрограмм
 
 
* Вывести индексы всех вхождений подстроки s1 в s (на Delete, PosEx)
 
 
==Ссылки==
 
*[[Конспекты|Другие конспекты]]
 

Версия 14:18, 29 января 2009

Содержание

Алгоритм

Лекция 1

Свойства алгоритма

  • дискретность
  • элементарность команд
  • определенность команд
  • каждая команда имеет четкое однозначное значение
  • конечность
  • каждый А. должен когда-то завершаться при любом наборе исходных данных
  • результативность
  • после выполнения А. известно, что считать результатом
  • массовость
  • применимость ко множеству исходных данных

Связанные понятия

Спецификация задачи — точное, однозначное описание задачи. Включает формулировку входных и выходных данных.

Исполнитель алгоритма — устройство, имеющее некоторую систему команд, и способное их исполнять.

Процессор — исполнитель машинных кодов.


Пример.

Дано: x,y,z.
Найти max

А.1. (словесное описание).

Если x>y и x>z, то максимум - это x
Если y>x и y>z, то максимум - это y
Если z>x и z>y, то максимум - это z

А.2. (псевдокод).

max := x
Если y<max то max := y
Если z<max то max := z


Эквивалентными называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных.

Способы описания алгоритмов

  • словесный
  • псевдокод
  • блок-схемы

Пример. А.2., представленный блоксхемой.

2.JPG
  • диаграммы деятельности (activity diagram) UML

Пример. А.2., представленный диаграммой деятельности

2-1.JPG
  • язык программирования (ЯП)

Команды алгоритма также называются:

  • операторы Я.
  • инструкции Я.


Правила записи программ на Object Pascal

По Шпаргалке

Пример программы, вычисляющей длину и площадь круга.
Общие правила записи программ на Паскале. Оформление, комментарии

PascalABC.NET. Как скачать, инсталлировать. (сайт системы программирования PascalABC.NET)

Лекция 2

Синтаксис и семантика ЯП

Определения

Синтаксис — формальные правила описания конструкций ЯП.

Семантика — описывает смысл конструкций ЯП, а также задает ряд ограничений.

Способы описания синтаксиса

  • БНФ (Бэкуса-Наура формы, 1960, Алгол-60).

Пример.

<цифра> ::= 0|1|2|3|4|5|6|7|8|9
<идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>

0, 1, ... 9

называют терминалами (лексемами) — это "конечные символы", т.е. по умолчанию известные в ЯП.

<цифра>

так называемый нетерминал (нетерминальный символ).
Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется рекурсивным (как определение нетерминала <идентификатор>)
  • РБНФ (Расширенные БНФ)
[] — 0 или 1 повторение.
{} — 0 и более повторений

Пример.

<идентификатор> ::= <буква> {<буква> | <цифра>}
  • Синтаксические диаграммы (Вирт, Паскаль)


Грамматика языка — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.

Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные семантические правила.


Замечание 1. Способы 1-3 эквивалентны.

Замечание 2. Синтаксис определяет лексемы языка.


Лексемы Паскаля

  1. спецсимволы: := += *
  2. ключевые слова (begin, end, if, for)
  3. идентификаторы (a, b1)
  4. константы (2, 'ABC', #5)
  5. комментарии (3 вида)
{...}
(*...*)
//...

Обзор современных ЯП

(самостоятельно на форуме)


Переменные и их описание

Основные сведения

Переменная — это ячейка памяти компьютера, имеющая имя и тип.

Тип определяет размер переменной и множество принимаемых ею значений.

В языке Pascal любая переменная перед использованием должна быть описана.

Обычно переменные описываются в разделе описаний.


Синтаксис в виде РБНФ

<программа>::= [program <имя>;] 
               <раздел описаний> 
               begin
                 <операторы>
               end.
<операторы>::= <оператор>{; <оператор>}
<раздел описаний>::= {<секция раздела описаний>}
<секция раздела описаний>::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>...

Пример секции описания переменных.

var
   a,b: real;
   i: integer;
<секция описания переменных>::= var<подсекция>{< подсекция>}
<подсекция>::= <список имен>: <тип>;
<список имен>::= <имя>{,<имя>}
<тип>::= <имя>


Внутриблочные переменные

В PascalABC.NET возможно внутриблочное описание переменных:

begin
  var i,j: integer;

  var r: real:=5.2;

  var Pi:=3.14;

В последнем случае происходит автоопределение типов.

(синтаксис внутриблочных описаний на дом)


Типы

  • Целые
integer (4 байта)
shortint (1)
smallint (2)
int64 (8)
  • Вещественные
real (8)
single (4)
  • Символьные
char (2 — Unicode)
  • Строковые
string
string[200]
shortstring = string[255]
  • Логический
boolean (1) | [True False]


Основные операторы. Их синтаксис и семантика.

Оператор присваивания :=

Синтаксис

<переменная> := <выражение>

Пример использования оператора присваивания.

a := ( 3 + 5 ) * 8; 
b := a + 2;

Семанитика

Вычисляется выражение в правой части, при этом вместо имен переменных подставляются их значения. Затем результат вычисления записывается в переменную в левой части.

Ограничение. Тип выражения должен быть совместим по присваиванию с переменной. Например:

  • одинаковые типы совместимы.
  • выражение типа integer можно присвоить переменной типа real, обратное неверно.

Операторы присваивания += и *=

Пример.

d += 1; //прибавить 1 к d
d *= 2; //умножить d на 2

Лекция 3

Примеры использования :=

  • Перемена местами двух значений.
Дано: x, y;
var x, y: integer;
begin
  read( x, y );
  var v:= x;
  x:=y;
  y:=v;
  writeln ( x, ' ', y );
end.

Это стандартное решение. В PascalABC.NET на основе этого алгоритма определена стандартная процедура Swap( x, y ).

Однако, существуют и другие решения. Например:

var x, y: integer;
begin
  read( x, y );
  x:=x + y;
  y:=x - y;
  x:=x - y;
  writeln ( x, ' ', y );
end.


  • Использование промежуточных переменных в вычислениях.
Дано: x: real;
Найти: x15;

Решение 1.

y:= x*x;
z:= y*y;
t:= z*z;
p:= t*z;
q:= p*x*y;

Решение 2.

y:= x*x;
z:= y*x;
t:= z*y;
p:= t*t*t;

Решение 3.

y:= x*x;
x:= x*y*y;
t:= x*x*x;

Заметим, что в первом решении используется 6 операций умножения, в во 2м и 3м — 5. Возникает задача:

найти xn за минимальное число ходов.
Об этом читай тему.

Оператор ввода

Синтаксис

read (<список переменных>) | readln (<список переменных>)

Семантика

Происходит считывание данных с клавиатуры и запись их в переменные из <списка переменных>. Вводить данные нужно либо через пробел, либо по нажатию <Enter>, при этом программа не перейдет к выполнению следующего оператора, пока не будут считаны все данные.

С процедурой ввода связан ряд ошибок (например, если переменная используется в качестве делителя и вводится 0, или если должно быть получено целое число, а вводится 'ABC'). Эти ошибки нужно уметь обрабатывать.

Обработка ошибок ввода

Операторы, которые могут получать ошибку, заключаются специальный охранный блок try.

Синтаксис.

try
  ...
  readln(a);
  ...
except
  <обработка ошибки>
end;
<продолжение работы>

Семантика.

Если внутри блока try происходит ошибка выполнения, то все последующие операторы в блоке игнорируются и выполнение программы переходит к блоку except. По выходе из except программа продолжает работу.

Если ошибки не происходит, то выполняются все операторы в блоке try, блок except не выполняется и программа продолжает работу.

Оператор вывода

Синтаксис

write( <список выражений> ) | writeln( <список выражений> )

Семантика

Выражения в списке вычисляются и тих значения выводятся на экран. В случае writeln после выводао существляется переход на новую строку.

Форматы вывода

После каждого выражения в списке вывода можно использовать формат вывода в виде :a, где a — выражение целого типа. После вещественного типа — :a:b

a задает ширину поля вывода ( выравнивание по правому краю ).
b — количество знаков в дробной части.

Вывод с помощью write[ln]Format

Синтаксис.

writelnFormat( '<форматная строка>', <список выражений> )

Пример вывода с использованием форматной строки

writelnFormat( '{0} * {1} = {2}', a, b, a*b );

Будет выведено:

a * b = a*b

В форматной строке тоже можно использовать формат вывода.
{0, 10} — 10 это ширина поля вывода
{0, 10:f3} — 3 это количество знаков в дробной части для вещественного числа (показывает это спецификатор f).

Условный оператор

Синтаксис

if <условие> then <оператор1>
             else <оператор2>

Семантика

If.jpg

Примеры использования для решения задач

Пример 1. Нахождение минимума.
Дано: x,y;
Найти: min;

if x > y then
  min:= y
else
  min:= x;

Пример 2. Упорядочение a, b по возрастанию.
Ясно, что если a>b, — нужно поменять их местами.
Но тут одним оператором не обойтись. Для этого можно использовать составной оператор — один или больше операторов, заключенных в пару begin - end;:

if a > b then
begin
  var v:=b;
  b:=a;
  a:=v;
end;

Пример 3. Вычисление функции по взаимоисключающим веткам.
<math> y = \begin{cases} x, & x < 2 \\ x^2, & 2 < x < 3 \\ 1-x, & x \ge\; 3 \end{cases}</math>

if x < 2then
  y:= x
else
  if x < 3 then
    y:= x * x
  else
    y:= 1 - x;

Замечание.Если по ветви else располагается другой оператор if, то говорят, что возникает цепочка вложенных операторов if.

Пример 4. Найти среднее среди a, b,c (a, b,c попарно не равны). Эта задача имеет несколько вариантов решения.

if a<b then
  if a<c then
    if b<c then
      sr:=b
    else
      sr:=c
  else
    sr:=a
else
  if a>c then
    if b>c then
      sr:=b
    else
      sr:=c
  else sr:=a;

Очевидно, это не самое лучшее решение.
Можно воспользоваться стандартными функциями сравнения.

sr:= min( a, b );
if sr<c then
  sr:=min( max(a,b), c );


Самостоятельно.

  • Даны координаты вершин треугольника и точка M. Принадлежит ли M треугольнику.
  • Является ли 4-угольник ABCD корректно заданным.

Лекция 4

Арифметические выражения

Операции div и mod. x div y = x/y, округленное до ближайшего целого, x mod y = x - (x div y)*y. Примеры использования.

Порядок действий в арифметических выражениях

Тип арифметического выражения

Стандартные функции. Вычисление степени x^y. Логические выражения

Операции and, or, not, xor. Таблицы истинности.

Сокращенное использование логических выражений

Таблица приоритетов операций

  1. унарные
  2. * / div mod and shl shr
  3. + - or xor
  4. in отношения

Логические переменные. Пример с определением того, лежит ли точка на границе прямоугольника

Побитовые and, or, xor.

Операции shl, shr

Оператор case выбора варианта

Синтакстис, семантика

Примеры

  1. День недели
  2. цифра или буква

Лекция 5

Циклы с предусловием (while) и постусловием (repeat)

Заголовок, тело, итерации

Синтаксис и семантика

Отличия

Примеры

  1. Факториал
  2. Сумма четных двузначных

Моделирование repeat с помощью while

Моделирование while с помощью repeat

Зацикливание

Оператор цикла с параметром (for)

Синтаксис, семантика: моделирование for с помощью while, ограничения

Примеры

  1. Факториал
  2. Сумма четных двузначных

Примеры использования циклов I

  1. Табулирование функции. использование for и while

Погрешность округления вещественных чисел и вычислительная погрешность.

Лекция 6

Примеры использования циклов II

Поиск минимального среди введенных.

Рекуррентные последовательности.

Числа Фибоначчи.

Суммирование рядов (конечных и бесконечных).

Алгоритм Евклида нахождения НОД.

Разложение целого числа на простые множители.

Лекция 7

Примеры использования циклов III

Поиск заданного значения среди введенных.

Операторы break и continue. Как обойтись без них.

Схема Горнера.

Поиск нуля функции на отрезке.

Лекция 8

Вложенные циклы

Метод окаймления и метод последовательной детализации.

Переборные задачи. Необходимость оптимизации самого внутреннего цикла.

Вспомогательные алгоритмы и их параметры. Подпрограммы. Мотивировка введения подпрограмм.

Лекция 9