Разработка несложного алгоритма решения задачи кратко

Обновлено: 05.07.2024

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

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

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

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

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

Начало алгоритма

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

разработка алгоритма,
его представление,
тестирование алгоритма;

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

Составление документации (если есть необходимость).

Рассмотрим в качестве примера постановки задачи следующую задачу.

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

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

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

С крыши здания свободно падает трансформатор. Время его падения определяем секундомером. Используя закономерности свободного падения тела в гравитационном поле, определить высоту здания.

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

Далее для формализованной задачи можно разрабатывать алгоритм решения.

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

Рассмотрим возможности построения алгоритма формализованной задачи.

Принцип нисходящего проектирования алгоритма

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

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

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

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

ввод (исходной) информации,
обработка информации,
вывод результатов.

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

Подобное разбиение мы видим при решении задач физики, математики, химии и т. д. (дано…решение [в буквенном виде…числовое решение]…ответ) названия разные – суть одна.

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

Таким образом, самый верхний уровень необходимо рассматривать как один неделимый блок – формулировка исходной (формализованной) задачи. Далее самый первый уровень детализации необходимо представляется тремя подзадачами. Назовем это ТРИЕДИНОЙ ЗАДАЧЕЙ АЛГОРИТМИКИ. Она едина потому, что каждая из подзадач отдельно от остальных не имеет смысла. И это три задачи, так как каждая из них достаточно замкнута, имеет свои особенности и, поэтому, может разрабатываться отдельно от остальных. А так как задач ВводаИнформации и ВыводаРезультатов ограниченное количество и они решаются отдельно, то далее принцип нисходящего проектирования алгоритма применяется только к задаче ОбработкиИнформации.

Триединая задача алгоритмики

Сформулируем понятие триединой задачи алгоритмики в следующем определении.

ВводИнформации,
ОбработкаИнформации,
ВыводРезультатов.

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

В дальнейшем геометрическое представление триединой задачи удобно делать в виде:

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

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

ВводИнформации( ).
ОбработкаИнформации( ; ).
ВыводРезультатов( ).

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

Обобщая изложенное, можно утверждать, что…

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

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

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

Постановка задачи:
Построение алгоритма (по формализованной задаче):
Реализация алогоритма.
Составление документации (если есть необходимость).

Первым шагом в построении алгоритма является, согласно принципа нисходящего проектирования алгоритма, ТРИЕДИНАЯ ЗАДАЧА АЛГОРИТМИКИ – это алгоритм решения формализоанной задачи. Он представляет исходную формализованную задачу как совокупность трех подзадач (вспомогательных алгоритмов):

ВводИнформации,
ОбработкаИнформации,
ВыводРезультатов.

При этом задачи ВводаИнформации и ВыводаРезультатом можно и нужно решать самостоятельно.

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

В рассматриваемом алгоритме (рис.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. Определение входных и выходных данных.

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

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

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

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

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

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

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

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

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

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

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ИРКУТСКОЙ ОБЛАСТИ

к практическому занятию

Ангарск, 2016

Рассмотрено и одобрено

на заседании ПЦК

по укрупненной группе НПО

Председатель ПЦК _____________ Дорош Е.Г.

на заседании методического совета

Председатель методического совета

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

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

Основными достоинствами практических занятий по информатике являются:

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

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

управление деятельностью студентов преподавателем осуществляется посредством инструктирования и консультирования;

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

возможность студентов осмыслить и обобщить собственную деятельность.

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

алгоритм, свойства алгоритма, способы записи алгоритмов;

исполнители алгоритмов (назначение, среда, режим работы, система команд);

компьютер как формальный исполнитель алгоритмов;

основные алгоритмические конструкции (следование, ветвление, повторение);

разбиение задачи на подзадачи, вспомогательный алгоритм;

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

УЧЕБНО-ТЕМАТИЧЕСКИЙ ПЛАН

Создание цифрового изображения. Программы сканирования. Основные параметры и настройки при сканировании.

Представление информации в различных системах счисления

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

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

Разработка несложного алгоритма решения задачи

Создание архива данных. Извлечение данных из архива. Запись информации на внешние носители различных видов.

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

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

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

Результативность – реализуемый вычислительный процесс выполняется за конечное число этапов с выдачей осмысленного результата

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

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

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

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

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

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

Исполнитель алгоритма – объект или субъект, выполняющий некоторые команды. Для каждого исполнителя существует система команд , т.е. совокупность всех команд, которую умеет делать исполнитель.

Теоретический материал.

Одним из наиболее трудоемких этапов решения задачи на ЭВМ является разработка алгоритма.

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

Основными характерными свойствами алгоритма являются:

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

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

массовость – пригодность для задач данного типа при исходных данных, принадлежащих заданному подмножеству;

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

результативность – реализуемый вычислительный процесс выполняется за конечное число этапов с выдачей осмысленного результата;

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

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

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

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

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

Выделяют следующие типы вычислительных процессов :

Линейный вычислительный процесс .

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

Разветвленный вычислительный процесс .

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

Циклический вычислительный процесс

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

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

С четные циклы (циклы с заданным количеством повторений) – это циклические процессы, для которых количество повторений известно.

Итерационные циклы – это циклические процессы, завершающиеся по достижении или нарушении некоторых условий.

П оисковые циклы – это циклические процессы, из которых возможны два варианта выхода:

- выход по завершению процесса;

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

По типу вычислительного процесса, реализуемого алгоритмом, различают:

- алгоритмы линейной структуры;

- алгоритмы разветвленной структуры;

- алгоритмы циклической структуры.

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

К изобразительным средствам описания алгоритмов относятся следующие основные способы их представления:

- словесный ( записи на естественном языке);

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

- графический ( изображение схем и графических символов);

- программный (тексты на языках программирования).

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

Алгоритм сложения двух чисел (a и b).

Спросить, чему равно число a.

Спросить, чему равно число b.

Сложить a и b, результат присвоить с.

Сообщить результат с.

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

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

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

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

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

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

Рисунок 1.1 – Основные блоки

Следует упомянуть некоторые основные правила выполнения блок-схем, которыми надлежит руководствоваться при графическом описании алгоритмов. Начало алгоритмов отмечается символом "Терминатор", из которого выходит одна линия. В нем записывается слово "Пуск" ("Начало"). Конец алгоритма отмечается этим же символом, в котором записывается слово "Останов" ("Конец"). В этом случае данный символ не имеет ни одной выходной линии, а на него может замыкаться одна или более линий. Символ “Процесс” может иметь одну или несколько входных линий и только одну выходную. Внутри символа может быть записано несколько предписаний – в этом случае они выполняются в порядке записи. Представление отдельных операций достаточно свободно. Для обозначения вычислений можно использовать математические выражения, для пересылки данных – стрелки, для других действий – пояснения на естественном языке, например, А: = Х + 4; i: = i + 1, ––> B.

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

Задача №1: Рассчитать площадь и периметр прямоугольника по двум известным сторонам.

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

Составим алгоритм решения подобных задач:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Послесловие

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

Специальность: 19.02.03 Технология хлеба, кондитерских и макаронных изделий.

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

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

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

Тип урока: закрепление ЗУН.

Вид урока: практическая работа.

Методы обучения: инструктаж и самостоятельная работа.

Метод контроля знаний: отчет о проделанной работе.

Оснащение: ПК, и ндивидуальные задания с алгоритмом выполнения.

Продолжительность урока: 45 минут.

Предметные связи: математика.

Формируемые компетенции:

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

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

ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность

ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.

ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

Требования к результатам усвоения учебного материала:

Студенты должны знать термины и понятия: алгоритм, алгоритмические конструкции.

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

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

Используемая литература:

1. Информатика и ИКТ: учебник для начального и среднего профессионального образования. Цветкова Н.С., Великович Л.С. – Академия, 2011 г.

2. Информатика и ИКТ. Практикум для профессий и специальностей технического и социально-экономического профилей. Н. Е. Астафьева, С. А. Гаврилова, под ред. М.С. Цветковой, Академия, 2012г.

Технологическая карта урока

1. Организационный момент 2 /

3. Контроль знаний по теме 5 /

4. Методические указания 5 /

5. Самостоятельная работа студентов по заданиям 27 /

6. Подведение итогов урока 1 /

Содержание этапов занятия

Методическое обоснование

1. Организационный момент

Приветствие. Контроль отсутствующих студентов, готовности аудитории к занятию.

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

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

3. Контроль знаний по теме.

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

4. Методические указания.

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

Преподаватель обращает внимание на соблюдение правил ТБ и санитарного режима при работе в компьютерном классе.

5.Самостоятельная работа студентов по заданиям.

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

6. Подведение итогов урока.

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

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

Подготовка студентов к работе, организация внимания всех студентов.

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

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

Читайте также: