что такое линейный алгоритм в информатике
Что такое линейный алгоритм в информатике
Понятие алгоритма. Исполнитель алгоритма. Свойства алгоритма. Способы записи алгоритмов.
Основные алгоритмические структуры: следование, ветвление, цикл; изображение
на блок-схемах. Вспомогательные алгоритмы.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач. ). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения:
1. Достать ключ из кармана.
2. Вставить ключ в замочную скважину.
3. Повернуть ключ два раза против часовой стрелки.
Если вы внимательно оглянитесь вокруг, то обнаружите множество алгоритмов которые мы с вами постоянно выполняем. Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм.
Дискретность (от лат. discretus — разделённый, прерывистый, раздельность) (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);
Детерминированность (от. лат. determinate – определенность, точность) (любое действие должно быть строго и недвусмысленно определено в каждом случае);
Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);
Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).
1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено заданное условие);
3. Разветвляющийся алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий);
4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).
На практике наиболее распространены следующие формы представления алгоритмов:
В письменной форме на естественном языке.
В письменной форме на формальном языке.
Для более наглядного представления алгоритма широко используется графическая форма – блок-схема, которая составляется из стандартных графических объектов.
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура.
Стадии создания алгоритма:
1. Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает (определить цель, наметить план действий).
2. Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия (выбрать среду и объект алгоритма, детализировать алгоритм).
Объект, который будет выполнять алгоритм, обычно называют исполнителем.
Назначение исполнителя точно выполнить предписания алгоритма, подчас не задумываясь о результате и целях, т.е. формально. Идеальными исполнителями являются машины, роботы, компьютеры.
Компьютер – автоматический исполнитель алгоритмов.
Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.
Линейный алгоритм
Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке в котором они следуют.
Блок-схема линейного алгоритма:
Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Перечень повторяющихся действий называют телом цикла.
Циклические алгоритмы бывают двух типов:
Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз;
Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.
Циклы со счетчиком используют когда заранее известно какое число повторений тела цикла необходимо выполнить. Например, на уроке физкультуры вы должны пробежать некоторое количество кругов вокруг стадиона.
Для счетчика от нач. значения до кон. значения выполнить действие.
Часто бывает так, что необходимо повторить тело цикла, но заранее не известно, какое количество раз это надо сделать. В таких случаях количество повторений зависит от некоторого условия. Такие циклы называются циклы с условием. Циклы в которых сначала проверяется условие, а затем, возможно, выполняется тело цикла называют циклы с предусловием. Если условие проверяется после первого выполнения тела цикла, то циклы называются циклы с постусловием.
Например, в субботу вечером вы смотрите телевизор. Время от времени поглядываете на часы и если время меньше полуночи, то продолжаете смотреть телевизор, если это не так, то вы прекращаете просмотр телепередач.
В общем случае схема циклического алгоритма с условием будет выглядеть так:
Пока условие повторять действие.
При составлении циклических алгоритмов важно думать о том, чтобы цикл был конечным. Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием.
Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других – другая.
Если пошел дождь, то надо открыть зонт.
Если прозвенел будильник, то надо вставать.
Если встречу Сашу, то скажу ему …
Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.
Эти предложения начинаются с проверки какого-либо условия: пошел дождь, прозвенел будильник, встретил Сашу… Далее в зависимости мы либо вылиняем какое-либо действие, либо не выполняем его (или выполняем какое-то другое действие).
Компьютер тоже в зависимости от какого-либо условия может выполнять или не выполнять те или иные действия. Алгоритм, в котором используется условие, получил название разветвляющегося, так как в зависимости от значения условия выбираются те или иные действия.
В общем случае схема разветвляющегося алгоритма будет выглядеть так: «если условие, то действие 1, иначе действие 2» (Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.). Так же можно использовать неполную форму: «если условие, то действие» (Если встречу Сашу, то скажу ему ). В этом случае не предусматривается действий на случай невыполнения условия.
Условие – это высказывание которое может быть либо истинно, либо ложно.
Еще раз обратим внимание, что существует две формы ветвления – неполная (когда присутствует только одна ветвь, т.е. в зависимости от истинности условия либо выполняется, либо не выполняется действие) и полная (когда присутствуют две ветви, т.е. в зависимости от истинности условия выполняется либо одно, либо другое действие).
Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав только его имя.
Алгоритмизация | Лекция №3
Линейные и разветвляющиеся алгоритмы
Содержание:
Данные. Понятие типа данных
Алгоритм, реализующий решение некоторой конкретной задачи, всегда работает с данными. Данные – это любая информация, представленная в формализованном виде и пригодная для обработки алгоритмом.
Данные делятся на переменные и константы.
Переменные – это такие данные, значения которых могут изменяться в процессе выполнения алгоритма.
Константы – это данные, значения которых не меняются в процессе выполнения алгоритма.
вычислить площадь круга по формуле S=пR 2
В данном алгоритме необходимо объявить две переменные:
Константой является число п.
Любая константа, как и переменная, занимает ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.
Типы констант определяются по контексту, т.е. по форме записи в тексте. А типы переменных устанавливаются в описаниях переменных.
Операции
Внутр.представле ние
Целые положительные и отрицательные числа.
Формат с фиксированной точкой
Любые (целые и дробные) числа.
Формат с плавающей точкой
Логические операции: И(and), ИЛИ(or), НЕ(not).
Любые символы компьютерного алфавита.
Коды таблицы символьной кодировки. 1 символ – 1 байт.
ЭВМ – исполнитель алгоритмов
Независимо от того, на каком языке программирования будет написана программа, алгоритм решения любой задачи на ЭВМ может быть составлен из команд:
Линейные алгоритмы
Тип алгоритма определяется характером решаемой задачи в соответствии с его командами задачи. Различают три типа алгоритмов: линейные, разветвляющиеся, циклические.
Линейными называются алгоритмы, в которых все действия осуществляются последовательно друг за другом, при этом каждая команда выполняется только один раз строго после той команды, которая ей предшествует.
Таким, например, является алгоритм вычисления по простейшим безальтернативны м формулам, не имеющий ограничений на значения входящих в эти формулы переменных. Как правило, линейные процессы являются составной частью более сложного алгоритма.
Линейный алгоритм составляется из команд присваивания, ввода, вывода и обращения к вспомогательным алгоритмам.
Присваивание – это операция, которая значение выражения, стоящее справа от символа «=» запоминает в переменной или элементе массива, стоящем слева. При присваивании происходит преобразование типов данных, если они не совпадают.
Присваивание может осуществляться двумя способами:
Например : вычислить дробь 
Формат команды присваивания следующий:
Переменная := выражение
Знак « :=» нужно читать как «присвоить».
Команда присваивания обозначает следующие действия, выполняемые компьютером:
1. вычисляется выражение ;
2. полученное значение присваивается переменной.
Поскольку присваивание является важнейшей операцией в вычислительных алгоритмах, обсудим ее более подробно.
В приведенной ниже таблице напротив каждой команды присваивания указываются значения переменных, которые устанавливаются после ее выполнения.
Линейные алгоритмы
Урок 26. Информатика 6 класс ФГОС
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока «Линейные алгоритмы»
На прошлых занятиях мы с вами узнали, что современная жизнь не возможна без технических помощников. Например, светофор, стиральная машина, принтер или кофеварка, все они выполняют алгоритмы, составленные человеком, и справляются с поставленной для них задачей.
Напомним, что эти технические устройства являются исполнителями алгоритмов. Согласитесь, каждый современный человек не представляет свою жизнь, например, без светофора. А задумывались ли вы, как он работает? Давайте разберёмся. Как видим, смена цветов светофора происходит последовательно друг за другом: красный – жёлтый – зелёный – жёлтый – красный – жёлтый – зелёный и т. д. Светофор управляет дорожным движением, не обращая внимания на обстановку на перекрёстке т.е. действует по определённому алгоритму.
Алгоритм, в котором команды выполняются в порядке их записи, т.е. последовательно друг за другом называется линейным.
Давайте рассмотрим ещё один пример линейного алгоритма:
Шестиклассницу Таню мама попросила посадить лук. Таня с радостью согласилась помочь. Опишем последовательность действий Тани:
1. Выкопать на грядке ямку;
2. Положить в ямку лук;
3. Засыпать ямку с луком землёй;
4. Полить лук водой.
Представим данный алгоритм с помощью блок-схемы:
Начало алгоритма изображается с помощью овала (Таня пришла на грядку)
Выполняемое действие изображается с помощью прямоугольника (Выкопать на грядке ямку; Положить в ямку лук; Засыпать ямку с луком землёй; Полить лук водой.)
Конец алгоритма также изображается овалом (Таня отправилась к маме сказать, что её просьба выполнена)
Система команд исполнителя Вычислитель состоит из двух команд:
Давайте придумаем для Вычислителя алгоритм, с помощью которого он получит из 0 число 50.
Алгоритм решения этой задачи может быть, например, таким:
Для того что бы понять, чем же для нас может быть полезен линейный алгоритм, давайте проведём компьютерный практикум. Создадим презентацию «Часы», с помощью редактора презентаций Power Point. Давайте в нашей презентации сделаем так, чтобы время на циферблате изменялось каждые 10 минут, т.е. зададим линейный алгоритм изменения времени.
1. Напомним, что открыть программу Power Point можно нажав в меню Пуск – Все программы.
2. Выберем вкладку Главная затем в группе Слайды нажмём на кнопке Макет здесь нам нужен Пустой слайд.
3. Для того чтобы у нас получился симметричный циферблат, нарисуем сначала в центре слайда пересекающиеся прямые по горизонтали и вертикали.
Теперь мы можем изображать часы. Начнём с циферблата. Выбираем вкладку Вставка, нажимаем на Фигуры и с помощью готовых фигур изображаем циферблат и две стрелки.
Копируйте повторяющиеся изображения. Не забывайте, их можно редактировать, поворачивать.
4. Далее на вкладке Слайды левой панели нажимаем на слайд с часами, переходим на вкладку Главная и щёлкаем на Копировать. Вставим в презентацию 4 копии нашего слайда (всего у нас будет 5 слайдов), для этого на вкладке Главная нажмём 4 раза Вставить.
5. Наши часы должны показывать время, поэтому изменим положение стрелок на слайдах, например, на 12.00, 12.10, 12.20, 12.30 и 12.40.
6. Для того, чтобы слайды менялись перейдём на вкладку Переходы и в группе Время показа слайдов установим минимальную длительность перехода (00,01) затем, нажмём кнопку Применить ко всем.
7. Запустим презентацию. Выбираем вкладку Показ слайдов, нажимаем С начала.
8. Сохраним презентацию в папке с вашей фамилией под названием Мои часы.
Итак, в нашей презентации «Часы» линейный алгоритм – это последовательное изменение времени каждые 10 минут.
Таким образом, сегодня на уроке мы узнали, что
Линейным алгоритмом называется алгоритм, в котором команды выполняются последовательно друг за другом, т.е. в порядке их записи.
Так же научились применять линейные алгоритмы для создания интересных презентаций в PowerPoint.
Линейный алгоритм. Понятие и особенности. Блок-схема
Каждый человек на протяжении своей жизни решает множество задач разной сложности. Но даже самые простые из задач выполняются последовательно, то есть за несколько шагов. Эту последовательность можно назвать алгоритмом. Последовательности бывают разные, но начинать их изучение лучше всего с линейных.
Прежде чем приступить к рассмотрению основной темы статьи, следует сделать краткое отступление и сказать несколько слов про алгоритмический язык.
Алгоритмический язык
Представьте, что человеку, работающему за компьютером, поставлена некая вычислительная задача. В языке программирования решение этой задачи выполняется с помощью алгоритмизации. Решение предполагает: — разбиение на этапы; — разработку алгоритма; — составление программы решения на алгоритмическом языке; — ввод данных; — отладку программы (возможны ошибки — их надо исправить); — выполнение на ПК; — анализ результатов.
Алгоритмический язык является средством описания алгоритмов, а уже алгоритм, в свою очередь, представляет собой чёткое описание определённой последовательности действий, направленных на решение необходимой задачи.
Свойства алгоритма
Их несколько: — конечность. Любой алгоритм должен быть завершённым, а окончание наступает после выполнения определённого числа шагов; — однозначность, понятность. Не допускается разных толкований, неопределённости и двусмысленности — всё должно быть чётко и ясно, а также понятно исполнителю — и правила выполнения действий линейного алгоритма, и сами действия; — результативность. Итог работы — результат, полученный за конечное число шагов; — универсальность, массовость. Качественный алгоритм способен решать не одну задачу, а целый класс задач, имеющих схожую постановку/структуру.
Линейная структура
Любой алгоритм составляется из ряда базовых структур. Простейшей базовой структурой является следование — структура с линейными характеристиками. Из этого можно сформулировать определение.
Линейный алгоритм — это алгоритм, образуемый командами, которые выполняются однократно и именно в той последовательности, в которой записаны. Линейная структура, по сути, проста. Записать её можно как в текстовой, так и в графической форме.
Представим, что у нас стоит задача пропылесосить ковёр в комнате. В текстовой форме алгоритм будет следующим: — принести пылесос к месту уборки; — включить; — пропылесосить; — выключить; — унести пылесос.
И каждый раз, когда нам надо будет пылесосить, мы будем выполнять один и тот же алгоритм.
Теперь поговорим про графическую форму представления.
Блок-схема
Для изображения алгоритма графически используют блок-схемы. Они представляют собой геометрические фигуры (блоки), соединённые стрелками. Стрелки показывают связь между этапами и последовательность их выполнения. Каждый блок сопровождается надписью.
Рассмотрим фигуры, которые используются при визуализации типичной линейной последовательности.
Блок ввода-вывода данных (отображает список вводимых и выводимых переменных):
Арифметический блок (отображает арифметическую операцию/группу операций):
Условный блок (позволяет описать условие). Алгоритмы с таким блоком используются при графической визуализации алгоритмов с ветвлением:
Условного блока нет в классическом линейном алгоритме, так как в нём, как уже было сказано ранее, все операции выполняются последовательно, то есть одна за другой. В линейном алгоритме размещение блоков выглядит следующим образом:
А вот, как решается задача по нахождению площади треугольника по формуле Герона. Здесь a, b, c – это длины сторон, S – площадь треугольника, P – периметр.
Следует обратить внимание, что запись «=» — это не математическое равенство, а операция присваивания. В результате этой операции переменная, стоящая слева от оператора, получает значение, которое указано справа. Значение не обязательно должно быть сразу определено (a = 3) — оно может вычисляться посредством выражения (a = b + z), где b = 1, a z = 2.
Примеры линейных алгоритмов
Если рассмотреть примеры решения на языке Pascal (именно этот язык до сих пор используется для изучения основ алгоритмизации и программирования), то можно увидеть следующую картину:
И, соответственно, блок-схема программы линейной структуры будет выглядеть следующим образом:
Как составить программу линейной структуры?
Порядок следующий: — определите, что именно относится к исходным данными, а также каков типы/класс этих данных, выберите имена переменных; — определите, каков тип данных будет у искомого результата, выберите название переменных (переменной); — определите, какие математические формулы связывают результат и исходные данные; — если требуется наличие промежуточных данных, определите класс/типы этих данных и выберите имена; — опишите все используемые переменные; — запишите окончательный алгоритм. Он должен включать в себя ввод данных, вычисления, вывод результатов.
На этом всё, в следующий раз рассмотрим на примерах программу разветвлённой структуры. Если же вас интересует тема алгоритмизации в контексте разработки программного обеспечения, ждём вас на профессиональном курсе OTUS!
Линейный алгоритм и как решать задачи: подборка примеров, детальное описание
Содержание:
Каждый линейный алгоритмический конструктив включает базовые структуры. К простейшим базовым принципам относят принцип следования, имеющий линейные характеристики. На основании этого информатика дает точное определение.
Линейная конструкция является алгоритмом из группы команд. Следование командам – однократное, последовательное. Простая структура может быть выражена в виде графика или текстового описания.
Как сформировать алгоритм: порядок действий
Чтобы получилась целостная конструкция, нужно выполнить следующие шаги:
В итоговой блок-схеме важно указать процесс ввода, вывода сведений, полный список всех вычислительных операций.
Дан фрагмент линейного алгоритма a 8 – как решить задачу
В задаче дан фрагмент линейного алгоритма а 8, при этом б : = 6 + 3а, а : = б : 3а. Нужно вычислить переменную после решения системы.
Коэффициент а инициализируется при первичном вводе, его установленное значение 8 является целым. Так как изначально дан фрагмент линейного алгоритма с переменной б, она также используется для выделения измененного следующего показателя. Чтобы установить изменение а, необходимо предварительно вычислить значение б. Для этого:
б = 6 + 3 × 8 = 6 + 24 = 30
Пока число а не изменилось, оно равняется 8. Формируется дробное выражение с 8 в знаменателе: а = 30 : 3 × 8 = 10 × 8 = 80
Итог: когда код исполнится, переменная станет равна 80.
Блок-схема простейшего линейного алгоритма
Рассмотрим принцип линейных выражений на простом примере из жизни. Необходимо построить алгоритм покупки хлеба. В текстовой форме он будет иметь вид:
Графическое представление выглядит следующим образом:
Решение задачи по алгоритму «Узор»
Робот владеет четырьмя командами: перемещается вправо, влево, вниз, вверх. Каждый ход – одна клетка в указанном направлении. Команда «Закрасить» заставляет исполнителя зарисовывать клетки, в которых он пребывает в данный момент. Нужно составить алгоритмическую структуру закрашивания двух угловых верхних клеток, одной средней, возврата в угловую верхнюю клетку. Точка возврата отмечена на рисунке *.
