Ивная работа по информатике (стр. 2 из 3)

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

2.1. Линейные вычислительные алгоритмы

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

1. Числитель первой дроби умножить на знаменатель второй дроби. 2. Знаменатель первой дроби умножить на числитель второй дроби. 3. Записать дробь, числитель которой есть результат выполнения пункта 1, а знаменатель — результат выполнения пункта 2. В алгебраической форме это выглядит следующим образом (см. рис. 6)

Построим алгоритм деления дробей для ЭВМ. В этом алгоритме сохраним те же обозначения для переменных, которые использованы в записанной выше формуле. Исходными данными являются целочисленные переменные а, b, с, d. Результатом — также целые величины тип. Блок-схема и текст алгоритма на учебном алгоритмическом языке приведены ниже (рис.7) (в дальнейшем для краткости будем обозначать учебный алгоритмический язык буквами АЯ). Формат команды присваивания следующий: переменная:=выражение. Знак «:=» нужно читать как «присвоить». Команда присваивания обозначает следующие действия, выполняемые компьютером:

1. Вычисляется выражение. 2. Полученное значение присваивается переменной.

В приведенном выше алгоритме присутствуют две команды присваивания. В блок-схемах команда присваивания записывается в прямоугольнике. Такой блок называется вычислительным блоком. В описаниях алгоритмов необязательно соблюдать строгие правила в записи выражений. Их можно писать в обычной математической форме. Это еще не язык программирования со строгим синтаксисом. В приведенном алгоритме присутствует команда ввода: ввод a,b,c,d. В блок-схеме команда ввода записывается в параллелограмме - блоке ввода-вывода. При выполнении данной команды процессор прерывает работу и ожидает действий пользователя. Пользователь должен набрать на устройстве ввода (клавиатуре) значения вводимых переменных и нажать на клавишу ввода Enter. Значения следует вводить в том же порядке, в каком соответствующие переменные расположены в списке ввода Обычно с помощью команды ввода присваиваются значения исходных данных, а команда присваивания используется для получения промежуточных и конечных величин. Полученные компьютером результаты решения задачи должны быть сообщены пользователю. Для этих целей предназначена команда вывода: вывод m,n. С помощью этой команды результаты выводятся на экран или на устройство печати на бумагу. Рассмотрим последовательное выполнение четырех команд присваивания, в которых участвуют две переменные величины а и b. В таблице 2.1. напротив каждой команды присваивания указываются значения переменных, которые устанавливаются после ее выполнения. Этот пример иллюстрирует три основных свойства команды присваивания:

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

Рассмотрим один очень полезный алгоритм, который приходится часто использовать при программировании. Даны две величины: X и Y. Требуется произвести между ними обмен значениями. Например, если первоначально было Х = 1, Y = 2, то после обмена должно стать: Х = 2, Y = 1. Хорошей моделью для решения этой задачи является следующая ситуация: имеются два стакана - один с молоком, другой с водой. Требуется произвести обмен их содержимым. Всякому ясно, что в этом случае нужен дополнительный третий пустой стакан. Последовательность действий будет следующей: 1) перелить из первого стакана в третий; 2) перелить из второго в первый; 3) перелить из третьего во второй. Цель достигнута! По аналогии для обмена значениями двух переменных нужна третья дополнительная переменная. Назовем ее Z. Тогда задача обмена решается последовательным выполнением трех команд присваивания (таб. 2.2). Аналогия со стаканами не совсем точна в том смысле, что при переливании из одного стакана в другой первый становится пустым. В результате же присваивания (Х: = Y) переменная, стоящая справа (Y), сохраняет свое значение. Алгоритм для деления дробей имеет линейную структуру. В нем все команды выполняются в строго однозначной последовательности, каждая по одному разу. Линейный алгоритм составляется из команд присваивания, ввода, вывода и обращения к вспомогательным алгоритмам. При описании алгоритмов в блок-схемах типы, как правило, не указываются (но подразумеваются). В алгоритмах на АЯ для всех переменных типы указываются явно. Описание типов переменных производится сразу после заголовка алгоритма. В них используются следующие обозначения типов: цел - целый тип, вещ - вещественный тип, лит - символьный (литерный) тип, лог - логический тип. В алгоритме для деления дробей для всех переменных указан целый тип.

3. Ветвления и циклы в вычислительных алгоритмах

Составим алгоритм решения квадратного уравнения

Задача хорошо знакома из математики. Исходными данными здесь являются коэффициенты а, b, с. Решением в общем случае будут два корня x1 и х2, которые вычисляются по формуле:

Все используемые в этой программе величины вещественного типа (см. рис. 8). Слабость такого алгоритма видна невооруженным глазом. Он не обладает важнейшим свойством, предъявляемым к качественным алгоритмам, — универсальностью по отношению к исходным данным. Какими бы ни были значения исходных данных, алгоритм должен приводить к определенному результату и завершать работу. Результатом может быть число, но может быть и сообщение о том, что при определенных данных задача решения не имеет. Недопустимы остановки в середине алгоритма из-за невозможности выполнить какую-то операцию. Упомянутое свойство в литературе по программированию называют результативностью алгоритма (в любом случае должен быть получен какой-то результат). Чтобы построить универсальный алгоритм, сначала требуется тщательно проанализировать математическое содержание задачи. Решение уравнения зависит от значений коэффициентов a, b, с. Вот анализ рассмотренной выше задачи (ограничиваемся только поиском вещественных корней):

если a = 0, b = 0, с = 0, то любое х - решение уравнения; если а = 0,b = 0, с ≠ 0,то уравнение действительных решений не имеет; если а = 0, b ≠ 0, то это линейное уравнение, которое имеет одно решение х = -с/b; если a ≠ 0 и d = b2- 4ас ≥ 0, то уравнение имеет два вещественных корня (формулы приведены выше); если а ≠ 0 и d < 0, то уравнение не имеет вещественных корней.

Блок-схема алгоритма приведена на рис. 9. Этот же алгоритм на алгоритмическом языке представлен на рис. 10.

В этом алгоритме многократно использована структурная команда ветвления. Общий вид команды ветвления в блок-схемах и на алгоритмическом языке представлен на рис. 11. Вначале проверяется условие (вычисляется отношение, логическое выражение). Если условие истинно, то выполняется серия 1 - последовательность команд, на которую указывает стрелка с надписью «да» (положительная ветвь). В противном случае выполняется серия 2 (отрицательная ветвь). В АЯ условие записывается после служебного слова если, положительная ветвь — после слова то, отрицательная — после слова иначе. Буквы кв обозначают конец ветвления. Если на ветвях одного ветвления содержатся другие ветвления, то такой алгоритм имеет структуру вложенных ветвлений. Именно такую структуру имеет алгоритм «Корни квадратного уравнения». Рассмотрим следующую задачу: дано целое положительное число п. Требуется вычислить n! (n-факториал). Определение факториала:

На рис. 4 приведена блок-схема алгоритма. В нем используются три переменные целого типа: п - аргумент; i - промежуточная переменная; F - результат. Для проверки правильности алгоритма построена трассировочная таблица. В такой таблице для конкретных значений исходных данных по шагам прослеживается изменение переменных, входящих в алгоритм. Данная таблица составлена для случая п = 3 (табл. 3). Трассировка доказывает правильность алгоритма. Алгоритм на алгоритмическом языке (рис. 12). Этот алгоритм имеет циклическую структуру. В алгоритме использована структурная команда цикл-пока, или цикл с предусловием. Общий вид команды цикл-пока в блок-схемах и в АЯ на рис. 13.