Тема: §7 Запись алгоритмов на языке программирования Паскаль

ЗАПИСЬ АЛГОРИТМОВ НА ЯЗЫКАХ ПРОГРАММИРОВАНИЯ

ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ

• языки программирования
• данные
• структура данных
• идентификаторы
• операторы
• трассировочные таблицы

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

Язык программирования – формальная знаковая система, предназначенная для записи компьютерных программ.

Компьютерную программу можно считать последовательностью строк символов некоторого алфавита. Современные системы програм-мирования допускают использование визуальных элементов (окон, иконок и др.) для построения программ, в частности, для создания интерфейса пользователя. Такое программирование называют визуальным . Тем не менее, основная, алгоритмическая часть любой программы строится с использованием символьных средств.

PascalABC.NET

КуМир

 Структурная организация данных

Информация, представленная в виде, пригодном для автоматизирован-ной обработки, называется данными .

Компьютер оперирует только одним видом данных – отдельными битами, или двоичными цифрами.

Под структурой данных в общем случае понимают множество эле­ментов данных и множество связей между ними.

!

Различают простые и сложные структуры данных.

На основе простых структур строятся сложные структуры данных :

• массивы,
• списки,
• графы,
• деревья и др.

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

К ним относятся:

• числовые,
• символьные,
• логические и др.

Некоторые простые типы данных

Некоторые простые типы данных

логический

числовые

Boolean (1 байт)

символьный

Char (1 байт)

целые

Integer

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

Real (8 байт)

Информация по каждому типу однозначно определяет:

• множество допустимых значений, которые может иметь тот или иной объект описываемого типа;
• множество допустимых операций, которые применимы к объекту описываемого типа;
• объём выделенной памяти для хранения данных указанного типа

Комментарии

Типы данных и, отводимое под них место, могут различаться в разных версиях Паскаля

Основные элементы языка Pascal

• алфавит языка:

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

Идентификаторы

Все величины имеют имена ( идентификаторы ), формируемые по определённым правилам:

• имя может состоять из буквы или последовательности букв латин­ского алфавита, цифр и символа подчёркивания, но начинаться такая последовательность должна с буквы или символа подчёр­кивания;
• желательно, чтобы имя отражало смысл величины;
• имя не должно совпадать ни с одним из зарезервированных слов.

!

12N

N12

Summa X

Summa_X

Факториал

Factorial

Program

MyProgram

меньше умножение div деление больше целочисленное деление = меньше или равно mod остаток от целочисленного деления больше или равно Логические операции Приоритет операций 1 not 2 and not логическое отрицание *, /, div, mod, and 3 or логическое И 4 xor логическое ИЛИ +, –, or, xor =, , , =, исключающее ИЛИ " width="640"

Операции в языке Pascal

Операции отношений

Арифметические операции

=

+

равно

сложение

–

вычитание

не равно

*

/

меньше

умножение

div

деление

больше

целочисленное деление

=

меньше или равно

mod

остаток от целочисленного деления

больше или равно

Логические операции

Приоритет операций

1

not

2

and

not

логическое отрицание

*, /, div, mod, and

3

or

логическое И

4

xor

логическое ИЛИ

+, –, or, xor

=, , , =,

исключающее ИЛИ

; begin ; end. Заголовок программы Блок описания данных Блок описания действий (программный блок) Данные, обрабатываемые компьютером, хранятся в памяти. С точки зрения языка Pascal она разделена на секции, называемые переменными . Каждая переменная имеет имя, тип и значение; значения переменных могут меняться в ходе выполнения программы. Блок описания действий начинается со слова begin , а заканчивается словом end и знаком точки. Действия представляются операторами . Операторы разделяются точкой с запятой. Комментарии Текст появляется " width="640"

Структура программы

program ;

var ;

const ;

begin

;

end.

Заголовок программы

Блок описания данных

Блок описания действий (программный блок)

Данные, обрабатываемые компьютером, хранятся в памяти. С точки зрения языка Pascal она разделена на секции, называемые переменными . Каждая переменная имеет имя, тип и значение; значения переменных могут меняться в ходе выполнения программы.

Блок описания действий начинается со слова begin , а заканчивается словом end и знаком точки. Действия представляются операторами . Операторы разделяются точкой с запятой.

Комментарии

Текст появляется

Основные операторы языка Pascal

Название

Общий вид

Присваивание

Имя переменной := Значение

Ввод с клавиатуры

readln ( список ввода )

Вывод на экран

writeln ( список вывода )

Условный

If Условие then Оператор1

Цикл с предусловием

Цикл с постусловием

else Оператор2

while Условие do Тело цикла

repeat

Цикл с параметром с шагом +1

Тело цикла

for Переменная := Нач_знач to Кон_знач do Тело цикла

Цикл с параметром с шагом –1

until Условие

for Переменная := Нач_знач downto Кон_знач do Тело цикла

Анализ программ. Трассировочные таблицы

Для анализа свойств алгоритма и проверки его соответствия решаемой задаче используются трассировочные таблицы . В них фиксируется пошаговое исполнение алгоритма (программы), что позволяет наглядно представлять значения переменных, изменяющиеся при его выполнении. Поэтому трассировочные таблицы иначе называют таблицами значений .

Используются трассировочные таблицы двух видов:

2

1

таблицы, каждая строка которых отражает результат выполнения группы действий

таблицы, каждая строка которых отражает результат одного действия

Комментарии

Кнопки «Далее» - переходы на два скрытых слайда с примерами трассировочных таблиц (выбирается на усмотрение учителя)

Пробел / щелчок на поле – переход на 14-й слайд

0 do begin Y := Y * 10 + X mod 10; Команда или условие X := X div 10 Y X № end ; writeln (Y) end. Составить трассировочную таблицу при Х = 356 . 356 356 readln (X) 1 0 2 Y := 0 0 В заголовке таблицы поместим имена всех переменных, используемых в программе. В отдельном столбце будем записывать команды и условия, имеющиеся в программе. Каждая строка таблицы соответствует одному шагу алгоритма. да X 0 3 program Number; var X, Y: longint; begin readln(X); Y := 0; while X 0 do begin Y := Y * 10 + X mod 10; X := X div 10 end ; writeln (Y) end. 6 4 6 Y := Y*10 + X mod 10 35 35 X := X div 10 5 да 6 X 0 65 7 65 Y := Y*10 + X mod 10 3 8 X := X div 10 3 да 9 X 0 653 653 10 Y := Y*10 + X mod 10 0 0 11 X := X div 10 нет X 0 12 13 writeln (Y) " width="640"

Трассировочная таблица первого вида

Пример 1. Дана программа:

Значение выражения

program Number;

var X, Y: longint;

begin

readln(X);

Y := 0;

while X 0 do

begin

Y := Y * 10 + X mod 10;

Команда или условие

X := X div 10

Y

X

№

end ;

writeln (Y)

end.

Составить трассировочную таблицу при Х = 356 .

356

356

readln (X)

1

0

2

Y := 0

0

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

да

X 0

3

program Number;

var X, Y: longint;

begin

readln(X);

Y := 0;

while X 0 do

begin

Y := Y * 10 + X mod 10;

X := X div 10

end ;

writeln (Y)

end.

6

4

6

Y := Y*10 + X mod 10

35

35

X := X div 10

5

да

6

X 0

65

7

65

Y := Y*10 + X mod 10

3

8

X := X div 10

3

да

9

X 0

653

653

10

Y := Y*10 + X mod 10

0

0

11

X := X div 10

нет

X 0

12

13

writeln (Y)

Трассировочная таблица второго вида

Пример 2. Дана программа:

program Summa;

var k, x, S: integer;

begin

S := 0;

for k := 0 to 4 do

begin

x := k * 3 + 2;

S := S + x

end ;

writeln (S)

end.

Определите, что будет напечатано в результате выполнения программы.

Результат в КТ

x

k

S

–

0

–

Начальные значения

0

2

2

1

Построим трассировочную таблицу второго вида, отражая в каждой строке результат группы действий. Группу действий ограничим контрольной точкой ( КТ ): выполнение алгоритма продолжается до контрольной точки и приостанавливается после выполнения отмеченной ею строки.

Будем считать, что контрольная точка поставлена на заголовке цикла.

1

2

5

7

program Summa;

var k, x, S: integer;

begin

S := 0;

for k := 0 to 4 do

begin

x := k * 3 + 2;

S := S + x

end ;

writeln (S)

end.

2

3

8

15

3

26

4

11

4

5

14

40

Ответ: S = 40

Другие приёмы анализа программ

Решение:

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

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

Начальное значение переменной S = 0 . При каждом выполнении тела цикла S увеличивается на 30 . Таким образом, искомое значение S = 30 ∙ k , где k — число выполнений тела цикла.

Начальное значение переменной n = 1 . При каж-дом выполнении тела цикла значение n увеличивается в 5 раз, т.е. n = 5, 25, 125 …, 5 k .

var n, s: integer; begin n := 1; s := 0; while n do begin s := s + 30; n := n * 5 end ; write(s) end .

var n, S: integer; begin n := 1; S := 0; while n do begin S := S + 30; n := n * 5 end ; write(s) end .

Выясним, при каком условии произойдёт выход из цикла. Цикл выполняется, пока n ≤ 625 . Следовательно, цикл завершится при достижении S значения, большего 625 = 5 4 , т.е. при n = 5 5 .

Таким образом цикл выполнится 5 раз. Следовательно, S = 30 ∙ 5 =150 .

Ответ: S = 150

13

Компьютерную программу можно считать последовательностью строк символов некоторого алфавита. Современные системы програм-мирования и языки допускают использование визуальных элементов (окон, иконок и др.) для построения программ и создания интерфейса пользователя. Тем не менее, основная, алгоритмическая часть любой программы строится с использованием символьных средств.

Компьютер оперирует только одним видом данных – отдельными битами, или двоичными цифрами. Задачи, решаемые с помощью компьютера, оперируют данными, имеющими форму чисел, символов, текстов и более сложных структур. Алгоритмы для обработки этих данных создаются с учётом их структуры – множества элементов данных и множества связей между ними.

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

Для анализа свойств алгоритма и проверки его соответствия решаемой задаче используются трассировочные таблицы. В них фиксируется пошаговое исполнение алгоритма (программы), что позволяет наглядно представлять значения переменных, изменяющиеся при его выполнении. Используются трассировочные таблицы двух видов:

• таблицы, каждая строка которых отражает результат одного действия;
• таблицы, каждая строка которых отражает результат выполнения группы действий.

0 do begin d := x mod 10; R := 10*R + d; x := x div 10 end ; writeln(R) end . var x, d, R: longint; begin readln(x); R := 0; while x 0 do begin d := x mod 10; R := 10*R + d; x := x div 10 end ; writeln(R) end . Решение: Сложность этого задания состоит в том, чтобы разобраться, что делает программа. Нетрудно заметить, что данная программа «переворачивает» исходное число х . Таким образом, надо найти двузначное число, сумма цифр которого равна 16 : 16 = 7 + 9 16 = 8 + 8 16 = 9 + 7 Наименьшее число: 79 Ответ: 79 Комментарии Задание 20 из Демоверсии ЕГЭ-2017 Ответ 13 " width="640"

Вопросы и задания

Задание 1. Ниже дана программа. Получив на вход натуральное число x , программа печатает число R . Укажи-те такое число x , при вводе которого будет напечатано двузначное число, сумма цифр которого равна 16 . Если таких чисел несколько, укажите наименьшее из них.

var x, d, R: longint; begin readln(x); R := 0; while x 0 do begin d := x mod 10; R := 10*R + d; x := x div 10 end ; writeln(R) end .

var x, d, R: longint; begin readln(x); R := 0; while x 0 do begin d := x mod 10; R := 10*R + d; x := x div 10 end ; writeln(R) end .

Решение:

Сложность этого задания состоит в том, чтобы разобраться, что делает программа.

Нетрудно заметить, что данная программа «переворачивает» исходное число х . Таким образом, надо найти двузначное число, сумма цифр которого равна 16 :

16 = 7 + 9

16 = 8 + 8

16 = 9 + 7

Наименьшее число: 79

Ответ: 79

Комментарии

Задание 20 из Демоверсии ЕГЭ-2017

Ответ

13

100 ), программа печатает число M . Укажите наименьшее значение переменой x , при вводе которого алгоритм печатает 26 . var x, L, M: integer; begin readln(x); L := x; M := 52; while L M do if L M then L := L – M else M := M – L; writeln(M) end . var x, L, M: integer; begin readln(x); L := x; M := 52; while L M do if L M then L := L – M else M := M – L; writeln(M) end . Решение: Данная программа реализует алгоритм Евклида для вычисления наибольшего общего делителя двух чисел – НОД ( M , L ). Тогда, по условию задачи НОД ( 52 , х ) = 26 . Отсюда, х = 104, 130, 156 … Наименьшее х = 104, но НОД ( 52 , 104 ) = 52. Следовательно, х = 130 . Ответ: 130 Комментарии Задание 20 из ЕГЭ-2017 Ответ 13 " width="640"

Вопросы и задания

Задание 2. Получив на вход натуральное число x ( x 100 ), программа печатает число M . Укажите наименьшее значение переменой x , при вводе которого алгоритм печатает 26 .

var x, L, M: integer; begin readln(x); L := x; M := 52; while L M do if L M then L := L – M else M := M – L; writeln(M) end .

var x, L, M: integer; begin readln(x); L := x; M := 52; while L M do if L M then L := L – M else M := M – L; writeln(M) end .

Решение:

Данная программа реализует алгоритм Евклида для вычисления наибольшего общего делителя двух чисел – НОД ( M , L ).

Тогда, по условию задачи НОД ( 52 , х ) = 26 .

Отсюда, х = 104, 130, 156 …

Наименьшее х = 104, но НОД ( 52 , 104 ) = 52.

Следовательно, х = 130 .

Ответ: 130

Комментарии

Задание 20 из ЕГЭ-2017

Ответ

13

Вопросы и задания

Задание 3. Дана программа. Что будет напечатано после выполнения программы?

var k, S: integer; begin k := 10; S := 0; while k do begin S := S + k; k := k + 5 end ; write (s) end .

Решение:

Данная программа находит сумму арифметической прогрессии:

S = 10 + 15 + 20 + … + 115 .

Формула для вычисления суммы первых n членов арифметической прогрессии:

В нашем случае:

n = ( 115 –10 ) : 5 + 1 = 22 .

Тогда:

S = ( 10 + 115 ) ∙ 22 / 2 = 1375 .

Ответ: 1375

var k, S: integer; begin k := 10; S := 0; while k do begin S := S + k; k := k + 5 end ; write (s) end .

Комментарии

Задание 8 из ЕГЭ-2017

Ответ

13