Лекция "Алгоритмы линейной, разветвляющийся, циклической структуры"
план-конспект урока

Разработка алгоритма решения задачи.

Решение любой конкретной задачи предполагает обработку разнообразной информации о реальных объектах. Например, при решении задачи о начислении зарплаты сотрудникам фирмы объектами задачи могут быть: табельный номер сотрудника, его фамилия, имя, отчество, оклад, отработанное время и т.д. При решении системы алгебраических уравнений необходимой информацией являются значения коэффициентов уравнений и их правых частей.

Любая информация, представленная в формализованном виде и пригодная для обработки, называется данными. Организация данных, обеспечивающая определенные связи и соотношения между ними, называется структурой данных.

Существуют линейные и нелинейные структуры данных. К линейным структурам можно отнести: константы, переменные и массивы. Нелинейные структуры данных – деревья и графы. Рассмотрение нелинейных структур данных выходит за рамки данной книги.

Константами называются данные, которые в период реализации алгоритма не изменяют своего значения.

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

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

Массивом называется множество упорядоченных однотипных данных, объединенных одним именем. Массивы характеризуются: именем, размерностью и типом данных, которые хранятся в данном массиве. Так, можно говорить о массиве символов, массиве целых чисел, массиве действительных чисел. Имя массива – уникальный набор символов, которые входят в алфавит языка программирования. Размерность массива – максимально допустимое число элементов массива. В памяти ЭВМ данные, образующие линейную структуру массива, хранятся в виде списка последовательно, одни за другими. Для определения положения элемента массива среди остальных необходимо задать значение индекса массива. В зависимости от количества индексов массивы бывают одномерными (один индекс)  двумерными – два индекса, трехмерными – три индекса и т.д.

Например, одномерный массив целых числе под именем N размерностью 46, описанный на языке BASIC как DIM N(45), можно схематично представить следующим образом.

Запись DIM N(45) означает, что под именем Nв памяти ЭВМ предусмотрено место для записи до 46 чисел (элементов массива). N(0), N(1), …, N(I), …, N(45) – имена переменных, используя которые, можно организовать хранение, поиск и обработку соответствующих данных. Доступ к каждому из элементов массива осуществляется по имени и значению индекса массива. Например, после выполнения команды А =  N(45) + N(2) переменной А будет присвоено значение, равное 3 + 0 =3.

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

Двумерный массив размерностью 12 (3 строки и 4 столбца) описывается на языке BASIK как DIM ST(2, 3). Схематично формирование условных адресов элементов массива можно представить следующим образом:

Этапы решения задачи на ЭВМ

Подготовка любой задачи к решению на ЭВМ состоит из нескольких этапов.

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

Первый этап – четкая формулировка задачи, выявление исходных данных, необходимых для ее решения.

Второй этап – разработка математической модели решаемой задачи.

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

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

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

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

Шестой этап – собственно программирование, то есть то есть запись разработанного алгоритма на языке программирования. Вопросы выбора подходящего языка здесь не рассматриваются.

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

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

Универсальная программа должна уметь обрабатывать ошибки, которые могут возникнуть в процессе обработки информации.

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

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

3. Некоторые простые приемы позволяют повысить эффективность программы ( то есть уменьшить количество выполняемых  операций и время работы программы). К таким приемам относятся:

• Использование операций умножение вместо возведения в степень ( = XX  X);
• Если некоторое арифметическое выражение встречается в вычислениях несколько раз, то его следует вычислить заранее и хранить в памяти ЭВМ, а по мере необходимости использовать;
• При организации циклов в качестве границ индексов использовать переменные, а не выражения, которые вычислялись бы при каждом прохождении цикла;
• Особое внимание обратить на организацию циклов, убрав из них все повторяющиеся с одинаковыми данными вычисления  и выполняя их до входа в цикл.

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

        Седьмой этап – тестирование, отладка и исправление обнаруженных ошибок.

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

      Далее даются некоторые рекомендации по тестированию и отладке.

1. Необходимо проверить работу программы (или отдельных ее частей)   вручную до выхода на компьютер.
2. Проводить тестирование и отладку нужно отдельно для логически самостоятельных частей программы.
3. При отладке программы необходимо использовать существующие средства в трансляторах алгоритмических языков.
4. При тестировании программы обычно используется минимально необходимый объем данных.

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

3.2. Алгоритм и его свойства

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

     Каждый алгоритм должен обладать следующими основными свойствами:

1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательность простых шагов. При этом для выполнения каждого шага алгоритма требуется некоторый конечный отрезок времени, то есть преобразование исходных данных в результате осуществляется во времени дискретно.
2. Определенность. Это свойство  состоит в том, что каждая команда алгоритма должна быть четкой, однозначной и не оставлять места для произвола.
3. Конечность. Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.
4. Массовость. Это свойство состоит в том, что алгоритм решение задачи  разрабатывается не для одной конкретной задачи, а для целого класса однотипных задач, различающихся лишь исходными данными.

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

Разработанный алгоритм можно зафиксировать несколькими способами, например:

• На естественном языке;
• В виде схемы (блок – схемы);
• На специальном языке (алгоритмическом языке).

3.3 Способы записи алгоритмов

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

Пример 3.1: Разработать алгоритм вычисления функции вида:

Y = (7  X – 4) / (5  X + 3).

Этап 1. Математическое описание решения задачи. Оно представлено в условии задачи.

Этап 2. Определение входных и выходных данных. Следую математическому  описанию, входным данным является аргумент функций x, выходным данным (результатом вычислений) – значение функции y.

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

1. Начало алгоритма.
2. Ввод значений X.

Обработка данных – вычисление значения y по формуле:

Y : = (7x – 4) / (5x + 3).

3. Вывод результата вычислений y.
4. Конец алгоритма

Перечисленная последовательность действий является алгоритмом решения задачи. Символ «:=» означает действие присваивания, которое соответствует тому, что значение выражения, стоящее с правой стороны от символа, вычисляется и присваивается величине, записанной с лева от символа.

Описание  алгоритма на соответствующем языке состоит из перечня действий (шагов), каждый из которых имеет порядковый номер. Алгоритм должен выполняться последовательно шаг за шагом. Если в тексте алгоритма написано «перейти к шагу с номером N», то это означает, что выполнение алгоритма продолжится с указанного шага с номером N. Словесное описание алгоритмов применяют при решении не сложных задач, но оно малопригодно для представления сложных алгоритмов из-за отсутствия наглядности.

Описание алгоритмов в виде схем. Для обозначения шагов решения, в виде схемы алгоритма, используются специальные обозначения (символы). Печень наиболее часто употребляемых символов приведен в таблице 3.1. Для задачи  3.1 алгоритм в виде схемы представлен на рис. 3.2.

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

                                                                                                              Таблица 3.1

Схема алгоритмов и программ

Рис. 3.1 обобщенная схема                                                                                                                                алгоритма  обработки данных                                       Рис. 3.2. Схема алгоритма для

                                                                                               Задачи 3.1.

3.3.1. Алгоритмы линейной структуры

Алгоритмы линейной структуры  (см. задачу 3.1.) состоят из последовательности определенных алгоритмом действий. Например, ввод значения x, вычисление значения y и вывод результата вычисления y.

Пример 3.2: Вычислить высоту треугольника, опущенную на сторону а, по известным значениям длин его сторон  a, b, c.

Этап 1. Математическое описание решения задачи. Площадь треугольника можно вычислить по формуле

 S =   /2                                                                                   (3.1)

или по формуле  Герона

 S =     ,                                           (3.2)

где    – высота, опущенная на сторону а;     - длины сторон    , b, c  соответственно;  ( p =  +  +  ) /2  - полупериметр треугольника.

Из выражений (3.1) и (3.2) получим формулу для вычисления высоты треугольника:

 = 2    /                                      (3.3)

Формула (3.3) является математическим описанием решения задачи.

Этап 2. Определение входных и выходных данных. Входными данными, исходя из условия задачи, являются значение высоты треугольника, опущенной на сторону а. Кроме того, как следует из математического описания, потребуется вычислить значение вспомогательной  величины – полупериметра треугольника.

Этап 3. Разработка алгоритма решения. Введем обозначения: LA – длина стороны  ; LB – длина стороны ; LC – длина стороны ; P – полупериметр треугольника; HA – длина высоты, опущенной на сторону a.

Словесное  описание алгоритма решения:

1. Начало алгоритма.

2. Ввод исходных данных – LA, LB, LC.

3. Вычисление полупериметра  треугольника

P = (LA  + LB +LC) /2.

4. Вычисление высоты треугольника, опущенной на сторону a:

  HA: =  .

5. Вывод результата вычисления на печать.

6. Конец алгоритма.  

Описание алгоритма в виде схемы представлено на рис 3.3.

                           Рис. 3.3 Схема алгоритма для задачи 3.2

3.3.2. Алгоритм разветвляющейся структуры

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

Пример 3.12: Разработать алгоритм нахождения действительных корней квадратного уравнения  +  + c = 0. Если действительных корней нет, то выдать соответствующее сообщение.

Этап 1. Математическое описание решения задачи. Из курса математики известно, что такое уравнение имеет два корня, которые вычисляются  по формулам:

 = ;   =,

Где  и - первый и второй корни уравнения соответственно; D = 4ac – дискриминант уравнения.

Уравнение имеет действительные корни, если дискриминант больше или равен 0  (D  0).

Этап 2. Определение входных и выходных данных. Входными данными являются коэффициенты уравнения  a, b, с, выходными данными – значения корней уравнения или сообщение об отсутствии действительных корней. Для вычисления корней уравнения необходимо знать дискриминант уравнения.

Этап 3. Разработка алгоритма решения. Введем обозначения: A, B, C – коэффициенты уравнения, соответствующие  a, b, и с; X1, X2 – первый и второй корни уравнения; D – дискриминант уравнения.

Словесное описание алгоритма решения:

1. Начало алгоритма.

2. Ввод значений A, B, C.

3. Вычисление дискриминанта D: =  - 4 * А * С.

4. Если дискриминант D  0, то перейти к шагу 5, иначе – к шагу 7.

5. Вычисление значений корней

 = ;   =.

6. Вывод значений X1 и X2 на печать, переход к шагу 8.

7. Вывод сообщения: «Дискриминант уравнения меньше нуля».

8. Конец алгоритма.

В разработанном алгоритме имеются две ветви: одну ветвь составляют шаги 5 и 6 другую – шаг 7.  Выбор ветви определяется по значению дискриминанта на шаге 4. Здесь неравенство D0 является условием, определяющим порядок выполнения шагов (ветвей) алгоритма.

Схема алгоритмов (рис. 3.4) имеет специальные обозначения для выделения условий и порядка выполнения алгоритма, в зависимости от выполнения условий.

В схеме алгоритма ( рис. 3.4) для обозначения условия использован символ «решение» ( см. табл. 3.1) для элемента с номером 4. Если условие (неравенство), записанное внутри символа «решение», удовлетворяется при данном значении дискриминанта, то следующими выполняются элементы 5 и 6. Это следует из того, что они соединены с элементом 4 линией с надписью «ДА». Если условие в элементе 4 не удовлетворяется, то следующим выполняется элемент 7 (он соединен с элементом 4 линией с надписью «НЕТ»).

Массивы

Понятие массива.

Часто в технике, науке и жизни используются не отдельные числа и величины, а множества связанных однородных величин. Так, дата – это совокупность трех величин, например 19, 11, 01. С листом бумаги связывается  2 числа – длина и ширина, например 250 *170 мм, с чемоданом три – длина, ширина, высота, 500*300*150. Многочлену =  + + +2x+3 определяется совокупностью из пяти чисел – коэффициентов: 7,4,5,2,3.  Несложно представить другие множества связанных однородных величин  с шестью, семью элементами и более. Такие множества широко используются и в информатике, где они называются массивами.

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

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

Различают разные виды массивов в зависимости от их внутреннего строения, временного расположения элементов.

Массивы, элементы которых располагаются строго последовательно, называются одномерными. (3, 4, 2, 8).    

Каждый  подобный массив определяется именем и числом элементов  и обозначаются T(1,n).

где  T- имя массива.

n- число элементов массива, например А(1;4)

Одномерные массивы

1. Найти сумму всех элементов таблицы B (1:10) (5, -1, 3, -4, 6, 2, -3, 7, 8, -5).

I. Этап Математического описания.

В качестве параметра цикла можно взять номер члена таблицы тогда начальное значение параметра равно 1, конечное значение 10, шаг цикла 1.

II. Вход - B (1:10); выход – S.

III. Разработка алгоритма. Введем обозначение S – значение суммы элементов в таблице, I – номер очередного члена таблицы ( параметр цикла). BI – элемент таблицы под номером  I.

Словесное описание.

1. Начало алгоритма.

2. Ввод B(1:10).

3. Подготовка цикла S: = 0; I = 1.

4. Накопление суммы  S: = S + BI.

5. Вычисление следующего значения параметра цикла i: = I + 1.

6. Если I10, то к ш.4, иначе – к ш. 7.

7. Вывод значения S.

8. Конец алгоритма.

Найти сумму квадратов элементов таблицы А(1:50).

1. Начало.

2. Ввод А (1:50)

3. S: = 0; i: = 1.

4. S: = S + Ai Ai

5. i: = i + 1

6. Если i 50, то к ш. 4, иначе к ш. 7.

7. Вывод S.

8. Конец.

Найти сумму положительных элементов таблицы К(1:100).

1. Начало.

2. Ввод К(1:100)

3. S: = 0; i: = 1.

4. Если i100, то к ш. 5, иначе к ш.8.

5. Если  к 0, то к ш. 6, иначе к ш. 7.

6. S: = S+ к .

7. i: =  + 1.переход к шагу 4.

8. Конец.

Найти сумму положительных элементов таблицы К(1:100).

Найти сумму элементов меньших 3,A(1;1000)

A

Заменить отрицательные элементы таблицы A(1;100) числом 5.

Заменить элементы табл. A(1:100) меньше двух единицей, а остальные нулями. Новую табл. Назвать B(1;100).

Ведомость представляет собой множество из 12 обязанных м/у собой однородных величин – это тоже пример массива. Но элементы ее расположены в четыре строки и три столбца.

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

    В математике подобные массивы называют матрицами.

    Каждый двумерный массив определяется именем, числом строк и столбцов и обозначается: T (1:m, 1:n) где T имя массива; m(n)- число строк (столб)

      Нашу ведомость можно обозначить так: B(1:4, 1:3), те как массив B из 4 строк  и 3-сталбцов.

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

         [ Каждый элемент двумерного массива определяется по мерам строки и столбца , на пересечении которых он находится, и в соответствии, с этим обозначаются именем массива с двумя индексами  первый-номер,  указанной строки, второй-номер столбца]. П.Р  , .

     Элементы нашей ведомости получат такие обозначения:

 B(1:4; 1;3)=  =       

Т.е. =5, =45…

Как одномерные, двумерные массивы м.б. не только числовыми, но и текстовыми.

Рассмотрим теперь меню школьной столовой.

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

В (1;4) = {   }={борщ, ...,}

С (1;4) = { ,…,} = {     }

Как представляется массив в ЭВМ?

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

Пример:  D (1;10;1;20) – потребляется 200 мик памяти.

                P (1: 100, 1:10) – 1000 мик.

Задача 1: Задан массив В (1:4). Каждому элементу массива присвоить значение значение соседнего с ним справа. Последнему элементу присвоить значение первого.

Решение:

Входные данные: В(1:4) = {  

Выходные данные: массив В(1:4)

(новые ячейки не требуются, т.к. меняется только содержимое исходных ячеек.

Пример: имеются четыре клетки с кроликами

   D                                            

1. Потребуются свободные ячейки, поэтому ведем исходную величину D и первая операция будет такая: D = , т.е. значение  переносим в свободную ячейку.
2. =

     =

      =

3.  = D