Теоретическая часть. Тема 1: Понятие алгоритма, составление простейшего алгоритма

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

Тема 1: Понятие алгоритма, составление простейшего алгоритма.

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

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

Формы записи алгоритмов

1. Словесная, или текстовая, форма – это пронумерованная последовательность предложений на естественном языке (разговорном языке пользователя) с применением математических обозначений и формул (то есть каждое предложение - это очередное предписание алгоритма). Такое представление весьма слабо формализовано, а поэтому под сомнением свойство определенности алгоритма. Зато для записи в этой форме не нужны никакие специальные знания кроме знаний собственно самого плана решения задачи.

2. Графическая, или схемная, форма (иначе – блок-схема) - это пронумерованная последовательность блоков различной конфигурации в зависимости от типа выполняемого предписания (т.е. каждая фигура – это очередное предписание алгоритма). Блоки соединены линиями связи в соответствии с порядком исполнения. Внутри блоков допустимы только математические записи. Конфигураций основных блоков столько, сколько выделено основных предписаний для построения вычислительных алгоритмов (они указаны выше). Несмотря на некоторые трудности, а может быть благодаря им, такое представление алгоритмов очень формализовано. И еще одно преимущество – наглядность алгоритма в смысле его структуры и характера исполнения.

3. Алгоритм, представленный на языке программирования, – это последовательность (не всегда пронумерованная) "предложений" на выбранном алгоритмическом языке с использованием математической символики в алфавите этого языка. Как было сказано ранее, каждое "предложение" (очередное предписание алгоритма) называется оператором, а весь алгоритм, записанный в виде последовательности операторов, называется программой. Такое представление формализовано, используется обычно для ввода алгоритма в ЭВМ, а получается в результате "перевода" разработанного алгоритма в любой из перечисленных выше форм на алгоритмический язык: переводится (заменяется) последовательно каждое предписание "своим" оператором. Для простых задач и при хорошем знании языка программирования возможно написание программы сразу, без промежуточных форм.

Таблица 1. Элементы блок-схемы

Тип	Текстовая форма	Графическая форма	Пояснения
	Ввести (значения для): <имена входных переменных>	Блок-ввода ... ...	После ключевого слова или внутри блока указывается список имен входных переменных через запятую, но не сами числа
	вычислить: <имя>=<формула>	Блок-процесс ... ...	После ключевого слова или внутри блока записывается имя вычисляемой переменной, знак = (присваивания) и формула, содержащая переменные, числа, арифметические операции, элементарные функции
	Сравнить: если <условие>, то п. К иначе п. М	Блок-принятие решения ...	Условие - это логическое выражение (например, сравнения чего-то с чем-то). При выполнении условия (истина) - переход к одному пункту (например, к п. К), при невыполнении (ложь) - переход к другому (например, к п. М)
	Вывести (напечатать): <имена выходных переменных>	Блок-документ ... ...	После ключевого слова или внутри блока указывается список имен выходных переменных через запятую, но не сами числа.
	Начало решения .... .... Остановка (конец решения)	Блоки пуск/остановка ... ...	Если в начале алгоритма, то допустимы слова: вкл., вход, пуск, готов, начало или оставить пусто. Конец решения помечают обязательно, допустимы слова: конец, останов., выкл., выход, стоп или оставить блок пустым.

Основные типы простейших алгоритмических структур.

1.Линейный тип алгоритма - это такая вычислительная структура, при которой все предписания выполняются в строго линейной последовательности друг за другом, как записаны; сам порядок исполнения называется естественным. В чистом виде линейные алгоритмы встречаются редко, они чрезвычайно просты. Но как фрагменты присутствуют почти во всех вычислительных схемах, так как именно на этих участках вводятся исходные данные, формируются и выходят на пользователя новые результаты (блок-ввода, блок-процесс, блок-печати). Примеры будут рассмотрены ниже.

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

3.Циклический тип алгоритма - эта такая схема разветвленной структуры, в которой одна ветвь операции сравнения является обратной связью (ОС) на предыдущую часть алгоритма (т.е. идет назад). Таким образом, некоторая последовательность операций алгоритма будет выполняться многократно (т.е. в цикле), образуя тело цикла (тц). В крайнем случае, тело цикла может состоять всего из одной операции. Для того чтобы результаты всякий раз получались новые, необходимо алгоритмически предусмотреть три момента:

А)надо организовать данные для первого прохождения тела цикла;

Б)после каждого выполнения тела цикла надо обновлять данные для очередного прохождения цикла;

В)надо управлять циклом, организовать условие выхода из цикла или его продолжения (ОС не должна охватывать указанные в пункте а операции!).

Задача 1. Варианты задания.

Составить линейный алгоритм для вычисления

1) длины окружности и площади круга радиуса R;

2) длины медианы на сторону а в треугольнике со сторонами а, b, с;

3)»» b»»

4)»» с»»

5) длины биссектрисы на сторону а в треугольнике со сторонами a,b,c

6)»» b»»

7)»» с»»

8) площади треугольника со сторонами а, b, с;

9) площади квадрата с диагоналями d;

10) площади ромба с диагоналями d₁ и d₂;

11) площади трапеции с высотой h и основаниями а и b;

12) площади вписанного четырехугольника со сторонами а, b, с, d (через полупериметры);

13) площади кольца с радиусами R и r;

14) диагонали параллелепипеда с ребрами а, b, с;

15) объема и поверхности параллелепипеда с ребрами а, b, с;