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

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

1
Программирование
на языке Паскаль
Тема 1. Введение
© К.Ю. Поляков, 2006-2008

2.

Алгоритм
Алгоритм – это четко определенный план
действий для исполнителя.
Свойства алгоритма
• дискретность: состоит из отдельных шагов (команд)
• понятность: должен включать только команды,
известные исполнителю (входящие в СКИ)
• определенность: при одинаковых исходных данных
всегда выдает один и тот же результат
• конечность: заканчивается за конечное число шагов
• массовость: может применяться многократно при
различных исходных данных
• корректность: дает верное решение при любых
допустимых исходных данных
2

3.

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

4.

Языки программирования
• Машинно-ориентированные (низкого уровня) каждая команда соответствует одной команде
процессора (ассемблер)
• Языки высокого уровня – приближены к
естественному (английскому) языку, легче
воспринимаются человеком, не зависят от
конкретного компьютера
• для обучения: Бейсик, ЛОГО, Паскаль
• профессиональные: Си, Фортран, Паскаль
• для задач искусственного интеллекта:
Пролог, ЛИСП
• для Интернета: JavaScript, Java, Perl, PHP,
ASP
4

5.

5
Язык Паскаль
1970 – Никлаус Вирт (Швейцария)
• язык для обучения студентов
• разработка программ «сверху вниз»
Задача
Подзадача1
1.1
1.2
1.3
Подзадача2
2.1
2.2
Подзадача3
2.3
3.1
3.2
3.3
• разнообразные структуры данных
(массивы, структуры, множества)

6.

Из чего состоит программа?
Константа – постоянная величина, имеющая
имя.
Переменная – изменяющаяся величина,
имеющая имя (ячейка памяти).
Процедура – вспомогательный алгоритм,
описывающий некоторые действия
(рисование окружности).
Функция – вспомогательный алгоритм для
выполнения вычислений (вычисление
квадратного корня, sin).
6

7.

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

8.

8
Константы
const
i2 = 45; { целое число }
pi = 3.14; { вещественное число }
целая и дробная часть отделяются точкой
qq = 'Вася'; { строка символов }
можно использовать русские буквы!
L
= True; { логическая величина }
может принимать два значения:
• True (истина, «да»)
• False (ложь, «нет»)

9.

Переменные
Переменная – это величина, имеющая имя, тип и
значение. Значение переменной можно изменять
во время работы программы.
Типы переменных:
• integer
{ целая }
• real
{ вещественная }
• char
{ один символ }
• string
{ символьная строка }
• boolean
{ логическая }
Объявление переменных (выделение памяти):
var a, b: integer;
Q: real;
s1, s2: string;
9

10.

Как изменить значение переменной?
Оператор – это команда языка программирования
высокого уровня.
Оператор присваивания служит для изменения
значения переменной.
Пример:
program qq;
a
5
?
5
var a, b: integer;
begin
b
a := 5;
5+2
?
7
b := a + 2;
a
a := (a + 2)*(b – 3);
7*4
28
5
end.
10

11.

11
Оператор присваивания
<имя переменной> := <выражение>;
Арифметическое выражение может включать
• константы
• имена переменных
• знаки арифметических операций:
+ *
/
div
mod
умножение
деление
• вызовы функций
• круглые скобки ( )
деление
нацело
остаток от
деления

12.

Какие операторы неправильные?
program qq;
var a, b: integer;
x, y: real;
begin
имя переменной должно
быть слева от знака :=
a := 5;
целая и дробная часть
10 := x;
отделяются точкой
y := 7,8;
нельзя записывать
b := 2.5;
вещественное значение в
целую переменную
x := 2*(a + y);
a := b + x;
end.
12

13.

Порядок выполнения операций
13
• вычисление выражений в скобках
• умножение, деление, div, mod слева направо
• сложение и вычитание слева направо
2 3 5 4 1
7 8 6 9
z := (5*a*c+3*(c-d))/a*(b-c)/ b;
a 2 5c 2 d (a b)
x
(c d )( d 2a)
5ac 3(c d )
z
(b c)
ab
2 6 3 4 7 5 1
12 8 11 10 9
x:=(a*a+5*c*c-d*(a+b))/((c+d)*(d-2*a));

14.

Сложение двух чисел
Задача. Ввести два целых числа и вывести на
экран их сумму.
Простейшее решение:
program qq;
var a, b, c: integer;
begin
read ( a, b );
c := a + b;
writeln ( c );
end.
14

15.

15
Оператор ввода
read ( a );
{ ввод значения
переменной a}
read ( a, b ); { ввод значений
переменных a и b}
Как вводить два числа?
25 a
30 b
через пробел:
25 30
через Enter:
25
30
25 a
30 b

16.

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

17.

Форматы вывода
program qq;
var i: integer;
x: real;
всего
begin
символов
i := 15;
writeln ( '>', i, '<' );
>15<
writeln ( '>', i:5, '<' ); >
15<
x := 12.345678;
writeln ( '>', x, '<' );
>1.234568E+001<
writeln ( '>', x:10, '<' ); > 1.23E+001<
writeln ( '>', x:7:2, '<' ); > 12.35<
end.
в дробной
всего
части
символов
17

18.

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

19.

Блок-схема линейного алгоритма
начало
блок «начало»
ввод a, b
блок «ввод»
c := a + b;
блок «процесс»
вывод c
блок «вывод»
конец
блок «конец»
19

20.

Задания
«4»: Ввести три числа, найти их сумму и
произведение.
Пример:
Введите три числа:
4
5
7
4+5+7=16
4*5*7=140
«5»: Ввести три числа, найти их сумму, произведение
и среднее арифметическое.
Пример:
Введите три числа:
4
5
7
4+5+7=16
4*5*7=140
(4+5+7)/3=5.33
20

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

21
Программирование
на языке Паскаль
Тема 2. Ветвления
© К.Ю. Поляков, 2006-2008

22.

Разветвляющиеся алгоритмы
Задача. Ввести два целых числа и вывести на экран
наибольшее из них.
Идея решения: надо вывести на экран первое число,
если оно больше второго, или второе, если оно больше
первого.
Особенность: действия исполнителя зависят от
некоторых условий (если … иначе …).
Алгоритмы, в которых последовательность шагов
зависит от выполнения некоторых условий, называются
разветвляющимися.
22

23.

23
Вариант 1. Блок-схема
начало
блок
«решение»
ввод a,b
да
a > b?
max:= a;
полная
форма
ветвления
нет
max:= b;
вывод max
конец
? Если a = b?

24.

Вариант 1. Программа
program qq;
var a, b, max: integer;
begin
writeln('Введите два целых числа');
read ( a, b );
полная форма
if a > b then begin
условного
max := a;
оператора
end
else begin
max := b;
end;
writeln ('Наибольшее число ', max);
end.
24

25.

Условный оператор
if <условие> then begin
{что делать, если условие верно}
end
else begin
{что делать, если условие неверно}
end;
Особенности:
• перед else НЕ ставится точка с запятой
• вторая часть (else …) может отсутствовать
(неполная форма)
• если в блоке один оператор, можно убрать слова
begin и end
25

26.

26
Что неправильно?
if a > b then begin
a := b;
end
else begin
b := a;
end;
if a > b then begin
a := b; end
else begin
b := a;
end;
if a > b then begin
a := b;
end
begin
else b
> a begin
b := a;
end;
if a > b then begin
a := b;
end;
end
else begin
b := a;
end;

27.

27
Вариант 2. Блок-схема
начало
ввод a,b
max:= a;
да
b > a?
max:= b;
вывод max
конец
нет
неполная
форма
ветвления

28.

Вариант 2. Программа
program qq;
var a, b, max: integer;
begin
writeln('Введите два целых числа');
read ( a, b );
неполная
форма
max := a;
условного
if b > a then
оператора
max := b;
writeln ('Наибольшее число ', max);
end.
28

29.

Вариант 2Б. Программа
program qq;
var a, b, max: integer;
begin
writeln('Введите два целых числа');
read ( a, b );
max := b;
if a???
> b then
???:= a;
max
writeln ('Наибольшее число ', max);
end.
29

30.

30
Что неправильно?
if a > b then begin
b;
a := b
else b := a;
if a > b then
b
a := b;
else b := a; end;
if a > b then begin
a := b;
end;
end
else b := a;
if a > b then
else
if b begin
>= a then
bb:=
:=a;
a;
end;

31.

31
Задания
«4»: Ввести три числа и найти наибольшее из них.
Пример:
Введите три числа:
4
15
9
Наибольшее число 15
«5»: Ввести пять чисел и найти наибольшее из них.
Пример:
Введите пять чисел:
4
15
9
56
Наибольшее число 56
4

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

32
Программирование
на языке Паскаль
Тема 3. Сложные условия
© К.Ю. Поляков, 2006-2008

33.

Сложные условия
Задача. Фирма набирает сотрудников от 25 до 40 лет
включительно. Ввести возраст человека и определить,
подходит ли он фирме (вывести ответ «подходит» или
«не подходит»).
Особенность: надо проверить, выполняются ли два
условия одновременно.
? Можно ли решить известными методами?
33

34.

34
Вариант 1. Алгоритм
начало
ввод x
да
да
'подходит'
x <= 40?
x >= 25?
нет
нет
'не подходит'
конец
'не подходит'

35.

Вариант 1. Программа
program qq;
var x: integer;
begin
writeln('Введите возраст');
read ( x );
if x >= 25 then
if x <= 40 then
writeln ('Подходит')
else writeln ('Не подходит')
else
writeln ('Не подходит');
end.
35

36.

36
Вариант 2. Алгоритм
начало
ввод x
да
x >= 25
и
x <= 40?
нет
'не подходит'
'подходит'
конец

37.

Вариант 2. Программа
program qq;
var x: integer;
begin
сложное
writeln('Введите возраст');
условие
read ( x );
if (x >= 25) and (x <= 40) then
writeln ('Подходит')
else writeln ('Не подходит')
end.
37

38.

38
Сложные условия
Сложное условие – это условие, состоящее из
нескольких простых условий (отношений), связанных с
помощью логических операций:
• not – НЕ (отрицание, инверсия)
• and – И (логическое умножение, конъюнкция,
одновременное выполнение условий)
• or – ИЛИ (логическое сложение, дизъюнкция,
выполнение хотя бы одного из условий)
• xor – исключающее ИЛИ (выполнение только
одного из двух условий, но не обоих)
Простые условия (отношения)
<
<=
>
>=
равно
=
не равно
<>

39.

Сложные условия
Порядок выполнения (приоритет = старшинство)
• выражения в скобках
• not
• and
• or, xor
• <, <=, >, >=, =, <>
Особенность – каждое из простых условий обязательно
заключать в скобки.
Пример
4
1
6
2
5
3
if not (a > b) or (c <> d) and (b <> a)
then begin
...
end
39

40.

40
Сложные условия
Истинно или ложно при a := 2; b := 3; c := 4;
True
not (a > b)
True
(a < b) and (b < c)
True
not (a >= b) or (c = d)
True
(a < c) or (b < c) and (b < a)
(a < b) xor not (b > c)
FALSE
Для каких значений x истинны условия:
(x < 6) and (x < 10)
(x < 6) and (x > 10)
(x > 6) and (x < 10)
(x > 6) and (x > 10)
(x < 6) or (x < 10)
(x < 6) or (x > 10)
(x > 6) or (x < 10)
(x > 6) or (x > 10)
(- , 6)
(6, 10)
(10, )
(- , 10)
(- , 6) (10, )
(- , )
(6, )
x<6
x > 10
x < 10
x>6

41.

41
Задания
«4»: Ввести номер месяца и вывести название
времени года.
Пример:
Введите номер месяца:
4
весна
«5»: Ввести возраст человека (от 1 до 150 лет) и
вывести его вместе с последующим словом
«год», «года» или «лет».
Пример:
Введите возраст:
24
Вам 24 года
Введите возраст:
57
Вам 57 лет

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

42
Программирование
на языке Паскаль
Тема 4. Циклы
© К.Ю. Поляков, 2006-2008

43.

Циклы
Цикл – это многократное выполнение одинаковой
последовательности действий.
• цикл с известным числом шагов
• цикл с неизвестным числом шагов (цикл с
условием)
Задача. Вывести на экран квадраты и кубы целых чисел
от 1 до 8 (от a до b).
Особенность: одинаковые действия выполняются 8 раз.
? Можно ли решить известными методами?
43

44.

44
Алгоритм
начало
задать начальное значение
переменной цикла
i := 1;
проверить, все ли сделали
i <= 8?
да
i2 := i * i;
i3 := i2 * i;
нет
конец
вычисляем квадрат и куб
вывод результата
i, i2, i3
перейти к
следующему i
i := i + 1;

45.

Алгоритм (с блоком «цикл»)
начало
блок «цикл»
i := 1,8
конец
i2 := i * i;
i3 := i2 * i;
i, i2, i3
тело цикла
45

46.

46
Программа
program qq;
var i, i2, i3: integer;
begin
начальное значение
переменная
цикла
конечное значение
for i:=1 to 8 do begin
i2 := i*i;
i3 := i2*i;
writeln(i:4, i2:4, i3:4);
end;
end.

47.

Цикл с уменьшением переменной
Задача. Вывести на экран квадраты и кубы целых чисел
от 8 до 1 (в обратном порядке).
Особенность: переменная цикла должна уменьшаться.
Решение:
for i:=8 downto 1 do begin
i2 := i*i;
i3 := i2*i;
writeln(i:4, i2:4, i3:4);
end;
47

48.

Цикл с переменной
Увеличение переменной на 1:
for <переменная> := <начальное значение> to
<конечное значение> do begin
{тело цикла}
end;
Уменьшение переменной на 1:
for <переменная> := <начальное значение>
downto
<конечное значение> do begin
{тело цикла}
end;
48

49.

Цикл с переменной
Особенности:
• переменная цикла может быть только целой
(integer)
• шаг изменения переменной цикла всегда равен 1
(to) или -1 (downto)
• если в теле цикла только один оператор, слова
begin и end можно не писать:
for i:=1 to 8 do
writeln('Привет');
• если конечное значение меньше начального, цикл
(to) не выполняется ни разу (проверка условия в
начале цикла, цикл с предусловием)
49

50.

Цикл с переменной
Особенности:
• в теле цикла не разрешается изменять переменную
цикла (почему?)
• при изменении начального и конечного значения
внутри цикла количество шагов не изменится:
n := 8;
for i:=1 to n do begin
writeln('Привет');
нет
n := n + 1;
зацикливания
end;
50

51.

51
Цикл с переменной
Особенности:
• после выполнения цикла во многих системах
устанавливается первое значение переменной
цикла, при котором нарушено условие:
for i:=1 to 8 do
writeln('Привет');
writeln('i=', i);
for i:=8 downto 1 do
writeln('Привет');
writeln('i=', i);
i=9
i=0

52.

52
Сколько раз выполняется цикл?
a := 1;
for i:=1 to 3 do a := a+1;
a= 4
a := 1;
for i:=3 to 1 do a := a+1;
a= 1
a := 1;
for i:=1 downto 3 do a := a+1;
a= 1
a := 1;
for i:=3 downto 1 do a := a+1;
a= 4

53.

53
Как изменить шаг?
Задача. Вывести на экран квадраты и кубы нечётных целых
чисел от 1 до 9.
Особенность: переменная цикла должна увеличиваться на 2.
Проблема: в Паскале шаг может быть 1 или -1.
Решение:
for i:=1 to 9 do begin
if i mod
???2 = 1 then begin
i2 := i*i;
i3 := i2*i;
writeln(i:4, i2:4, i3:4);
end;
end;
выполняется
только для
нечетных i
? Что плохо?

54.

Как изменить шаг? – II
Идея: Надо вывести всего 5 чисел, переменная k изменяется
от 1 до 5. Начальное значение i равно 1, с каждым шагом
цикла i увеличивается на 2.
Решение:
i := 1;
???
for k:=1 to 5 do begin
i2 := i*i;
i3 := i2*i;
writeln(i:4, i2:4, i3:4);
???
i := i + 2;
end;
54

55.

55
Как изменить шаг? – III
Идея: Надо вывести всего 5 чисел, переменная k изменяется
от 1 до 5. Зная k, надо рассчитать i.
k
1
2
3
4
5
i
1
3
5
7
9
Решение:
for k:=1 to 5 do begin
i ???
:= 2*k – 1;
i2 := i*i;
i3 := i2*i;
writeln(i:4, i2:4, i3:4);
end;
i = 2k-1

56.

Задания
«4»: Ввести a и b и вывести квадраты и кубы чисел от a до b.
Пример:
Введите границы интервала:
4 6
4 16
64
5 25 125
6 36 216
«5»: Вывести квадраты и кубы 10 чисел следующей
последовательности: 1, 2, 4, 7, 11, 16, …
Пример:
1
1
1
2
4
8
4
16
64
...
46 2116 97336
56

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

57
Программирование
на языке Паскаль
Тема 5. Циклы с условием
© К.Ю. Поляков, 2006-2008

58.

Цикл с неизвестным числом шагов
Пример: Отпилить полено от бревна. Сколько раз надо
сделать движения пилой?
Задача: Ввести целое число (<2000000) и определить число
цифр в нем.
Идея решения: Отсекаем последовательно последнюю
цифру, увеличиваем счетчик.
n
count
123
0
12
1
1
2
0
3
Проблема: Неизвестно, сколько шагов надо сделать.
Решение: Надо остановиться, когда n = 0, т.е. надо делать
«пока n <> 0».
58

59.

59
Алгоритм
начало
обнулить
счетчик цифр
ввод n
count := 0;
выполнять
«пока n <> 0»
n <> 0?
нет
да
count := count + 1;
n := n div 10;
count
конец

60.

60
Программа
program qq;
n1: integer;
var n, count:, integer;
begin
writeln('Введите целое число');
read(n); n1 := n;
выполнять
count := 0;
«пока n <> 0»
while nn <>
<> 00 do
do begin
begin
while
count:=:=count
count+ +1;1;
count
div10;
10;
n n:=:=n ndiv
end;
end;
writeln('В числе ', n1,
n, ' нашли ',
count, ' цифр');
end.
Что плохо?
?

61.

Цикл с условием
while <условие> do begin
{тело цикла}
end;
Особенности:
• можно использовать сложные условия:
while (a<b) and (b<c) do begin
{тело цикла}
end;
• если в теле цикла только один оператор, слова
begin и end можно не писать:
while a < b do
a := a + 1;
61

62.

Цикл с условием
Особенности:
• условие пересчитывается каждый раз при входе в
цикл
• если условие на входе в цикл ложно, цикл не
выполняется ни разу
a := 4; b := 6;
while a > b do
a := a – b;
• если условие никогда не станет ложным, программа
зацикливается
a := 4; b := 6;
while a < b do
d := a + b;
62

63.

63
Сколько раз выполняется цикл?
a := 4; b := 6;
while a < b do a := a + 1;
2 раза
a=6
a := 4; b := 6;
while a < b do a := a + b;
1 раз
a = 10
a := 4; b := 6;
while a > b do a := a + 1;
0 раз
a=4
a := 4; b := 6;
while a < b do b := a - b;
1 раз
b = -2
a := 4; b := 6;
while a < b do a := a - 1;
зацикливание

64.

Замена for на while и наоборот
for i:=1 to 10 do begin
{тело цикла}
end;
for i:=a downto b do
begin
{тело цикла}
end;
i := 1;
while i <= 10 do begin
{тело цикла}
i := i + 1;
end;
i := a;
while i >= b do begin
{тело цикла}
i := i - 1;
end;
Замена цикла for на while возможна всегда.
Замена while на for возможна только тогда, когда
можно заранее рассчитать число шагов цикла.
64

65.

Задания
65
«4»: Ввести целое число и найти сумму его цифр.
Пример:
Введите целое число:
1234
Сумма цифр числа 1234 равна 10.
«5»: Ввести целое число и определить, верно ли,
что в его записи есть две одинаковые цифры.
Пример:
Введите целое число:
Введите целое число:
1234
1224
Нет.
Да.