Файл: Запись алгоритмов на языках программирования основные сведения об алгоритмах языки программирования.pptx

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Некоторые простые типы данныхлогическийBoolean (1 байт)символьныйChar (1 байт)числовыецелыеIntegerвещественныеReal (8 байт)

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

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

---

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

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

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

!12NSumma XФакториалProgramN12Summa_XFactorialMyProgram

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

Операции отношений
=	равно
<>	не равно
<	меньше
>	больше
<=	меньше или равно
>=	больше или равно

Логические операции
not	логическое отрицание
and	логическое И
or	логическое ИЛИ
xor	исключающее ИЛИ

Приоритет операций
1	not
2	*, /, div, mod, and
3	+, –, or, xor
4	=, <>, >, <, >=, <=

Арифметические операции
+	сложение
–	вычитание
*	умножение
/	деление
div	целочисленное деление
mod	остаток от целочисленного деления

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

Блок описания данныхБлок описания действий (программный блок)Заголовок программыprogram <имя программы>;var <переменные с указанием типов>; const <постоянные <с указанием типов>>;begin<последовательность команд>;end.Данные, обрабатываемые компьютером, хранятся в памяти. С точки зрения языка Pascal она разделена на секции, называемые переменными. Каждая переменная имеет имя, тип и значение; значения переменных могут меняться в ходе выполнения программы.Блок описания действий начинается со слова begin, а заканчивается словом

---

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

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

Название	Общий вид
Присваивание	Имя переменной := Значение
Ввод с клавиатуры	readln (список ввода)
Вывод на экран	writeln (список вывода)
Условный	If Условие then Оператор1 else Оператор2
Цикл с предусловием	while Условие do Тело цикла
Цикл с постусловием	repeat Тело цикла until Условие
Цикл с параметром с шагом +1	for Переменная := Нач_знач to Кон_знач do Тело цикла
Цикл с параметром с шагом –1	for Переменная := Нач_знач downto Кон_знач do Тело цикла

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

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

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

Пример 1. Дана программа:program Number;var X, Y: longint; beginreadln(X); Y := 0;while X > 0 dobegin Y := Y * 10 + X mod 10; X := X div 10end;writeln (Y)end.Составить трассировочную таблицу при Х = 356. №Команда или условиеЗначение выраженияXY1readln (X)3563562Y := 0003X > 0да4Y := Y*10 + X mod 10665X := X div 1035356X > 0да7Y := Y*10 + X mod 1065658X := X div 10339X > 0да10Y := Y*10 + X mod 1065365311X := X div 100012X > 0нет13writeln (Y)В заголовке таблицы поместим имена всех переменных, используемых в программе. В отдельном столбце будем записывать команды и условия, имеющиеся в программе. Каждая строка таблицы соответствует

---

одному шагу алгоритма.program Number;var X, Y: longint; beginreadln(X); Y := 0;while X > 0 dobegin Y := Y * 10 + X mod 10; X := X div 10end;writeln (Y)end.

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

Пример 2. Дана программа:program Summa;var k, x, S: integer; beginS := 0;for k := 0 to 4 dobegin x := k * 3 + 2; S := S + xend;writeln (S)end.Определите, что будет напечатано в результате выполнения программы. program Summa;var k, x, S: integer; beginS := 0;for k := 0 to 4 dobegin x := k * 3 + 2; S := S + xend;writeln (S)end.Результат в КТkxSНачальные значения––0Построим трассировочную таблицу второго вида, отражая в каждой строке результат группы действий. Группу действий ограничим контрольной точкой (КТ): выполнение алгоритма продолжается до контрольной точки и приостанавливается после выполнения отмеченной ею строки.Будем считать, что контрольная точка поставлена на заголовке цикла.1022215732815431126541440Ответ: S = 40

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

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

var n, s: integer; begin n := 1; s := 0; while n <= 625 do begin s := s + 30; n := n * 5 end; write(s) end.var n, S: integer; begin n := 1; S := 0; while n <= 625 do begin S := S + 30; n := n * 5 end; write(s) end.Решение: Выясним, какую функцию выполняет каждая из переменных, задействованных в программе.Начальное значение переменной S = 0. При каждом выполнении тела цикла S увеличивается на 30. Таким образом, искомое значение S = 30 ∙ k, где k — число выполнений тела цикла.Начальное значение переменной n = 1. При каж-дом выполнении тела цикла значение n увеличивается в 5 раз, т.е. n = 5, 25, 125 …, 5k.Выясним, при каком условии произойдёт выход из цикла. Цикл выполняется, пока n ≤ 625. Следовательно, цикл завершится при достижении S значения, большего 625 = 54, т.е. при n = 55.Таким образом цикл выполнится 5 раз. Следовательно, S = 30 ∙ 5 =150.Ответ: S = 150 Компьютер оперирует только одним видом данных – отдельными битами, или двоичными цифрами. Задачи, решаемые с помощью компьютера, оперируют данными, имеющими форму чисел, символов, текстов и более сложных структур. Алгоритмы для обработки этих данных создаются с учётом их структуры – множества элементов данных и множества связей между ними. Для анализа свойств алгоритма и проверки его соответствия решаемой задаче используются трассировочные таблицы. В них фиксируется пошаговое исполнение алгоритма (программы), что позволяет наглядно представлять значения переменных, изменяющиеся при его выполнении. Используются трассировочные таблицы двух видов:

---

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

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

Задание 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 + 816 = 9 + 7Наименьшее число: 79Ответ: 79Ответ

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

Задание 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Ответ

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

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

var k, S: integer; begin k := 10; S := 0; while k < 120 do begin S := S + k; k := k + 5 end; write (s) end. var k, S: integer; begin k := 10; S := 0; while k < 120 do begin S := S + k; k := k + 5 end; write (s) end. Решение: Данная программа находит сумму арифметической прогрессии:

---