Лабораторная работа №5. Алгоритмы и алгоритмизация

Запись арифметических выражений

Арифметические выражения записываются по следующим правилам:

• 
  Нельзя опускать знак умножения между сомножителями и ставить рядом два знака операций.
  
• 
  Индексы элементов массивов записываются в квадратных (школьный АЯ, Рascal) или круглых (Basic) скобках.
  
• 
  Для обозначения переменных используются буквы латинского алфавита.
  
• 
  Операции выполняются в порядке старшинства: сначала вычисление функций, затем возведение в степень, потом умножение и деление и в последнюю очередь — сложение и вычитание.
  
• 
  Операции одного старшинства выполняются слева направо. Например, a/b*c соответствует a/b*c. Однако, в школьном АЯ есть одно исключение из этого правила: операции возведения в степень выполняются справа налево. Так, выражение 2**(3**2) в школьном АЯ вычисляется как 2**(3**2) = 512. В языке QBasic аналогичное выражение 2^3^2 вычислясляется как (2^3)^2 = 64. А в языке Рascal вообще не предусмотрена операция возведения в степень, в Рascal x^y записывается как exр(y*ln(x)), а x^y^z как exр(exр(z*ln(y))*ln(x)).
  

Примеры записи арифметических выражений

Математическая запись	Запись на школьном алгоритмическом языке
	x*y/z
	x/(y*z) или x/y/z
	(a**3+b**3)/(b*c)
	(a[i+1]+b[i-1])/(2*x*y)
	(-b+sqrt(b*b-4*a*c))/(2*a)
(x<0)	sign(x)*abs(x)**(1/5)
	0.49*exр(a*a-b*b)+ln(cos(a*a))**3
	x/(1+x*x/(3+(2*x)**3))

Типичные ошибки в записи выражений:

5x+1 a+sin x ((a+b)/c**3

Пропущен знак умножения между 5 и х Аргумент x функции sin x не заключен в скобки Не хватает закрывающей скобки

Запись логических выражений

В записи логических выражений помимо арифметических операций сложения, вычитания, умножения, деления и возведения в степень используются операции отношения < (меньше), <= (меньше или равно), > (больше), >= (больше или равно), = (равно), <> (не равно), а также логические операции и, или, не.

Примеры записи логических выражений, истинных при выполнении указанных условий.

Условие	Запись на школьном алгоритмическом языке
Дробная часть вещественого числа a равна нулю	int(a) = 0
Целое число a — четное	mod(a,2) = 0
Целое число a — нечетное	mod(a,2) = 1
Целое число k кратно семи	mod(a,7) = 0
Каждое из чисел a,b положительно	(a>0) и (b>0)
Только одно из чисел a,b положительно	((a>0) и (b<=0)) или ((a<=0) и (b>0))
Хотя бы одно из чисел a,b,c является отрицательным	(a<0) или (b<0) или (c<0)
Число x удовлетворяет условию a	(x>a) и (x
Число x имеет значение в промежутке [1, 3]	(x>=1) и (x<=3)
Целые числа a и b имеют одинаковую четность	((mod(a,2)=0) и (mod(b,2)=0) или ((mod(a,2)=1) и (mod(b,2)=1))
Точка с координатами (x,y) лежит в круге радиуса r с центром в точке (a,b)	(x-a)**2+(y-b)**2
Уравнение ax^2+bx+c=0 не имеет действительных корней	b*b-4*a*c<0
Точка (x,y) принадлежит первому или третьему квадранту	((x>0) и (y>0)) или ((x<0) и (y>0))
Точка (x,y) принндлежит внешности единичного круга с центром в начале координат или его второй четверти	(x*x+y*y>1) или ((x*x+y*y<=1) и (x<0) и (y>0))
Целые числа a и b являются взаимнопротивоположными	a = -b
Целые числа a и b являются взаимнообратными	a*b = 1
Число a больше среднего арифметического чисел b,c,d	a>(b+c+d)/3
Число a не меньше среднего геометрического чисел b,c,d	a>=(b+c+d)**(1/3)
Хотя бы одна из логических переменных F1 и F2 имеет значение да	F1 или F2
Обе логические переменые F1 и F2 имеют значение да	F1 и F2
Обе логические переменые F1 и F2 имеют значение нет	не F1 и не F2
Логическая переменная F1 имеет значение да, а логическая переменная F2 имеет значение нет	F1 и не F2
Только одна из логических переменных F1 и F2 имеет значение да	(F1 и не F2) или (F2 и не F1)

ГОСТ на описание блок-схем

Для графического представления алгоритма используют определенные геометрические фигуры. Такое представление называется блок-схемой. Размеры и соотношения размеров фигур приводятся в ГОСТ 19–002–80 и ГОСТ 19–003–80. Согласно им все размеры связаны с двумя величинами: а и в, где а – величина, кратная 5, а в вычисляется по формуле в = 1,5а, допускается в = 2а.

В январе 1992 года введен новый ГОСТ 19–701–90. Он описывает, как и где следует использовать фигуры. Согласно ему допускаются следующие символы для изображения схем:

1. Для изображения данных

1.1. вводимые данные, носитель данных не определен



1.2. хранимые данные, носитель не определен



1.3. данные, хранимые в оперативной памяти хранимые в оперативной памяти



1.4. данные, хранимые в запоминающих устройствах с последовательным доступом



1.5. данные, хранимые в запоминающих устройствах с прямым доступом



2. Для изображения документов

2.1. данные на носителе (машинограммы, документы для оптического считывания, микрофильмы, бланки ввода)



2.2. отображаемые данные, вводимые вручную (клавиатура, переключатели, кнопки, световое перо и т.д.)



2.3. данные на бумажной ленте



2.4. данные в читаемой форме на носителе в виде отображающего устройства (дисплей и т.д.)



3. Для отображения действий

3.1. выполнение операций, группы операций, приводящих к изменению значения, формы, их размещения и т.д. Блок “процесс”



3.2. предопределенный (т.е. определенный заранее) процесс (процедуры, функции, подпрограммы)



3.3. ручная операция – процесс, выполняемый человеком.



3.4. подготовка команды или группа команд с целью воздействия на последующую функцию (инициализация)



3.5 решение, блок “условие”



3.6. выполнение параллельных действий



Например



3.7. обозначение цикла осуществляется двумя блоками, внутри первого или второго обозначается условие инициализации или условие цикла. Между ними размещаются другие блоки



3.8. передача управления непосредственно с указанием типа (запрос, вызов, событие и т.д.)



3.9. Соединитель (межстраничный, межлистовой)

к странице



от страницы



 Внутри используют уникальные одни и те же буквенные обозначения

3.10. выход и вход во внешнюю среду, блок “ввод/вывод”



3.11. комментарий



3.12. канал связи



Практическая часть
Вариант 1.
№ 1. Запишите по правилам алгоритмического языка выражения:

а) , б)
№ 2. Запишите в обычной математической форме арифметические выражения:

а) a**b**c/2; б) (a**b)**c/2; в) a/b/c/d*р*q
№ 3. Постройте графики функций , заданных командами если и нарисуйте фрагмент блок-схемы:

если x<=-1

то y:=1/x**2

иначе

если x<=2

то y:=x*x

иначе y:=4

все

все
№4. Составьте блок-схему алгоритма, запрашивающего имя и затем приветствующего его обладателя.
№5. Определить, является ли заданное целое число А нечётным двузначным числом.
№6. Смешали v₁ литров воды с температурой t₁ градусов Цельсия с v₂ литрами воды с температурой t₂ градусов Цельсия. Вычислить объём и температуру образовавшейся смеси.
№7. Вычислить сумму элементов числового массива A=(a₁, a₂, ... , a_N).
№8. Элементы заданного массива B(N) переписать в новый массив A(N) в обратном порядке.
№9. У кассы аэрофлота выстроилась очередь из N человек. Время обслуживания кассиром i-го клиента равно T_i (i = 1, ..., N). Требуется определить время пребывания в очереди каждого клиента.
№10. Вычислить суммы элементов столбцов заданной матрицы A(N, M).
№11. Определить, является ли заданная последовательность чисел a₁, a₂, ... , a_N монотонно убывающей.
№12. Имеется последовательность чисел a₁, a₂, ..., a_N . Найти сумму первых из них (считая слева направо), произведение которых не превышает заданного числа М.
№13. Малое предприятие в первый день работы выпустило P единиц товарной продукции. Каждый последующий день оно выпускало продукции на Q единиц больше, чем в предыдущий. Сколько дней потребуется предприятию, чтобы общее количество выпущенной продукции за все время работы впервые превысило запланированный объем?
№14. В заданной целочисленной матрице A(N, M) найти количество строк, содержащих нули.
№15. Используя сведения о результатах сдачи n вступительных экзаменов m абитуриентами, определить, сколько абитуриентов сдали все экзамены на "отлично".
№16. В бублике 1 дырка, в кренделе - 2. На сколько меньше дырок в А бубликах, чем в В кренделях?
№17. С автостанции автобусы отправляются по 16 маршрутам и переезжают через реку по 4-м мостам: 1, 2, 3, 5 - по Южному, 4, 6, 7, 8 - по Центральному, 9, 10, 11, 12 - по Северному, 13, 14, 15, 16 - по Окружному. Ввести с клавиатуры номер маршрута. Определить, по какому мосту он пойдет.
№18. На мини-рынке продают молоко и цветы. Задать случайным образом N - номер торгового места - целое число от 1 до 6. Определить, чем торгуют: 1, 3, 5 - молоко, 2, 4, 6 - цветы.
№19. Алгоритм нахождения суммы отрицательных чисел в произвольной последовательности
№20. Алгоритм решения:

Вариант 2.
№ 1. Запишите по правилам алгоритмического языка выражения:

а) , б)
№2. Запишите в обычной математической форме арифметические выражения:

а) x**y**z/a/b; б) 4/3*3.14*r**3; в) b/sqrt(a*a+b)
№3. Постройте графики функций , заданных командами если и нарисуйте фрагмент блок-схемы:

если x<-0.5

то y:=1/abs(x)

иначе

если x<1

то y:=2

иначе y:=1/(x-0.5)

все

все
№4. Составьте блок-схему алгоритма, определяющего объём и площадь боковой поверхности цилиндра с заданными радиусом основания R и высотой H.
№5. Определить, имеется ли среди заданных целых чисел A, B, C хотя бы одно чётное.
№6. Выбрать наибольшее из трёх заданных чисел.
№7. Найти наибольший элемент числового массива A=(a₁, a₂, ..., a_N) и его номер.
№8. Вычислить сумму квадратов всех элементов заданного массива X(N), за исключением элементов, кратных пяти.
№9. У кассы аэрофлота выстроилась очередь из N человек. Время обслуживания кассиром i-го клиента равно T_i (i = 1, ..., N). Требуется указать номер клиента, для обслуживания которого кассиру потребовалось самое большое время.
№10. Подсчитать, сколько раз встречается в заданной целочисленной матрице A(N, M) максимальное по величине число.
№11. Задано множество точек на плоскости. Определить, принадлежит ли хотя бы одна точка множества внутренней области круга с центром в точке (a, b) и радиусом R.


№12. Найти наименьший делитель заданного натурального числа A (не считая единицы).
№13. Определить, является ли заданное натуральное число палиндромом (палиндром – число, одинаково читаемое слева направо и справа налево).
№14. Дана целочисленная матрица A(N, M). Определить, встречается ли заданное целое K среди максимальных элементов столбцов этой матрицы.
№15. Даны сведения о количестве забитых голов каждого футболиста команды в каждом из матчей чемпионата. Проверить, сколько в команде есть футболистов, забивших хотя бы два гола.
№16. Одна тетенька произносит К слов в минуту, а другая - С слов. Кто и на сколько больше скажет слов за 3 часа, если они разговаривают одновременно и непрерывно, не слушая друг друга?
№17. В поликлинике кабинеты распределены так: 1, 2, 3, 17 - окулисты, 4, 18, 19, 20 - хирурги, 5-8 стоматологи, 9-16 - педиатры. Задать целое число от 1 до 20 (номер кабинета) и определить специальность врача.
№18. Вовочка, любитель стрелять из рогатки, 7 раз попадал в милицию. Ввести случайным образом число - номер попадания. Определить результат: 4, 6, 7 - милиционеры вставляли новое стекло, 1, 2, 3, 5 - майор лично менял разбитые лампочки.
№19. Алгоритм нахождения наибольшего целого числа в последовательности
№20. Алгоритм решения:

Вариант 3.
№ 1. Запишите по правилам алгоритмического языка выражения:

а) , б)
№ 2. Запишите в обычной математической форме арифметические выражения:

а) d*c/2/R+a**3 б) 5*arctg(x)-arctg(y)/4; в) lg(u*(1/3)+sqrt(v)+z)
№ 3. Постройте графики функций , заданных командами если и нарисуйте фрагмент блок-схемы:

если x<0

то y:=1

иначе

если x<3.14

то y:=cos(x)

иначе y:=-1

все

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


№5. В баскетбольную команду могут быть приняты ученики, рост которых превышает 170 см. Составьте список кандидатов в команду из учеников класса.
№6. Даны три числа. Выбрать те из них, которые принадлежат заданному отрезку [e, f].
№7. Значения заданных переменных a, b и c перераспределить таким образом, что a, b, c станут, соответственно, наименьшим, средним и наибольшим значениями.
№8. В заданном массиве A(N) поменять местами наибольший и наименьший элементы.
№9. В соревнованиях по фигурному катанию N судей независимо выставляют оценки спортсмену. Затем из объявленных оценок удаляют самую высокую (одну, если самую высокую оценку выставили несколько судей). Аналогично поступают с самой низкой оценкой. Для оставшихся оценок вычисляется среднее арифметическое, которое и становится зачетной оценкой. По заданным оценкам судей определить зачетную оценку спортсмена.
№10. заданной матрице A(N, M) поменять местами строки с номерами P и Q (1<=P<=N, 1<=Q<=N).
№11. Определить, имеется ли среди элементов главной диагонали заданной целочисленной матрицы A(N, N) хотя бы один положительный нечётный элемент.
№12. Числа Фибоначчи (F_i) определяются по формулам F₀=F₁=1; F_i=F_i–1+F_i–2 при i=2, 3, ... Найти первое из чисел Фибоначчи, которое превосходит заданное число M (M>0).
№13. Определить по данным музейного каталога, есть ли в музее хотя бы одна картина Левитана или Шишкина. Если есть, выдать ее название, в противном случае выдать соответствующий текст.
№14. Проверить, является ли заданная целочисленная матрица A(N, N) "магическим квадратом" (это значит, что суммы чисел во всех её строках, всех столбцах и двух диагоналях одинаковы).
№15. Даны сведения о количестве забитых голов каждого футболиста команды в каждом из матчей чемпионата. Проверить, сколько в команде есть футболистов, забивавших голы в каждом матче.
№16. Маша Петрова сделала в диктанте М ошибок, а Гриша Кружков, который у нее все списал, - на К ошибок больше. Ввести с клавиатуры значения для М и К. Сколько ошибок сделал Гриша?
№17. В шеренге спортсмены стоят по росту. Определить по номеру спортсмена вид спорта, которым он занимается: 1, 2, 9 - баскетбол, 3, 4, 5 - бег, 6, 7, 8 - штанга.
№18. Задать с помощью генератора случайных чисел номер ряда в кинотеатре - целое число от 1 до 25. Определить сколько стоит билет, если его цена зависит от ряда: 1,2,3, 25- 10 руб, 4,5 - 15 руб, с 6 по 24 - 20 рублей.
№19. Ввести с клавиатуры a и b. Найти сумму целых чисел, принадлежащих отрезку [a, b].
№20. Алгоритм решения:

Вариант 4.
№ 1. Запишите по правилам алгоритмического языка выражения:

а) , б)
№2. Запишите в обычной математической форме арифметические выражения:

а) ln(y*(-sqrt(abs(x)))); б) abs(x**(y/x)-(y/x)**(1/3));

в) sqrt((x1-x2)**2+(y1-y2)**2)
№3. Постройте графики функций , заданных командами если и нарисуйте фрагмент блок-схемы:

если abs(x)>2

то y:=x*x

иначе

если x<0

то y:=-2*x

иначе

если x>=1

то y:=4

иначе y:=4*x*x

все

все

№4. Составьте блок-схему алгоритма, определяющего произведение цифр заданного целого четырехзначного числа.
№5. Определить число, полученное выписыванием в обратном порядке цифр заданного целого трёхзначного числа.
№6. Определить, пройдет ли кирпич с рёбрами a, b, c в прямоугольное отверстие со сторонами x и y. Просовывать кирпич в отверстие разрешается только так, чтобы каждое из его рёбер было параллельно или перпендикулярно каждой из сторон отверстия.
№7. Для заданного x вычислить .
№8. В заданном массиве A(N) определить количество элементов, которые меньше заданного значения.
№9. В заданном массиве A(N) вычислить среднее арифметическое значение для положительных элементов.
№10. Элементы заданного числового массива a₁, a₂, ..., a_N упорядочить по возрастанию.
№11. Определить, имеется ли среди элементов главной диагонали заданной целочисленной матрицы A(N, N) хотя бы один положительный чётный элемент.
№12. Вычислить приближённое значение бесконечной суммы: Суммирование производить до тех пор, пока очередное слагаемое не станет по абсолютной величине меньше заданного числа e>0.
№13. Определить по прейскуранту, можно ли подобрать в спортивном магазине велосипед, стоимость которого не превышает имеющуюся у покупателя сумму.
№14. Дана матрица A(N, N). Если хотя бы один элемент строки матрицы отрицателен, то все элементы этой строки заменить нулями.
№15. Даны сведения о количестве забитых голов каждого футболиста команды в каждом из матчей чемпионата. Проверить, сколько в команде есть футболистов, не забивших ни одного гола.
№16. Папа, воспитывая сына-двоечника, изнашивает в год 3 ремня. Ввести с клавиатуры количество изношенных папой ремней, определить: какой класс закончил сын.
№17. В поезде 17 вагонов. С 10 по 17 вагоны купейные, а остальные - плацкартные. Ввести с клавиатуры номер вагона. Напечатать его вид.
№18. Один мальчик на перемене 12 раз дергал девочек за косички. Ввести номер косички. Определить, кому она принадлежит: 1, 2, 3, 8 - девочке из 3"а", 4, 5, 6 - девочке из 3"б", 7, 10, 11, 12 - девочке из 3"в", 9 - завучу Маргарите Багратионовне.
№19. Найти и сообщить все положительные члены арифметической прогрессии с первым членом 10 и разностью -1/3.
№20. Алгоритм решения:
Вариант 5.
№ 1. Запишите по правилам алгоритмического языка выражения:

а) б)
№2. Запишите в обычной математической форме арифметические выражения:

а) exр(abs(x-y))*(tg(z)**2+1)**x; б) lg(sqrt(exр(x-y))+x**abs(y)+z);

в) sqrt(exр(a*x)*sin(x)**n)/cos(x)**2
№3. Постройте графики функций , заданных командами если и нарисуйте фрагмент блок-схемы:

если x<-5

то y:=-5

иначе

если x<0

то y:=x

иначе

если x<3

то y:=2*x

иначе y:=6

все

все

все
№4. Составьте блок-схему алгоритма, определяющего сумму цифр заданного целого пятизначного числа.
№5. Определить, есть ли среди цифр заданного целого трёхзначного числа одинаковые.
№6. Идет k-ая секунда суток. Определить, сколько полных часов и полных минут прошло к этому моменту.
№7. Дан массив X(N). Получить новый массив Y(N) такой, что в нем сначала идут положительные числа, затем нулевые, и затем отрицательные из X.
№8. Вывести на печать номера элементов заданного массива Y(N), удовлетворяющих условию 0_i<1.
№9. В заданном массиве A(N), все элементы которого попарно различны, найти наибольший элемент из отрицательных.
№10. В массиве A(N, N) вычислить две суммы элементов, расположенных ниже и выше главной диагонали.
№11. Числа Фибоначчи (F_i) определяются по формулам F₀=F₁=1; F_i=F_i–1+F_i–2 при i=2, 3, ... (каждое очередное число равно сумме двух предыдущих). Вычислить сумму всех чисел Фибоначчи, которые не превосходят заданного натурального числа М.
№12. Найти любое трёхзначные число, кратное заданному Р и не равное ему.
№13. Известен начальный вклад клиента в банк и процент годового дохода. Определить, через сколько лет вклад превысит заданный размер и каков при этом будет размер вклада.
№14. В заданной матрице A(N, M) найти количество строк, не содержащих отрицательных чисел.
№15. Используя сведения о ежемесячных выплатах зарплаты сотрудникам фирмы, выяснить, не оказалась ли годовая зарплата кого-либо из сотрудников ниже годового минимума, оговоренного в его контракте.
№16. В специальный ящик можно уложить 68 яиц. А если уминать их ногами, то поместится в 100 раз больше. Сколько уминаемых ногами яиц можно уложить в Х таких ящиков? (Х задать случайным образом.)
№17. У младенца Кузьки вылезло уже s зубов , а у его бабы Дуси осталось w зубов. Задать с помощью генератора случайных чисел 2 целых числа от 0 до 5 - значения для s и w. У кого зубов больше?
№18. Во время сильного дождя на остановке стояло 12 человек. Подкативший автобус забрызгал грязью 4-го, 5-го, 6, 7 и 8-го человека. Остальные попрыгали в колючие кусты, причем 3-ий, 9-ый и 12-ый так и не смогли выбраться из них. Задать номер пассажира, определить:

а) грязный он или исцарапанный; б) едет или сидит в кустах.
№19. Самолет летит равномерно со скоростью V. Рассмотреть движение свободнопадающего груза, который до падения находился в самолете.


№20. Алгоритм решения:

Вариант 6.
№ 1. Запишите по правилам алгоритмического языка выражения:

a) б)

№ 2. Запишите в обычной математической форме арифметические выражения:

а) a/b**2; б) a+b/c+1; в) 1/a*b/c
№ 3. Постройте графики функций , заданных командами если и нарисуйте фрагмент блок-схемы:

если x<-5

то y:=5

иначе

если x<0

то y:=3*x

иначе

если x<3

то y:=2*x

иначе y:=6

все

все

все
№ 4. Составьте блок-схему алгоритма, определяющего, есть ли среди цифр заданного целого трёхзначного числа одинаковые.
№5. Проверить, можно ли построить треугольник из отрезков с длинами x, y, z и, если можно, то какой – остроугольный, прямоугольный или тупоугольный.
№6. Решить линейное уравнение .
№7. Вычислить произведение элементов числового массива A=(a₁, a₂, ... , a_N)
№8. Включить заданное число D в массив A(N), упорядоченный по возрастанию, с сохранением упорядоченности.
№9. В заданном массиве A(N), все элементы которого попарно различны, найти наименьший элемент из положительных.
№10. Элементы заданного числового массива a₁, a₂, ..., a_N упорядочить по убыванию.
№11. В заданном массиве A(N) положительные элементы уменьшить вдвое, а отрицательные заменить на значения их индексов.
№12. Дано натуральное N. Выяснить, сколько цифр оно содержит.
№13. Торговая фирма в первый день работы реализовала товаров на P тыс. руб., а затем ежедневно увеличивала выручку на 3%. Какой будет выручка фирмы в тот день, когда она впервые превысит заданное значение Q? Сколько дней придется торговать фирме для достижения этого результата?
№14. Подсчитать количество различных (не повторяющихся) чисел, встречающихся в заданной целочисленной матрице A(N, M).
№15. Используя сведения о размере обуви каждого члена баскетбольной команды, а также сведения о наличии в обувном магазине размеров спортивной обуви, определить, сколько членов команды можно обуть в этом магазине.
№16. Посчитайте, сколько очков набрала команда «Динамо» в первом круге чемпионата России по хоккею, если известно, что m встреч она выиграла, n встреч проиграла, k встреч закончились ничьими, полагая, что за выигрыш команда получает 2 очка, за ничью -1 очко, за проигрыш – 0 очков.
№17. Мама завела себе Х кактусов. Когда трехлетняя Маша старательно побрила папиной бритвой Т кактусов, мама не смогла определить каких кактусов больше: гладких или небритых. Помоги ей.
№18. На заданном расстоянии l от пушки находится стена. Известен угол наклона пушки и начальная скорость снаряда V₀. Попадет ли снаряд в стену?

Соотношение


№19. Расположенный на берегу реки завод осуществляет сброс сточных вод, в результате чего произошло увеличение концентрации вредных веществ. С течением времени концентрация уменьшается. Нужно сообщить каков будет уровень загрязнения реки через сутки, двое, трое и до тех пор пока концентрация станет меньше допустимой. Д – предельно допустимая концентрация. С – начальная концентрация. К – коэффициент. Соотношение - .
№20. Алгоритм решения: