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

Программирование на языке Паскаль
§ 54. Алгоритм и его свойства

Что такое алгоритм?
Алгоритм — это точное описание порядка действий, которые должен выполнить исполнитель для решения задачи за конечное время.
Исполнитель – это устройство или одушёвленное существо (человек), способное понять и выполнить команды, составляющие алгоритм.
Формальные исполнители: не понимают
(и не могут понять) смысл команд.

Свойства алгоритма
Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное время.
Детерминированность (определённость) — при каждом запуске алгоритма с одними и теми же исходными данными получается один и тот же результат.
Понятность — алгоритм содержит только команды, входящие в систему команд исполнителя.
Конечность (результативность) — для корректного набора данных алгоритм должен завершаться через конечное время.
Корректность — для допустимых исходных данных алгоритм должен приводить к правильному результату.

Как работает алгоритм?
дискретный
объект
1 2 3 4
алгоритм
шаг 1
шаг 2
шаг 3
2 3 4 5
5 4 3 2
дискретный
объект
25 16 9 4
получает на вход дискретный объект
в результате строит другой дискретный объект (или выдаёт сообщение об ошибке)
обрабатывает объект по шагам
на каждом шаге получается новый дискретный объект

Способы записи алгоритмов
естественный язык
псевдокод
установить соединение
пока не принята команда «стоп»
принять команду
выполнить команду
завершить сеанс связи
установить соединение
нц
принять команду
выполнить команду
кц_при команда = 'stop'
завершить сеанс связи

Способы записи алгоритмов
блок-схема
setConnection;
repeat
cmd:= getCommand;
executeCommand(cmd);
until cmd = "stop";
closeConnection;
программа

Программирование на языке Паскаль
§ 55. Простейшие программы

Простейшая программа
program qq;
begin { начало программы }
{ тело программы }
end. { конец программы }
комментарии в скобках {}
не обрабатываются
название алгоритма

Вывод на экран
program qq;
begin
write('2+'); { без перехода }
writeln('2=?'); { на новую строку}
writeln('Ответ: 4');
end.
Протокол:
2+2=?
Ответ: 4

Задания
«B»: Вывести на экран текст «лесенкой»
Вася
пошел
гулять
«C»: Вывести на экран рисунок из букв
Ж
ЖЖЖ
ЖЖЖЖЖ
ЖЖЖЖЖЖЖ
HH HH
ZZZZZ

Сложение чисел
Задача. Ввести с клавиатуры два числа и найти их сумму.
Протокол:
Введите два целых числа
25 30
25+30=55
компьютер
пользователь
компьютер считает сам!

Сумма: псевдокод
program qq;
begin
{ ввести два числа }
{ вычислить их сумму }
{ вывести сумму на экран }
end.
Псевдокод: алгоритм на русском языке с элементами Паскаля.

Переменные
Переменная – это величина, имеющая имя, тип и значение. Значение переменной можно изменять во время работы программы.
a
Значение
Имя
Другой тип данных

Имена переменных
МОЖНО использовать
латинские буквы (A-Z)
цифры
знак подчеркивания _
заглавные и строчные буквы НЕ различаются
НЕЛЬЗЯ использовать
русские буквы
пробелы
скобки, знаки +, =, !, ? и др.
имя не может начинаться с цифры
Какие имена правильные?
AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B

Объявление переменных
Типы переменных:
integer { целая }
real { вещественная }
и другие…
Объявление переменных:
var a, b, c: integer;
выделение места в памяти
variable – переменная
тип – целые
список имен переменных

Тип переменной
область допустимых значений
допустимые операции
объём памяти
формат хранения данных
для предотвращения случайных ошибок

Ввод значения в переменную
read ( a );
оператор ввода
5
a

Ввод значений переменной
через пробел:
25 30
через Enter:
25
30
read ( a, b );
Ввод значений двух переменных (через пробел или Enter).

Изменение значений переменной
var a, b: integer;
...
a := 5;
b := a + 2;
a := (a + 2)*(b – 3);
b := b + 1;
a
?
5
5
b
?
5+2
7
a
5
7*4
28
b
7
7+1
8

Вывод данных
{ вывод значения переменной a}
{ вывод значения переменной a и переход на новую строку}
{ вывод текста }
{вывод текста и значения переменной c}
write( a );
writeln( a );
writeln( 'Привет!' );
writeln( 'Ответ: ', c );
writeln ( a, '+', b, '=', c );

Сложение чисел: простое решение
program Sum;
var a, b, c: integer;
begin
read ( a, b );
c := a + b;
writeln ( c );
end.

Сложение чисел: полное решение
program Sum;
var a, b, c: integer;
begin
writeln('Введите два целых числа');
read ( a, b );
c := a + b;
writeln ( a, '+', b, '=', c );
end.
Протокол:
Введите два целых числа
25 30
25+30=55
компьютер
пользователь

Снова про оператор вывода
a:= 123;
write( a:5 );
Форматный вывод:
Вычисление выражений:
writeln ( a, '+', b, '=', a+b );
a+b

Программирование на языке Паскаль
§ 56. Вычисления

Типы данных
byte { целые 0..255 }
shortint { целые -128..127 }
word { целые 0..65535 }
longint { целые –2147483648..2147483647 }
single { вещественная, 4 байта }
real { вещественная, 6 байта }
double { вещественная, 8 байтов }
extended { вещественная, 10 байтов }
boolean { логическая, 1 байт }
char { символ, 1 байт }
string { символьная строка }

Арифметические выражения
a:= (c + b*5*3 - 1) / 2 * d;
Приоритет (старшинство):
скобки
умножение и деление
сложение и вычитание
2
1
3
4
5
6

Деление, div, mod
Результат деления «/» – вещественное число:
a:= 2 / 3;
var a: single;
0.6666…
div – деление нацело (остаток отбрасывается)
mod – остаток от деления
var a, b, d: integer;
...
d := 85;
b := d div 10; { 8 }
a := d mod 10; { 5 }

div и mod для отрицательных чисел
write(-7 div 2, ',');
write(-7 mod 2);
-3
-1
-7 = (-3)*2 + (-1)
-7 = (-4)*2 + 1
остаток ≥ 0

Вещественные числа
var x: double;
...
x:= 123.456;
Форматный вывод:
a:= 1;
write( a/3 );
write( a/3:7:3 );
3.333333E-001
3,333333 ⋅ 10-1 = 0,3333333
всего знаков
в дробной части

Стандартные функции
abs(x) — модуль
sqrt(x) — квадратный корень
sin(x) — синус угла, заданного в радианах
cos(x) — косинус угла, заданного в радианах
exp(x) — экспонента ех
ln(x) — натуральный логарифм
trunc(x)— отсечение дробной части
round(x)— округление до ближайшего целого

Случайные числа
Случайно…
встретить друга на улице
разбить тарелку
найти 10 рублей
выиграть в лотерею
Случайный выбор:
жеребьевка на соревнованиях
выигравшие номера
в лотерее
Как получить случайность?

Случайные числа на компьютере
Электронный генератор
нужно специальное устройство
нельзя воспроизвести результаты
318458191041
564321
209938992481
458191
938992
малый период
(последовательность повторяется через 106 чисел)
Метод середины квадрата (Дж. фон Нейман)
в квадрате
Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.
зерно

Линейный конгруэнтный генератор
X := (a*X+b) mod c | интервал от 0 до c-1
X := (X+3) mod 10 | интервал от 0 до 9
X := 0
зерно
→ 3
→ 6
→ 9
→ 2
→ 5
→ 8
→ 0
зацикливание
8
→ 1
→ 4
→ 7
Компилятор GCC:
a = 1103515245
b = 12345
c = 231

Генератор случайных чисел
Вещественные числа в интервале [0,1):
var X, Y: double;
...
X:= random; { интервал от 0 до 1 (<1) }
Y:= random; { это уже другое число! }
англ. random – случайный
Целые числа в интервале [0,10):
var K, L: integer;
...
K:= random( 10 ) { интервал от 0 до 9 (<10) }
L:= random( 10 ) { это уже другое число! }

Другой интервал
Вещественные числа:
var X, a, b: double;
...
X:= random*10; { расширение интервала: [0,10) }
X:= random*10 + 5;
{ расширение и сдвиг: [5,15) }
X:= random*(b-a) + a;
{ расширение и сдвиг: [a,b) }
var K, a, b: integer;
...
K:= random(10) + 5; { [5,14] }
X:= random(b-a+1) + a; { [a,b] }
Целые числа: