Алгоритм линейный задачи – «Линейные алгоритмы Линейные алгоритмы. Алгоритмизация – процесс разработки алгоритма (плана действий) для решения задачи.». Скачать бесплатно и без регистрации.
Решение задач с разветвляющим алгоритмы — Мегаобучалка
Решение задач с линейными алгоритмами.
Линейным называется алгоритм, в котором выполняются все этапы решения задачи строго последовательно. Это означает, что он не содержит проверок условий и повторений.
Блок схема алгоритма выглядит, как последовательность действий.
Графический способ описания алгоритма (блок — схема) получил самое широкое распространение. Для графического описания алгоритмов используются схемы алгоритмов или блочные символы (блоки), которые соединяются между собой линиями связи.
Каждый этап вычислительного процесса представляется геометрическими фигурами (блоками). Они делятся на арифметические или вычислительные (прямоугольник), логические (ромб) и блоки ввода-вывода данных (параллелограмм).
Задание 1. Определить расстояние на плоскости между двумя точками с заданными координатами M1(x1,y1) и M2(x2,y2).
Дана блок схема, для решения задачи, составить программу на псевдокодах
Выполните самостоятельно
Задание 2.Составить линейную программу, в виде блок схемы и в псевдокодах, для решения следующей задачи :
Вариант 1.Дана длина ребра куба. Найти объем куба и площадь его боковой поверхности.
Вариант 2.Известна длина окружности. Найти площадь круга, ограниченного этой окружностью.
Вариант 3.Вычислить высоту треугольника, опущенную на сторону а, по известным значениям длин его сторон a, b, c.
Вариант 4.По данным сторонам прямоугольника вычислить его периметр, площадь и длину диагонали.
Решение задач с разветвляющим алгоритмы
На практике часто встречаются задачи, в которых в зависимости от первоначальных условий или промежуточных результатов необходимо выполнить вычисления по одним или другим формулам.
Такие задачи можно описать с помощью алгоритмов разветвляющейся структуры. В таких алгоритмах выбор направления продолжения вычисления осуществляется по итогам проверки заданного условия. Ветвящиеся процессы описываются оператором IF (условие ЕСЛИ).
Для решения многих задач характерно многократное повторение отдельных участков вычислений. Для решения таких задач применяются алгоритмы циклической структуры (циклические алгоритмы).
Задание 3.Даны целые числа X, Y. Определить, принадлежит ли точка с координатами X, Y кругу радиуса R.
Вывести на экран сообщение «Принадлежит» или «Не принадлежит».
Дана блок схема . Составьте алгоритм в псевдокодах
. 
Выполните самостоятельно
Задание 4.Составьте алгоритм для задачи в виде псевдокодов и блок схемы.
Вариант 1. Составить программу, реализующую эпизод сказки: машина спрашивает, куда пойдет герой, и в зависимости от ответа (налево – (-1), прямо – 0, направо – 1), печатает, что произойдет с героем.
Вариант 2.Морской бой. Машина задумывает два числа от 0 до 9. Игрок пытается их угадать, вводя свои два числа. Если они совпали (в любом сочетании), то игрок выиграл.
Вариант 3.В Атлантическом океане терпит бедствие пассажирский теплоход «Посудина».
Все пассажиры будут спасены, если на помощь успеют два судна. Судно продержится на плаву 2 часа. Скорость судов-спасателей 40 узлов/ч. Составить программу, определяющую спасутся ли пассажиры.
Известны расстояния судов-спасателей до тонущего судна, равны 30 км и 45 км
Узел- морская миля в час- мера скорости. А вот в миле- 1852 метра.час.
Вариант 4.
megaobuchalka.ru
Линейные алгоритмы. Примеры решения задач школьного курса с помощью линейных алгоритмов
Материал из Letopisi.Ru — «Время вернуться домой»
Линейные алгоритмы. Примеры решения задач школьного курса с помощью линейных алгоритмов
Алгоритмизация – процесс разработки алгоритма (плана действий) для решения задачи. Алгоритм называется линейным, если все его действия выполняются последовательно друг за другом от начала и до конца. Блок-схемой называется наглядное графическое изображение алгоритма, когда отдельные его действия (этапы) изображаются при помощи различных геометрических фигур (блоков), а связи между этапами указываются при помощи стрелок, соединяющих эти фигуры.
1) Даны длины сторон треугольника A, B, C. Найти площадь треугольника S. Составьте блок-схему алгоритма решения поставленной задачи.
2) Даны координаты вершин треугольника АВС. Найти его площадь. Составьте блок-схему алгоритма решения поставленной задачи.
3) В квадратной комнате шириной A и высотой B есть окно и дверь с размерами C на D и M на N соответственно. Вычислите площадь стен для оклеивания их обоями. Составьте блок-схему алгоритма решения поставленной задачи.
4) Дана величина A, выражающая объем информации в байтах. Перевести А в более крупные единицы измерения информации. Составьте блок-схему алгоритма решения поставленной задачи.
5) Вычислить путь, пройденный лодкой, если ее скорость в стоячей воде v км/ч, скорость течения реки v1 км/ч, время движения по озеру t1 ч, а против течения реки – t2 ч. Составьте блок-схему алгоритма решения поставленной задачи.
6) Вычислите значение функции Y при X=2, используя блок-схему алгоритма. Y = 2 РЕШЕНИЕ: 1. X = 2 2. Z = 8 * 2 = 16 3. Z = = 4 4. Z = 4 – 1 = 3 5. Y = 3 * 2 = 6 6. Y = 6 / 3 = 2
7) По данной блок-схеме вычисления значения некоторой функции, восстановите условие задачи; напишите формулу вычисления значения функции.
8) По данной блок-схеме вычисления значения некоторой функции, восстановите условие задачи; напишите формулу вычисления значения функции.
Линейные алгоритмы в Turbo Pascal. Примеры задач
Линейный алгоритм
Линейный алгоритм(следование) состоит из последовательности операций, выполняющихся только один раз в порядке их следования.
Рис. 1 Линейная структура алгоритма
Разветвляющийся алгоритм
Разветвляющийся алгоритм(ветвление) обеспечивает выбор между двумя альтернативами. Выполняется проверка, а затем выбирается один из путей.
Подобная структура называется также «ЕСЛИ – ТО – ИНАЧЕ», или «развилка». Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.
Может оказаться, что для одного из результатов проверки ничего предпринимать не надо. В этом случае можно применять только один обрабатывающий блок.
|
|
Рис. 2 Разветвляющаяся структура алгоритма |
Циклический алгоритм
Циклический алгоритм(Цикл) содержит некоторую последовательность операций, выполняемую многократно. Основной блок цикла, тело цикла, производит требуемые вычисления. Остальные блоки организуют циклический процесс: устанавливают начальные и новые значения данных, проверяют условия окончания или продолжения циклического процесса.
Различают два типа структур цикла: цикл с параметромилис повторением ицикл с условием. Циклический алгоритм позволяет компактно описать большое число одинаковых вычислений над разными данными для получения необходимого результата.
Циклы с параметромиспользуют тогда, когда количество повторов тела цикла заранее известно. Схематично такой цикл и зображен на рис. 6.
Циклы с условиемиспользуются тогда, когда число повторений заранее неизвестно, но задано условие окончания цикла. Причем, если условие окончания цикла проверяется перед выполнением тела цикла, то такие циклические структуры называют цикламис предусловием(«Выполнять пока» рис. 4), а если проверка условия происходит после выполнения тела цикла – цикламис постусловием(«Выполнять до тех пор пока не» рис.5).
Рис. 4 | Рис. 5 | Рис. 6 |
Объекты алгоритма
Решение любой задачи предполагает наличие реальных объектов – объектов задачи.
Например. При решении задачи о начислении зарплаты сотрудникам предприятия объектом задачи могут быть: табельный номер сотрудника, его фамилия, имя, отчество, оклад, отработанное время и т.д. При решении системы уравнений объектами задачи являются – число уравнений, коэффициенты уравнений, правые части.
Каждый объект задачи имеет свои характеристики (атрибуты). Фамилии и наименования – это строки символов, а коэффициенты уравнений, количество выпускаемой продукции – это числовые константы, представленные арифметическими выражениями или числами.
Если выполнение алгоритма возложено на ЭВМ, необходима строгая формализация задачи. Она предполагает замену объектов задачи – объектами алгоритма, которые должны наследовать их атрибуты. При разработке алгоритма могут появиться вспомогательные объекты не соответствующие никаким объектам задачи.
В практике программирования число базовых объектов невелико. Это константы, переменные массивы, файлы и некоторые другие.
Понятие константы. Например, в задаче нужно вычислить длину окружностиL= π *D, здесьLиD– объекты задачи, а π – величина постоянная в любой задаче, т.е. это константа.
Константа может быть не только числом. Например, в некотором списке фамилий определяется наличие фамилии Иванов. В алгоритме фамилия – это объект, а Иванов – символьная константа.
Константа – это объект алгоритма. Каждая константа как объект алгоритма имеет фиксированный тип (арифметический, символьный или другой) и имеет фиксированное, неизменяемое в данном алгоритме значение, соответствующее ее типу. Значение константы обычно определено в условии задачи и известно до начала разработки алгоритма.
Понятие переменной. Переменная – это объект алгоритма, который имеет определенный фиксированный тип (арифметический, символьный или другой) и который в каждый момент исполнения алгоритма имеет единственное значение соответствующего типа. К моменту использования переменной в алгоритме ее значение должно быть определено. В ходе выполнения алгоритма значение переменной может изменяться.
Например, требуется вычислить и напечатать значение функции при изменении аргумента от заданного начального значения до заданного конечного значения с заданным шагом. Начальное значение, конечное значение, шаг – объекты задачи, которые в условии задачи не определены. Эти значения станут известны по ходу выполнения алгоритма: введены пользователем или получены в результате вычислений. Если не предусмотреть механизм их определения, исполнение алгоритма будет невозможно.
Имя объекта алгоритма. Каждый объект в алгоритме фигурирует под своим именем. Имя это неизменно, фиксировано и уникально. Имена для объектов устанавливает автор алгоритма. Рекомендуется выбирать мнемонические имена, которые отражают суть объекта.
Понятие массива. Массив – объект алгоритма. Во многих случаях разрозненные переменные удобно объединить в совокупность – массив, именуя все коэффициенты общим именем (именем массива) и индексами (номерами в массиве).
Индекс элемента массива позволяет обратиться к элементу массива «напрямую». По индексу массив строго упорядочен.
Массивом называется конечная упорядоченная совокупность данных одного типа, доступ к каждому осуществляется по его индексу.
В задачах используются как одномерные, так и многомерные массивы. Для указания положения элемента в двумерном массиве используют два индекса – сначала номер строки, затем номер столбца. Массивы могут быть как числовыми, так и символьными.
В любом алгоритме всегда присутствует раздел инструкций (выполнения действий), который имеет одну точку входа (НАЧАЛО) и одну точку выхода (КОНЕЦ). Закодированная форма инструкции, несущая определенный смысл называется оператором.
Рис. 7 – Пример записи алгоритм сортировки выбором с помощью блок-схемы
studfiles.net
Задачи на линейные алгоритмы
Вычислить значения выражений по формулам №№ l-26 (все переменные имеют действительный тип):
№ 27
Вычислить периметр и площадь прямоугольного треугольника по заданным длинам двух катетов а и b.
№ 28
Заданы координаты трех вершин треугольника (х1, y1), (х2, у2), (х3, у3). Найти его периметр и площадь.
№ 29
Вычислить длину окружности и площадь круга одного и того же заданного радиуса R.
№ 30
Найти произведение цифр заданного четырехзначного числа.
№ 31
Даны два числа. Найти среднее арифметическое кубов этих чисел и среднее геометрическое модулей этих чисел.
№ 32
Вычислить расстояние между двумя точками с данными координатами (х1, у1) и (х2, у2).
№ 33
Даны два действительных числа x и у. Вычислить их сумму, разность, произведение и частное.
№ 34
Дана длина ребра куба. Найти площадь грани, площадь полной поверхности и объем этого куба.
№ 35
Дана сторона равностороннего треугольника. Найти площадь этого треугольника, его высоты, радиусы вписанной и описанной окружностей.
№ 36
Известна длина окружности. Найти площадь круга, ограниченного этой окружностью.
№ 37
Найти площадь кольца, внутренний радиус которого равен r, а внешний — заданному числу R (R > r).
№ 38
Треугольник задан величинами своих углов и радиусом описанной окружности. Найти стороны треугольника.
№ 39
Найти площадь равнобедренной трапеции с основаниями а и b и углом а при большем основании а.
№ 40
Вычислить корни квадратного уравнения ах2 + bx + с = 0, заданного коэффициентами a, b и с (предполагается, что а 0 и что дискриминант уравнения неотрицателен).
№ 41
Дано действительное число x. Не пользуясь никакими другими арифметическими операциями, кроме умножения, сложения и вычитания, вычислить за минимальное число операций 2x4 — Зх3 + 4x2 – 5х + 6.
№ 42
Дано x. Получить значения -2x + Зх2 – 4х3 и 1 + 2x + Зх2 + 4х3. Позаботиться об экономии операций.
№ 43
Найти площадь треугольника, две стороны которого равны а и b, а угол между этими сторонами равен g.
№ 44
Дано а. Не используя никаких функций и никаких операций, кроме умножения, получить а8 за три операции; а10 и а16 за четыре операции.
№ 45
Найти сумму членов арифметической прогрессии, если известны ее первый член, знаменатель и число членов прогрессии.
№ 46
Найти все углы треугольника со сторонами a, b, с. Предусмотреть в программе перевод радианной меры угла в градусы, минуты и секунды.
№ 47
Три сопротивления R1, R2, R3 соединены параллельно. Найдите сопротивление соединения.
№ 48
Составить программу для вычисления пути, пройденного лодкой, если ее скорость в стоячей воде v км/ч, скорость течения реки и км/ч, время движения по озеру t1 ч, а против течения реки — t2 ч.
№ 49
Текущее показание электронных часов: m часов (0 < m < 23), n мин (0 < n < 59), k сек (0 < k < 59). Какое время будут показывать часы через p ч q мин r с?
№ 50
Полторы кошки за полтора часа съедают полторы мышки. Сколько мышек съедят X кошек за Y часов?
№ 51
Составить программу вычисления объема цилиндра и конуса, которые имеют одинаковую высоту H и одинаковый радиус основания R.
№ 52
Ввести любой символ и определить его порядковый номер, а также указать предыдущий и последующий символы.
№ 53
Дана величина А, выражающая объем информации в байтах. Перевести А в более крупные единицы измерения информации.
studfiles.net
Линейные алгоритмыАлгоритмизация – процесс разработки алгоритма (плана действий) для решения задачи
Линейные алгоритмы
Блок-схемой называется наглядное графическое изображение алгоритма, когда отдельные его действия (этапы) изображаются при помощи различных геометрических фигур (блоков), а связи между этапами указываются при помощи стрелок, соединяющих эти фигуры.
Примеры решения задачДаны длины сторон треугольника A, B, C. Найти площадь треугольника S. Составьте блок-схему алгоритма решения поставленной задачи.
Даны координаты вершин треугольника АВС. Найти его площадь. Составьте блок-схему алгоритма решения поставленной задачи.В квадратной комнате шириной A и высотой B есть окно и дверь с размерами C на D и M на N соответственно. Вычислите площадь стен для оклеивания их обоями. Составьте блок-схему алгоритма решения поставленной задачи.
Дана величина A, выражающая объем информации в байтах. Перевести А в более крупные единицы измерения информации. Составьте блок-схему алгоритма решения поставленной задачи.
Вычислить путь, пройденный лодкой, если ее скорость в стоячей воде v км/ч, скорость течения реки v1 км/ч, время движения по озеру t1 ч, а против течения реки – t2 ч. Составьте блок-схему алгоритма решения поставленной задачи.
Вычислите значение функции Y при X=2, используя блок-схему алгоритма.
Вычислите значение функции Y при X=0; -1; 3 используя блок-схему алгоритма.
По данной блок-схеме вычисления значения некоторой функции, восстановите условие задачи; напишите формулу вычисления значения функции.
По данной блок-схеме вычисления значения некоторой функции, восстановите условие задачи; напишите формулу вычисления значения функции.
|
rpp.nashaucheba.ru
Основы алгоритмизации. Линейный алгоритм. Разветвляющийся алгоритм
Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 8 классы | Планирование уроков на учебный год | Основы алгоритмизации
Алгоритмы
Изучив эту тему, вы узнаете:
— назначение алгоритма и его основные свойства;
— формы представления алгоритма;
— типовые алгоритмические конструкции и виды алгоритмов;
— разновидности циклических алгоритмов и их особенности;
— назначение вспомогательных алгоритмов;
— основные стадии создания алгоритма.
12.4. Линейный алгоритм
В основе линейных алгоритмов лежит структура «последовательность». Покажем это на примерах.
Пример 12.6
В своей книге «Арифметика» Леонтий Филиппович Магницкий привел следующий способ отгадывания задуманного двузначного числа: «Если кто задумает двузначное число, то ты скажи ему, чтобы он увеличил число десятков задуманного числа в 2 раза, к произведению прибавил бы 5 единиц, полученную сумму увеличил в 5 раз и к новому произведению прибавил сумму 10 единиц и числа единиц задуманного числа, а результат произведенных действий сообщил бы тебе. Если ты из указанного тебе результата вычтешь 35, то узнаешь задуманное число».
Представим предлагаемые JI. Ф. Магницким действия в виде алгоритма в словесной форме. В предлагаемом процессе должны участвовать два человека: загадывающий число и отгадывающий его. Поэтому алгоритмов тоже будет два.
Алгоритм для загадывающего число
1. Задумайте двузначное число.
2. Умножьте число десятков на 2.
3. К полученному произведению прибавьте 5.
4. Полученную сумму умножьте на 5.
5. К полученному произведению прибавьте 10.
6. К полученной сумме добавьте количество единиц задуманного числа.
7. Сообщите полученное число отгадывающему. Конец алгоритма
Алгоритм для отгадывающего число
1. Отнимите от сообщенного числа 35.
2. Сообщите результат. Конец алгоритма
В этих двух алгоритмах действия выполняются в том порядке, в котором записаны.
Пример 12.7
Требуется найти вес любого продукта, который должен быть закуплен для туристического похода.
Для исходных данных алгоритма будем использовать следующие обозначения:
п — норма расхода продукта на человека в сутки;
k — количество участников похода;
d — количество дней.
Результат работы алгоритма (рассчитанный вес продукта) будет занесен в переменную m (рисунок 12.6).
Рис. 12.6. Алгоритм решения задачи «Вес продукта» в двух формах представления: в виде блок-схемы и в виде программы на школьном алгоритмическом языке
Приведенные ранее в п. 12.3 алгоритмы разведения костра, приготовления каши, измерения расстояния до предмета являются линейными или последовательными.
Линейный алгоритм — алгоритм, в котором действия выполняются последовательно одно за другим.
12.5. Разветвляющийся алгоритм
Вспомним сюжет из русской сказки. Царевич останавливается у развилки дороги и видит камень с надписью: «Пойдешь направо — коня потеряешь, налево — сам пропадешь…»
Подобная ситуация, заставляющая нас принимать решения или делать выводы в зависимости от некоторого условия, постоянно встречается в повседневной жизни. Это отражается и в народных приметах, поговорках и пословицах.
— Если закат красный, то жди ветреной погоды.
— Нет дыма без огня (если есть дым, то ищи источник возгорания).
— Кончил дело — гуляй смело (если работа закончена, то можно отдыхать).
— Если вы нашли в лесу муравейник, то его местоположение относительно дерева указывает на юг.
Здесь условиями, позволяющими делать выводы или влияющими на принятие решений, являются слова, расположенные между «если» и «то»:
— в первом примере — красный закат;
— во втором примере — дым;
— в третьем примере — окончание работы;
— в четвертом примере — муравейник.
Условие может принимать значение «истина», когда оно выполнено, или «ложь», когда оно не выполнено. От значения условия зависит наше дальнейшее поведение. Например, в предложении «Если закат красный, то ‘жди ветреной погоды» условие «закат красный» может быть или истинным, или ложным. Если условие истинно, то следует ждать ветреной погоды, иначе (если условие ложно) ничего о погоде сказать нельзя.
В одних случаях анализ ситуации и сам выбор не вызывают затруднений, а в других сделать это очень трудно. Приходится продумывать каждый возможный вариант и последствия принимаемого решения. Шахматист, перед тем как сделать очередной ход, анализирует позицию на несколько ходов вперед. Компьютерные игры также построены на анализе ситуации и выборе действий.
Рассмотрим примеры алгоритмов, содержащих анализ условия.
Пример 12.8
Существует неписанное правило — собранные грибы должен проверить человек, разбирающийся в грибах.
Алгоритм проверки можно записать так:
Если гриб съедобный, то положить его в котелок для варки, иначе — выбросить в костер.
В приведенной записи в зависимости от значения условия выполняется либо действие, указанное после слова «то» — положить гриб в котелок, либо другое действие, указанное после слова «иначе» — выбросить в костер. На рисунке 12.7 представлен фрагмент блок-схемы алгоритма сортировки грибов для варки супа по признаку съедобный-несъедобный.
Рис. 12.7. Алгоритм проверки грибов, в котором использована полная форма ветвления
Пример 12.9
Вы идете в гости и вам необходимо перевязать коробку с подарком красивой лентой, длина которой d. Но хватит ли этой ленты?
Представим решение этой задачи на школьном алгоритмическом языке. Исходными данными для решения этой задачи являются размеры коробки и длина ленточки. Примем для них следующие обозначения: а, b, с — соответственно длина, ширина и высота коробки; d — длина ленточки.
алг Подарок
нач вещ a,b,c,d
вывод «Введите размеры коробки» ввод а,b,с
вывод «Введите размеры ленты» ввод d
если (a+b+2*c)*2 <= d то
вывод «Ленты хватит» иначе
вывод «Ленты не хватит» все кон
В примерах 12.8 и 12.9 при описании алгоритмов в виде блок- схемы и программы на школьном алгоритмическом языке использовалась конструкция «ветвление».
Различают полную и неполную форму ветвления.
При полной форме ветвления действия выполняются в обоих случаях: и при истинности, и при ложности условия. Вспомните кота из сказки А. С. Пушкина: «идет направо — песнь заводит, налево — сказку говорит ». В рассмотренных выше примерах использовалась полная форма ветвления, которой соответствует выражение
если <условие>, то <действие 1>9 иначе <действие 2>.
Неполной форме ветвления соответствует выражение
если <условие>9 то <действия>
Неполная форма предполагает отсутствие действий в случае невыполнения условия. Например: среднесуточная температура воздуха ниже +8 °С, приступить к протапливанию помещений.
На рисунке 12.8 представлен фрагмент блок-схемы алгоритма, описывающего поведение участников туристского похода, покидающих стоянку: если костер горит, то необходимо залить его водой.
Рис. 12.8. Алгоритм тушения костра, в котором используется неполная форма ветвления
Пример 12.10
Известно, что в аэропорту существуют ограничения на бесплатный провоз багажа. Если вес багажа превышает норму, то за каждый килограмм сверх нормы необходимо доплачивать. Исходными данными для решения задачи являются: v — вес багажа; vn — разрешенная норма провоза багажа; st — стоимость килограмма сверх нормы. Результат будем записывать в переменную s — сумму выплат сверх нормы.
Алгоритм «Доплата за багаж» представим на школьном алгоритмическом языке.
алг Доплата за багаж
нач вещ v, vn, st, s
вывод «введите вес багажа, норму, стоимость кг»
ввод v, vn, st
если v>vn
то s:=(v-vn)*st
вывод «Доплата составляет», s
все
кон
Во всех приведенных алгоритмах анализ условия приводит к выполнению тех или иных действий. Если представить алгоритм в виде дороги, ведущей к достижению поставленной цели, то условный блок «если…, то…, иначе…» является развилкой на этой дороге.
На приведенных выше блок- схемах хорошо видны подобные развилки. Они создаются при помощи структуры ветвления, имеющей полную и неполную форму. Подобные алгоритмы называются разветвляющимися.
Разветвляющийся алгоритм — алгоритм, содержащий структуру ветвления.
12.6. Циклический алгоритм
Общее представление
Многие процессы в окружающем мире основаны на многократном повторении одной и той же последовательности действий.
Каждый год наступают весна, лето, осень и зима. Жизнь растений в течение года проходит одни и те же циклы. Подсчитывая число полных поворотов минутной или часовой стрелки, человек измеряет время.
Алгоритмы, которые содержат описания повторяющихся действий, принято называть циклическими.
Циклические алгоритмы могут содержать разные типы циклов. Классификация типов циклов представлена на рисунке 12.9 и подробно рассмотрена далее.
Циклический алгоритм — алгоритм, содержащий типовую конструкцию «цикл».
Тело цикла — описание действий, повторяющихся в цикле.
Рис. 12.9. Типы циклов
Цикл с известным числом повторений
Цикл с известным числом повторений часто называют «циклом ДЛЯ». Рассмотрим примеры циклических алгоритмов с известным числом повторений.
Пример 12.11
В различных журналах приводятся упражнения, которые необходимо повторять заданное число раз. Рассмотрим пример упражнения для глаз. Особенно это полезно тем, кто долго сидит за компьютером. Подобные алгоритмы чаще всего представляются в словесной или графической форме.
Алгоритм «Упражнение для глаз»
1. Возьмите карандаш.
2. Установите его в исходное положение у кончика носа.
3. Повторите 10 раз, следя за движением карандаша:
a. Переместите карандаш на расстояние вытянутой руки;
b. Верните карандаш в исходное положение.
4. Положите карандаш. Конец алгоритма
В этом примере заранее известно число повторений. Цикл закончится, когда действия пунктов а и b повторятся 10 раз. Действия а и Ь, повторяющиеся в цикле, определяют тело цикла.
Пример 12.12
Требуется подвести итоги контрольной работы.
Исходными данными для этой задачи являются:
b — балл теущего ученика;
n — количество учеников.
Расчетные данные:
s — сумма баллов;
sr — средний балл.
Решение этой задачи представим на школьном алгоритмическом языке в таблице 12.3.
Таблица 12.3. Алгоритм «Итоги» на школьном алгоритмическом языке
Здесь нц, кц — служебные слова, обозначающие соответстенно начало и конец цикла.
В этом примере повторяются следующие операции:
♦ ввод оценки каждого ученика;
♦ добавление ее к общей сумме.
Эти операции составляют тело цикла. Число повторений в цикле равно количеству учащихся в классе.
Цикл с постусловием
Не всякую циклическую задачу можно решить с помощью цикла с известным числом повторений. В некоторых задачах число повторений заранее неизвестно. Для организации циклической последовательности действий и выхода из нее к другому фрагменту алгоритма используется условие, которое ставится в конце тела цикла.
Цикл с неизвестным числом повторений, в котором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ».
Рассмотрим алгоритмы решения циклических задач с неизвестным числом повторений.
Пример 12.13
После соревнований по бегу рекомендуется измерить пульс. Измерение пульса можно описать следующим алгоритмом.
Алгоритм «Пульс»
1. Удобно положите левую руку ладонью вверх.
2. Два пальца правой руки положите на запястье левой руки.
3. Заметьте положение секундной стрелки.
4. Сосчитайте очередной удар.
5. Посмотрите на часы.
6. Если секундная стрелка прошла полный круг, то закончите действия, иначе перейдите к п. 4.
Конец алгоритма
В этом примере действия закончатся, когда секундная стрелка пройдет полный круг, то есть условие «Стрелка прошла полный круг» будет выполнено, в противном случае действия будут продолжаться. На рисунке 12.10 приведена блок-схема этого алгоритма. На блок-схеме видно, что проверка условия стоит в конце цикла.
Рис. 12.10. Блок-схема алгоритма «Пульс»
Пример 12.14
Требуется рассчитать время работы батарейки в часах с кукушкой, если известно, что заряда хватает примерно на 1000 звуковых сигналов «ку-ку». Однократный звуковой сигнал звучит, когда минутная стрелка показывает 30 минут. Начало каждого часа сопровождается повторением сигнала столько раз, сколько показывает часовая стрелка (от 1 до 12).
Расчетными данными для этой задачи являются:
t — обозначение текущего часа;
к — количество звуковых сигналов.
Алгоритм «Кукушка» представим на школьном алгоритмическом языке в таблице 12.4.
В этом алгоритме повторяются следующие действия:
♦ определение значения текущего часа;
♦ определение количества звуковых сигналов.
Эти действия составляют тело-цикла.
Цикл заканчивается, если количество поданных звуковых сигналов превысило 1000, что является признаком выработки ресурса батарейки.
Таблица 12.4. Алгоритм «Кукушка» на школьном алгоритмическом языке
Из рассмотренных примеров 12.13 и 12.14 видно, что цикл с постусловием имеет следующие особенности:
♦ проверка условия осуществляется в конце цикла, поэтому тело цикла выполняется хотя бы один раз;
♦ цикл заканчивается по выполнению условия.
Цикл с предусловием
Рассмотрим другой тип цикла, в котором проверка условия осуществляется в начале цикла. Для организации циклической последовательности действий и выхода из нее к другому фрагменту алгоритма используется условие, которое ставится в начале тела цикла. Цикл с неизвестным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА».
Пример 12.15
На даче требуется наполнить бочку водой. Действия по наполнению бочки можно описать следующим алгоритмом.
Алгоритм «Бочка»
1. Подойдите к бочке.
2. Если бочка неполная (есть место для воды), то перейдите к п. 3, иначе конец алгоритма.
3. Наберите ведро воды.
4. Вылейте ведро в бочку.
5. Перейдите к п. 2. Конец алгоритма
На блок-схеме (рис. 12.11) видно, что условие проверки стоит в самом начале цикла.
Рис. 12.11. Блок-схема алгоритма «Бочка»
Такой цикл получил название цикла с предусловием.
Возможна ситуация, что цикл закончится так и не начавшись, например, если бочка наполнилась из-за прошедшего накануне дождя. В этом цикле при выполнении условия «есть место для воды» действия продолжаются, при невыполнении — заканчиваются.
Пример 12.16
Требуется проверить число на симметричность (примеры симметричных чисел: 12321, 8668).
Исходными данными для этой задачи является введенное число n.
Для промежуточных вычислений будут использоваться переменные:
s — для записи цифр числа п в обратном порядке;
nl — для дублирования введенного числа п.
В алгоритме используются функции:
mod — вычисление остатка от деления на 10;
div — определение целой части числа.
Решение этой задачи представим в виде программы на школьном алгоритмическом языке в таблице 12.5.
Таблица 12.5. Алгоритм «Симметричное число» на школьном алгоритмическом языке
В этом алгоритме в цикле получается перевернутое число, которое затем сравнивается с введенным. Если они равны, то введенное число симметрично. Цикл выполняется до тех пор, пока nl при целочисленном делении на 10 не превратится в 0. Если введенное число равно 0, то цикл не выполнится ни разу, но будет выдан ответ «Число симметричное».
Из рассмотренных примеров 12.15 и 12.16 видно, что цикл с предусловием имеет следующие особенности.
— проверка условия осуществляется в начале цикла, поэтому тело цикла может не выполниться ни одного раза;
— цикл заканчивается при невыполнении условия;
— цикл является универсальным, так как с помощью этого цикла можно решить любую циклическую задачу.
Практикум
Линейные алгоритмы
Выполнив задания этой темы, вы научитесь:
— представлять линейный алгоритм в различных формах;
— использовать линейные алгоритмы при решении задач;
— применять переменные для хранения данных; осуществлять ввод-вывод информации.
Как вам уже известно, существуют различные типы алгоритмов и разные формы их представления.
Для представления линейного алгоритма в виде блок-схемы используются блоки ввода-вывода, выполнения действий, вызова вспомогательного алгоритма.
Для представления линейного алгоритма в виде программы используются операторы ввода-вывода, оператор присваивания, оператор вызова вспомогательного алгоритма.
Задание 8.1
Коллекция Эрмитажа содержит более 2 800 ООО единиц хранения. Если у каждого музейного экспоната задержаться всего на 5 минут и проводить в Эрмитаже по 8 часов каждый день, то может не хватить жизни, чтобы ознакомиться со всей коллекцией. Требуется вычислить суммарное время просмотра всей коллекции в минутах, часах, днях, годах, «жизнях», считая, что средняя продолжительность жизни в Роcсии составляет 70 лет.
Словесный алгоритм Начало алгоритма • в минутах; |
Алгоритм в виде программы
В табл. 8.1 приведена программа к заданию на школьном алгоритмическом языке Кумир (с пояснениями). В табл. 8.2 приведены тексты программ на языках программирования Паскаль и Visual Basic.
Таблица 8.1. Программа на Кумире с пояснениями (к заданию 8.1)
Таблица 8.2. Примеры программ на Паскале и Visual Basic (к заданию 8.1)
Задание 8.2
Требуется рассчитать параметры прямоугольного треугольника с углом 30° по заданному катету, лежащему против угла 30°.
Словесный алгоритм Начало алгоритма |
Алгоритм в виде программы
В табл. 8.3 приведена программа к заданию на школьном алгоритмическом языке Кумир. В табл. 8.4 приведены тексты программ на языках программирования Паскаль и Visual Basic.
Таблица 8.3. Программа на Кумире с пояснениями (к заданию 8.2)
Таблица 8.4. Примеры программ на Паскале и Visual Basic (к заданию 8.2)
Задание 8.3
На памятнике Пифагору высечен чертеж вписанного в цилиндр шара, так как Пифагор нашел соотношение между их объемами. Современный почитатель гения Пифагора решил создать объемный памятник в честь этого открытия. Городские власти определили статус памятника — скульптура малой формы, и выделили для него небольшую площадь. Требуется рассчитать объем цилиндра и вписанного в него шара по заданной площади основания памятника (цилиндра) и убедиться в правильности выведенного Пифагором соотношения.
Словесный алгоритм Начало алгоритма | Рис. 8.3. К заданию 8.3 |
Алгоритм в виде программы
В табл. 8.5 приведена программа к заданию на школьном алгоритмическом языке Кумир. В табл. 8.6 приведены тексты программ на языках программирования Паскаль и Visual Basic.
Таблица 8.5. Программа на Кумире с пояснениями (к заданию 8.3)
Таблица 8.6. Примеры программ на Паскале и Visual Basic (к заданию 8.3)
Контрольные вопросы и задания
К заданию 8.1
1. Разработчик алгоритма к заданию 8.1 (рис. 8.1), введя переменную п, хотел придать алгоритму свойство массовости. Какие еще переменные следует ввести, чтобы алгоритм соответствовал этому свойству в полной мере?
2. В приведенном последовательном алгоритме порядок вывода расчетных данных можно изменять. Какие команды в приведенных программах нельзя переставлять? Почему?
3. На блок-схеме представлены два блока вывода информации на экран. В чем их различие?
4. Запишите в тетради имена переменных, которые были использованы в процессе решения задания. Напишите под ними значения переменных, полученные в результате тестирования.
5. Что происходит в результате выполнения блока 3 представленного алгоритма?
6. Добавьте в программу блок вычислений, определяющий, сколько экспонатов в день удастся посмотреть посетителю.
К заданию 8.2
1. Замените в программе формулу расчета катета b = a-j3 и убедитесь, что результат от этого не изменится.
2. Используя готовый каркас блок-схемы, заполните его таким образом, чтобы по новой блок-схеме вычислялись высота и площадь равнобедренной трапеции с углом при основании 45° (рис. 8.5). Задание выполните в тетради.
3. Напишите текст программы на Кумире или другом языке для полученной блок-схемы.
4. Что надо изменить в условии задачи, чтобы расширить границы применимости алгоритма?
5. Из пояснительного рисунка видно, что а > b. Что произойдет, если при вводе а и b это соотношение будет нарушено?
К заданию 8.3
1. При расчетах радиуса и объемов используется константа 3,1415926. Что нужно изменить в программе, чтобы не набирать ее каждый раз заново?
2. В примере программы на языке Кумир тип используемых переменных описан следующим образом: вещ r, s, vshara, veil, k. Что означает эта запись? Почему для переменных выбран такой тип?
3. В формуле вычисления объема шара используется формула V — r3. В примерах программ на разных языках она записана по-разному. Есть ли здесь ошибки? Объясните, что означают разные записи? Придумайте такой вид записи, который будет верен для всех языков.
Рис. 8.5. Чертеж для вычисления высоты и площади равнобедренной трапеции
4. Можно ли изменить последовательность операторов расчета?
Разветвляющиеся алгоритмы
Выполнив задания этой темы, вы научитесь:
— использовать различные структуры ветвления;
— использовать простые и сложные условия;
— использовать вложенные ветвления;
— использовать структуру множественного выбора при наличии более чем двух ситуаций;
— тестировать алгоритм в пошаговом режиме для проверки всех его ветвей.
Для представления разветвляющегося алгоритма в виде блок-схемы используются блоки принятия решения. Для представления разветвляющегося алгоритма в виде программы используются условные операторы и операторы выбора (если вариантов выбора больше двух).
Задание 8.4
Требуется разработать алгоритм проверки принадлежности введенного числа данной арифметической прогрессии. Прогрессия задается двумя последовательными членами.
Словесный алгоритм
Начало алгоритма
1. Введите два последовательных члена арифметической
прогрессии.
2. Введите произвольное целое число.
3. Найдите разность (d) арифметической прогрессии.
4. Найдите разность между введенным числом и
членом арифметической прогрессии.
5. Найдите остаток от деления нацело найденной
разности на d.
6. Организуйте проверку остатка:
— если остаток от деления равен 0, выведите сообщение:
«Число принадлежит рассматриваемой арифметической
прогрессии»;
— иначе выведите сообщение:
«Число не принадлежит рассматриваемой
арифметической прогрессии».
Конец алгоритма
Алгоритм в виде блок-схемы
Алгоритм в виде программы
В табл. 8.7 приведена программа к заданию на алгоритмическом языке Кумир. В табл. 8.8 приведены тексты программ на языках программирования Паскаль и Visual Basic.
Таблица 8.7. Программа на Кумире с пояснениями (к заданию 8.4)
Таблица 8.8. Примеры программ на Паскале и Visual Basic (к заданию 8.4)
Задание 8.5
Из «Арифметики» таджикского ученого Авиценны (X-XI вв.) известно следующее свойство целых чисел: если число, будучи разделено на 9, дает в остатке 1 или 8, то квадрат этого числа, деленный на 9, даст 1. Требуется подтвердить верность свойства или опровергнуть его.
Словесный алгоритм
Начало алгоритма
1. Введите целое число.
2. Найдите остаток от деления этого числа на 8.
3. Организуйте проверку остатка на равенство 1 или 8:
• если остаток от деления равен 1 или 8, то:
а) найдите квадрат введенного числа;
б) найдите остаток от деления квадрата числа на 9;
в) организуйте проверку остатка от деления:
если остаток равен 1, то выведите сообщение «Свойство верно», иначе выведите сообщение «Свойство не верно»;
• иначе (остаток от деления не равен 1 и остаток от деления
не равен 8) выведите сообщение «Остаток от деления < > 1
и Остаток от деления < > 8».
Конец алгоритма
Алгоритм в виде блок-схемы
Рис. 8.7. Блок-схема алгоритма (к заданию 8.5)
Алгоритм в виде программы
В табл. 8.9 приведена программа к заданию на алгоритмическом языке Кумир. В табл. 8.10 приведены тексты программ на языках Паскаль и Visual Basic.
Таблица 8.9. Программа на Кумире с пояснениями (к заданию 8.5)
Таблица 8.10. Примеры программ на Паскале и Visual Basic (к заданию 8.5)
Задание 8.6
Требуется определить тип треугольника по двум введенным углам. При выполнении задания необходимо учесть ситуации некорректного ввода данных, например: 90, 90 или 120, 80.
Словесный алгоритм
Начало алгоритма
1. Введите два угла треугольника в градусах.
2. Организуйте проверку типа треугольника:
• если сумма двух углов меньше 180°, то вычислите значение третьего угла и рассмотрите три ситуации:
а) если все углы острые, то выведите сообщение
«Треугольник остроугольный»;
б) если один из углов равен 90°, то выведите сообщение
«Треугольник прямоугольный»;
в) в противном случае выведите сообщение
«Треугольник тупоугольный »;
• иначе (если сумма углов больше 180°) выведите сообщение
«Некорректный ввод».
Конец алгоритма
Алгоритм в виде блок-схемы
Фраза «один из углов равен 90°» в словесном алгоритме понятна человеку. Для компьютера ее следует детализировать, рассмотрев три ситуации (для каждого из углов ul, u2, u3). На алгоритмическом языке эта проверка может выглядеть следующим образом: ((ul = 90) и (и2 о 90) и (иЗ < > 90)) или ((и2 = 90) и (ul о 90) и (u3 < > 90)) или ((иЗ = 90) и (ul < > 90) и (и2 < > 90)).
Чтобы упростить проверку, в алгоритм должен быть введен блок, обеспечивающий условие «сумма углов = 180». После этого достаточно рассмотреть выполнение условия «(ul = 90) или (и2 = 90) или (иЗ = 90)».
Алгоритм в виде программы
В табл. 8.11 приведена программа к заданию на алгоритмическом языке Кумир. В табл. 8.12 приведены тексты программ на языках Паскаль и Visual Basic.
Таблица 8.11. Программа на Кумире с пояснениями (к заданию 8.6)
Таблица 8.12. Примеры программ на Паскале и Visual Basic (к заданию 8.6)
Контрольные вопросы и задания
К заданию 8.4
1. Какое сообщение будет получено в результате выполнения алгоритма и программ, если введенное число с будет равно al или а2?
2. Могут ли быть введены различающиеся по знаку или отрицательные числа al и а2?
3. Что надо изменить в блок-схеме и программе, чтобы они работали с тремя последовательными членами геометрической прогрессии (al, а2 — являются членами, с — следует проверить)?
4. Найдите на блок-схеме (см. рис. 8.6) блок ветвления и определите, является ли ветвление полным или нет.
К заданию 8.5
1. Заполните таблицу тестирования для числа 10 (см. табл. 8.9).
2. Почему в 7-й строке табл. 8.9 тестирования (первый тест) ничего нет?
3. Достаточно ли представленных в табл. 8.9 тестов, чтобы проверить все ситуации, которые могут возникнуть при выполнении программ (все ветви алгоритма)?
4. Можно ли объединить оба условия проверки (пп. 5 и 8) в одно сложное условие? Напишите логическое выражение для подобной проверки.
5. Составьте самостоятельно фрагмент блок-схемы алгоритма для приема менеджера на работу по следующим условиям:
• возраст от 30 до 40 лет;
• знание персонального компьютера или стаж работы по специальности не менее 5 лет.
К заданию 8.6
1. Почему при формировании сложного условия (см. табл. 8.11, п. 6) использована логическая связка И, а не ИЛИ?
2. Почему при формировании сложного условия (см. табл. 8.11, п. 8) использована логическая связка ИЛИ, а не И?
3. В алгоритме и программе тупоугольный треугольник определяется по веткам «иначе» (не прямоугольный и не остроугольный). Напишите самостоятельно сложное условие, определяющее, является ли треугольник тупоугольным.
4. Выполните тестирование программы для угла 900.
5. Дополните алгоритм и программу блоком проверки положительных значений углов.
xn—-7sbbfb7a7aej.xn--p1ai
8.4. Линейный алгоритм
Приведем пример записи алгоритма в виде блок-схемы, псевдокодов и на языке Паскаль. Ручное тестирование и подбор системы тестов выполняются аналогично предыдущему заданию.
8.5. Разветвляющийся алгоритм
Приведем пример записи разветвляющегося алгоритма для нахождения наибольшего из двух чисел.
8.6. Циклический алгоритм
Рассмотрим алгоритм нахождения суммы первых натуральных нечетных чисел до n. Представим запись алгоритма тремя способами: в виде блок-схемы, школьного алгоритмического языка и на языке программирования Pascal.
Блок-схема состоит из следующих базовых структур: две составные команды (команда следования и команда повторения с предусловием), далее простая команда. Все команды соединены последовательно. Конструкции оформлены стандартным образом, поэтому их легко распознать и перевести на язык программирования. Каждая конструкция имеет один вход и один выход. Пунктирные стрелки в таблице отражают последовательность выполнения технологической цепочки. После записи алгоритма в виде блок-схемы каждая команда переводится на школьный алгоритмический язык, а уже затем на язык программирования. Запишем алгоритм вычисления суммы первых n натуральных чисел. Для этого воспользуемся циклом с параметром, поскольку заранее известно сколько раз будет выполняться команда нахождения суммы. Во всех звеньях цепочки поменяем цикл «пока» на цикл «для» и приведем пример перевода алгоритма с языка блок-схем на школьный алгоритмический язык и на язык программирования Pascal.
Рассмотрим нахождение количества натуральных чисел, сумма которых не больше заданной. Для этого воспользуемся командой повторения с постусловием.
Основные понятия программирования
Программирование — это раздел информатики, изучающий методы и приемы составления программ для компьютеров. Кроме того, программирование — это подготовка задачи к решению ее на компьютере.
Программа — это последовательность команд, понятных компьютеру.
Программа записывается в виде символов, к числу которых относятся латинские и русские буквы, цифры, знаки препинания и знаки операций.
Требования, предъявляемые к программе
1. Минимальные требования к компьютеру, на котором работает программа.
2. Ясность входных и выходных данных и простота программы.
3. Минимальное время создания программы и простота ее изменения.
4. Минимальное время работы программы, минимум занимаемой памяти и минимум использованных в программе операторов.
Чтобы программа удовлетворяла этим противоречивым требованиям, необходимо обладать искусством программирования.
Свойства программ — выполнимость, мобильность, правильность, эффективность.
Выполнимость — возможность выполнения программы на данном типе компьютеров.
Мобильность — возможность переноса программы на другой тип компьютеров.
Правильность программы — правильность результатов, получаемых с помощью данной программы.
Эффективность — минимум времени выполнения, минимум машинной памяти и других ресурсов компьютера.
Языки программирования — языки для записи программ для компьютеров. Это совокупность средств и правил представления алгоритма в виде, приемлемом для компьютера.
Оператор — выражение обозначающее и описывающее какую-либо операцию.
Типы языков программирования: машинные, машинно-ориентированные, алгоритмические, логические, функциональные, учебные, инструментальные, диалоговые, графические и т.д.
Алгоритмический язык — это формальный язык, предназначенный для записи алгоритмов.
Системы программирования — это набор средств ввода, редактирования, трансляции и выполнения программ на ЭВМ.
Транслятор — это комплекс программ, обеспечивающий перевод программы, написанной на символическом языке, в совокупность машинных команд.
Компилятор — это транслятор, обеспечивающий перевод программы, написанной на алгоритмическом языке, в совокупность машинных команд без ее выполнения в компьютере.
Интерпретатор — это транслятор, обеспечивающий перевод каждой конструкции алгоритмического языка в машинные команды и одновременное выполнение этой конструкции в компьютере.
Все системы (языки) программирования имеют свой транслятор, компилятор и интерпретатор.
studfiles.net