ОСНОВНЫЕ ЭТАПЫ РЕШЕНИЯ ЗАДАЧ НА КОМПЬЮТЕРЕ

Если отнести последние три компоненты к алгоритмической части программы, то можно дать такое короткое определение: Программа = алгоритм + данные.

Алгоритм Евклида. Даны два целых положительных числа т п. Требуется найти их наибольший общий делитель, т. е. наибольшее целое положительное число, которое нацело делит оба числа m и n.

1. [Нахождение остатка.] Разделим m на n, и пусть остаток от деления будет равен r (где 0 ≤ r ≤ n).

2. [Сравнение с нулем.] Если r = 0, то выполнение алгоритма прекращается; n — искомое значение.

3. [Замещение.] Присвоить m ← n, n ← r и вернуться к шагу 1.

Примечание:

Для удобства программной реализации алгоритма Евклида приведенный алгоритм имеет смысл переписать следующим образом.

0. [Сравнение m и n.] Если n > m, то поменять значения m и n местами.

1. [Нахождение остатка.] Разделим m на n, и пусть остаток от деления будет равен r (где 0 ≤ r ≤ n).

3. [Замещение.] Присвоить m ← n, n ← r.

2. [Сравнение с нулем.] Если r = 0, то выполнение алгоритма прекращается; m — искомое значение, иначе вернуться к шагу 1.

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

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

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

Каждый шаг алгоритма должен быть точно определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая. Чтобы преодолеть возможность неоднозначного понимания инструкций алгоритма, для описания алгоритмов были разработаны формально определенные языки программирования, или машинные языки, в которых каждый оператор имеет строго определенное значение. Метод вычислений, выраженный на языке программирования, называется программой.

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

Алгоритм Евклида удовлетворяет этому условию, потому что после шага 1 значение r меньше, чем п. Поэтому если r≠ 0, то в следующем цикле на шаге 1 значение n уменьшается. Убывающая последовательность положительных целых чисел имеет конечное число членов, поэтому шаг 1 может выполняться только конечное число раз для любого первоначально заданного значения n. Но имейте в виду, что количество шагов может быть сколь угодно большим; выбор слишком больших значений т и п приведет к тому, что шаг 1 будет выполняться более миллиона раз.

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

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

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

Массовость, т. е. возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. Так как рассматриваемый алгоритм позволяет правильно подсчитать сумму не только чисел 2 и 3, но любой другой пары целых чисел, он обладает свойством массовости. Для того чтобы алгоритм обладал свойством массовости, следует составлять алгоритм, ис­пользуя обозначения величин (переменные) и избегая конкретных значений. Данное свойство означает, что разрабатываемый алгоритм должен иметь общий вид. Иначе говоря, нужно, чтобы алгоритм можно было применять для любых задач какого-то определенного класса, различающихся только исходными данными. Причем исходные данные можно выбирать из так называемой области применимости алгоритма.

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

(Можно легко доказать, что число r в реализации алгоритма Евклида действительно является наибольшим общим делителем. После шага 1 имеем

m = qn + r,

где q — некоторое целое число. Если r = 0, то m кратно n и, очевидно, в этом случае n — наибольший общий делитель тип. Если r≠ 0, то любой делитель обоих чисел m и n должен быть также делителем m — qn = r и любой делитель n и r — также делителем qn+r=m. Таким образом, множество делителей чисел {m, n} совпадает с множеством делителей чисел {n, r}. Следовательно, пары чисел {m, n} и {n, r} имеют один и тот же наибольший общий делитель. Таким образом, шаг 3 не изменяет ответа исходной задачи.)

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

Ввод. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных, т. е. величин, которые задаются до начала его работы или определяются динамически во время его работы. Эти входные данные берутся из определенного набора объектов. Например, в алгоритме Евклида есть два входных значения, а именно — т и п, которые принадлежат множеству целых положительных чисел.

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

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

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

ü На естественном языке.

ü В виде блок-схемы.

ü На алгоритмическом языке.

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