Линейный алгоритм

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное государственное бюджетное общеобразовательное учреждение высшего образования

Дальневосточный государственный университет путей сообщения

Кафедра «Информационные технологии и системы»

Расчетно-графическая работа по теме «Алгоритмизация»

Выполнил: Катаева Е.Е.

Проверил: Дорогинина О.В.

Хабаровск 2018



Практическая часть

Линейный алгоритм

Вычисление площади трапеции

Формулировка задания: Составить алгоритм вычисления площади трапеции S=(a+b)/2*h.

Анализ задачи.

Выходные данные. Выходными данными являются длины сторон трапеции а,b и её высота h.

Результат. Результатом работы алгоритма является вычисленное значение площади трапеции S.

Формулы. Будем вычислять по формуле площади трапеции.

Проектирование алгоритма.

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Детализируем главный алгоритм. Для этого: напишем входные данные и результат в явном виде. (рис.2)

Рисунок 2.

Тестирование алгоритма.

Осталось протестировать этот алгоритм вычисления площади трапеции. Расставим на алгоритме контрольные точки A, B, C (см. рис. 2). Контрольные точки ставятся везде, где вводятся или изменяются данные, т. е. после каждого ввода и каждого действия алгоритма (на блок-схеме контрольные точки ставятся после всех параллелограммов и прямоугольников, кроме вывода данных).

Исполнитель начинает выполнять алгоритм с его начала. При движении по алгоритму его активная точка проходит сначала контрольную точку A, затем B, и наконец C.

Зададим входные данные. Пусть сторона а= 8, сторона b= 10, а высота h=2. Тогда, по формуле площади трапеции, S=4,5. Разберем работу алгоритма, представленного на рис. 2. Для этого составим таблицу 1 из значений данных в контрольных точках.

Контрольная точка	Значения данных
A	a = 8, b = 10, h = 2
B	a = 8, b = 10, h = 2, S=4,5
C	a = 8, b = 10, h = 2, S=4,5

Вывод.

Алгоритм вычислил значение площади трапеции S=4,5, что совпадает с расчетным значением. Поскольку алгоритм простой, то, скорее всего, он работает правильно. Для большей уверенности в правильной работе алгоритма желательно проверить его еще на нескольких более сложных тестах.

Алгоритм ветвления

Определение существования треугольника по двум углам

Формулировка задания. Даны два угла треугольника (в градусах). Определить, существует ли такой треугольник.

Анализ задачи.

Входные данные. Из условия задачи следует, что входными данными являются два угла треугольника <a и <b.

Результат. Результатом работы алгоритма является определение существования данного треугольника.

Формулы. Чтобы узнать существует ли такой треугольник, нужно обратиться к формуле суммы углов треугольника

.Проектирование алгоритма.

Детализируем общую блок-схему (см. рис. 3): запишем входные данные в явном виде.

Тестирование алгоритма.

При тестировании расставим на алгоритме контрольные точки A, B, C, D (см. рис. 3). При движении по алгоритму активная точка исполнителя проходит не все контрольные точки!

Тест: Зададим значения двух углов треугольника <а = ,

<b = .

3. Протестируем алгоритм и запишем значения переменных в контрольных точках (таблица 2). Полученная последовательность контрольных точек показывает, по каким ветвям выбора проходит исполнитель: точка С пропущена.

Таблица 2

Контрольная точка	Значения данных
A	<a = , <b =
условие	“да”
B	<a = , <b = , меньше
D	<a = , <b = , <c =

Итак, мы убедились, что алгоритм вычислил правильное значение и вывел правильный результат.

Циклические операторы

Сумма и произведение ряда

2. Формулировка задания. Составить алгоритм вычисления суммы и произведения ряда lg2, lg3, … , lgn

Решим данную задачу тремя способами используя «цикл с параметром», «цикл-пока» и «цикл-до».

3. Анализ задачи.

3.1. Входные данные. Из суммы (1) следует, что входным данным является количество первых натуральных чисел n. Из произведения (2) следует, что выходными данными является произведение первых натуральных чисел n.

3.2. Результат. Результатом работы алгоритма является вывод суммы (1) и произведения (2).

3.3. Формулы. Нужно найти сумму и произведение n чисел

S= lg2 + lg3 + … + lgn. (1)

P= lg2 * lg3 * … * lgn (2)

S:=S+i (3)

P:=P+i (4)

4. Проектирование алгоритма.

Детализируем общую блок-схему (см рис. 1):

1) напишем входные данные в явном виде;

2) выведем сообщение о величине суммы и произведения;

Заметим, что текущее слагаемое суммы (1) и произведения (2) имеет вид i.

1) присвоим им начальные значение S = 0; P=1.

2) прибавляем к сумме (3) и произведению (4) в цикле переменную i, изменяя ее от 2 до n.

Способ 1. Алгоритм с использованием структуры «цикл с параметром»

Результат проектирования представлен на рис. 4.

Тестирование алгоритма.

При тестировании расставим на алгоритме контрольные точки A, B, C, D (см. рис. 4). Зададим количество первых натуральных чисел n = 5. Мы должны получить значение суммы и произведения первых четырёх натуральных чисел S = 14, Р = 120.Протестируем алгоритм и запишем значения переменных в контрольных точках в таблицу 4.



Таблица 4.

Контрольная точка	Значения данных
A	n = 5
B	n = 5, S=0, Р=1
С	n = 5, i=2, S=2, Р=2
С	n = 5, i=3, S=5, Р=6
С	n = 5, i=4, S=9, Р=24
С	n=5, i=5, S=14, P=120
D	n = 5, i=5, S=14, P=120

Способ 2. Алгоритм с использованием структуры «цикл постусловие»

Результат проектирования представлен на рис. 5.

3.4. Тестирование алгоритма.



При тестировании расставим на алгоритме контрольные точки A, B, C, D (см. рис. 5). Зададим количество суммируемых первых натуральных чисел n = 5. Мы должны получить значение суммы S=14 и произведения P=120 первых четырёх натуральных чисел. Протестируем алгоритм и запишем значения переменных в контрольных точках в таблицу 5.

Таблица 5.

Контрольная точка	Значения данных
A	n = 5
B	n = 5, S=0, P=1, i=2
С	n = 5, S=2, P=1, i=2
условие	2>5 - ложь (нет)
С	n = 5, S=5, P=2, i=3
условие	3>5 - ложь (нет)
С	n = 5, S=9, P=6, i=4
условие	4>5 - ложь (нет)
С	n = 5, S=14, P=24, i=5
условие	5>5 - ложь (нет)
С	n=5, S=14, P=120, j=6
условие	6>5 - истина (да)
D	n = 5, S=14, Р=120, i=6

Способ 3. Алгоритм с использованием структуры «цикл предусловие»

Результат проектирования представлен на рис. 6.



Тестирование алгоритма.

При тестировании расставим на алгоритме контрольные точки A, B, C, D (см. рис. 6). Зададим количество первых натуральных чисел n = 5. Мы должны получить значение суммы S=14 и произведения P=120 первых четырёх натуральных чисел. Протестируем алгоритм и запишем значения переменных в контрольных точках в таблицу 6.



Таблица 6

Контрольная точка	Значения данных
A	n = 5
B	n = 5, S=0, Р=1, i=2
С	n = 5, S=2, Р=1, i=2
условие	2<=5 - истина (да)
С	n = 5, S=5, Р=2, i=3
условие	3<=5 - истина (да)
С	n = 5, S=9, Р=6, i=4
условие	4<=5 - истина (да)
С	n = 5, S=14, Р=120, i=5
условие	5<=5 - истина (да)
С	n=5, S=14, P=120, j=6
условие	6<=5 - ложь (нет)
D	n = 5, S=14, Р=120, i=6

Вывод

Итак, мы убедились, что алгоритм вычислил правильное значение и вывел правильный результат. Данную задачу мы разобрали тремя способами используя «цикл с параметром», «цикл предусловие» и «цикл постусловие».



Теоретическая часть

1.Каково происхождение слова «алгоритм»?

Слово «алгоритм» происходит от Арабского название книги «Книги о сложении и вычитании» персидского астронома и математика IX века аль-Хорезми (полное имя Абу Абдулла Мухаммед ибн Муса аль-Хорезми). Название книги было переведено, в XII веке на латынь как Algoritmi de numero Indorum («Алгоритми о счёте индийском») . Слово Algoritmi, преобразованное затем под влиянием др. -греч. ?сйимьт «число, счёт» , вошло в обиход западной науки как обозначение последовательности вычисления.

2.Приведите определение алгоритма.

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

3.Что такое исполнитель? Приведите примеры.

Исполнитель - это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Пример: компьютер, калькулятор, человек и др.

4. Из каких элементов состоят алгоритмы?

5. Охарактеризуйте способы представления алгоритмов.

Словесный способ заключается в описи алгоритма в терминах какого либо языка. Данный способ применяется редко, поскольку запись при этом довольно громоздкая и могут возникнуть противоречивые толкования алгоритма.

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

Графический способ- изображение алгоритма в виде структурной схемы, которая состоит из отдельных блоков. Этот способ представления алгоритма есть наиболее удобным и наглядным.

6.Какова роль языка в представлении алгоритмов?

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

7. Что называется «алгоритмическим языком»?

Алгоритмический язык -- это система обозначений и правил для единообразной и точной записи алгоритмов и их исполнения. Всякий императивный язык программирования является алгоритмическим языком, но не всякий алгоритмический язык пригоден для использования в качестве языка программирования.

8.В чем состоит свойство дискретности алгоритма?

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

9.Что означает свойство результативности алгоритма?

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

10.Что означает «массовость алгоритма»?

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

11.Каковы основные алгоритмические конструкции?

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

1) Линейная алгоритмическая конструкция

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

2) Разветвляющаяся алгоритмическая конструкция

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

3)Алгоритмическая конструкция «Цикл»

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

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

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

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

алгоритм линейный треугольник



Размещено на Allbest.ru

...