Алгоритм: понятие, свойства, структура и виды. Как делать алгоритм


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

Что такое алгоритм программы?Алгоритм программы — это точное предписание (совокупность последовательных шагов, схема действий), которое определяет процесс перехода от первичных данных к желаемому результату.

Формы представления алгоритма

Как известно, существует две формы представления алгоритма:

  1. Словесное описание алгоритма
  2. Графическое представление алгоритма (с помощью блок-схем)

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

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

Примеры алгоритмов в программировании

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

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

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

Похожие записи:

kvodo.ru

Виды алгоритмов в информатике: примеры

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

Понятие

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

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

Свойства

Прежде чем рассматривать виды алгоритмов в информатике, необходимо выяснить их основные свойства.

Среди основных свойств алгоритмов необходимо выделить следующие:

  • Детерминированность, то есть определенность. Заключается в том, что любой алгоритм предполагает получение определенного результата при заданных исходных.
  • Результативность. Означает, что при наличии ряда исходных данных после выполнения ряда шагов будет достигнут определенный, ожидаемый результат.
  • Массовость. Написанный единожды алгоритм может использоваться для решения всех задач заданного типа.
  • Дискретность. Она подразумевает, что любой алгоритм можно разбить на несколько этапов, каждый из которых имеет свое назначение.

Способы записи

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

  1. Словестный.
  2. Формульно-словестный.
  3. Графический.
  4. Язык алгоритма.

Наиболее часто изображают алгоритм в виде блок-схемы, используя специальные обозначения, зафиксированные ГОСТами.

Основные виды

Выделяют три основных схемы:

  1. Линейный алгоритм.
  2. Ветвящийся алгоритм, или разветвленный.
  3. Циклический.

Далее мы рассмотрим виды алгоритмов в информатике, примеры, которые помогут более детально понять, как они работают.

Линейный

Наиболее простым в информатике считается линейный алгоритм. Он предполагает последовательность выполнения действий. Приведем наиболее простой пример алгоритма такого вида. Назовем его «Сбор в школу».

1. Встаем, когда звенит будильник.

2. Умываемся.

3. Чистим зубы.

4. Делаем зарядку.

5. Одеваемся.

6. Кушаем.

7. Обуваемся и идем в школу.

8. Конец алгоритма.

Разветвляющийся алгоритм

Рассматривая виды алгоритмов в информатике, нельзя не вспомнить о разветвляющейся структуре. Данный вид предполагает наличие условия, при котором в случае его выполнения действия выполняются в одном порядке, а в случае невыполнения – в другом.

Например, возьмем следующую ситуацию – переход дороги пешеходом.

1. Подходим к светофору.

2. Смотрим на сигнал светофора.

3. Он должен быть зеленым (это условие).

4. Если условие выполняется, мы переходим дорогу.

4.1 Если нет – ждем, пока загорится зеленый.

4.2 Переходим дорогу.

5. Конец алгоритма.

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

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

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

1. Берем число 1.

2. Проверяем, меньше ли оно 100.

3. Если да, проверяем простое ли это число.

4. Если условие выполняется, записываем его.

5. Берем число 2.

6. Проверяем, меньше ли оно 100.

7. Проверяем, простое ли оно.

…. Берем число 8.

Проверяем, меньше ли оно 100.

Проверяем, простое ли число.

Нет, пропускаем его.

Берем число 9.

Таким образом перебираем все числа, до 100.

Как видите, шаги 1 – 4 будут повторяться некоторое число раз.

Среди циклических выделяют алгоритмы с предусловием, когда условие проверяется в начале цикла, или с постусловием, когда проверка идет в конце цикла.

Другие варианты

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

Обозначения в блок-схеме

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

  1. Начало и конец алгоритма записываются в овальной рамке.
  2. Каждая команда фиксируется в прямоугольнике.
  3. Условие прописывается в ромбе.
  4. Все части алгоритма соединяются при помощи стрелок.

Выводы

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

fb.ru

Как создать блок-схему. Блок-схема программы, массива

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

Для чего применяют блок-схемы?

Упомянутые системы призваны выполнять следующие функции:

- разрабатывать новый процесс;

- описывать и документировать текущий алгоритм;

- разрабатывать модификации к данному процессу либо исследовать звенья с вероятным возникновением ошибок и сбоев;

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

Разработка последовательности операций

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

Типы алгоритмов

На практике чаще всего применяют следующие виды блок-схем:

- графическая, то есть в основе находятся геометрические символы;

- словесная: составляется с помощью обычных слов того или иного языка;

- псевдокоды: представляют собой полуформализованное описание на условно-алгоритмическом языке, которое включает в себя элементы языка программирования и фразы литературного, а также общепринятые математические символы;

- программная: для записи используются исключительно языки программирования.

Блок-схема устройства: описание

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

Основные элементы, употребляемые при составлении блок-схем

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

Элементы блок-схемы:

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

2. Решение. Данный блок применяется для обозначения перехода управления по определенному условию. В каждом таком элементе указывается вопрос, сравнение или условие, которые его определяет. Другими словами, решение - это выбор направления для выполнения программы или алгоритма в зависимости от некоего переменного условия. Графический вид данного элемента – это ромб. Упомянутый символ может использоваться в качестве изображения следующих унифицированных структур: выбор, развилка полная и неполная, цикл «до» и «пока».

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

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

5. Ввод-вывод данных в общем виде.

6. Пуск и остановка. Этот элемент означает начало и конец алгоритма, а также вход в программу и выход из неё. Графически данный символ напоминает прямоугольник, у которого вместо боковых прямых – дуги.

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

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

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

10. Линии потока – это стрелки, которые указывают последовательность связей. Ни одна блок-схема структуры не может обходиться без данного элемента. Существуют определенные правила начертания этих символов. Перечислим их:

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

- направление линии сверху вниз или слева направо считается основным, стрелками оно не обозначается, остальные случаи указания направлений обозначены ими;

- изменение направления данного элемента производится только под углом 90о.

11. Соединитель. Данный элемент предназначен для указания связи на прерванных линиях потока. Эти символы используются в том случае, если блок-схема программы строится из нескольких частей. Тогда линия потока от одной части должна закончиться «соединителем», а новой части - начаться с данного символа. Внутри такого элемента ставится один и тот же порядковый номер. Графическое изображение «соединителя» - это круг.

12. Межстраничный соединитель. Назначение этого элемента аналогично предыдущему, только используется он для соединения блок-схем, размещенных на разных страницах. Изображение такого элемента представлено пятиугольником в виде домика.

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

Построение блок-схем

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

Массивы и построение алгоритмов

Массив представляет собой совокупность однотипной информации, которая хранится в последовательных кластерах памяти и имеет общее имя. Такие ячейки называются "элементами системы". Все кластеры нумеруются по порядку. Такой номер называется "индексом элемента массива". Как составить блок-схему для подобной системы? Рассмотрим пример создания алгоритма для элементарного массива одномерного типа. Простейшая система имеет условно вид строки. Зададим имя для данного массива – «А». Будем считать, что наша система состоит из восьми ячеек (от 1 до 8). Каждый из упомянутых кластеров содержит случайное число, которое называется "элементом массива". Для обращения в конкретной ячейке необходимо указывать имя в квадратных скобках ([3]). Рассмотрим пример, в котором блок-схема массива предназначена для заполнения системы случайными числами с последующим выводом информации на экран. Что представляет собой такой алгоритм? Это элементарная система. По сути, она не имеет практического применения, однако удобна для учебного процесса. Рассматриваемая блок-схема (пример построения описан ниже) содержит всего семь основных элементов, соединенных линиями переходов.

Описание последовательности выполнения задачи

1. Первым элементом схемы будет символ «Начало».

2. Вторым блоком – «Процесс», внутри которого вписываем «инициализация random».

3. Следующий элемент – «Модификация», в блоке вписываем значение ячеек массива.

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

5. В этом блоке «Модификации», согласно вписанной функции, происходит переадресация на следующий элемент.

6. «Вывод» производит отображение информации о новом содержимом массива на мониторе с последующим направлением на предыдущий блок. Далее - на последний элемент.

7. «Конец» работы алгоритма.

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

«Редактор блок-схем»

Если вы задаетесь вопросом о том, как составить блок-схему, то знайте, что существуют специальные программы, которые предназначены для создания, а также редактирования таких систем. Удобством графического отображения алгоритма является то, что пользователь не привязан к синтаксису конкретного языка программирования. Построенная блок-схема одинаково подходит для всех языков (например, С, Паскаль, Бейсик и другие). Кроме того, редактор может использоваться для построения диаграмм и проверки работоспособности схем. Такая программа является специализированным софтом. Она предоставляет разнообразный набор инструментов, необходимых для построения блок-схем, что делает ее более удобной, по сравнению с обычными графическими редакторами. Дополнительные опции позволяют оптимизировать процесс составления системы с дальнейшим ее преобразованием в функции и процедуры языка программирования. Кроме того, редактор блок-схем предлагает набор шаблонов, способных существенно ускорить работу начинающего пользователя. Ведь известно, что при построении алгоритма часто применяются повторяющиеся структуры, например разнообразные варианты циклов, альтернативы (полные и неполные), множественные ветвления и прочее. Редактор позволяет выделять часто используемые в блок-схемах элементы и добавлять их в создаваемую схему. Это избавляет от прорисовки их каждый раз заново. Кроме того, с помощью редактора можно импортировать функции и процедуры, реализованные на любом известном языке программирования. Данная опция полезна для разбора структуры алгоритма, который написан на малознакомом языке. Системные требования рассматриваемой программы довольно скромные, что позволяет использовать ее на любом персональном компьютере.

Заключение

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

fb.ru

это... Схема алгоритма :: SYL.ru

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

История происхождения термина

Понятие об алгоритме впервые было сформировано благодаря математику по имени Мухаммед Аль-Хорезми. Он жил на Востоке в 8-9-м веках и написал два великих труда. Первый из них дал начало слову «алгебра», а второй – понятию «алгоритм». Он обозначал арифметические операции, которые мы знаем как сложение, вычитание, умножение и деление. В 1957 году в одном из изданий английского словаря авторы посчитали, что алгоритм – это понятие устаревшее. Опять оно активно вошло в обиход лишь с появлением компьютеров. Им обозначали действия, которые входили в определенный процесс. Но он не обязательно должен быть только математическим. Тут подразумевается алгоритм действий любого характера, например, приготовления какого-либо блюда. С того времени это понятие не сходит с уст почти всех людей.

Попытки определения термина

Долгое время этот термин рассматривался исключительно как алгоритм чисел и действий с ними. Ведь и сама математика была по большей части прикладной наукой. Формулы, которые применяются для вычислений, в то время и считались алгоритмами. Шаги, которые выполнялись при решении, были элементарными, а сами вычисления – очень громоздкими и отнимали много времени и сил. Математики даже не задумывались над тем, чтобы дать определение этому понятию. Но со временем наука все больше развивалась и появлялись объекты, которые раньше не встречались (матрицы, векторы, множества и т. д.). Всеми ими нужно было оперировать. Это и дало толчок к пониманию того, что алгоритм – это непростое понятие, и его нужно в точности определить для дальнейшего использования. Ученые разделились во мнениях по поводу этого вопроса. Одни считали, что алгоритм применим ко всему, другие же сомневались, что каждую проблему можно решить с его помощью. Последняя точка зрения оказалась верной, но обосновать ее можно было, лишь дав точное определение понятию «алгоритм».

Что обозначает термин «алгоритм»?

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

Свойства, общие для всех алгоритмов

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

  • Дискретность – схема алгоритма предвидит решение поставленной задачи через последовательные действия, которые выполняются в строгой очередности.
  • Определенность – все поставленные условия четкие и не имеют какой-либо двузначности. Алгоритм действий, таким образом, не дает места для любых импровизаций. Это позволяет механически все выполнять, не нуждаясь в дополнительных подсказках.
  • Результативность – за определенное число шагов алгоритм всегда дает правильное решение задачи.
  • Массовость – алгоритм – это решение проблемы, имеющее общий вид. То есть он применим для всех задач определенного класса, независимо от исходных данных. Их выбирают из некого поля под названием "область применимости алгоритма".

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

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

  • Механические – жесткая, единственно верная последовательность для достижения требуемого результата (обеспечение работы двигателя и т. д.).
  • Гибкие: 1) вероятностные – имеют несколько путей для достижения верного решения; 2) эвристические – схема алгоритма, которая не имеет однозначной программы действий (предписания и т. д.), ведь она основана на личных качествах человека, его опыте.
  • Вспомогательные - ранее разработанные и полностью предназначенные для разрешения конкретной задачи.

Алгоритмы в информатике

Для информатики алгоритмы имеют особое значение. В этой науке их разделяют на такие виды:

  1. Линейный – все действия выполняются последовательно, друг за другом.
  2. Разветвляющийся алгоритм – это такой, в котором выполнение определенного условия приводит к выбору одного из двух возможных вариантов дальнейших действий.
  3. Циклический – одни и те же действия повторяются над разными исходными данными, таким образом подбираются наиболее подходящие.

Структура алгоритмов

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

Правила составления алгоритмов

  • Первым правилом является то, что нужно определить большое количество объектов, которые смогут поддаться построенному алгоритму. Программист с помощью кодировки переводит их в данные. Они бывают входные и выходные. Первые служат для начала работы, вторые становятся ее результатом. Это называется преобразованием данных.
  • Второе правило говорит о том, что работа с алгоритмом требует свободной памяти. Ведь без нее не будет возможности разместить входные данные, работать с ними и получить выходные. Память состоит из ячеек. Если одной из них дать имя, она станет переменной.
  • Третье правило уже описывалось выше как одна из характеристик алгоритма, а именно – дискретность. То есть алгоритм состоит из отдельных операций, или шагов.
  • Четвертое правило напоминает о детерминированности алгоритма. То есть после каждого действия нужно указать, какое будет следующим, либо остановить процесс.
  • Последнее правило гласит, что после определенного числа шагов алгоритм завершает свою работу, имея тот или иной результат. А какой именно, указывает сам программист.

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

www.syl.ru

Правила построения алгоритма

Поиск Лекций

Понятие алгоритма

Понятие алгоритма является центральным понятием информатики. Слово «алгоритм» произошло от имени узбекского математика аль-Хорезми, который еще в IX веке сформулировал правила выполнения арифметических действий. В современной математике и информатике термин алгоритм имеет следующие определения:

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

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

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

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

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

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

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

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

  • Вероятностный (стохастический) алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
  • Эвристический алгоритм (от греческого слова «эврика») — это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения схожих задач.
  • Линейный алгоритм — набор команд (указаний), выполняемых последовательно друг за другом.
  • Разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
  • Циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) Над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы — последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторому условию.
  • Вспомогательный (подчиненный) алгоритм (процедура) — алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм.

Алгоритм можно задать несколькими способами:

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

Блок-схема алгоритма

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

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

В таблице приведены наиболее часто употребляемые символы.

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

Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.

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

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

Для примера приведем блок-схемы алгоритма нахождения максимального из двух значений:

 

Правила построения алгоритма

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

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

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

Третье правило — дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Точнее — из множества шагов.

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

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

Запись опубликована в рубрике Информатика с метками алгоритм, правила, программирование. Добавьте в закладки постоянную ссылку.

 

Свойства алгоритма

Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

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

Результативность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.

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

 

poisk-ru.ru

понятие, свойства, структура и виды

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

В этой статье мы разберем основные понятия алгоритма.

История появления алгоритмов

Алгоритм - понятие, появившиеся в XII веке. Само слово "алгоритм" происходит от латинской интерпретации имени известного математика среднего востока Мухаммеда аль Хорезми, который написал книгу "Об индийском счете". В этой книге описано, как правильно записывать натуральные числа, используя арабские цифры, и приведено описание алгоритма действий столбиком над такими числами.

В XII веке книга "Об индийском счете" была переведена на латинский язык, тогда-то и появилось данное определение.

Взаимодействие алгоритма с человеком и машиной

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

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

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

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

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

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

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

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

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

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

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

Основные свойства алгоритма

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

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

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

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

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

Существуют разные типы алгоритмов, но есть три основных.

Цикличный алгоритм

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

Итерация цикла — это выполнение всех пунктов, входящих в тело цикла.Части цикла, которые постоянно выполняются определенное количество раз, называются циклом с фиксированным числом итераций.

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

Самый простой вид цикла — это фиксированный.

Существует два вида цикличных алгоритмов:

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

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

Разветвляющийся алгоритм

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

Пример. Вопрос: "Идет дождь?" Варианты ответов: "Да" или "Нет". Если "да" — откройте зонт, если "нет" — положите зонт в сумку.

Вспомогательный алгоритм

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

Термины, встречающиеся в алгоритмах

Условие находится между словами "если" и "тогда".

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

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

Алгоритмический процесс — решение задачи по алгоритму с применением определенных данных.

Структура алгоритма

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

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

Графический вариант построения алгоритма

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

Графические схемы изображаются не как попало. Для того чтобы их мог понять любой человек применяются чаще всего блок-схемы и структурограммы Насси-Шнейдермана.

Также блок-схемы изображаются в соответствии с ГОСТ-19701-90 и ГОСТ-19.003-80.Графические фигуры, применяемые в алгоритме, делятся на:

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

  • Вспомогательные. Вспомогательные изображения нужны для обозначения отдельных, не самых важных, элементов решения задачи.

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

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

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

Как правильно построить алгоритм?

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

Общая методика по записи включает в себя следующие пункты:

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

У каждого алгоритма должны быть четко обозначены начало и конец.

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

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

  • Имя схемы.
  • Данные.
  • Начало.
  • Команды.
  • Конец.

Правильное построение схемы существенно облегчит вычисление алгоритмов.

Геометрические фигуры, отвечающие за разные действия в алгоритме

Горизонтально расположенный овал - начало и конец (знак завершения).

Горизонтально расположенный прямоугольник — вычисление или другие действия (знак процесса).

Горизонтально расположенный параллелограмм — ввод или вывод (знак данных).

Горизонтально расположенный ромб — проверка условия (знак решения).

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

Модели алгоритмов представлены ниже на рисунке.

Формульно-словестный вариант построения алгоритма.

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

Понятие алгоритма в информатике

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

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

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

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

Вывод

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

fb.ru

Интуитивная разработка алгоритмов / Хабр

Если вы программист, то, возможно, у вас возникали ситуации, когда в выбранном игровом движке или библиотеке нет нужной функции. За этим следовал ужасающий момент, когда вам приходилось обыскивать весь Интернет в поисках кода, написанного людьми, решавшими эту проблему до вас (я говорю о вас, пользователи StackOverflow). Конечно, в этом нет ничего плохого (я и сам так поступаю), но очень часто вы можете сделать это самостоятельно, даже когда речь идёт о таких теоретических задачах, как геометрия или перетасовка. Я один из тех людей, которые всегда пытаются понять, как всё работает, и разве есть способ понимания лучше, чем прийти к нему самому, заново изобретя решение на лету (если, конечно, оно существует)?

Ставим перед собой пример задачи

В этой статье я опишу несколько этапов, которые, как мне кажется, довольно эффективны для самостоятельного выведения решающего задачу алгоритма. Чтобы применить их к чему-то конкретному, мы рассмотрим пример задачи: выпуклое разбиение простых многоугольников. Это звучит сложно и по-научному, но на самом деле это не так трудно. Простой многоугольник — это многоугольник, который не пересекает сам себя и не имеет отверстий. Выпуклый многоугольник — это тот, в котором все углы меньше 180°. Разумеется, выпуклый многоугольник является простым многоугольником, а простой многоугольник — это сложный многоугольник (наиболее общий класс многоугольников), однако обратное не всегда верно.

Выпуклый, простой и сложный многоугольники.

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

В идеале наш алгоритм должен уметь выполнять такую операцию.

Изучи то, с чем работаешь

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

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

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

В первую очередь — мозг и бумага

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

Во-первых, для разработки интуитивного подхода чаще всего стоит начинать с зарисовки (или записывания, в зависимости от того, над чем вы работаете) простых случаев, которые вы можете решить самостоятельно, не особо задумываясь над тем, что вы делаете. В процессе этой работы или после него вам стоит проанализировать способ размышлений над ним и упорядочить его, разбив на этапы. Идея заключается в том, что, хотите вы этого или нет, вы выполняете алгоритм: ваш мозг — тоже компьютер, самый мощный компьютер, известный человеку. Настолько мощный, что способен посмотреть на собственную работу и понять её; настолько мощный, что вы уже выполняете алгоритм, который пытаетесь записать, но почему-то пока не понимаете его (потому что ещё не осознали его!). Однако вы можете выполнить алгоритм шаг за шагом, чтобы понять, как он работает. Для проверки этой теории давайте вернёмся к нашему примеру задачи и воспользуемся тем самым простым многоугольником.

Рекомендую вам самим нарисовать такой многоугольник, и в этот момент прервать чтение, чтобы попытаться разделить этот многоугольник на меньшие фигуры таким образом, чтобы в них никогда не было внутренних углов больше 180°. Я показал моё решение на рисунке выше, но поскольку все думают по-разному, в конце у нас могут получиться другие фигуры. И это абсолютно нормально, на самом деле выпуклое разбиение простого многоугольника не уникально!

Оба этих разбиения являются выпуклыми.

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

Во-первых, я задал себе вопрос: почему этот многоугольник ещё не выпуклый? Ответ пришёл довольно быстро: потому что некоторые из внутренних углов больше 180° (а именно два из них, показанные на рисунке стрелками), что по определению не даёт многоугольнику быть выпуклым. Чтобы исправить это, я затем подумал, что нужно разрезать угол, чтобы получить два меньших угла, которые в идеале будут не больше 180°. Этого можно достичь, соединив «дефектную» вершину с какой-нибудь другой вершиной многоугольника. Повторим это для всех дефектных вершин и получим наше выпуклое разбиение!

Пошаговое интуитивное выпуклое разбиение; стрелками показаны «дефектные» вершины.

Отлично, всё произошло довольно быстро. Но что же случилось на самом деле? На этом этапе мы можем записать зародыш алгоритма в псевдокоде, напоминающем естественный язык. Это не совсем предложение из языка, но и не совсем программирование. Оно просто выглядит достаточно похоже на программирование, чтобы запустить в мозгу установку «думай, как программист».

пока существует "дефектная" вершина соединять её с другой вершиной многоугольника конец пока Из этого становится понятно, что нам нужен способ определить, является ли вершина «дефектной». Для этого достаточно просто проверить, образуют ли две составляющих вершину ребра угол больше 180°. Однако есть и другая, более серьёзная задача: какую вершину мы выбираем для соединения с дефектной вершиной? Давайте ещё раз подумаем, как мы делали это в прошлый раз.

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

пока есть дефектная вершина пока следующая вершина образует с дефектной вершиной угол 180° или меньше перейти к следующей вершине если угол, образованный этой новой вершиной больше 180°, остановиться и выбрать предыдущую конец пока соединить дефектную вершину с выбранной вершиной конец пока Но эта проверка может привести к паре сомнительных ситуаций: что, если вершина сразу после нашей дефектной вершины тоже является дефектной? Что, если в процессе проверки мы дойдём до дефектной вершины? Второй вопрос вроде бы решает себя благодаря тому наблюдению, что в выпуклом многоугольнике не может быть дефектных вершин, необходимо сразу же остановиться и выбрать её, чтобы ребро, которое мы добавляем при разбиении угла превратила её в «правильную» вершину. Первый вопрос можно решить интуитивно: когда мы решаем задачу вручную, этого никогда не происходит, потому что мы намеренно начинаем или с самой левой, или самой правой дефектной вершины, а очевидно не с той, которая находится между другими дефектными вершинами. В коде это просто преобразуется в то, что мы начинаем исследование с дефектной вершины, у которой точно есть правильный сосед. Это возможно всегда, потому что простой многоугольник всегда имеет хотя бы одну «правильную» (то есть недефектную) вершину. Найдите её, используйте, чтобы избавиться от одной дефектной вершины, повторите. Наш псевдокод теперь выглядит так:пока есть дефектная вершина выбрать ту, после которой есть "правильная" вершина пока следующая вершина с дефектной вершиной образуют угол в 180° или меньше перейти к следующей вершине если эта новая вершина "неправильна", остановиться и выбрать её иначе если угол, образованный этой новой вершиной больше 180°, остановиться и выбрать предыдущую вершину конец пока соединить дефектную вершину с выбранной вершиной конец пока И при выполнении код даст нам что-то подобное:

Один шаг алгоритма: выбор вершины, с которой нужно соединить дефектную вершину.

Выглядит довольно неплохо!

Остаётся ещё один вопрос: сейчас мы сохраняем наши многоугольники как массив вершин, а не рёбер, что же означает тогда «соединение вершин»? Мы не добавляем и не удаляем вершины из многоугольника, поэтому, наверно, не можем изменять массив вершин? Или можем?

Давайте посмотрим на то, как мы подходили к этому вопросу при работе вручную: после прорисовки ребра нам становится совершенно неинтересна часть, ставшая выпуклой, и мы сосредоточены только на оставшихся вершинах. Однако нас по-прежнему интересует только что добавленное ребро, и мы по-прежнему добавляем в поиск составляющие его вершины. У этого есть довольно чёткая интерпретация: мы просто разбиваем многоугольник на две части, выпуклую и простую, и нас перестаёт интересовать выпуклая часть при повторном применении алгоритма к новому, меньшему простому многоугольнику!

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

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

Теперь наш псевдокод выглядит вот так:

function makeConvex выбрать дефектную вершину, после которой есть "правильная" вершина пока следующая вершина образует с дефектной угол в 180° или меньше перейти к следующей вершине если эта новая вершина "неправильна", остановиться и выбрать её иначе если угол, образованный этой новой вершиной, больше 180°, остановиться и выбрать предыдущую вершину конец пока добавить в массив все вершины между дефектной вершиной и выбранной вершиной, включая их обе удалить из исходного многоугольника все вершины между дефектной вершиной и выбранной вершиной, не включая их обе вернуть выпуклый массив, конкатенированный с результатом функции makeConvex, вызванной для нового многоугольника конец функции И на этом всё, мы закончили! Наш этап работы с мозгом и бумагой закончен; после этого этапа вся дальнейшая работа относится уже к реализации, поэтому оставляю её вам!

Послесловие

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

habr.com