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

Алгоритм

Лекция 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., представленный блоксхемой.

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

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

• язык программирования (ЯП)

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

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

Правила записи программ на 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;

Найти: x¹⁵;

Решение 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. Возникает задача:

найти xⁿ за минимальное число ходов.

Об этом читай тему.

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

Синтаксис

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>

Семантика

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

Пример 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

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

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

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

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

Ссылки

• Вторая часть конспекта
• Другие конспекты