Как сделать линейный алгоритм
Обновлено: 05.07.2024
Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке в котором они следуют.
Блок-схема линейного алгоритма:
Лучшее качества компьютеров проявляются не тогда, когда они рассчитывают значения сложных выражений, а когда многократно, с незначительными изменениями, повторяют сравнительно простые операции. Даже очень простые расчеты могут поставить человека в тупик, если их надо повторить тысячи раз, а повторять операции миллионы раз человек совершенно не способен.
С необходимостью повторяющихся вычислений программисты сталкиваются постоянно. Например, если надо подсчитать, сколько раз буква "о" встречается в тексте необходимо перебрать все буквы. При всей простоте этой программы исполнить ее человеку очень трудно, а для компьютера это задача на несколько секунд.
Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Перечень повторяющихся действий называют телом цикла .
Циклические алгоритмы бывают двух типов:
Циклы со счетчиком , в которых какие-то действия выполняются определенное число раз;
Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.
Циклы со счетчиком используют когда заранее известно какое число повторений тела цикла необходимо выполнить. Например, на уроке физкультуры вы должны пробежать некоторое количество кругов вокруг стадиона.
В общем случае схема циклического алгоритма со счетчиком будет выглядеть так:
Для счетчика от нач. значения до кон. значения выполнить действие .
Часто бывает так, что необходимо повторить тело цикла, но заранее не известно, какое количество раз это надо сделать. В таких случаях количество повторений зависит от некоторого условия. Такие циклы называются циклы с условием. Циклы в которых сначала проверяется условие, а затем, возможно, выполняется тело цикла называют циклы с предусловием. Если условие проверяется после первого выполнения тела цикла, то циклы называются циклы с постусловием.
Например, в субботу вечером вы смотрите телевизор. Время от времени поглядываете на часы и если время меньше полуночи, то продолжаете смотреть телевизор, если это не так, то вы прекращаете просмотр телепередач.
В общем случае схема циклического алгоритма с условием будет выглядеть так:
Пока условие повторять действие .
При составлении циклических алгоритмов важно думать о том, чтобы цикл был конечным. Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием .
Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других – другая.
Если пошел дождь, то надо открыть зонт.
Если прозвенел будильник, то надо вставать.
Если встречу Сашу, то скажу ему …
Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.
Разветвляющийся алгоритм - алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Эти предложения начинаются с проверки какого-либо условия: пошел дождь, прозвенел будильник, встретил Сашу… Далее в зависимости мы либо вылиняем какое-либо действие, либо не выполняем его (или выполняем какое-то другое действие).
Компьютер тоже в зависимости от какого-либо условия может выполнять или не выполнять те или иные действия. Алгоритм, в котором используется условие, получил название разветвляющегося, так как в зависимости от значения условия выбираются те или иные действия.
Условие – это высказывание которое может быть либо истинно, либо ложно.
Еще раз обратим внимание, что существует две формы ветвления – неполная (когда присутствует только одна ветвь, т.е. в зависимости от истинности условия либо выполняется, либо не выполняется действие) и полная (когда присутствуют две ветви, т.е. в зависимости от истинности условия выполняется либо одно, либо другое действие).
Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав только его имя.
Вспомогательный алгоритм, записанный на языке программирования, называется подпрограммой. При создании средних по размеру программ используется структурное программирование, идея которого заключается в том, что структура программы должна отражать структуру решаемой задачи, чтобы алгоритм решения был ясно виден из исходного текста. Программа разбивается на множество подпрограмм, каждая из которых выполняет какое-то действие, предусмотренное исходным заданием.
Комбинируя подпрограммы, удается сформировать итоговый алгоритм используя блоки кода (подпрограммы), имеющих определенную смысловую нагрузку. Обращаться к этим подпрограммам можно по их имени. Очень важная характеристика подпрограмм - это возможность их повторного использования.
Рассмотрим пример с графическим исполнителем ГРИС. Пусть требуется составить алгоритм рисования четырехзначного числа 1919.
Можно составить один длинный алгоритм, по которому исполнитель шаг за шагом нарисует эти цифры. Но ведь цифры 1 и 9 повторяются по два раза. Алгоритм можно сократить используя вспомогательный алгоритм.
Получится более короткий и понятный алгоритм:
Где ЕДИНИЦА и ДЕВЯТЬ вспомогательные алгоритмы:
| Алгоритм ЕДИНИЦА начало поворот шаг шаг шаг шаг поворот поворот прыжок прыжок прыжок прыжок поворот конец | Алгоритм ДЕВЯТЬ начало шаг поворот шаг шаг шаг шаг поворот шаг поворот шаг шаг поворот шаг поворот поворот поворот прыжок прыжок поворот конец |
Метод последовательной детализации
Использованный нами подход облегчает программирование сложных задач. Задача разбивается на более простые подзадачи. Решение каждой оформляется в виде вспомогательного алгоритма, а основной алгоритм организует связку между ними.
Метод программирования, при котором сначала пишется основная программа, в ней записываются обращения к пока еще не составленным подпрограммам, а потом описываются эти подпрограммы, называется методом последовательной (пошаговой) детализации . Причем количество шагов детализации может быть гораздо большим, чем в нашем примере, поскольку сами подпрограммы могут содержать внутри себя обращения к другим подпрограммам.
Возможен и другой подход к построению сложных программ: первоначально составляется множество подпрограмм, которые могут понадобиться при решении задачи, а затем пишется основная программа, содержащая обращения к ним. Подпрограммы могут быть объединены в библиотеку подпрограмм и сохранены в долговременной памяти компьютера. Такую библиотеку можно постепенно пополнять новыми подпрограммами.
Например, если для управления графическим исполнителем создать библиотеку процедур рисования всех букв и цифр, то программа получения любого текста будет состоять из команд обращения к библиотечным процедурам.
Описанный метод называется сборочным программированием .
Часто в литературе по программированию используется такая терминология: метод последовательной детализации называют программированием сверху вниз , а сборочный метод — п рограммированием снизу вверх .
Линейный алгоритм – это алгоритм, в котором блоки выполняются последовательно сверху вниз от начала до конца.
На рисунке 1 приведен пример блок-схемы алгоритма вычисления периметра Р и площади S квадрата со стороной длины A.
Рисунок 1. Линейный алгоритм
Для данного примера способ передачи константы не имеет значения, важно лишь то, что при выполнении блока 2 в ячейку с адресом А будет занесена конкретная константа. Пусть такой константой является число 5.
В блоке 4 аналогичным образом производится умножение значений переменной А и результат (константа 25) присваивается переменной S (в ячейку по адресу S будет занесена константа 25). После этого выполняется переход к блоку 5.
При выполнении команд блока 5 выводятся (например, на экран, бумагу, во внешний файл и т. д.) значения переменных А, Р, S, которые сохранились в соответствующих ячейках к этому моменту. Понятно, что для конкретного примера А = 5 будут выведена константы 5, 20, 25, т. е. длина сторона квадрата, его периметр и площадь. Далее управление передается последнему блоку 6.
В блоке б “Конец” производится освобождение ячеек памяти, которые были зарезервированы под переменные А, P, S, и алгоритм заканчивает работу.
Понятно, что при новом запуске этого же алгоритма можно получить совсем другие числа. Так, если в блоке 2 переменной А присвоить значение 20, то алгоритм выдаст в блоке 5 константы 20, 80, 400.
Детальное описание алгоритма рисунка 1 приведено для того, чтобы показать, в какой последовательности автомат выполняет предписанные операции и как при этом меняется состояние памяти автомата, т. е. для того, чтобы объяснить суть происходящих в автомате процессов. Из сказанного нужно уяснить, что автомат выполняет предписанную ему работу шаг за шагом. Всякий шаг обрабатывается процессором. Помимо вычислений процессор при необходимости отдает команды считывавшей/записывавшей головке, что и куда записывать, откуда читать. Конечный результат следует искать в ячейках памяти, каждая из которых до окончания алгоритма имеет известный адрес и хранит записанную в нее константу.
При выполнении проектов нет нужды давать столь подробное описание алгоритма. Тем не менее, описание должно быть выполнено с той степенью полноты, которая позволяет дать ясное представление о всех сторонах и особенностях алгоритмического процесса.
Коммуникативный педагогический тренинг: способы взаимодействия с разными категориями учащихся
Сертификат и скидка на обучение каждому участнику
Составление линейных алгоритмов
На предыдущих уроках мы узнали, что такое алгоритм, какие бывают виды алгоритмов, и кто их исполняет.
Сегодня мы попрактикуемся в составлении алгоритмов. Это очень важные навыки. Мы уже неоднократно отмечали, что составить алгоритм, то есть объяснить другому, как выполнять те или иные задачи так, чтобы это было понятно каждому, - очень тяжело. Наша задача – научиться составлять алгоритмы для различных примеров, чтобы впоследствии, когда вы столкнётесь с необходимостью составлять алгоритмы для написания различных программ, это не составляло для вас особого труда.
Начнём мы с самых простых алгоритмов – линейных. Их составление, обычно, не вызывает особого труда. Однако, навыки составления таких алгоритмов чрезвычайно важны.
Пример 1. Составить алгоритм запуска программы Paint в ОС Windows 7.
Решение: Вспомним из курса информатики 5 класса порядок действий для запуска программы Paint.
Данный алгоритм в виде блок-схемы имеет следующий вид:
Рис. 1. Блок-схема к примеру 1.
Составление алгоритмов с ветвлениями
Рассмотрим пример на составление алгоритмов с ветвлениями.
Пример 2. Составьте алгоритм для перехода дороги на светофоре.
Возможны следующие ситуации: в тот момент, когда мы подошли к дороге горел красный или зелёный свет. Если горел зелёный свет, то можно переходить дорогу. Если же горел красный свет, то необходимо дождаться зелёного – и уже тогда переходить дорогу.
Таким образом, алгоритм имеет следующий вид:
Подойти к светофору.
Посмотреть на его свет.
Если горит зелёный, то перейти дорогу.
Если горит красный, то подождать, пока загорится зелёный, и уже тогда перейти дорогу.
Блок-схема данного алгоритма имеет вид:
Рис. 3. Блок-схема к примеру 2.
Составление циклических алгоритмов
Рассмотрим пример на составление циклического алгоритма. Мы уже несколько раз обсуждали перевод чисел из десятичной системы в двоичную. Теперь пришло время чётко сформулировать этот алгоритм.
Напомним, что его принцип состоит в делении числа на 2 и записей остатков, получающихся при делении.
Пример 3. Составить алгоритм перевода чисел из десятичной системы в двоичную.
То есть, алгоритм будет выглядеть так:
Если число равно 0 или 1, то это и будет его двоичное представление.
Если число больше 1, то мы делим его на 2.
Полученный остаток от деления записываем в последний разряд двоичного представления числа.
Если полученное частное равно 1, то его дописываем в первый разряд двоичного представления числа и прекращаем вычисления.
Если же полученное частное больше 1, то мы заменяем исходное число на него и возвращаемся в пункт 2).
Блок-схема этого алгоритма выглядит следующим образом:
Рис. 4. Блок-схема к примеру 3.
Примечание: подумайте, можно ли как-то упростить приведенную блок-схему.
Пример 4. По заданной блок-схеме выполнить действия алгоритма для числа 23.
Рис. 5. Блок-схема к примеру 4.
76 – двузначное число
На следующем уроке мы обсудим игры и выигрышные стратегии.
Как убить Кощея?
Рис. 6. Кощей Бессмертный и Василиса Премудрая (Источник).
Предположим, вместо Ивана-царевича бороться с Кощеем был брошен Иван-дурак. Давайте поможем Василисе Премудрой составить такой алгоритм, чтобы даже Иван-дурак смог убить Кощея.
Конечно же, сначала необходимо разыскать остров Буян (на такие вещи, будем считать, Иван-дурак способен).
Поскольку сундук закопан под самым большим дубом, то сначала необходимо найти самый большой дуб на острове.
Затем нужно выкопать сам сундук.
Прежде чем доставать зайца, необходимо сломать крепкий замок.
Теперь уже можно достать зайца.
Из зайца нужно достать утку.
Из утки достать яйцо.
Разбить яйцо и достать иголку.
Это тоже линейный алгоритм, хотя и более длинный, чем алгоритм запуска программы Paint.
Его блок-схема выглядит так:
Рис. 7. Блок-схема.
На распутье…
И снова обратимся к сказочным персонажам в поисках примеров различных алгоритмов. Когда речь идёт об алгоритмах с ветвлениями, то, конечно, нельзя не вспомнить о богатыре, стоящем на распутье возле камня.
Рис. 8. Богатырь на распутье (Источник).
На камне написано:
Попробуем составить алгоритм действий, который составил автор надписи на камне для путников?
Если мы пойдём направо, то потеряем коня. Если же мы не пойдём направо, то у нас остаётся два варианта (мы считаем, что назад возвращаться путник не будет): пойти прямо и налево.
В случае, если мы пойдём налево, то потеряем себя, а коня спасём.
Если же мы пойдём прямо, то потеряем и себя, и коня.
Блок-схема этого алгоритма выглядит так:
Рис. 9. Блок-схема.
Вспомним сюжет сказки: дед тянет-потянет – вытянуть не может. Затем на помощь к деду по очереди подходят новые персонажи – и так до тех пор, пока не приходит мышка.
Попытаемся составить алгоритм действий всех персонажей сказки для того, чтобы они всё-таки смогли вытянуть Репку.
Изначально к Репке подошёл дед и попытался вытянуть.
Поскольку вытянуть Репку не получилось, то понадобилась помощь следующего персонажа.
И так происходит до тех пор, пока не появилась мышка (или, другими словами, до тех пор, пока Репку не вытащили).
Приведем простейшие примеры, соответствующие линейному алгоритму.
Пример 1. Вася хочет позвонить Пете по городскому телефону. Необходимо составить блок-схему, описывающую порядок действий Васи.
Решение. Чтобы позвонить по городскому телефону, нужно знать номер Пети. Значит, сначала надо найти номер телефона Пети, набрать его и поговорить с Петей. На этом цель Васи (поговорить с Петей по телефону) будет достигнута. Результат блок схемы представлен на рис. 2.1.
Пример 2. Ученику требуется купить учебник. Составить блок-схему, описывающую порядок действий ученика.
Решение. Сначала ученику нужно взять деньги, потом прийти в книжный магазин и заплатить за учебник. На этом цель (покупка учебника) будет достигнута. Результат блок схемы представлен на рис. 2.2.
Пример 3. Даны числа . Вычислить сумму и разность чисел и .
Решение. Сначала следует задать значения для чисел и , согласно условиям задачи. После этого их уже можно будет использовать в расчетах для получения суммы и разности по формулам: . Полученные значения суммы и разности нужно будет показать на экране, и мы используем блок вывода данных. Если не выводить данные на экран, то пользователь нашего алгоритма не узнает, какие получились значения суммы и разности. Результат блок схемы представлен на рис. 2.3.
увеличить изображение
Рис. 2.3. Блок-схема для примера 3: а) в каждом блоке по одному действию, б) действия объединены по смыслу операции
В блок-схеме на рис. 2.3а каждое действие расположено в отдельном блоке. В блок-схеме рис. 2.3б объединены между собой схожие по смыслу операции. В дальнейшем мы будем объединять некоторые действия в один блок. Это очень удобно и визуально упрощает чтение блок-схемы.
Читайте также: