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

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

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

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

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

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

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

На основе простых структур строятся сложные структуры данных:
массивы,
списки,
графы,
деревья и др.

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

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

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

program <имя программы>;

var <переменные с указанием типов>;
const <постоянные <с указанием типов>>;

begin
<последовательность команд>;
end.

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

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

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

1

2

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

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

Пример 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
end;
writeln (Y)
end.

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

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

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.

Пример 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.

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

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.

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

Ответ: 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 + 8
16 = 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.

Решение:
Данная программа находит сумму арифметической прогрессии:
S = 10 + 15 + 20 + … + 115.
Формула для вычисления суммы первых n членов арифметической прогрессии:
𝑆𝑆= 𝑎 1 + 𝑎 𝑛 2 𝑎 1 𝑎𝑎 𝑎 1 1 𝑎 1 + 𝑎 𝑛 𝑎𝑎 𝑎 𝑛 𝑛𝑛 𝑎 𝑛 𝑎 1 + 𝑎 𝑛 2 2 𝑎 1 + 𝑎 𝑛 2 ∙𝑛𝑛
В нашем случае:
n = (115 –10) : 5 + 1 = 22.
Тогда:
S = (10 + 115) ∙ 22 / 2 = 1375.


Ответ: 1375