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

Алгоритм — это последовательность допустимых для некоторого исполнителя действий, направленная на достижение определенной цели”.

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

а) если X имеет вид аР, где Р — любое слово над данным алфавитом, то Y = Pb;

б) если X имеет вид bаР, где Р — любое слово над данным алфавитом, то Y = Paba.

Сам алгоритм выглядит так:

алг Слова (арг сим Х, рез сим Y)

нач

Y := X;

начинающееся буквосочетанием bb,

применить к слову Y то действие,

которое можно применить,

и результат обозначить снова Y;

кц

вывод Y

— стереть с доски два числа и вместо них написать одно, равное их сумме, увеличенной на 1;

— сосчитать количество чисел на доске;

— сравнить два натуральных числа.

Рассмотрите следующий алгоритм.

алг Суммирование+

нач

нц пока (на доске более одного числа)

и вместо них записать их сумму,

увеличенную на 1

кц

кон

б) Будет ли этот алгоритм однозначным?

нач цел K

ввод N

S := 0

S := S + K

кц

вывод S

б)

нач

А := С + " " + "goes to school."

B := "Does" + " " + С + " " + Часть (А, 1, 2) + Часть (А, 5, 10) + "?"

вывод А, В

кон
Практическая работа «Решение задач по теме алгоритмы»
Рассмотрим следующую задачу.
Задача 1. Последовательность Xn строится так:

X1 = 1; X2 = 3; ... ; Xn = Xn-2 — 2Xn-1

для каждого n > 2. Составьте алгоритм нахождения первого числа в этой последовательности, большего 100 000.

Каждый из вас легко составит такой алгоритм. Ясно, что переменные здесь можно считать имеющими целочисленный тип. Нужный алгоритм записывается так:

алг Задача_1 (рез вещ Z)

нач цел X, Y

X := 1

Y := 3

нц пока (Z < 100000)

Z := X - 2 * Y

X := Y

кц

вывод Z

Изменим условие этой задачи.

Задача 2. Последовательность Xn строится так:

X1 = 1; X2 = 3; ... ; Xn = Xn-2 – 2Xn-1

для каждого n > 2. Найти первое в этой последовательности число, большее 100 000.

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

И тут возникает вопрос: получим ли мы ответ, запустив созданный нами алгоритм? Легко понять, что помешать этому может только одно отсутствие в данной последовательности хотя бы одного числа, большего 100 000. Алгоритм же в этом случае будет исполняться бесконечно, вырабатывая все новые и новые члены последовательности.

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

Итак, надо убедиться, что в данной последовательности встретится хотя бы один раз число, большее 100 000. Чтобы найти подход к тому, как в этом можно убедиться, полезно взглянуть на десяток первых членов последовательности. Вот эти 10 членов:
1; 3; –5; 13; –31; 78; –181; 437; –1055; 2547.
Глядя на них, можно высказать гипотезу, что члены с четными номерами положительны и неограниченно возрастают. Докажем эту гипотезу. Для этого выразим X2k через предшествующие члены последовательности с четными номерами.

X2k = X2k-2 – 2 X2k-1 = X2k-2 – 2 (X2k-3 – 2 X2k-2) = 5 X2k-2 – 2 X2k-3 = 5 X2k-2 – 2 (X2k-5 – 2 X2k-4) = 5 X2k-2 + 4 X2k-4 – 2 X2k-5 = 5 X2k-2 + 4 X2k-4 – 2 (X2k-7 – 2 X2k-6) = 5 X2k-2 + 4 X2k-4 + 4 X2k-6 – 2 X2k-7 = ... = 5 X2k-2 + 4 X2k-4 + 4 X2k-6 + ... + 4 X2 – 2 X1.

Поскольку 4X2 – 2X1 = 10, индуктивное рассуждение показывает, что все члены последовательности с четными номерами положительны. Более того, теперь ясно, что X2k > 5 X2k-2. Применяя это неравенство k раз, получаем: X2k > 5k–1 X2. Поэтому в данной последовательности имеются члены, большие не только 100 000, но и вообще любого положительного числа. Можно сказать, что мы доказали следующую теорему:

Теорема. Пусть последовательность Xn определена следующим рекуррентным соотношением:

X1 = 1; X2 = 3; ... ; Xn = Xn-2 – 2Xn-1

для каждого n > 2. Тогда для любого положительного числа M в этой последовательности существует член, больший чем M.

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


Задания для самостоятельной работы
1. В чем различие между конструктивными теоремами и теоремами чистого существования?
2. Для решения задачи “В какую наименьшую натуральную степень надо возвести число 3, чтобы получилось число, оканчивающееся на 00001?” был составлен следующий алгоритм:

алг Показатель степени (рез цел N)

нач цел: X, Y

X := 1

N := 0

X := 3 * X

Y := mod(X, 100000)

N := N + 1

кц

вывод N

а) Объясните, почему данный алгоритм решает поставленную задачу.

б) Докажите, что данный алгоритм конечен.
3. Дан алгоритм:

алг Задача_2 (арг вещ А, Е, рез вещ Х)

нач

ввод А

X := 1

X := (X + A/X)/2

кц

вывод Х

а) Доказать, что при любых положительных A и E алгоритм завершит свою работу за конечное число шагов.