лр 5

Лабораторная работа №5

Тема: «Основы алгоритмизации»

Цель работы:

Задачи:

Понятие алгоритма и его свойства. Средства словесной и формально словесной записи алгоритмов. Средства графического представления алгоритмов. Основные типы структур алгоритмов. Описание линейных и разветвленных структур алгоритмов. Понятие цикла. Типы алгоритмов циклической структуры. Циклы с предусловием и с постусловием. Циклические структуры с заданным и бесконечным числом повторений. Итерационный цикл. Вложенные циклы. Примеры реализации алгоритмов.

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

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

Алгоритм характеризуется следующими свойствами:

1. дискретность (разрывность – противоположно непрерывности) – свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, «делится на шаги»;

2. массовость – применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных;

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

4. результативность – свойство, состоящее в том, что любой алгоритм должен завершаться за конечное число шагов.

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

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

Словесное описание представляет структуру алгоритма на естественном языке. Никаких правил составления словесного описания не существует. Запись осуществляется в произвольной форме на естественном языке.

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

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

Программа – описание структуры алгоритма на языке алгоритмического программирования.

Основные конструкции, использующиеся для построения блок-схем.

Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат)
Блок – «процесс», предназначенный для описания отдельных действий
Блок – ввода/вывода с неопределенного носителя
Блок – решение (проверка условия или условный блок)
Блок, описывающий цикл с параметром
Блок – границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»
Соединительные блоки

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

Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i+1)-е действие (шаг), если i-е действие – не конец алгоритма.

Пример: вывести значение суммы двух чисел.

Начало Ввод двух чисел a,b Вычисление суммы S=a+b Вывод S Конец

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

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

Начало Ввод двух чисел a,b ЕСЛИ a>b, ТО «вывести a», ИНАЧЕ «вывести b» Конец

Часто при выборе одного из возможных вариантов действий приходится проверять значение выражения на принадлежность заданному набору данных. В этом случае сначала вычисляется значение некоторого выражения Z. Затем последовательно проверяются условия V1, V2,…, Vn относительно Z,начиная с первого, до тех пор, пока не встретится условие, принимающее значение ИСТИНА. Далее выполняется соответствующее этому условию действие (или серия действий), после чего команда выбора завершается. Если ни одно из условий не является истинным, то выполняется действие (или набор действий), идущее по ветви ЛОЖЬ для каждого из условий.

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

Арифметический цикл (цикл с параметром).

В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (K) значений параметра и шагом (h) его изменения. Т.е. на первом шаге цикла значение параметра равно N, на втором – (N+h), на третьем – (N+2h) и т.д. На последнем шаге цикла значение параметра не больше K, но такое, что дальнейшее его изменение приведет к значению, большему, чем K.

Пример: вывести 10 раз слово «Привет».

Цикл с предусловием

Количество шагов цикла заранее не определено и зависит от входных данных задачи. В данной циклической структуре сначала проверяется значение условного выражения (условие) перед выполнением очередного шага цикла. После чего управление вновь передается проверке условия и т.д. Эти действия выполняются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При первом же несоблюдении условия цикл завершается.

Если изначально условное выражение ложно, то тело цикла не выполнится ни разу.

Пример: Вывести значение наибольшего общего делителя двух натуральных чисел.

Ввод натуральных чисел m и n Пока m≠n делать. Если m>n, то m=m-n, иначе n=n-m Переход к шагу 2. Вывод m. Конец.

Цикл с постусловием.

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

Пример: Составить алгоритм игры «Угадай число».

Ввод числа x первым игроком. Ввод числа y вторым игроком. Если x>y, то вывести сообщение «Число меньше x», иначе если x<y, то вывести сообщение «Число больше x», Пока x≠y повторять пункты 2–3. Вывести сообщение «Вы угадали». Конец.

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

Рекурсивным называется алгоритм, организованный таким образом, что в процессе выполнения команд на каком-либо шаге он прямо или косвенно обращается сам к себе.

Задания

Задание 1. Составить алгоритм.

№ варианта	Задание
	Вычислить расстояние между двумя точками с координатами (x1,y1), (x2,y2).
	Дано действительное число a. Не пользуясь никакими другими арифметическими операциями, кроме умножения получить A^15за пять операций, A^21 за шесть операций и A^28 за шесть операций.
	Даны гипотенуза и катет прямоугольного треугольника. Найти второй катет и радиус описанной окружности.
	Дано трехзначное число. Найти число, полученное при перестановке первой и второй цифр заданного числа.
	Даны два действительных числа. Найти среднее арифметическое этих чисел и среднее геометрическое их модулей.
	Идет k-тая секунда суток. Определить, сколько полных часов и полных минут прошло к этому моменту от начала суток.
	Дано действительное число a. Не пользуясь никакими другими арифметическими операциями, кроме умножения получить A^4за две операции, A^6 за три операции и A^7 за четыре операции.
	Вычислить площадь параллелограмма по двум сторонам и углу между ними, заданного в градусах.
	Дано трехзначное число. Найти число, полученное при перестановке второй и третьей цифр заданного числа.
	Треугольник задан координатами своих вершин. Найти периметр и площадь треугольника.
	Три сопротивления соединены параллельно. Найти сопротивление соединения.
	Даны действительные числа x и y. Пользуясь только восемью операциями умножения и восемью операциями сложения и вычитания вычислить 3x^2y^2 – 2xy^2 – 7x^2y – 4y^2 + 15xy + 3x +10y + 6
	Дано действительное число a. Не пользуясь никакими другими арифметическими операциями, кроме умножения получить A^8за три операции, A^9 за четыре операции и A^13 за пять операций.
	Вычислить длины медиан треугольника заданного длинами сторон.
	Вычислить дробную часть среднего арифметического трех целых цисел.
	Определить число, выписыванием в обратном порядке цифр заданного трехзначного числа (например a=543 получить b=345).
	Даны действительные числа x и y. Пользуясь не более четырьмя операциями умножения и четырьмя операциями сложения и вычитания вычислить 2x^4 – 3x^3 + 4x^2 - 5x + 6
	Определить h-полное количество часов и m-полное количество минут, прошедших от начало суток до того момента (в первой половине дня), когда часовая стрелка повернулась на f градусов (0<=f<=360).
	Дано действительное число a. Не пользуясь никакими другими арифметическими операциями, кроме умножения получить A^2, А^5и А^17за шесть операций.
	Присвоить целой переменной h третью от конца цифру в записи положительного целого числа к (например, если к=123456, то h=4).
	Известны размеры комнаты ( длина и ширина в метрах) и цена покрытия за кв.м. Известны также цены за доставку одного кв.м. покрытия и отдельно за установку одного кв.м. покрытия. Вычислить общую стоимость покрытия комнаты.
	В кубический, наполненный до краев аквариум со стороной а метров выпустили рыбу-шар диаметром b см. Вычислить, сколько процентов от первоначального объема воды выплеснется из аквариума (хвост и плавники не учитывать).
	Присвоить целой переменой d первую цифру из дробной части действительного положительного числа x (например x=23.543, то d=5).
	Дано натуральное число. Найти число тысяч в нем.
	Даны действительное число x. Пользуясь не более восьми операциями умножения, сложения и вычитания вычислить 1-2x + 3x^2 – 4x^3 и 1+2x+3x^2 + 4x^3.
	Вычислить длину ломаной, заданной координатами четырех точек.
	Вычислить время колебания маятника дины L.
	Дано действительное число a. Не пользуясь никакими другими арифметическими операциями, кроме умножения получить A^3и A^10 за четыре операции, A^4 и А^20 за пять операций.
	Найти площадь сектора, радиус которого равен 13.7, а дуга содержит заданное число радиан w.
	Смешали v1 литров воды с температурой t1 градусов Цельсия с v2 литрами воды с температурой t2 градусов Цельсия. Вычислить объем и температуру образовавшейся смеси.

Задание 2. Составить алгоритм.

№ варианта	Задание
	e=
	z=
	z=
	z=
	g=
	f=
	d=
	z=
	z=
	d=
	p=
	r=
	r=
	s=
	t=
	u=
	f=
	v=
	h=
	z=
	l=
	Z=
	z=
	z=
	y=

Задание 3. Составить алгоритм.

№ варианта	Задание
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: ромб с вершинами в точках (0,1), (1,0), (0,-1), (-1,0).
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: черырехугольник с вершинами (0,1), (0.5,0), (0,-1),(-0.5,0).
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: фигура, состоящая из треугольника с вершинами в точках (-2,0), (0,1), (0,-1) и правого полукруга радиуса R с центром в начале координат.
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: треугольник с вершинами (-1,-1), (1,-1), (0,2).
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: пятиугольник с вершинами (0,0), (1,1), (1,-2), (-1,-2), (-1,1).
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: четырехугольник с вершинами (0,0), (1,0), (-2,-1), (1,-2).
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: верхняя часть плоскости, ограниченной ломаной линией, проходящей через точки (-∞,1),(-1,1),(0,0),(1,1),(∞,1).
	Определить, лежит ли заданная точка на одной из сторон треугольника, заданного своими вершинами.
	Станции A, B, C расположены на n-том, m-том и p-том километрах железной дороги, соответственно. Какие из этих станций расположены наиболее близко друг к другу.
	Даны действительные числа x и y. Меньшее из этих двух чисел заменить их полусуммой, а большее – их удвоенным проведением.
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: область, ограниченная кривыми, заданными выражениями y=abs(x) и x^2+y^2=1.
	Определить, пройдет ли кирпич с ребрами a, b, c в прямоугольное отверстие со сторонами x и y.
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: нижняя часть полуокружности, заданной уравнением x^2+y^2=1 и прямой y=x/2.
	Заданы площади круга и квадрата. Определить , поместиться ли квадрат в круге.
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: круг радиуса 1 с центром в точке (0,1) ( x^2+(y-1)^2<1 ) и треугольник с координатами вершин (0,1), (-1,0), (1,0).
	Выяснить можно уместить прямоугольник со сторонами a,b уместить внутрь прямоугольника c,d.
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: область, ограниченная кривыми, заданными выражениями x^2+(y-1)^2=1 и y=1-x^2.
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: область, ограниченная кривыми, заданными выражениями y=e^x, y=e^-^x, y=x^2.
	Даны действительные числа a, b, c (a<>0). Выяснить, имеет ли уравнение ax^2+bx+c=0 действительные корни. Если корни имеются, то найти их. В противном случае ответом должно служить сообщение, что действительных корней нет.
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: два круга радиуса 1 с центрами в точках (-1,0) и (1,0).
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: треугольник с координатами вершин (-1,1), (1,1) и (0,0) и круг с центром в точке (0,-1) и радиусом 1.
	Даны действительные числа x , y. Определить, принадлежит ли точка с координатами геометрической фигуре: два треугольника с вершинами в точках (-1,1), (-1,-1), (0,0) и (1,1), (-1,1), (0,0).
	На карте координаты начала и конца строящегося прямолинейного участка дороги обозначены как (x1,y1) и (x2,y2). Карьер, откуда можно брать гравий для стройки имеет координаты (x0,y0). Определить минимальное расстояние от строящегося участка шоссе до карьера.
	Определить номер квадранта, в котором находится точка, заданная координатами (x,y).
	Определить, имеются ли среди цифр заданного целого трехзначного числа одинаковые
	Определить, лежат ли две точки заданные своими координатами окружности с центром в начале координат.
	Определить, есть ли в заданном целом трехзначном числе цифры, кратные друг другу.
	Числа a, b – катеты одного треугольника, c,d – катеты другого треугольника. Определить подобны ли эти треугольники.
	На карте координаты начала и конца строящегося прямолинейного участка дороги обозначены как (x1,y1) и (x2,y2). Карьер, откуда можно брать гравий для стройки имеет координаты (x0,y0). Определить максимальное расстояние от строящегося участка шоссе до карьера.
	Заданы площади круга и квадрата. Определить , поместиться ли круг в квадрате.