Как найти алгоритм решения задачи

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

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

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

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

• Этап 1 . Математическое описание решения задачи.
• Этап 2 . Определение входных и выходных данных.
• Этап 3 . Разработка алгоритма решения задачи.

Базовые алгоритмические конструкции

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

• следование (линейный алгоритм);
• ветвление (разветвляющийся алгоритм);
• цикл-пока (циклический алгоритм).

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

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

Пример

ЗАДАЧА. Разработать алгоритм вычисления гипотенузы прямоугольного треугольника по известным значениям длин его катетов a и b.

На примере данной задачи рассмотрим все три этапа разработки алгоритма решения задачи:

Этап 1. Математическое описание решения задачи.

Математическим решением задачи является известная формула:

,

где с-длина гипотенузы, a, b – длины катетов.

Этап 2. Определение входных и выходных данных.

Входными данными являются значения катетов a и b. Выходными данными является длина гипотенузы – c.

Этап 3. Разработка алгоритма решения задачи.

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

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

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

Пример

ЗАДАЧА. Разработать алгоритм вычисления наибольшего числа из двух чисел x и y.

Этап 1. Математическое описание решения задачи.

Из курса математики известно, если x > y, то наибольшее число x, если x < y, то наибольшее число y, если x = y, то число x равно числу y.

Этап 2. Определение входных и выходных данных.

Входными данными являются значения чисел x и y. Выходным данными являются:

• наибольшее число
• любое из чисел, если числа равны

Для решения задачи нам необходимо знать значения x и y.

Этап 3. Разработка алгоритма решения задачи.

Словесное описание алгоритма	Запись алгоритма на языке блок-схем
Начало алгоритма. Ввод значений x и y. Сравниваем x и y. Если x = y, то переход к шагу 4, иначе к шагу 5. Вывод информации: числа x и y равны. Переход к шагу 8. Сравниваем x и y. Если x > y, то переход к шагу 6, иначе к шагу 7. Вывод информации: число x больше y. Переход к шагу 8. Вывод информации: число y больше x. Переход к шагу 8. Конец алгоритма.

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

В рассматриваемом алгоритме (рис.3) имеются три ветви решения задачи:

• первая: это элементы 1, 2, 3, 4, 8.
• вторая: это элементы 1, 2, 3, 5, 6, 8
• третья: это элементы 1, 2, 3, 5, 7, 8.

Выбор ветви определяется значениями x и y в элементах 3 и 5, которые являются условиями, определяющими порядок выполнения элементов алгоритма. Если условие (равенство), записанное внутри символа «решение», выполняется при введенных значениях x и y, то следующими выполняется элементы 4 и 8. Это следует из того, что они соединены линией с надписью «да» и направление (последовательность) вычислений обозначена стрелочкой.

Если условие в элементе 3 не выполняется, то следующим выполняется элемент 5. Он соединен с элементом 3 линией с надписью «нет». Если условие, записанное в элементе 5, выполняется, то выполняется элементы 6 и 8, в противном случае выполняются элементы 7 и 8.

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

Циклический алгоритм – определяет повторение некоторой части действий (операций), пока не будет нарушено условие, выполнение которого проверяется в начале цикла. Совокупность операций, выполняемых многократно, называется телом цикла.

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

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

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

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

 

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

• начальные значения цикла;
• конечные значения цикла;
• шаг цикла.

В тело цикла входят:

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

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

 Пример

ЗАДАЧА. Разработать алгоритм вычисления суммы натуральных чисел от 1 до 100.

Этап 1. Математическое описание решения задачи.

Обозначим сумму натуральных чисел через S. Тогда формула вычисления суммы натуральных чисел от 1 до 100 может быть записана так:

где Xi – натуральное число X c номером i, который изменяется от 1 до n, n=100 – количество натуральных чисел.

Этап 2. Определение входных и выходных данных.

Входными данными являются натуральные числа: 1, 2, 3, 4, 5, …, 98, 99, 100.

Выходные данные – значение суммы членов последовательности натуральных чисел.

Параметр цикла – величина, определяющая количество повторений цикла. В нашем случае i – номер натурального числа.

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

• начальное значение параметра цикла равно 1,
• конечное значение параметра цикла равно n,
• шаг цикла равен 1.

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

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

S=S+i;              I=I+1;

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

Этап 3. Разработка алгоритма решения задачи.

Введем обозначения: S – сумма последовательности, i – значение натурального числа.

Начальное значение цикла i=1, конечное значение цикла i =100, шаг цикла 1.

Словесное описание алгоритма	Запись алгоритма на языке блок-схем
Начало алгоритма. Подготовка цикла: S:=0; i=1; n= 100; Проверка условия. Если i <=n , то перейти к шагу 4, иначе к шагу 6. Накопление суммы: S:=S+i; Вычисление следующего значения параметра цикла: i:=i+1; Вывод информации: сумма натуральных чисел – S. Конец алгоритма.	В схеме алгоритма решения задачи цифрами указаны номера элементов алгоритма. Номера элементов соответствуют номерам шагов словесного описания алгоритма.

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

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

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

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

В решении задачи на алгоритмы выделяют ряд этапов:

1. Математическое описание.
2. Определение входных/выходных данных.
3. Разработка алгоритма по решению поставленной задачи.

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

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

• линейного класса;
• ветвления (речь идет о разветвляющихся алгоритмах);
• циклического класса.

Алгоритмы линейного класса

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

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

1. Математическое описание.

Математически задача решается по следующей формуле:

Здесь c является длиной гипотенузы, a, b – длинами катетов.

2. Определяем входные/выходные данные.

Входные данные — значения катетов a и b. Выходные — длина гипотенузы c.

3. Разработка алгоритма.

Алгоритмы ветвления

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

Для примера возьмем задание, постановка которого связана с разработкой алгоритма по вычислению наибольшего числа из 2-х чисел: x и y.

1. Математическое описание.

Из первых классов математики мы знаем, что когда x > y, то x больше y и наоборот, что является очевидными вещами. И если x = y, то числа равны.

2. Определяем входные/выходные данные.

Входные данные — это значения x и y. Выходными данными являются:

• самое большое число;
• любое из чисел в том случае, если они равны.

Таким образом, чтобы решить эту задачу на алгоритмы, надо знать значения переменных x и y.

3. Разработка.

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

• 1, 2, 3, 4, 8;
• 1, 2, 3, 5, 6, 8;
• 1, 2, 3, 5, 7, 8.

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

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

В алгоритмических последовательностях этого класса выделяют ряд понятий:

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

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

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

• начальные значения;
• конечные значения;
• шаг.

В тело цикла входят:

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

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

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

1. Математическое описание.

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

Здесь Xi является натуральным числом X c номером i. Этот номер меняется от 1 до n. А n=100 обозначает общее кол-во натуральных чисел.

2. Определяем входные/выходные данные.

Входные данные — это натуральные числа: 1, 2, 3, …, 99, 100.

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

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

Подготовка цикла — задание начального и конечного значений циклического параметра. Тут надо пояснить следующее:

• начальное значение циклического параметра равняется единице,
• конечное значение — n,
• шаг равен 1.

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

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

• S=S+i;             
• I=I+1.

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

3. Разработка.

Вводим следующие обозначения: S – это сумма последовательности, i – это значение натурального числа.

Начальное циклическое значение i=1, конечное — i =100, шаг равен 1.

По материалам: https://www.turbopro.ru/index.php/osnovy-programmirovaniya/6836-algoritmy-razrabotka-algoritma-resheniya-zadachi.

Алгоритм — это точное предписание,
определяющее вычислительный процесс,
ведущий от варьируемых начальных данных
к искомому результату (ГОСТ 19.781-74).

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

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

К алгоритмам предъявляются следующие
требования.

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

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

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

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

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

1. Словесная
   запись (не формализованная запись
   алгоритма на естественном языке,
   например, рецепт приготовления манной
   каши);

2. Блок-схема (наиболее наглядная
   графическая форма представления
   алгоритмов, используемая профессионалами
   особенно в тех случаях, когда алгоритм
   обладает изощренной логикой исполнения);

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

4. Компьютерная программа (жестко
   формализованная запись алгоритма,
   ориентированная на исполнителя – ЭВМ).
   Для разработки компьютерных программ
   используются инструментальные средства,
   называемые языками программирования.

Рассмотрим запись алгоритма Евклида
нахождения наибольшего общего делителя
(НОД) для двух натуральных чисел во всех
четырех перечисленных выше формах.

начало,
конец алгоритма

простое
действие, вычисление

задание
исходных данных, вывод результата

проверка
условия

Это линейный
тип алгоритма
(следование)

к
содержанию

задание
исходных данных, вывод результата

Правила разработки, оформления и
обращения программ и программной
документации определяются ЕДИНОЙ
системой программной документации
(ЕСПД) — комплексов государственных
стандартов (ГОСТ 19.001-77).

Требования стандартов ЕСПД предъявляются
к оформлению программ и программной
документации в любой области, где
применяются вычислительные машины.

2.4Выбор языка программирования

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

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

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

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

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

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

В каждой команде указывается:

— код операции;

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

Характерные особенности программирования
на машинном языке:

— детальное разбиение алгоритма на
элементарные шаги;

— предварительное распределение ячеек
памяти.

Достоинства: экономичность программ
(малый объем памяти, высокое быстродействие
и точность).

Недостатки: трудоемкость процесса
составления программ, громоздкость
текста (записи) программ (т.к. они состоят
из элементарных операций машины).

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

Машинная ориентированность означает,
что в основе этих языков лежит система
команд вычислительной машины.

Примером является язык АССЕМБЛЕР, каждый
оператор которого соответствует одной
команде компьютера.

Программа на АССЕМБЛЕРе также
детализирована, как и при использовании
машинного языка. Однако применение
АССЕМБЛЕРа имеет ряд преимуществ:

— с символическим языком удобнее работать,
чем с цифровыми кодами;

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

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

Часто сознательно избирают АССЕМБЛЕР,
если стремятся наиболее эффективно
использовать возможности машины.

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

В настоящее время широкое применение
находят языки программирования Си++,
Паскаль, Бейсик.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

пока существует "дефектная" вершина
    соединять её с другой вершиной многоугольника
конец пока

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

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

пока есть дефектная вершина
    пока следующая вершина образует с дефектной вершиной угол 180° или меньше
        перейти к следующей вершине
        если угол, образованный этой новой вершиной больше 180°, остановиться и выбрать предыдущую
    конец пока
    соединить дефектную вершину с выбранной вершиной
конец пока

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

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

И при выполнении код даст нам что-то подобное:

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

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

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

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

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

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

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

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

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

Послесловие

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

«Алгоритм решения задач с помощью уравнения»:

1) Обозначить буквой х неизвестную величину, записав ответ на вопрос задачи (Пусть…).

2) Составить уравнение по условию задачи.

3) Решить это уравнение.

1. Записать краткий ответ на вопрос задачи.

«Алгоритм решения задач на применение теоремы Пифагора»:

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

2)Определить катет это или гипотенуза.

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

4)Подставив в формулу известные величины, найти неизвестную величину.

Как решать задачи.

1. Прочитай задачу и представь себе то, о чем говорится в задаче.
2. Запиши задачу кратко или выполни чертеж.
3. Поясни, что показывает каждое число, повтори вопрос задачи.
4. Подумай, можно ли сразу ответить на вопрос задачи. Если нет, то почему. Что  

          нужно узнать сначала, что потом.

1. Составь план решения.
2. Выполни решение.
3. Проверь решение и ответь на вопрос задачи.
4. Не забудь записать ответ к задаче, проверь правильно ли записаны пояснения к

           действиям.

Рекомендации по решению нестандартных задач:

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

2.  Ввести вспомогательный элемент (часть).

3.  Использовать для решения задачи способ подбора.

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

5.  Разделить условие или вопрос задачи на части и решить ее по частям.

6.  Начать решение задачи «с конца».

Алгоритм решения задач на переливание:

 В задачах на переливание разрешены следующие операции:

1. заполнение жидкостью одного сосуда до краев;
2. переливание жидкости в другой сосуд или выливание жидкости;

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

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

Каждую задачу на переливание таким методом можно решать двумя способами:

а) начать переливания с большего сосуда;

б) начать переливания с меньшего сосуда.        

При решении задач первого типа («Водолей») можно использовать такой алгоритм:

1. Наполнить большую емкость жидкостью из бесконечного источника.
2. Перелить из большей емкости в меньшую емкость.
3. Вылить жидкость из меньшей емкости.
4. Повторить действия 1-3 до тех пор, пока не будет получено обозначенное в условии задачи количество жидкости.

При решении задач второго типа («Переливашка») можно использовать следующий алгоритм:  

1. Из большей емкости наполнить емкость промежуточного объема.
2. Перелить жидкость из промежуточной емкости в самую маленькую емкость.
3. Перелить жидкость из самой маленькой емкости в большую емкость.
4. Повторять действия 2-3 до тех пор, пока емкость промежуточного объема не станет пустой.
5. Если емкость промежуточного объема опустела, то  повторить действия 1-5 до тех пор, пока не будет получено обозначенное в условии задачи количество жидкости.

Алгоритм решения задач :

• Читаем условие задачи. Условие – это та часть текста, где содержатся сведения об известных и неизвестных значениях величин, об отношениях между ними.
• Определяем требование, т.е. указание на то, что надо найти. Требование обычно выражается вопросом, начинающимся словом «Сколько…?» и заканчивающимся знаком вопроса.
• Находим данные задачи. Данные – это известные числа.
• Определяем искомое. Это конечная цель процесса решения арифметической задачи.
• Если что-то непонятно, необходимо обратиться за разъяснением к учителю. Могут встретиться непонятные слова и обороты.
• Ищем пути решения задачи и составляем план решения.
• Можно использовать графическую модель (схема в «отрезках») или составить таблицу.
• Записываем решение и ответ.