Алгоритм — это система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа.
Примеры: правила сложения, умножения, решения алгебраических уравнений и т.п.
1.Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.
2.Дискретность — процесс решения задачи по алгоритму разбит на отдельные действия.
3.Конечность — каждое из действий и весь алгоритм в целом обязательно завершаются.
4.Результативность — по завершении выполнения алгоритма обязательно получается конечный результат.
5.Выполнимость (эффективность) — результата алгоритма достигается за конечное число шагов.
6.Детерминированность (определенность) — алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один и тот же результат.
7.Последовательность – порядок исполнения команд должен быть понятен исполнителю и не должен допускать неоднозначности.
1. вычислительные алгоритмы , работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;
2. информационные алгоритмы , представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);
3. управляющие алгоритмы , генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.
По типу передачи управления алгоритмы бывают: основные (главные выполняемые программы) и вспомогательные (подпрограммы).
Для задания алгоритма необходимо описать следующие его элементы:
1.набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;
3.правило непосредственной переработки информации (описание последовательности действий);
5.правило извлечения результатов.
Способы описания алгоритмов.
Символьный, когда алгоритм описывается с помощью специального набора символов (специального языка).
Словесная форма записи алгоритмов обычно используется для алгоритмов, ориентированных на исполнителя-человека. Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противного.
Графическая запись с помощью блок-схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Графическая запись алгоритма имеет ряд преимуществ: каждая операция вычислительного процесса изображается отдельной геометрической фигурой и графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали.
Правила создания блок – схем:
1.Линии, соединяющие блоки и указывающие последовательность связей между ними, должны проводится параллельно линиям рамки.
2.Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз.
3.В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков.
4.Из блока (кроме логического) может выходить только одна линия.
5.Логический блок может иметь в качестве продолжения один из двух блоков, и из него выходят две линии.
6.Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить.
7.Схему алгоритма следует выполнять как единое целое, однако в случае необходимости допускается обрывать линии, соединяющие блоки.
В линейном алгоритме операции выполняются последовательно, в порядке их записи. Каждая операция является самостоятельной, независимой от каких-либо условий. На схеме блоки, отображающие эти операции, располагаются в линейной последовательности.
В алгоритме с ветвлением предусмотрено несколько направлений (ветвей). Каждое отдельное направление алгоритма обработки данных является отдельной ветвью вычислений. Направление ветвления выбирается логической проверкой, в результате которой возможны два ответа:
1.«да» — условие выполнено.
2.«нет» — условие не выполнено.
Циклические алгоритмы содержат цикл – это многократно повторяемый участок алгоритма.Различают циклы с предусловием и постусловием.Также циклы бывают детерминированные и итерационные.Цикл называется детерминированным, если число повторений тела цикла заранее известно или определено. Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а зависит от значений параметров (некоторых переменных), участвующих в вычислениях.
Источник
Алгоритмы
Алгоритмы. Разработка алгоритма решения задачи
Исключительно важно использовать язык блок-схем при разработке алгоритма решения задачи. Решение одной и той же задачи может быть реализовано с помощью различных алгоритмов, отличающихся друг от друга как по времени счета и объему вычислений, так и по своей сложности. Запись этих алгоритмов с помощью блок-схем позволяет сравнивать их, выбирать наилучший алгоритм, упрощать, находить и устранять ошибки.
Отказ от языка блок-схем при разработке алгоритма и разработка алгоритма сразу на языке программирования приводит к значительным потерям времени, к выбору неоптимального алгоритма. Поэтому необходимо изначально разработать алгоритм решения задачи на языке блок-схем, после чего алгоритм перевести на язык программирования.
При разработке алгоритма сложной задачи используется метод пошаговой детализации. На первом шаге продумывается общая структура алгоритма без детальной проработки отдельных его частей. Блоки, требующие детализации, обводятся пунктирной линией и на последующих шагах разработки алгоритма продумываются и детализируются.
В процессе разработки алгоритма решения задачи можно выделить следующие этапы:
Этап 1 . Математическое описание решения задачи.
Этап 2 . Определение входных и выходных данных.
Этап 3 . Разработка алгоритма решения задачи.
Базовые алгоритмические конструкции
В теории программирования доказано, что для записи любого, сколь угодно сложного алгоритма достаточно трех базовых структур:
следование (линейный алгоритм);
ветвление (разветвляющийся алгоритм);
цикл-пока (циклический алгоритм).
Линейные алгоритмы
Линейный алгоритм образуется из последовательности действий, следующих одно за другим. Например, для определения площади прямоугольника необходимо сначала задать длину первой стороны, затем задать длину второй стороны, а уже затем по формуле вычислить его площадь.
Пример
ЗАДАЧА. Разработать алгоритм вычисления гипотенузы прямоугольного треугольника по известным значениям длин его катетов a и b.
На примере данной задачи рассмотрим все три этапа разработки алгоритма решения задачи:
Этап 1. Математическое описание решения задачи.
Математическим решением задачи является известная формула:
,
где с-длина гипотенузы, a, b – длины катетов.
Этап 2. Определение входных и выходных данных.
Входными данными являются значения катетов a и b. Выходными данными является длина гипотенузы – c.
Этап 3. Разработка алгоритма решения задачи.
Словесное описание алгоритма
Запись алгоритма на языке блок-схем
Начало алгоритма.
Ввод значений длин катетов a и b.
Вычисление длины гипотенузы с по формуле
Вывод значения длины гипотенузы.
Конец алгоритма
На данной схеме цифрами указаны номера элементов алгоритма, которые соответствуют номерам пунктов словесного описания алгоритма.
Разветвляющиеся алгоритмы
Алгоритм ветвления содержит условие, в зависимости от которого выполняется та или иная последовательность действий.
Пример
ЗАДАЧА. Разработать алгоритм вычисления наибольшего числа из двух чисел x и y.
Этап 1. Математическое описание решения задачи.
Из курса математики известно, если x > y, то наибольшее число x, если 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 – количество натуральных чисел.
Выходные данные – значение суммы членов последовательности натуральных чисел.
Параметр цикла –величина, определяющая количество повторений цикла. В нашем случае i – номер натурального числа.
Подготовка цикла заключается в задании начального и конечного значений параметра цикла.
начальное значение параметра цикла равно 1,
конечное значение параметра цикла равно n,
шаг цикла равен 1.
Для корректного суммирования необходимо предварительно задать начальное значение суммы, равное 0.
Тело цикла. В теле цикла будет выполняться накопление значения суммы чисел, а также вычисляться следующее значение параметра цикла по формулам:
Условие продолжения цикла: цикл должен повторяться до тех пор, пока не будет добавлен последний член последовательности натуральных чисел, т.е. пока параметр цикла будет меньше или равен конечному значению параметра цикла.
Этап 3. Разработка алгоритма решения задачи.
Введем обозначения: S – сумма последовательности, i – значение натурального числа.
Начальное значение цикла i=1, конечное значение цикла i =100, шаг цикла 1.
Источник
Практическая работа №11 Алгоритмы и способы их описания. Основные алгоритмические конструкции
Практическая работа №11
Тема: «Алгоритмы и способы их описания. Основные алгоритмические конструкции»
— сформировать представление об алгоритме и его свойствах;
— сформировать представление о способах их описания алгоритмов;
— сформировать представление о типах алгоритмов;
— сформировать представление об основных алгоритмических конструкциях.
Теоретические сведения к практической работе
Слово алгоритм происходит от латинской формы написания имени великого математика IX века Аль-Хорезми , который сформулировал правила выполнения арифметических действий.
Первоначально под алгоритмами понимали только правила выполнения четырёх арифметических действий над многозначными числами.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Алгоритмизация – процесс разработки алгоритма (плана действий) для решения задачи.
Шаг алгоритма – это каждое отдельное действие алгоритма.
Исполнитель – это объект, умеющий выполнять определенный набор действий. Исполнителем может быть человек, робот, животное, компьютер.
Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять.
Среда исполнителя – обстановка, в которой функционирует исполнитель.
Дискретность — (прерывность, раздельность) – разбиение алгоритма на шаги
Результативность — получение результата за конечное количество шагов
Массовость — использование алгоритма для решения однотипных задач
Конечность — каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения
Детерминированность — (определенность, точность) – каждое действие должно быть строго и недвусмысленно определено
Способы записи алгоритмов (блок-схема)
Начало или конец алгоритма
Ввод или вывод данных.
Внутри блока перечисляются данные через запятую .
Внутри блока записываются математические формулы и операции для обработки данных.
Внутри блока записываются логические условия. Имеет два выхода Да(+) и Нет(-) .
Блок вывода информации на печатающее устройство
Блок вывода информации на экран дисплея
Алгоритмы могут быть заданы:
Словесное задание описывает алгоритм с помощью слов и предложений естественного языка.
Табличное задание служит для представления алгоритма в форме таблиц и расчётных формул.
Графическое задание или блок-схема – способ представления алгоритма с помощью геометрических фигур, называемых блоками .
Алгоритм, в котором команды выполняются последовательно одна за другой, называется линейным алгоритмом.
В разветвляющиеся алгоритмы входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (серий).
В алгоритмической структуре «ветвление» та или иная серия команд выполняется в зависимости от истинности условия.
Условие может быть либо истинным, либо ложным.
В циклические алгоритмы входит последовательность команд, выполняемая многократно. Такая последовательность команд называется телом цикла.
В алгоритмической структуре «цикл» серия команд (тело цикла) выполняется многократно.
Циклические алгоритмические структуры бывают двух типов:
циклы со счётчиком , в которых тело цикла выполняется определённое количество раз;
циклы с условием, в которых тело цикла выполняется, пока условие истинно.
Задание 1. составить в виде блок-схемы алгоритм нахождения середины отрезка при помощи циркуля и линейки опираясь на пример алгоритма естественного языка
Пример: «Алгоритм деления отрезка АВ пополам».
поставить ножку циркуля в т.А;
установить раствор циркуля равным длине отрезка АВ;
поставить ножку циркуля в т.В;
через точки пересечения окружностей провести прямую;
отметить точку пересечения этой прямой с отрезком АВ.
Задание 2. Используйте ресурсы Интернета для нахождения определения свойств алгоритма и запишите их в тетрадь. Приведите примеры.
Задание 3. Допишите в тетради в основные алгоритмические конструкции недостающие правила блок-схем.
Задание 4. Сделать вывод о проделанной практической работе
1. Информатика и ИКТ: учебник для начального и среднего профессионального образования. Цветкова Н.С., Великович Л.С. – Академия, 2012 г.
2. Информатика и ИКТ. Практикум для профессий и специальностей технического и социально-экономического профилей. Н. Е. Астафьева, С. А. Гаврилова, под ред. М.С. Цветковой, Академия, 2014г.
Этапы решения задач. Примеры построения алгоритмов и их реализация на ПК
Теоретические сведения к практической работе
Человек использует компьютер для решения самых разнообразных информационных задач:
работа с текстами,
создание графических изображений,
получение справки из базы данных,
решение математических задач,
расчет технических конструкций и многое другое.
Для их решения в распоряжении пользователя имеется обширное программное обеспечение:
системное ПО (ядром которого является операционная система)
прикладное ПО (программы, предназначенные для пользователя)
системы программирования (средства для создания программ на языках программирования).
Процесс решения задач на компьютере – это совместная деятельность человека и ЭВМ. На долю человека приходятся этапы, связанные с творческой деятельностью – постановкой, алгоритмизацией, программированием задач и анализом результатов, а на долю персонального компьютера – обработка информации с разработанным алгоритмом.
Рассмотрим эти этапы на примере: пусть требуется найти сумму двух чисел.
Первый этап – постановка задачи. На этом этапе участвует человек, хорошо представляющий предметную область задачи (биолог, экономист, инженер). Он должен чётко определить цель задачи, дать словесное описание содержания задачи и предложить общий подход к её решению.
Для задачи вычисления суммы двух чисел человек, знающий, как складываются числа, может описать задачу следующим образом: ввести два целых числа, сложить их и вывести сумму в качестве результата решения задачи.
Второй этап – выбор метода решения (математическое или информационное моделирование ). Цель данного этапа – создать такую математическую модель решаемой задачи, которая могла быть реализована в компьютере. Существует целый ряд задач, где математическая постановка сводится к простому перечислению формул и логических условий.
Этот этап тесно связан с первым этапом, и его можно отдельно не рассматривать. Однако возможно, что для полученной модели известны несколько методов решения и необходимо выбрать лучший.
Для нашего примера: введённые в компьютер числа запомним в памяти под именами А и В, а результат запомним в памяти под именем Summa.
Третий этап – алгоритмизация задачи. На основе математического описания необходимо разработать алгоритм решения.
Алгоритм – система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа (класса).
Понятие возникло и используется давно. Сам термин «алгоритм» ведёт начало от перевода на европейские языки имени арабского математика Аль-Хорезми (IX век). Им были описаны правила (в нашем понимании – алгоритмы) выполнения основных арифметических действий в десятичной системе счисления.
Задача составления алгоритма не имеет смысла, если не известны или не учитываются возможности его исполнителя (ребёнок может прочесть, но не может решить сложную задачу).
Исполнителем может быть не только человек, но и автомат. Компьютер – лишь частный, но наиболее впечатляющий пример исполнителя, чьё поведение основано на реализации алгоритма. Более того, создание персонального компьютера оказало воздействие на развитие теории алгоритмов, одной из областей дискретной математики.
Эффективный метод построения алгоритма – метод пошаговой детализации (последовательного построения). При этом сложная задача разбивается на ряд более простых. Для каждой подзадачи – свой алгоритм. Универсальный эффективный метод построения алгоритма является основой структурного программирования (языки QBasic, Turbo Pascal и др.).
Если алгоритм разработан, то его можно вручить разным людям (пусть и не знакомым с сутью решаемой задачи), и они, следуя системе правил, будут действовать одинаково и получат (при безошибочных действиях) одинаковый результат.
Используются различные способы записи алгоритмов:
– словесный (запись рецептов в кулинарной книге, инструкции по использованию технических устройств и т. п.);
– графический – пример на рисунке;
– структурно-стилизованный (для записи используется язык псевдокода).
Пример графического изображения алгоритма
Свойства алгоритма. При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств.
Однозначность алгоритма – единственность толкования исполнителем правил выполнения действий и порядка их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя (сложить А и В ).
Конечность алгоритма – обязательность завершения каждого из действий, составляющих алгоритм, и завершимость алгоритма в целом. Представленный на рисунке алгоритм обладает этим свойством.
Результативность алгоритма – предполагает, что выполнение алгоритма должно завершиться получением определённых результатов. У нас для целых А и В всегда будет вычислена сумма.
Массовость – возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. В нашем примере алгоритмом используется обозначение, а не конкретные числа, поэтому он может быть использован для сложения любых целых чисел.
Правильность алгоритма – способность алгоритма давать правильные результаты решения поставленных задач.
Четвёртый этап – программирование. Программой называется план действий, подлежащих выполнению некоторым исполнителем, в качестве которого может выступать компьютер. Программа позволяет реализовать разработанный алгоритм. Именно этому этапу посвящена большая часть данного учебного пособия.
Пятый этап – ввод программы и исходных данных в ЭВМ с клавиатуры с помощью редактора текстов и их запись на гибкий или жёсткий диск для постоянного хранения.
Шестой этап – тестирование и отладка программы. Исполнение алгоритма с помощью ЭВМ, поиск и исключение ошибок. При этом программисту приходится выполнять рутинную работу по проверке работы программы, поиску и исключению ошибок, и поэтому для сложных программ этот этап часто требует гораздо больше времени и сил, чем написание первоначального текста программы.
Отладка программы – сложный и нестандартный процесс, который заключается в том, чтобы протестировать программу на контрольных примерах.
Контрольные примеры стремятся выбрать так, чтобы при работе с ними программа прошла все основные пути блок-схем алгоритма, поскольку на каждом из путей могут быть свои ошибки, а детализация плана зависит от того, как поведёт себя программа на этих примерах. На одном она может «зациклиться», на другом дать бессмысленный результат. Сложные программы отлаживают отдельными фрагментами.
Для повышения качества выполнения этого этапа используются специальные программы – отладчики, которые позволяют исполнить программу «по шагам» с наблюдением за изменением значений переменных, выражений и других объектов программы, с отслеживанием выполнения операторов.
Седьмой этап – исполнение отлаженной программы и анализ результатов. На этом этапе программист запускает программу и задаёт исходные данные, требуемые по условию задачи.
Полученные результаты анализируются постановщиком задачи, и на основании этого анализа вырабатываются соответствующие решения, рекомендации, выводы. Например, если при решении задачи на ПК результат 2+3=4, то следует изменить алгоритм и программу.
Постройте структурную схему алгоритма поиска среднего роста учащихся в колледже, а также минимального и максимального значений роста. Используйте массив для описания списка учащихся, циклическую алгоритмическую конструкцию для поиска минимума и максимума, суммирования всех элементов этого массива. Результат представьте, как итог вычисления среднего арифметического, а для минимального и максимального значений роста учащихся сообщите соответствующие номера этих учащихся в списке группы.
1. Информатика и ИКТ: учебник для начального и среднего профессионального образования. Цветкова Н.С., Великович Л.С. – Академия, 2012 г.
2. Информатика и ИКТ. Практикум для профессий и специальностей технического и социально-экономического профилей. Н. Е. Астафьева, С. А. Гаврилова, под ред. М.С. Цветковой, Академия, 2014г.
,
