Алгоритмы и подпрограммы

Введение в подпрограммы

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

Описание вспомогательных (дополнительных) алгоритмов в языках высокого уровня состоит из:

• тела – набора операторов, которые выполняются при вызове процедуры;
• заголовка – описании имени, а также параметров (при необходимости).

Для активации заданного набора операций нужно использовать команду вызова и имя процедуры. Каждая выполненная последовательность после обработки компилятором получает пролог и эпилог. Они необходимы для сохранения и восстановления вспомогательных алгоритмов.

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

Параметры

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

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

Виды параметров

Параметры у вспомогательных алгоритмов бывают:

• фактическими;
• формальными.

Формальные параметры описываются в заголовке подпрограммы. Их список формирует список условных переменных. При помощи формальных параметров разработчик может описать информацию, передаваемую в подпрограмму.

Списки формальных параметров определяют:

• порядок;
• типы;
• количество параметров.

Фактические параметры используют, указав их при вызове подпрограммы. Они обязательно существуют в реальной жизни. Выступают списками определенных значений, передаваемых во вспомогательный алгоритм для дальнейшей обработки. Списком фактических параметров служат выражения, написанные при помощи разделителя – запятых. Их значения будут последовательно подставляться во фрагмент кода вместо формальных данных.

О способах передачи

Информатика в школе рассматривает элементарные примеры процедур, не углубляясь в их особенности. Разработчикам необходимо помнить о нескольких способах их передачи в итоговом проекте:

1. Стеками. Вся информация расположена на стеке, а их типы, порядок и количество не контролируются компилятором.
2. По имени. Формальный параметр получит произвольное выражение, а затем произойдут необходимые вычисления. Они осуществляются внутри процесса.
3. По ссылкам. Формальный параметр находится в фактическом. Программисты чаще всего используют данный вариант, указав ссылки на фактическое значение.
4. По значению. Формальный параметр получает значение фактического, содержит его копию.

Использование вспомогательных (дополнительных) алгоритмов для разработчика – один из способов облегчения написания исходного кода.

Что такое алгоритм

В широком смысле алгоритм — это последовательность действий, которые нужно выполнить, чтобы получить определённый результат.

Слово «алгоритм» произошло от имени персидского математика Абу Абдуллаха аль-Хорезми. В своём труде «Китаб аль-джебр валь-мукабала» учёный впервые дал описание десятичной системы счисления. А наука алгебра получила своё название в честь его книги.

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

1. Устанавливаем капсулу.

2. Проверяем уровень воды в специальном отсеке.

3. Если воды недостаточно — доливаем.

4. Ставим чашку под кран кофемашины.

5. Запускаем кофемашину.

6. Выключаем кофемашину, когда чашка наполнилась.

7. Достаём кружку.

Если не перепутать порядок шагов, то с помощью такой инструкции любой сможет порадовать себя чашкой горячего кофе. Достаточно лишь знать, как установить капсулу и включить/выключить кофемашину.

С компьютерами намного сложнее. Им неизвестно, что значит «установить капсулу», «долить воду», «запустить кофемашину» и так далее. Чтобы запрограммировать робота-баристу под определённую модель бытовой техники, алгоритм придётся расписать более детально:

1. Возьми штепсельную вилку шнура питания кофемашины.

2. Вставь штепсельную вилку в розетку.

3. Проверь, есть ли вода в отсеке для воды.

4. Если воды недостаточно:

4.1. Подними крышку отсека.

4.2. Возьми кувшин с водой.

4.3. Лей воду из кувшина в отсек, пока он не заполнится.

4.4. Закрой крышку отсека.

4.5. Поставь кувшин с водой на стол.

5. Открой крышку кофемашины.

6. Возьми из коробки капсулу с кофе.

7. Вставь капсулу в отсек для капсулы.

8. Закрой крышку кофемашины.

9. Поверни рычаг кофемашины вправо.

10. Когда чашка наполнится, поверни рычаг кофемашины влево.

11. Возьми кружку.

12. Принеси кружку хозяину.

Конечно, если мы собираем робота с нуля, то даже такой детализации будет недостаточно. Каждую процедуру ещё нужно будет реализовать на языке программирования (например, на C++ или Python), что само по себе — нетривиальная задача. Тем не менее описание стало более точным и формальным.

C научной точки зрения определение алгоритма, которое мы дали выше, не совсем точное. Ведь не всякую последовательность действий, приводящую к результату, можно назвать алгоритмом.

Виды алгоритмов и примеры

По конструкции алгоритмы можно разделить на несколько групп.

Линейные алгоритмы

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

Пример. Напишите программу, которая умножает число, введённое пользователем, на 100 и выводит результат на экран.

Последовательность действий уже изложена в задании: ввести число → умножить на 100 → вывести результат. Переведём это на язык блок-схем:

Изображение: Skillbox Media

Ниже приведена реализация алгоритма на языке Python:

Ветвящиеся алгоритмы

В ветвящихся алгоритмах ход программы зависит от значения логического выражения в блоке «Условие». По большому счёту, любое логическое выражение сводится к выбору между истиной (True, «1») или ложью (False, «0»).

Пример. Напишите программу, которая запрашивает у пользователя возраст. Если он равен или больше 18, программа выводит приветствие, увеличивает значения счётчика посетителей на 1 и прощается, а если меньше — сразу прощается и завершает работу.

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

Изображение: Skillbox Media

То же самое на Python:

Когда пользователь вводит 18 или больше, программа выполняет часть кода, которая записана под оператором if. Если же возраст меньше 18, то на экран выводится сообщение «Доступ запрещён» и программа завершает работу.

Циклические алгоритмы

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

Пример. Напишите программу, которая циклично увеличивает значения счётчика на 1 и на каждом шаге выводит его значение. Когда значение счётчика достигнет 10, программа должна завершиться.

В основе нашего решения будет лежать следующее условие: если значение счётчика меньше 10 — прибавить 1, иначе — завершить работу. Вот как это выглядит в виде блок-схемы:

Изображение: Skillbox Media

Переведём это в код на Python

Обратите внимание, что мы не прописываем отдельную ветвь для случая «Нет»:. Результат работы программы:

Результат работы программы:

Рекурсивные алгоритмы

Рекурсия — это явление, при котором система вызывает саму себя, но с другими входными данными. Такие алгоритмы используют для обхода словарей в глубину, вычисления факториала, расчёта степеней и других практических задач. В целом всё это можно сделать с помощью циклов, но код рекурсивных функций более лаконичен и удобочитаем.

Пример. Пользователь вводит число n. Посчитайте его факториал и выведите результат на экран.

Вот как выглядит блок-схема рекурсивного алгоритма:

Изображение: Skillbox Media

На практике чисто последовательные, условные или циклические алгоритмы встречаются редко, но вместе они позволяют создать решение любой сложности.

Уровень абстракции

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

Программа, с другой стороны, является конкретной реализацией алгоритма. Она представляет собой набор инструкций на определенном языке программирования, который компьютер может понять и выполнить. Код программы — это набор команд, которые выполняются последовательно для достижения требуемого результата.

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

Таким образом, понимание разницы между алгоритмом и программой поможет программистам разрабатывать эффективные решения для задач, основываясь на логическом уровне абстракции и затем транслируя его в конкретный код программы.

Алгоритм: определяет логику решения

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

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

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

Таким образом, алгоритм определяет логику и методику решения задачи, а программа является конкретным кодом, который реализует эту логику, чтобы компьютер мог выполнить нужные операции и получить ожидаемый результат.

Программа: реализует конкретную логику

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

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

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

Таким образом, программа — это реализация алгоритма в виде кода, который определяет последовательность действий и логику работы компьютера для достижения нужного результата.

Презентация на тему: » Вспомогательный алгоритм Цель : понятие вспомогательного и основного алгоритма, структура вспомогательного алгоритма, метод пошаговой детализации.» — Транскрипт:

2

Вспомогательный алгоритм Цель : понятие вспомогательного и основного алгоритма, структура вспомогательного алгоритма, метод пошаговой детализации

3

2005 Bolgova N.A.2 ПЛАН 1. Определение вспомогательного алгоритма 2. Определение основного алгоритма 3. Структура вспомогательного алгоритма 4. Метод пошаговой детализации

4

2005 Bolgova N.A.3 Определение вспомогательного алгоритма Определение 1 Алгоритм, целиком используемый в составе другого алгоритма и имеющий собственное имя, называется ВСПОМОГАТЕЛЬНЫМ Определение 2 Алгоритм, по которому решается некоторая подзадача основной задачи и который выполняется многократно, называется ВСПОМОГАТЕЛЬНЫМ

5

2005 Bolgova N.A.4 В роли вспомогательного алгоритма может выступать любой алгоритм, имеющий ЗАГОЛОВОК, позволяющий вызывать его из других алгоритмов. В заголовке указывается НАЗВАНИЕ АЛГ, АРГУМЕНТЫ, (т.е. имена тех переменных, значения которых передаются вспомогательному алгоритму из основного), РЕЗУЛЬТАТЫ ( т.е. имена тех переменных, значения которых передаются из вспомогательного алгоритма основному).

6

2005 Bolgova N.A.5 Определение основного алгоритма Алгоритм, содержащий в себе обращение к вспомогательному алгоритму (или содержащий заголовок вспомогательного алгоритма) называется ОСНОВНЫМ

7

2005 Bolgova N.A.6 Каждый вспомогательный алгоритм — описывает решение какой-либо подзадачи ; -имеет линейную, разветвляющую, циклическую структуру; — может быть составлен заранее и к нему можно обратиться.

8

2005 Bolgova N.A.7 Задача 1: составить алгоритм рисования фигуры Чертежником

9

2005 Bolgova N.A.8 АЛГ скобка НАЧ шаг поворот шаг поворот шаг КОН

10

2005 Bolgova N.A.9 АЛГ фигура НАЧ СКОБКА поворот СКОБКА поворот СКОБКА поворот СКОБКА КОН

11

2005 Bolgova N.A.10 Задача 2 Составить алгоритм поиска большего из трех целых чисел (БИТ) АЛГ БИТ ( цел А, В, С, max) арг А, В, С рез max НАЧ БИД (А, В, max )БИД (А, В, max ) А := МАХ, В := С БИД (А, В, max ) КОН

12

2005 Bolgova N.A.11 АЛГ БИД ( цел А, В, max) арг А, В рез max НАЧ если А>В то max := А иначе max := В все КОН Вспомогательный алгоритм

13

2005 Bolgova N.A.12 Блок — схема нач А, В, С БИД(А,В,Х) А := Мах В := С БИД(А,В,Х) max кон БИД(А,В,Х) А > В Max := AMax := B

14

2005 Bolgova N.A.13 Определение Метод составления алгоритма, при котором сначала пишется основной алгоритм, затем записывается обращение к вспомогательному и описывается вспомогательный алгоритм называется МЕТОДОМ ПОШАГОВОЙ ДЕТАЛИЗАЦИИ

15

2005 Bolgova N.A.14 Вопросы: Какой алгоритм называется вспомогательным? Какой алгоритм называется основным? Дайте определение метода пошаговой детализации.

Структурная методика

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

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

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

Линейный алгоритм

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

Алгоритмы, шаги которых описываются такими простыми действиями, называются линейными

Важно понимать, что линейность относится к способу выполнения алгоритма, а не к тому результату, который им достигается. Например, линейным алгоритмом можно описать построение сложного рисунка, но сами действия при его построении будут выполняться линейно, как только что было описано

Линейность алгоритма наглядно демонстрирует схема, показанная на рис. 5.1.

Идущие друг за другом действия линейного алгоритма образуют алгоритмическую конструкцию следование. Это — самая простая и естественная алгоритмическая конструкция, и она уже использовалась, например, в программах рисования квадратов, только не называлась. На графических схемах алгоритмов конструкция следование изображается в виде идущих друг за другом (сверху вниз или слева направо) прямоугольников, соединённых линиями или стрелками, показывающими направление выполнения алгоритма (рис. 5.2).

Рис. 5.2. Графическое изображение алгоритмической конструкции следование.

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

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

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

Следование

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

Это самый простой алгоритм, за предыдущим действие, всегда идет последующее. Иногда такая конструкция может быть увеличена или уточнена, более мелкими действиями. Разберем на примере, каждый человек, просыпаясь утром, идет умываться и чистить зубы.

1. Встать с постели

2. Пойти в ванную

3. Умыть лицо

4. Почистить зубы

5. Выйти из ванной комнаты

6. Заправить постель

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

Способы описания алгоритмов

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

1. Словесное описание — это когда структура алгоритма описывается естественным языком. Лучше всего вспомнить любой бытовой прибор (утюг, телевизор, микроволновую печь, холодильник и т. п.). Все эти приборы имеют инструкцию по эксплуатации, то есть перед нами типичное описание алгоритма словами, с учётом которых прибором надо пользоваться. Такой способ не формализован и не учитывает все возможные ситуации, возникающие при эксплуатации. К недостаткам словесного описания относят и неоднозначность толкования некоторых терминов.
   Представьте, что вы куда-то собрались, и вас интересует погода на улице. Словесное описание будет приблизительно таким:
   1) смотрим на градусник, определяем температуру на улице;
   2) если температура ниже 0, надеваем шубу, если выше — куртку.
2. Псевдокод — в этом случае можно говорить о естественном и частично формализованном языке, то есть это описание уже позволяет определить главные этапы решения задачи, что необходимо перед составлением программы — точной записи на языке программирования. Псевдокод характеризуется уже наличием формализованных конструкций и общепринятой математической символикой, однако строгих синтаксических правил по записи не существует.
3. Блок-схема. Схему, состоящую из блоков и линий, включая значения наиболее часто используемых блоков, уже рассмотрели выше. Но вернёмся к нашему примеру с погодой:
4. Программа — описание, созданное на языке алгоритмического программирования. Такой вариант характеризуется высокой степенью формализации, то есть появление программы позволяет решать прикладные задачи. В форме программы описываемый ранее пример будет выглядеть следующим образом:

Типы данных: простые и структурированные

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

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

Определение 5

Переменная представляет собой именованный объект (ячейку памяти), изменяющий свое значение.

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

Типом переменной задается:

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

Для каждого типа объем памяти определяется так, чтобы в него можно было поместить любое значение из допустимо¬го диапазона значений для данного типа.

Определение 6

Переменные, которые присутствуют в программе на протяжении всего периода ее работы, называются статическими.

Определение 7

Переменные, которые создаются и уничтожаются на разных этапах выполнения про¬граммы, называются динамическими.

Определение 8

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

Константы также имеют тип. Их возможно ука¬зывать явно или с помощью идентификаторов.

Чтобы повысить производительность и качество работы нужно иметь данные, которые будут максимально приближены к реальным аналогам.

Определение 9

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

Любой язык программирования имеет свои структурированные типы. Рассмотрим одну из таких структур — массив.

Определение 10

Массивом называют упорядоченную совокупность однотипных величин, которые имеют общее имя, порядковые номера у элементов (индексы).

Элементы массива хранятся в памяти компьютера по соседству в отличие от одиночных элементов. Массивы различают по количеству индексов элементов.

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

Определение 11

Количество элементов массива называется размерностью.

У одномерного массива его размерность записывают рядом с именем в круглых скобках.

Элементы одномерного массива вводятся поэлемен¬тно, в порядке, необходимом для решения конкретной задачи. При необходимости ввода всего массива элементы вводятся в порядке возрастания индексов.

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

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

В реальных задачах, как правило, присутствует любое количество циклов.

Ниже приведены блок-схемы циклических алгоритмов.

Подпрограмма

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

Программирование «снизу вверх»

Возможен и другой подход: сперва составляется множество подпрограмм, выполняющих различные неполные задачи, а после создается основная программа, включающая их вызовы. Иногда такие подпрограммы объединяются в библиотеку подпрограмм, которая может пополняться со временем. Такой подход называется методом программирования «снизу вверх».

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

Обращение к подпрограмме

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

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

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