Работа. Запись алгоритмов на языках программирования основные сведения об алгоритмах языки программирования
Скачать 0.64 Mb.
|
ЗАПИСЬ АЛГОРИТМОВ НА ЯЗЫКАХ ПРОГРАММИРОВАНИЯОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХязыки программирования
Язык программированияЯзык программирования – формальная знаковая система, предназначенная для записи компьютерных программ.Компьютерную программу можно считать последовательностью строк символов некоторого алфавита. Современные системы програм-мирования допускают использование визуальных элементов (окон, иконок и др.) для построения программ, в частности, для создания интерфейса пользователя. Такое программирование называют визуальным. Тем не менее, основная, алгоритмическая часть любой программы строится с использованием символьных средств.PascalABC.NET КуМир Структурная организация данныхИнформация, представленная в виде, пригодном для автоматизирован-ной обработки, называется данными.Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними. ! Различают простые и сложные структуры данных. Простые структуры данных не могут быть разделены на составные части больше, чем бит. К ним относятся:
На основе простых структур строятся сложные структуры данных:
Информация по каждому типу однозначно определяет:
Некоторые простые типы данных логический Boolean (1 байт) символьный Char (1 байт) числовые целые Integer вещественные Real (8 байт) Основные элементы языка Pascal
ИдентификаторыВсе величины имеют имена (идентификаторы), формируемые по определённым правилам:
! 12N Summa X Факториал Program N12 Summa_X Factorial MyProgram Операции в языке Pascal
Структура программыБлок описания данных Блок описания действий (программный блок) Заголовок программы program <имя программы>; var <переменные с указанием типов>; const <постоянные <с указанием типов>>; begin <последовательность команд>; end. Данные, обрабатываемые компьютером, хранятся в памяти. С точки зрения языка Pascal она разделена на секции, называемые переменными. Каждая переменная имеет имя, тип и значение; значения переменных могут меняться в ходе выполнения программы. Блок описания действий начинается со слова begin, а заканчивается словом end и знаком точки. Действия представляются операторами. Операторы разделяются точкой с запятой. Основные операторы языка Pascal
Анализ программ. Трассировочные таблицыДля анализа свойств алгоритма и проверки его соответствия решаемой задаче используются трассировочные таблицы. В них фиксируется пошаговое исполнение алгоритма (программы), что позволяет наглядно представлять значения переменных, изменяющиеся при его выполнении. Поэтому трассировочные таблицы иначе называют таблицами значений.Используются трассировочные таблицы двух видов: 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. № Команда или условие Значение выражения X Y 1 readln (X) 356 356 2 Y := 0 0 0 3 X > 0 да 4 Y := Y*10 + X mod 10 6 6 5 X := X div 10 35 35 6 X > 0 да 7 Y := Y*10 + X mod 10 65 65 8 X := X div 10 3 3 9 X > 0 да 10 Y := Y*10 + X mod 10 653 653 11 X := X div 10 0 0 12 X > 0 нет 13 writeln (Y) В заголовке таблицы поместим имена всех переменных, используемых в программе. В отдельном столбце будем записывать команды и условия, имеющиеся в программе. Каждая строка таблицы соответствует одному шагу алгоритма. 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. Результат в КТ k x S Начальные значения – – 0 Построим трассировочную таблицу второго вида, отражая в каждой строке результат группы действий. Группу действий ограничим контрольной точкой (КТ): выполнение алгоритма продолжается до контрольной точки и приостанавливается после выполнения отмеченной ею строки. Будем считать, что контрольная точка поставлена на заголовке цикла. 1 0 2 2 2 1 5 7 3 2 8 15 4 3 11 26 5 4 14 40 Ответ: 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 членов арифметической прогрессии: В нашем случае: n = (115 –10) : 5 + 1 = 22. Тогда: S = (10 + 115) ∙ 22 / 2 = 1375. Ответ: 1375 Ответ |