программирование. Структурное программирование основные сведения об алгоритмах структурное программирование
 Скачать 1.85 Mb.
|
СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХструктурное программирование
Структурное программированиеСтруктурное программирование – технология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры логически целостных фрагментов (блоков). ! Э́дсгер Ви́бе Де́йкстра (11.05.1930–6.08.2002) – нидерландский учёный, труды которого оказали влияние на развитие информатики и информационных технологий; один из разработчиков концепции структурного про-граммирования, исследователь формальной верификации и распределенных вычислений. Автор нескольких книг и множества статей, самые известные публикации – книги «Дисциплина программирования», «Заметки по структурному программированию», статья «О вреде оператора GOTO». Принципы структурного программированияНекоторые принципы структурного программирования
Вспомогательный алгоритмПример 1. Найти периметр треугольника АВС, заданного координатами своих вершин – (XA, YA), (XB, YB), (XC, YC).(x2; y2) (x1; y1) x1 x2 y2 y1 ГЕОМЕТРИЯ Решение: Чтобы найти периметр треугольника, надо знать длины его сторон. Для вычисления длины отрезка по координатам его концов используем формулу из геометрии. Действия по вычислению длины отрезка представляют собой логически целостный фрагмент, который можно оформить в виде вспомогательного алгоритма. Вызывая вспомогательный алгоритм с разными исходными данными, вычислим длины всех сторон. А затем Найдем периметр. Вспомогательный алгоритм – это алгоритм, целиком используемый в составе другого алгоритма. При вызове вспомогательного алгоритма указываются его параметры (входные данные и результаты). ! Блок-схема Пример программирования сверху внизНачало Отрезок Конец Начало Периметр Конец P := D Отрезок (XА, YA, XB, YB, D) XА, YA, XB, YB, XC, YC P := P + D Отрезок (XB, YB, XC, YC, D) P := P + D Отрезок (XА, YA, XC, YC, D) P X1, Y1, X2, Y2 REZ D := SQRT (SQR(X1-X2)+SQR(Y1-Y2)) Каким будет результат работы алгоритма при следующих исходных данных: XA = 1, YA = 1, XB = 1, YB = 5, XC = 4, YC = 1? ? Рекурсивные алгоритмы? ? ? ? ? ? 5 4 3 2 1 Рекурсивные алгоритмыАлгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе. В рекурсивном определении должно присутствовать ограничение (граничное условие), при выходе на которое дальнейшая инициация рекурсивных обращений прекращается. ! Приведите примеры рекурсии, встречающиеся в жизни, природе или литературных произведениях. ? Ночь, улица, фонарь, аптека, Бессмысленный и тусклый свет. Живи еще хоть четверть века – Все будет так. Исхода нет. Умрешь – начнешь опять сначала И повторится все, как встарь: Ночь, ледяная рябь канала, Аптека, улица, фонарь. А. Блок Пример 2. Числа Фибоначчи – элементы последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … , в которой первые два числа равны 1, а каждое следующее число равно сумме двух предыдущих чисел. Запишите рекуррентное определение чисел Фибоначчи. Ответ: F (n) = 1 при n ≤ 2; F (n) = F (n-1) + F (n-2) при n > 2. Пример 3. Запишите рекуррентное определение функции, вычисляющей количество цифр в натуральном числе n. Ответ: К (n) = 1 при n < 10; К (n) = К (n div 10) + 1 при n ≥ 10. Пример 4. Алгоритм вычисления значения функции F (n), где n – натуральное число, задан следующими соотношениями: F (1) = 2; F (n) = n ∙ F (n – 1) при n > 1. Определите значение функции F (6). Решение: F (1) = 2 F (2) = 2 ∙ F (1) = 2 ∙ 2 = 4 F (3) = 3 ∙ F (2) = 3 ∙ 4 = 12
F (4) = 4 ∙ F (3) = 4 ∙ 12 = 48 F (5) = 5 ∙ F (4) = 5 ∙ 48 = 240 F (6) = 6 ∙ F (5) = 6 ∙ 240 = 1440 Подобные вычисления можно проводить в уме, а их результаты фиксировать в таблице: Ответ: 1440 Подпрограммы в ПаскалеПодпрограмма – относительно независимая часть программы, оформленная специальным образом и имеющая оригинальное имя, по которому ее можно вызывать в тексте программы.Подпрограммы в Паскале Процедуры Функции ПроцедураПроцедура – подпрограмма, имеющая произволь-ное количество входных и выходных данных. ! Описание процедуры: procedure <имя>(<описание параметров-значений>; var <описание параметров-переменных>); begin <операторы> end; В заголовке процедуры после её имени приводится перечень формальных параметров и их типов. Для вызова процедуры достаточно указать её имя со списком фактических параметров. Между фактическими и формальными параметрами должно быть полное соответствие по количеству, порядку следования и типу. ФункцияФункция – подпрограмма, имеющая единственный результат, записываемый в ячейку памяти, имя которой совпадает с именем функции. ! Описание функции: function <имя>(<описание параметров>): <тип_функции>; begin <операторы> end; В заголовке функции после её имени приводится описание входных данных – перечень формальных параметров и их типов. Там же указывается тип самой функции, т. е. тип результата. В блоке функции должен присутствовать оператор: <имя_функции> := <результат>; Для вызова функции достаточно указать её имя со списком фактических параметров. Типы формальных параметров
Формальные параметры Параметры-значения Параметры-переменные Основные принципы структурного программирования:
Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.Запись вспомогательных алгоритмов в языках программирования осуществляется с помощью подпрограмм. В Паскале различают два вида подпрограмм: процедуры и функции.Вопросы и заданияЗадание 1. Запишите на языке Pascal подпрограмму нахождения длины отрезка, заданного координатами точек:
Начало Отрезок Конец X1, Y1, X2, Y2 REZ D := SQRT (SQR(X1-X2)+SQR(Y1-Y2)) Ответ (с помощью функции): function d (x1,y1, x2,y2: real): real; begin d := sqrt (sqr (x1-x2) + sqr (y1-y2)) end; Ответ (с помощью процедуры): procedure otrezok (x1,y1, x2,y2: real; var d: real); begin d := sqrt (sqr (x1-x2) + sqr (y1-y2)) end; Вопросы и заданияЗадание 2. С клавиатуры вводятся n чисел (n<100, запрашивается с клавиатуры). Требуется вывести числа в обратном порядке. Массив использовать нельзя.Подсказка. Составьте рекурсивную процедуру. var n: integer; procedure back (n: integer); var x: integer; begin if n > 0 then begin read (x); back (n-1); write (x,' ') end end; BEGIN write ('Введите n = '); readln (n); back (n) END. Программа Подсказка Вопросы и заданияЗадание 3. С клавиатуры вводится натуральное число Х. Требуется получить число Y, в котором записаны цифры числа Х в обратном порядке. Например, для Х=123 Y=321.Примечание. Решите задачу с помощью рекурсивной процедуры. var x, y: integer; procedure reverse (x: integer; var y: integer); begin if x>0 then begin y := y*10 + x mod 10; reverse (x div 10, y) end end; BEGIN write ('Введите число = '); readln (x); reverse (x, y); writeln ('Ответ: ', y) END. Программа Вопросы и заданияЗадание 4. У исполнителя Калькулятор есть две команды:1. Прибавить 1 – увеличивает число на экране на 1 2. Умножить на 2 – умножает число на экране на 2Программа для исполнителя – это последовательность команд.Сколько существует программ, для которых при исходном числе 4 результатом является число 14?Решение: Количество программ, с помощью которых можно попасть в некоторое число n будем рассматривать как функцию K (n). К(n) = 0 при n < 4; К(n) = 1 при n = 4; К(n) = К(n – 1) + К(n / 2) при n > 4.
Ответ: 5 Информационные источники
|