Глава 1. Понятие алгоритма, базовые алгоритмические констркуции

E-mail Печать PDF
Рейтинг пользователей: / 17
ХудшийЛучший 
Индекс материала
Глава 1. Понятие алгоритма, базовые алгоритмические констркуции
1.2. Свойства алгоритма
1.3. Способы записи алгоритмов
1.4. Базовые алгоритмические конструкции
1.4.1. Линейные алгоритмы
1.4.2. Разветвляющиеся алгоритмы
1.4.3. Циклические алгоритмы
1.4.4. Итерационные циклы
1.4.5. Вложенные циклы
1.4.6. Использование рекуррентной формулы
1.5. Тестирование алгоритма
Все страницы

Глава 1. Понятие алгоритма.
Базовые алгоритмические конструкции

1.1. Определение алгоритма

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

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

Пример 1.1

Алгоритм определения площади трапеции:

Дано: a, b - длины сторон трапеции, h - высота.

Найти площадь трапеции.

Математическая модель:

S = (a + b) ? h/2.

1.     Задать числовые значения a, b, h.

2.     Сложить a и b. Результат обозначить y.

3.     Умножить y на h. Результат обозначить p.

4.     Разделить р на 2. Результат обозначить S.

5.     Записать в качестве ответа значение S.

6.     Конец.

Данный алгоритм рассчитан на человека, который может выполнить указанные действия. У каждого исполнителя имеется перечень команд, который называют системой команд исполнителя. Понятно, что, составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его системе команд.

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

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


1.2. Свойства алгоритма

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

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

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

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

Массовость. Разработанный  алгоритм должен давать возможность получения результата при различных исходных данных для однотипных задач.

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

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

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

Если решить задачу при заданных значениях исходных данных за конечное число шагов не удается, то говорят, что алгоритм «зацикливается».

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

 

Пример 1.2

Составить алгоритм решения уравнения вида ax = b, где a и b - произвольные числа.

Дано: а, b - произвольные числа.

Найти x - корень уравнения ax = b.

Математическая модель:

x = b/a при a ? 0;

x - любое число при a = 0 и b = 0;

решений нет при a = 0 и b ? 0.

Алгоритм решения задачи можно представить схематично:

 

 

Запишем алгоритм так, как мы писали его раньше.

1.     Задать числовые значения a, b.

2.     Если a ? 0, то x = b/a. Перейти к п. 5.

3.     Если b = 0, то x - любое число. Перейти к п. 6.

4.     Если b ? 0, то решений нет. Перейти к п. 6.

5.     Записать в качестве ответа значение x.

6.     Конец.

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

1.     Выделить величины, являющиеся исходными данными для задачи.

2.     Разбить решение задачи на такие команды, каждую из которых исполнитель может выполнить однозначно.

3.     Указать порядок выполнения команд.

4.     Указать признак окончания процесса решения задачи.

5.     Указать, что является результатом решения задачи в каждом из возможных случаев.


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

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

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

Запишем алгоритм поиска максимального из двух чисел a и b.

1.     Задать числовые значения a и b.

2.     Если a > b, то max присвоить значение a, иначе max = b.

3.     Записать в качестве результата значение max.

4.     Конец.

Правильность алгоритма можно проверить, если выполнить его формально «вручную».

Номер этапа

a

b

max

Пояснение

1

8

16

-

Задаем числовые значения a, b

2

8

16

-

8 > 16 - неверно, следовательно,  max = 16 (выбираем действие после слова иначе)

3

8

16

16

Записываем ответ: max = 16

 

Номер этапа

a

b

max

Пояснение

1

8

3

-

Задаем числовые значения a, b

2

8

3

-

8 > 3 - верно, следовательно,  max = 8

3

8

8

16

Записываем ответ: max = 8  (выбираем действие  после слова то)

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

Когда запись алгоритма формализована частично, то используется псевдокод. Он содержит как элементы естественного языка, так и формальные конструкции, описывающие базовые алгоритмические структуры. Эти конструкции называются служебными словами Формального определения псевдокода или строгих правил записи алгоритмов в таком формате не существует.

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

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

Итак, алгоритм, записанный на учебном алгоритмическом языке, имеет следующую форму:

алг название алгоритма (арг список исходных данных; рез список результатов)

нач

    описание промежуточных величин

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

кон

Запишем задачу нахождения наибольшего из двух чисел a и b с использованием псевдокода.

алг Нахождение наибольшего (арг a, b; рез max)

нач

    ввод a, b

Если a > b

то max = a

иначе max = b

Все если

вывод max

кон

В дальнейшем мы будем использовать этот язык для записи алгоритмов в силу его простоты и наглядности.

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

Отдельные блоки соединяются линиями потоков информации. Направление линий сверху вниз или слева направо принимается за основное (см. табл. 1).

Алгоритм, записанный на языке программирования, называется программой. При использовании этих языков запись алгоритма совершенно формальна и пригодна для выполнения на ЭВМ. Отдельная конструкция языка программирования называется оператором. Программа - это упорядоченная последовательность операторов.

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

В записи алгоритма команда ввода выглядит так:

ввод < список переменных >

Пример: ввод а, b, c.

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

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

вывод < список вывода >.

Пример: вывод a, b, c.

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

< переменная > = < выражение >

Знак «=» читается «присвоить».

Например, y = 5 читается «переменной y присвоить значение 5». После выполнения команды присваивания значение переменной, записанной слева от знака «=», становится равным значению выражения, записанного справа от знака «=».

Таблица 1

Изображение основных блоков на блок-схеме

Обозначение блока

Пояснение

Процесс (вычислительное действие, реализованное операцией присваивания)

Решение (проверка условия, реализующая условный переход)

Начало, конец алгоритма

Ввод исходных данных, вывод результатов

Модификация (для организации циклов с параметром)

Примеры команд присваивания: x = 1/2; z = a + b; k = 2 * k.

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

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

2.     Переменной присваивается новое вычисленное текущее значение. При этом предшествующее значение переменной стирается из памяти компьютера.

Следовательно, команда k = 2 * k означает, что значение переменной k, хранящее в ячейке памяти, увеличивается в 2 раза и полученный результат становится новым текущим значением переменной k.


1.4. Базовые алгоритмические конструкции

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

Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:

  • следование;
  • ветвление (в полной и сокращенной форме);
  • цикл (с предусловием или постусловием).

Характерной особенностью этих структур является наличие у них одного входа и одного выхода.


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

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

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

 
 

Решение. В алгебраической форме решение задачи выглядит следующим образом:

Исходными данными являются четыре целые величины: a, b, c, d. Результат  - два целых числа m и n.

Алг
арг
рез
нач




кон

Деление дробей   

a, b, c, d; 

n, m

ввод a, b, c, d

m = a * d

n = b * c

Вывод  «числитель» , m

Вывод  «знаменатель», n

Пример 1.4.  Построить блок-схему алгоритма вычисления высот треугольника со сторонами a, b, c по формулам:

;

;

,

где  - полупериметр.

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

Ввести численные значения сторон треугольника.

 

Вычислить полупериметр.

 

Вспомогательная величина t.

 

Вычислить высоты, опущенные на стороны а, b, c.

 

 

Вывести результаты.

 


1.4.2. Разветвляющиеся алгоритмы

Второй базовой структурой является ветвление. Эта структура обеспечивает, в зависимости от результата проверки условия, выбор одного из альтернативных путей работы алгоритма, причем каждый из путей ведет к общему выходу (структура ЕСЛИ-ТО-ИНАЧЕ). В частном случае может оказаться, что для одного из выбранных путей действий предпринимать не надо. Это структура ЕСЛИ-ТО.

Структура с полным ветвлением записывается так:

Если < условие >

то < серия 1 >

иначе < серия 2 >

Все если

Команда выполняется так: если <условие> является истинным, то выполняется <серия 1>команд, записанная после ключевого слова то, если <условие> является ложным, то выполняется <серия 2> команд, записанная после слова иначе.

Структура с неполным ветвлением не содержит части, начинающейся со слова иначе:

Если < условие >

то < серия 1 >

Все если

Команда выполняется так: если <условие> является истинным, то выполняется <серия 1>команд, записанная после ключевого слова то.

Блок-схема алгоритма с ветвлением выглядит так:

Полное ветвление
Структура Если - То - Иначе

Неполное ветвление
Структура Если - То

Пример 1.5. Вычислить y = |x| по формуле

 
 

Решение. Решение задачи выглядит так:

Алг
арг
рез
нач





кон

Модуль

x

y

ввод x

Если x > 0

    то y = x

    иначе y = - х

Все если

вывод y

 


1.4.3. Циклические алгоритмы

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

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

 

 

нц

Пока Р повторять

          S

кц

Если условие Р не выполняется, то происходит выход из цикла на команду, записанную после строки «конец цикла». Здесь условие Р - это условие на продолжение цикла.

Возможен другой случай, когда тело цикла S выполняется по крайней мере один раз и будет повторяться до тех пор, пока не станет истинным условие Р. Такая организация цикла, когда его тело расположено перед проверкой условия Р, называется циклом с постусловием или циклом «до».

 

нц

До S

Пока не Р

кц

Третий вид циклов - цикл с параметром. Тело цикла S выполняется, пока целочисленный параметр цикла i пробегает множество значений от начального (In) до конечного (Ik).

Переменная i определяет количество повторений тела цикла S. Если шаг изменения значения параметра цикла обозначить через Di, то количество повторений тела цикла n можно вычислить по формуле:

Очень часто в задачах с использованием такого цикла шаг изменения параметра цикла равен 1. Переменные i, In, Ik и Di обычно имеют целый тип.

 

нц

Для i от In до Ik повторять

      S

кц

Цикл выполняется так: начальное значение параметра цикла i равно In. Если i < Ik, выполняется тело цикла S, после чего параметр цикла увеличивается на 1 с помощью оператора присваивания i = i + 1 и снова проверяется условие i < Ik. Тело цикла выполняется до тех пор, пока значение i не превысит Ik.

Пример 1.6. Дано целое положительное число n. Вычислить факториал этого числа. Факториал любого целого положительного числа n определяется как произведение чисел от 1 до заданного числа n: n! = 1 2 3 ... n. По определению 0! = 1 и 1! = 1.

Решение. Задача решается с помощью циклического алгоритма. Введем следующие обозначения: N - заданное число, F - факториал числа, R - параметр цикла. Составим два варианта алгоритма: с применением цикла с предусловием и цикла с параметром.

Цикл с предусловием

Цикл с параметром

алг
нач

 

 

 

 

 

 

 

 

кон

Факториал 1 (арг N; рез F)
цел R

ввод N

F = 1

R = 1

нц

пока R < N повторять
        F = F * R
         R = R + 1
кц
вывод «Факториал =», F

алг

нач

 

 

 

 

 

 

 

кон

Факториал 2 (арг N; рез F)
цел R

ввод N

F = 1

нц

для от до повторять
        F = F * R

кц
вывод «Факториал =», F

       

 

Выполним алгоритм при n = 4.

Цикл с предусловием

 

Цикл  с параметром

R

R < N

F

 

R

R < N

F

1

Да

1?1 = 1

 

1

Да

1?1 = 1

2

Да

1?2 = 2

 

2

Да

1?2 = 2

3

Да

2?3 = 6

 

3

Да

2?3 = 6

4

Да

6?4=24

 

4

Да

6?4=24

5

Нет

-

 

5

Нет

-

Итак, при решении данной задачи выполнение цикла с предусловием ничем не отличается от выполнения цикла с параметром. При R = 5 произойдет выход из цикла и окончательное значение 4! = 24.

В чем же отличие? Посмотрим на структуру этих циклов. В цикле пока начальное значение параметра цикла R задается перед входом в цикл, в теле цикла организовано изменение параметра цикла командой R = R + 1, условие R < N определяет условие продолжение цикла. В цикле с заданным числом повторений эти же команды неявно заданы в операторе заголовка цикла.

Пример 1.7. Вычислить и вывести на печать положительные значения функции  при n = 1, 2, ..., 50.

В этой задаче количество повторений цикла заранее известно. Оно равно 50 и определяется значением переменной n. Следовательно, n является параметром цикла. Для каждого значения n следует вычислить значение y. Так как на печать требуется вывести только положительные значения переменной y, то внутри цикла будет проверка заданного условия.

 

Ввести значение х.

 

Заголовок цикла. Параметру цикла n присвоить начальное значение. Указать условие продолжения цикла.

 

В теле цикла вычислить значение функции y для каждого значения n от 1 до 50.

Если y имеет положительное значение, то напечатать.

 

 

Пример 1.8. Вычислить значение функции  при значениях аргумента x, которое изменяется в диапазоне от 0 до 3 с шагом 0,1.

В примере параметром цикла является аргумент x. Количество повторений тела цикла k = (3 - 0)/0,1 + 1 = 31.

В качестве параметра цикла с заданным числом повторений нельзя взять аргумент функции x, так как аргумент является вещественным числом. Обозначим параметр цикла буквой i, количество повторений параметра равно 31. Начальное значение переменной х задается только один раз, поэтому этот блок должен стоять вне тела цикла. В теле цикла вычислим значение функции y, полученное значение напечатаем. Для получения нового значения y нам необходимо изменять значение переменной x на величину шага.

 

Ввести значение коэффициента a.

 

Задать начальное значение аргумента х.

Параметр цикла i изменяется от начального значения, равного 1, до конечного значения, равного 31 с шагом 1. Он  определяет, сколько раз вычислялось значение y.

 

Напечатать полученное значение y и величину х, при котором оно было получено.

 

 

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


1.4.4. Итерационные циклы

В предыдущих примерах количество повторений в цикле заранее известно. Выход из цикла выполняется при достижении параметром цикла конечного значения.

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

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

Рассмотрим блок-схемы итерационных циклов на примерах.

Пример 1.9. Составить алгоритм проверки, является ли произвольное целое число степенью числа три или нет.

Задачу можно решить с использованием как цикла с предусловием, так и цикла с постусловием.

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

Пусть numb - произвольное число. В цикле будем вычислять значение вспомогательной переменной k, формируя в ней степень числа три. Как только для значения переменной k выполнится неравенство k ? numb, выйдем из цикла. Тогда если k = numb, то numb степень числа 3.

1.Ввести проверяемое число.

 

2.Вспомогательной переменной k присвоить значение 1.

 

3.Пока k < number выполнять цикл.

4.Формировать степень числа. 3. Переменной k присвоить значение, равное предыдущему, умноженному на 3.

5.По выходе из цикла проверить равенство значения k и введенного числа. Если значения равны, то number является степенью числа 3. Печатаем слово «Да» (блок 7). В противном случае печатаем слово «Нет» (блок 6).

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

Введем следующие обозначения: number - вводимые числа, sum - искомая сумма.

Построим блок-схему алгоритма, используя цикл  с предусловием.

До цикла начальное значение суммы равно нулю (sum = 0). Параметром цикла является вводимое число number, первое значение этого числа вводится до цикла. Операторы вычисления суммы и ввода нового значения number выполняются в цикле до тех пор, пока не будет введено значение number = 0. На этом выполнение цикла заканчивается и выводится вычисленное значение sum. Заранее нам неизвестно, сколько раз выполнится цикл (это зависит от того, когда будет введено нулевое значение), поэтому используем итерационный цикл.

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

Присвоить переменной sum нулевое значение.

 

Ввести число.

 

Если введенное число не равно нулю, то выполнить цикл. Если число равно нулю, то закончить цикл.

 

В теле цикла вычислить значение суммы.

 

Вывести полученное значение суммы.


1.4.5. Вложенные циклы

Рассмотрим понятие вложенного цикла на примере.

Пример 1.11. Дано 5 последовательностей, каждая из которых состоит  из 10 чисел. Требуется вычислить сумму чисел каждой последовательности.

Обозначим: number - очередное число; i - текущий номер последовательности; sum - сумма членов последовательности.

Алгоритм будет иметь циклическую структуру. Используем цикл с заданным числом повторений, так как 5 раз требуется вычислить одно и то же - сумму чисел каждой последовательности. Параметром цикла является переменная i. Начальное значение параметра равно 1, конечное значение - 5.

Составим укрупненную блок-схему алгоритма.

Параметр цикла i - номер очередной последовательности.

 

Тело вложенного цикла.

 

Переход к новой последовательности чисел.

 

Есть еще последовательности? Если есть, то продолжить выполнение цикла. Если нет, то закончить вычисления.

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

Выполним последовательное уточнение блок-схемы примера и составим детальную блок-схему.

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

Задание параметров внешнего цикла. Цикл выполняется 5 раз.

 

Обнуление начального значения суммы для каждой последовательности.

 

Задание параметра вложенного цикла. Этот цикл выполняется 10 раз.

 

Ввод очередного числа.

 

Суммирование числа

 

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

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

 

Итак, мы имеем два цикла. Параметром внешнего цикла является переменная i, которая изменяется от 1 до 5 с шагом 1. Она подсчитывает количество последовательностей. Во внешнем цикле для каждой новой последовательности обнуляется значение суммы sum и вычисленное значение sum печатается после окончания вложенного цикла. Во вложенном цикле параметром цикла является переменная j, которая посчитывает количество введенных чисел. Она меняется от 1 до 10 с шагом 1. Во внутреннем цикле вводится очередное значение числа (переменная number), это число прибавляется к текущему значению суммы. Когда все числа введены и просуммированы, осуществляется выход из внутреннего цикла.

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

Пусть в первой последовательности (i = 1) численные значения слагаемых number: 1, 2, 4, 6. Во второй последовательности (i = 2) находятся значения -10, 15, -25, 6. В третьей последовательности (i = 3) - 70, 150, -15, 9. Эти значения произвольны и могут быть любыми. Количество чисел в каждой последовательности одинаковое и равно 4.

Номер
последо-вательности

Номер шага

Номер числа

Начальное
значение
суммы

Значение числа

Значение
 суммы

Результат

r

s

number

s

i = 1

1

1

0

-1

0 - 1 = -1

Печать
 s = 11

2

2

2

-1 + 2 = 1

3

3

4

1 + 4 = 5

4

4

6

5 + 6 = 11

i = 2

6

1

0

-10

0 - 10 = -10

Печать
 s = -14

7

2

15

-10 + 15 = 5

8

3

-25

5 - 25 = -20

9

4

6

-20 + 6 = -14

i = 3

11

1

0

70

0 + 70 = 70

Печать
 s = 214

12

2

150

70 + 150 = 220

13

3

-15

220 - 15 = 205

14

4

9

205 + 9 = 214


1.4.6. Использование рекуррентной формулы

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

Пример 1.13. Вычислить с заданной точностью e функцию

Вычисления выполнить для любого значения х.

В этом примере требуется вычислить сумму слагаемых, количество которых заранее неизвестно, т.е. алгоритм будет итерационным. Вычисления закончатся, как только очередное слагаемое станет меньше заданной точности e. Точность вычисления слагаемого может принимать различные значения, например, e = 0,1; e = 0,01; e = 0,001;...

Обозначим: slag - значение слагаемого, n - номер слагаемого, y - значение суммы.

Построим рекуррентную формулу, связывающую текущее и предыдущее значение слагаемых. Текущее значение слагаемого  предыдущее значение

Отношение слагаемых

Таким образом, если было вычислено значение слагаемого на n-1-м шаге, то очередное слагаемое на n-м шаге получается умножением полученного значения на величину x/n. Обозначим значение слагаемого  на этом шаге также через slag, тогда из последнего соотношения можно вывести рекуррентную формулу slag = slag ? x/n.

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

Параметром цикла в обоих случаях будет значение переменной n, так как значение слагаемого зависит от номера слагаемого. Присвоим начальные значения: n = 1, так как вычисления начинаются с первого слагаемого; slag = 1, так как слагаемое вычисляется как произведение; y = 1, исходя из условия задачи.

Блок-схема, использующая цикл с предусловием.

 

Ввод значения х и точности вычислений eps.

 

1. Присваивание начального значения суммы, произведению. Первый шаг вычисления.

 

2. Точность не достигнута? Если «да», то продолжаем выполнение цикла.

 

3. Увеличение номера слагаемого

 

 

4. Вычисление очередного слагаемого.

 

 

5. Суммирование слагаемого.

 

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


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

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

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

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

При использовании структурного тестирования для построения тестовых наборов данных возможно использование следующих критериев:

1) набор данных должен обеспечивать выполнение каждого оператора, по крайней мере, один раз;

2) тестовые наборы данных в узлах ветвления с более чем одним условием должны обеспечивать принятие каждым условием значения истина или ложь хотя бы по одному разу;

3) тестовые наборы данных в узлах ветвления с более чем одним условием должны обеспечивать перебор всех возможных сочетаний значений условий в одном узле ветвления.

Рассмотрим пример простого алгоритма.

Пусть требуется вычислить значение выражения  Блок-схема вычисления этого выражения выглядит так:

При построении тестов с помощью первого критерия достаточно проверки алгоритма на тестах:

1) a = 1, b = 4;

2) a = 1, b = 6.

Заметим, что в этих тестах ни разу не был рассмотрен случай, когда  a равно нулю.

При построении тестов с помощью второго критерия можно использовать следующий набор тестов:

1) a = 1, b = 6;

2) a = 0, b = 1.

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

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

1) a = 1, b = 4;

2) a = 0, b = 4;

3) a = 1, b = 6;

4) a = 0, b = 6.

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

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

Входное условие

Классы эквивалентности

правильные

неправильные

а не должно быть равно 0

а <> 0

а = 0

 

b находится в диапазоне от -5 до 5

-5 ? b ? 5

b < -5; b > 5

 

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

1) a = 0, b = 6;

2) a = 1, b = -7.

1.6. Вопросы для самоконтроля

1. Дайте определение алгоритма.

2. Перечислите свойства алгоритма.

3. Как определяется свойство массовости алгоритма? Если алгоритм позволяет решить одну задачу, обладает ли он свойством массовости?

4. Для чего используется свойство детерминированности алгоритма? Может ли алгоритм быть недерминированным?

5. Когда алгоритм теряет свойство результативности?

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

7. Что значит зацикливание алгоритма?

8. Можно ли считать, что программа - это один из способов записи алгоритма?

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

10. Перечислите формы записи алгоритма.

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

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

13. Что такое псевдокод? Для каких целей он используется?

14. Чем отличается программный способ записи алгоритмом от других способов?

15. Назовите три базовые алгоритмические структуры.

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

17. Для чего используется базовая структура ветвление? Какие варианты этой структуры существуют?

18. Для каких целей используются циклы?

19. Дайте определение цикла с заданным числом повторений. Когда целесообразно применять циклы с заданным числом повторений?

20. Что такое итерационные циклы. Когда возникает необходимость в их использовании?

21. Как реализуется цикл с предусловием?

22. Как реализуется цикл с постусловием?

23. Определите основные отличия между циклами с постусловием и предусловием. Как они выполняются?

24. Что такое вложенные циклы?

25. Что такое итерационные циклы? Для решения каких задач они используются?

26. Что называется рекуррентной формулой? Для решения какого класса задач ее следует применять?

27. Что такое тестирование алгоритма,  для какой цели оно используется?

28. Какие виды тестирования алгоритма существуют?

29. Когда используется структурное тестирование алгоритма? Перечислите правила составления тестовых наборов данных для этого вида тестирования.

30. Что такое функциональное тестирование алгоритма, когда оно используется? Как разбить входные наборы данных на классы эквивалентности?

 

Добавьтe Ваш комментарий

Ваше имя (псевдоним):
Ваш адрес почты:
Заголовок:
Комментарий:

Комментарии

Интересное




Похожие материалы

Партнёры