Вопрос №19 Структурные части алгоритма. Линейная часть, разветвление и цикл.

Основными алгоритмическими структурами являются - следование, ветвление(развилка) и цикл

Ниже приведены графические обозначения на блок-схемах.

Структура “следование”	Полное ветвление	Неполное ветвление
Цикл с предусловие (цикл ПОКА)	Цикл с постусловием (цикл ДО)	Цикл с параметром

На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.

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

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

Ветвление

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

Циклы

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

Вопрос №20 Стандартные алгоритмы. Действия с целыми числами. Суммирование и умножение. Вычисление многочлена по схеме Горнера.

Алгоритм Евклида

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

Описание алгоритма:

1. Если a = b, то НОД = a = b и заканчиваем вычисления.

2. Если a > b, то из a вычитаем b ( ). Переходим к 1.

3. Если же b > a, то из b вычитаем a ( ). Переходим к 1.

Схема Горнера

Рассмотрим еще один важный пример функции на последовательности. Пусть дана последовательность коэффициентов многочлена p(x) по убыванию степеней:

p(x) = a₀xⁿ +a ₁x^n-1 + ... + a_n

Нужно вычислить значение многочлена в точке x = t. Алгоритм, основанный на просмотре последовательности коэффициентов в направлении от старшего к младшему, называется схемой Горнера. Проиллюстрируем его идею на примере многочлена третьей степени:

p(x) = ax³+bx²+cx+d

Его можно представить в виде

p(x) = ((ax+b)x+c)x+d

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

p(x) = (...((a₀x+a₁)x+a₂)x+...+a_n-1)x+a_n.

Обозначим через p_k(x) многочлен k-ой степени, вычисленный по коэффициентам a₀, a₁, ..., a_k:

p_k(x) = a₀x^k + a₁x^k-1 + ... + a_k.

Тогда

p_k+1(x) = p_k(x)x + a_k+1

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

Выпишем алгоритм:

вещ алгоритм схема Горнера(вх: цел n, вещ a[n+1], вещ t)

| дано: n -- степень многочлена

| a[n+1] -- массив коэффициентов многочлена по

| убыванию степеней

| надо: вычислить значение многочлена в точке t

начало алгоритма

| вещ p; цел i;

| p := 0.0; // Инициализация значения многочлена

| i := 0;

| цикл пока i <= n

| | p := p * t + a[i]; // Вычисление нового значения по

| | // старому значению и добавленному коэффициенту

| | i := i + 1;

| конец цикла

| ответ := p;

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