Основы программирования — первый семестр 08-09

К основной странице курса

Содержание

1 Алгоритм
2 Язык программирования PascalABC.NET
3 Синтаксис и семантика ЯП
4 Переменные и их описание
- 4.1 Основные сведения
- 4.2 Внутриблочные переменные
5 Основные типы
6 Основные операторы

Алгоритм

Алгоритм — набор команд, определяющих порядок действий для решения поставленной задачи.

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

В частности, процессор компьютера выступает исполнителем машинных команд.

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

Дискретность — алгоритм представляет собой последовательность элементарных шагов (команд исполнителя).
Детерминированность (определённость) — при одних и тех же входных данных получается один и тот же результат.
Завершаемость (конечность) — каждый алгоритм завершается за конечное число шагов при любом наборе исходных данных.
Результативность — после выполнения алгоритма известно, что считать результатом.
Массовость — применимость алгоритма ко множеству исходных данных.

Пример алгоритма.

Дано: 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

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

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

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

1. Словесный

2. Псевдокод

3. Блок-схемы

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

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

Для языка программирования команды алгоритма называются операторами или инструкциями.

Основные характеристики алгоритма

правильность работы
скорость выполнения
объем занимаемой памяти
сложность написания
возможность распараллеливания

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

Те же, что и у алгоритма, а также:

понятность при чтении
модифицируемость (легкость изменения кода)
масштабируемость (возможность изменения кода для решения родственной или более общей задачи)
безопасность

Если два алгоритма эквивалентны, то какой из них лучше? Тот же вопрос можно задать о программах, реализующих эти алгоритмы. Как правило, не существует однозначного ответа на этот вопрос. Лучшие по скорости алгоритмы как правило более сложны, труднее для понимания и могут требовать больше памяти. Часто для решения задачи не нужна самая быстрая программа - достаточно простой и понятной программы.

Обзор современных языков программирования

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

Язык программирования PascalABC.NET

Правила записи программ на PascalABC.NET

Шпаргалка

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

program First; // заголовок программы – необязательная строка
{ Программа вычисления длины окружности и площади круга 
  Автор: Михалкович С.С. Дата написания: 2.09.08 }
const Pi = 3.14;
var
  r: real;   // входные данные - радиус круга
  S,C: real; (* выходные данные - площадь круга и длина окружности *)
begin
  write('Введите радиус окружности: ');
  readln(r);
  S := Pi*r*r;
  C := 2*Pi*r;
  writeln('Длина окружности равна ',С);
  writeln('Площадь круга равна ',S);
end.

Структура программы на языке Паскаль

Заголовок программы
Раздел описаний (описываются все используемые в программе переменные и определяются их типы)
begin
  операторы (разделяются ;)
end.

Как правило, программа начинается с ввода исходных данных, после чего следуют вычисления и вывод результатов. Ввод сопровождается приглашением к вводу.

Система программирования PascalABC.NET

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

Общая характеристика PascalABC.NET.

Отличия языка PascalABC.NET от обычного языка Паскаль.

Компиляторы и интерпретаторы

Схема компиляции в машинный код

Схема компиляции в промежуточный код. JIT-компиляция

Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения

Синтаксис - правила записи конструкций, семантика - смысл конструкций.

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

// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.

Определения

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

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

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

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

Примеры.

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

0, 1, ... 9

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

<цифра>

так называемый нетерминал (нетерминальный символ).

Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется рекурсивным (как определение нетерминала <идентификатор>)

РБНФ (Расширенные БНФ)

[] — 0 или 1 повторение.

{} — 0 и более повторений

Пример.

<идентификатор> ::= <буква> {<буква> | <цифра>}

Синтаксические диаграммы (Вирт, Паскаль)

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

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

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

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

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

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

{...}

(*...*)

//...

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

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

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

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

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

<xh4> Синтаксис в виде РБНФ </xh4>

<программа> ::= [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 байта)

int64 (8)

byte (1)

Вещественные

real (8)

Символьные

char (2 байта — Unicode)

Строковые

string

string[200]

shortstring = string[255]

Логический

boolean (1) [True False]К основной странице курса

Основные операторы

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

<xh4> Синтаксис </xh4>

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

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

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

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

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

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

<xh4> Операторы присваивания += и *= </xh4> Пример.

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

<xh4> Примеры использования := </xh4> Пример 1. Перемена местами двух значений. Дано: 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.

Пример 2. Использование промежуточных переменных в вычислениях Дано: 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ⁿ за минимальное число умножений.
Об этом читай тему.

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

<xh4> Синтаксис </xh4>

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

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

Имеются также стандартные функции ReadInteger, ReadReal, ReadlnInteger, ReadlnReal:

var n := ReadInteger;
var r := ReadlnReal;

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

Оператор try/except и обработка ошибок ввода

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

<xh4> Синтаксис </xh4>

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

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

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

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

<xh4> Синтаксис </xh4>

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

<xh4> Семантика </xh4> Выражения в списке вычисляются, и их значения выводятся на экран.
В случае writeln после вывода осуществляется переход на новую строку.

<xh4> Форматы вывода </xh4> После каждого выражения в списке вывода можно использовать формат вывода в виде :a, где a — выражение целого типа.
После вещественного типа — :a:b (a задает ширину поля вывода (выравнивание по правому краю), b — количество знаков в дробной части).

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

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

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

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

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

a * b = a * b

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

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

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

Каждое выражение имеет тип. Выражение называется арифметическим, если его тип — числовой.
Выражение строится посредством операций (унарных или бинарных) и операндов.

В арифметических выражениях если a и b — одного типа, то и a op b принадлежит к тому же типу. Исключением является операция "/":

a / b — вещественное.

Если a и b принадлежат к различным типам, то выражение принадлежит к "старшему" типу.
Например:

byte < integer < int64
integer < real

Стандартные функции

В арифметические выражения могут входить стандартные функции:

exp(x)
ln(x)
abs(x)  // модуль x
sin(x)
cos(x)
sqr(x)  // квадрат x
sqrt(x) // корень из x 
round(x) - целое, полученное в результате округления вещественного x
trunc(x) - целое, полученное в результате отбрасывания дробной части у вещественного x
min(x,y) 
max(x,y) 
power(x,y)// x в степени y
random(n)// псевдослучайное целое число от 0 до n-1
random(a,b)// псевдослучайное целое число от a до b

<xh4> Порядок выполнения операций в арифметических выражениях </xh4>

Операции с большим приоритетом выполняются первыми
Функции вычисляются до операций
Выражение в скобках вычисляется раньше
Операции с одинаковым приоритетом выполняются слева направо, если идут подряд.

<xh4> Операции div и mod для целых </xh4> x div y = x / y, округленное до ближайшего целого по направлению к нулю. Это результат от целочисленного деления.
x mod y = x - (x div y) * y. Это остаток от целочисленного деления.

Пример использования
Целочисленные операции часто применяются для определения четности числа:

x mod 2 = 0    <->   x — четное
x mod 2 <> 0   <->   x — нечетное

Логические выражения

<xh4> Основные сведения </xh4> Выражение назывется логическим, если оно имеет тип boolean.
Пример.

x < 0
a >= b
a <> 3

Это простые логические выражения. Однако, с помщью логических операций можно составлять сложные.

 (бинарные)     (унарные)
  a and b         not a
  a or b
  a xor b

<xh4> Таблицы истинности логических операций </xh4>

a | b | a and b | a or b | a xor b 

T | T |    T    |   T    |    F
T | F |    F    |   T    |    T
F | T |    F    |   T    |    T
F | F |    F    |   F    |    F

<xh4> Сокращение вычислений логических выражений </xh4> Большинство современных компиляторов, в т.ч. PascalABC.NET производит сокращенное вычисление логических выражений.
Это означает, что в выражении

a and b

если a — ложно, то b не вычисляется, а в

a or b

если a — истинно, b не вычисляется.

Это очень полезно при вычислении таких выражений, как, например,

(y <> 0) and (x / y > 0)

Логически здесь все верно, однако, если бы не использовалось сокращенное вычисление, в случае равенства нулю y'а возникала бы ошибка деления на ноль.

<xh4> Логические переменные </xh4> Можно описывать логические переменные (тип boolean). Им можно присваивать логические выражения.
Эти переменные принимают одно из двух возможных значений:

true (истина)

false (ложь)

Пример использования логических переменных
Дано: прямоугольник со сторонами, параллельными осям координат, задан координатами абсцисс вертикальных сторон (x1, x2) и ординатами горизонтальных (y1, y2); точка M( x, y );
Найти: находится ли точка внутри прямоугольника, снаружи, или лежит на границе;

var inside, outside, bound: boolean;
begin
  inside := (x > x1) and (x < x2) and (y > y1) and (y < y2);
  outside := (x < x1) or (x > x2) or (y < y1) or (y > y2);
  bound := not inside and not outside;
end.

Побитовые операции

<xh4> Побитовые операции and, or, xor, not </xh4> Замечание. Работают только с целыми.

Соответствующая операция применяется к каждому биту двоичного представления числа.
Пример.

5 and 7

5₁₀ = 101₂
7₁₀ = 111₂

101
   ( and )
111
———
101₂ = 5₁₀

<xh4> Операции shl и shr </xh4> Побитовый сдвиг влево и сдвиг вправо соответственно.

x shl n = x * 2ⁿ

Сдвигает двоичное представление x на n позиций влево.

x shr n = x div 2ⁿ

Сдвигает двоичное представление x на n позиций вправо.

<xh4> Примеры </xh4>

x = 5₁₀ = 101₂

x shl 2 = <—(²)101
             10100₂ = 20₁₀

x shr 2 = 101—>(²)
          001₂ = 1₁₀

Таблица приоритетов операций языка Object Pascal

унарные + - not
имеющие смысл умножения * / div mod and shl shr
имеющие смысл сложения + - or xor
операции отношения <> <= >= < > in

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

<xh4> Синтаксис </xh4>

if <условие> then <оператор₁>
             [else <оператор₂>]

<xh4> Семантика </xh4>

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

Пример 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 < 2 then
  y := x
else if x < 3 then
  y := x * x
else y := 1 - x;

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

Координаты средней точки

Пример 4. Даны координаты трех точек на прямой a, b, c (a, b, c попарно не равны). Найти m - координаты средней точки

Решение 1.

Достаточно рассмотреть случай, когда координаты точек равны 1,2 и 3

Рассмотрим все возможные ситуации распределения этих значений между a,b,c:

a  b  c
1  2  3  a<b
1  3  2  a<b
2  1  3
2  3  1  a<b
3  1  2
3  2  1

При a<b возможны три варианта, в двух из которых a<c. При a>b возможны три варианта, в двух из которых a>c.

Решение представляется вложенными операторами if с уровнем вложенности 3.

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

По количеству операций (3 сравнения, одно присваивание) это - самое лучшее решение

То же решение, записанное с помощью функции min:

if a < b then
  if a < c then
    m := min(b,c)
  else m := a
else
  if a > c then
    m := min(b,c)
  else m := a;

Решение 2.

var m1 := min(a,b);
var m2 := max(a,b);

a  b  c  
1  2  3  c>m2
1  3  2  
2  1  3  c>m2
2  3  1  c<m1
3  1  2  
3  2  1  c<m1

var m1 := min(a,b);
var m2 := max(a,b);
if c<m1 then
  m := m1
else if c>m2 then
  m := m2
else m := c;

Данное решение менее эффективно по числу сравнений и присваиваний (посчитайте самостоятельно), но по понятности может восприниматься лучше предыдущего.

Самостоятельные задания

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

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

<xh4> Синтакстис </xh4>

case <переключатель> of
  {<список выбора>: <оператор>;}
  [else <оператор>[;]]
end

<xh4> Семантика </xh4> Вначале вычисляется выражение-<переключатель>, после чего его значение ищется в одном из <списков выбора>.
Если значение попадает в какой-то <список выбора>, то выполняется соответствующий ему оператор, иначе, если есть ветвь else, то выполняется оператор по ветке else.

<xh4> Ограничения </xh4>

выражение-переключатель должно иметь так называемый порядковый тип:

целый

символьный

перечислимый

НО НЕ строковый или вещественный.

значения в <списках выбора> не должны пересекаться.

<xh4> Примеры использования оператора выбора </xh4> Пример 1. День недели

case DayOfWeek of
  1..5: writeln('Будний');
  6, 7: writeln('Выходный');
  else  writeln('Ошибка');
end;

Пример 2. Цифра или буква

var c: char;
read(c);
case c of
  '0'..'9': writeln('Цифра');
  'A'..'Z', 'a'..'z', 'а'..'я', 'А'..'Я', 'ё', 'Ё': writeln('Буква');
end;

Основы программирования — первый семестр 08-09

Содержание

Алгоритм

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

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

Основные характеристики алгоритма

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

Обзор современных языков программирования

Язык программирования PascalABC.NET

Правила записи программ на PascalABC.NET

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

Структура программы на языке Паскаль

Система программирования PascalABC.NET

Компиляторы и интерпретаторы

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

Определения

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

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

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

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

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

Основные типы

Основные операторы

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

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

Оператор try/except и обработка ошибок ввода

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

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

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

Стандартные функции

Логические выражения

Побитовые операции

Таблица приоритетов операций языка Object Pascal

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

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

Координаты средней точки

Самостоятельные задания

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

Навигация

Поиск