Стандартные Алгоритмы. Приложение 2 алгоритмы
 Скачать 126 Kb.
|
|
ПРИЛОЖЕНИЕ 2 АЛГОРИТМЫ Сведения, представленные в этом приложении, не относится ни к одному конкретному языку программирования. Однако они важны любому создателю программ и особенно актуальны для начинающих программистов, поскольку все компьютерные программы предназначены для решения конкретных задач с помощью компьютера, а любая задача в любой области деятельности человека решается на основе того или иного алгоритма. Поэтому здесь систематизированы основные понятия, способы представления и типы алгоритмов, а также приведены примеры некоторых стандартных алгоритмов. П.2.1. Этапы решения задачРешение задач в любой области человеческой деятельности, в том числе и в повседневной жизни, выполняется в определенной последовательности, и решение задач с помощью компьютера не является исключением. Выделим четыре основных этапа решения задач:
и рассмотрим особенности каждого из них. Задача может быть предложена для решения либо сформулирована самостоятельно. В первом случае существует условие задачи, где представлены исходные данные и необходимые результаты («Дано» и «Требуется»). В корректно сформулированном условии задачи присутствуют однозначно понимаемые все и только все необходимые факты, представленные в виде чисел, условий, ситуаций, и требования. Для успешного решения такой задачи требуется выделить все составляющие исходных данных, в том числе и сформулированные по смыслу, например, сочетаниями слов «вверх по течению», что равносильно «против течения». Некоторые исходные данные и требования могут быть заданы неявно. Например, если требуется узнать, сколько землекопов выполнят задание, или сколько деталей изготовлено, ответ необходимо искать среди множества натуральных чисел, если требуется решить уравнение х=а/(х-1), значение х не может быть равно 1, а для уравнения х=  значение х не может быть отрицательным.В некорректно сформулированном условии либо не хватает исходных данных, либо они избыточны, либо существует возможность неоднозначного понимания элементов условия. В таких ситуациях необходимо добиться корректной формулировки либо для данной задачи, либо для группы задач, следующих из общего условия. Так, в случае избыточных данных следует установить, не являются ли они полностью противоречивыми, и тогда задача не имеет решения вообще, например, «как высоко расположено солнце над линией горизонта в два часа ночи на экваторе?». Если данных недостаточно либо они противоречивы частично, результат может оказаться неоднозначным. Например, «как высоко расположено солнце над линией горизонта на экваторе?» (результат либо существует, и тогда зависит от времени суток, либо отсутствует, когда солнце скрывается за горизонтом), либо «как высоко расположено солнце над линией горизонта в два часа дня?» (результат зависит от географической широты и времени года). Наконец, неоднозначность понимания условия можно продемонстрировать на примере: «как высоко расположено солнце над линией горизонта на экваторе в два часа?», из которого следует, что «два часа» можно понимать в 24-часовом либо 12-часовом формате представления времени. Применительно к решению задачи с помощью компьютера зачастую не оговаривается, в каком режиме, текстовом или графическом, и с какими параметрами режима представляются результаты на экране. В подобных ситуациях для решающего задачу остается свобода выбора недостающих данных. Случаи самостоятельного формулирования задачи обычно сводятся к ситуациям некорректных условий, особенно если это касается повседневной жизни. Так, задача «Мучает жажда. Надо ее утолить» при попытке уточнения формулировки может привести к ситуациям «любой жидкостью» (уксусом?), «любой пригодной для этого жидкостью» (лед, снег, мятный леденец исключены?), «водой» (строго говоря, компот, молоко и многие другие напитки не попадают под это условие). В ситуациях такого рода следует чередовать попытки решения задачи с уточнением формулировки задания до достижения приемлемого или требуемого результата. Выбор метода решения подразумевает поиск набора средств, позволяющих привести данную задачу к такой, для которой решение уже известно, то есть к стандартной задаче. Чем больше в активе человека, решающего задачу, стандартных задач, тем легче и быстрее будет найдено решение новой задачи. В качестве примера рассмотрим выбор метода решения уравнения х= . Найти значения х, обращающих данное равенство в тождество, можно, во-первых, подбором: очевидно, что искомые значения – 0 и 1. Во-вторых, искомые значения можно найти, построив графики функций, записанных в обеих частях равенства, и определив координаты точек пересечения графиков. В-третьих, возведя обе части уравнения в квадрат (поскольку правая часть неотрицательна, уравнение окажется равносильным исходному) и перенеся правую часть налево, получим квадратное уравнение, для решения которого имеются стандартные методы. Остается выбрать один из них: решение полного квадратного уравнения по известной формуле либо решение неполного квадратного уравнения разложением левой части на множители и приравниванием каждого из них нулюПредыдущий этап в принципе можно считать первым шагом создания алгоритма – последовательности действий, приводящих к достижению требуемого результата. Однако такое определение алгоритма является неполным. Если рассмотренную выше задачу решает человек, знакомый с алгеброй в рамках школьного курса, ему окажется достаточным сказанного выше, и это и будет для него алгоритмом. Если эту задачу решает семиклассник, только метод подбора (и, возможно, метод разложения на множители) окажется для него алгоритмом, поскольку он еще не владеет (в рамках школьной программы) методами решения квадратного уравнения, и для него потребуется уточнить действия, на которых этот метод основан. Поэтому при создании алгоритма требуется обязательно учитывать, кто либо что будет выполнять предусмотренные алгоритмом действия, то есть алгоритм должен быть ориентирован на конкретного исполнителя. Каждый исполнитель способен выполнять конкретный набор действий (по-другому – набор команд), и никому не придет в голову заставить башенный подъемный кран, способный поворачивать стрелу в ту или другую сторону, поднимать и опускать крюк и перемещаться по рельсам туда и обратно, сложить два числа. Поэтому алгоритм – последовательность действий (команд), понятных исполнителю и приводящих к достижению требуемого результата. Эта последовательность фиксируется тем или иным способом и в этом случае называется программой. При решении задач с помощью компьютера в состав алгоритма могут входить только те команды, которые компьютер может выполнить. А он способен выполнять только простые (машинные) команды, представленные в виде чисел (машинных кодов). Для удобства программиста созданы различные языки программирования, в каждом из которых предусмотрен определенный набор команд (операторов), зачастую содержащих большие группы машинных команд и записываемых в виде набора символов (текста). Для преобразования таких команд в машинные коды созданы программы-компиляторы и программы-интерпретаторы, которые выполняются самим компьютером. Надо только указать компьютеру, на каком языке представлена выполняемая программа. И, конечно, программист обязан знать набор доступных команд и правила их написания в данном языке. Следует учесть, что некоторые действия, такие как ввод, вывод, следование, ветвление, повтор, являются универсальными и в той или иной форме представлены во всех языках программирования. Если выполнение алгоритма поручено человеку либо устройству, постоянно контролируемому человеком, именно человек обеспечивает строгое выполнение созданной программы и достижение заданного результата. Он способен исправить ошибки, вкравшиеся в алгоритм, в процессе выполнения программы, он способен оценить соответствие полученного и требуемого результатов. Иная ситуация складывается, если выполнение программы поручается автомату, в частности, компьютеру. В этом случае после создания алгоритма и программы требуются еще два этапа до начала реального выполнения программы – отладка программы и ее тестирование. Под отладкой программы понимают проверку, понимает ли автомат все имеющиеся в программе команды и выполняет ли их так, как это представлял себе программист. На этом этапе программисту помогает программа-компилятор, выявляющая те команды, которые она не может преобразовать в машинные коды. Ошибки такого рода называют синтаксическими. Однако существуют и ошибки алгоритмические, связанные либо с неправильной последовательностью правильных команд, либо с неправильным пониманием программистом действий, выполняемых данной командой. В качестве первого примера рассмотрим ситуацию, когда для вычисления среднего арифметического значения переменных a и b в программе задано вычислить значение выражения a+b/2, Компьютер способен выполнить указанное действие, в котором всего-то не хватает скобок, но результат будет соответствовать требуемому значению далеко не при всех значениях a и b. В качестве второго примера рассмотрим ситуацию, когда хозяин на прогулке вместо команды «Апорт!» подает своей собаке команду «Фас!» с, возможно, весьма печальными последствиями для случайного прохожего и самого хозяина. Алгоритмические ошибки иногда так замаскированы, что отыскиваются с большим трудом. Здесь обязательно потребуются тестовые наборы исходных данных и правильных результатов. Несовпадение полученного и тестового результатов при заданном наборе исходных данных сигнализирует о наличии по крайней мере одной ошибки, что может оказаться достаточным для нахождения и устранения всех имеющихся ошибок. В сложных случаях для локализации ошибки приходится прибегать к услугам программ-отладчиков, выполняющих трассировку программы - либо пошаговое, либо пофрагментное выполнение программы с выдачей промежуточных результатов вычислений. Таким способом удается локализовать ошибку с точностью до оператора. Найти же и устранить алгоритмическую ошибку может только человек. Искусство программиста заключается в том, чтобы найти компромиссное решение - минимальный тестовый набор данных, требующий не слишком большого объема работы по тестированию программы, но гарантирующий максимальную вероятность обнаружения ошибок. В компьютерном мире известны случаи, когда спешка, неизбежная в конкурентной борьбе, приводила к появлению на рынке аппаратных и программных средств, содержащих ошибочные решения. Следует отметить, что использование компьютера для решения задач не освобождает человека от необходимости иметь достаточные по объему твердые знания, прочные навыки и определенную долю таланта и ответственности. П.2.2. Способы представления алгоритмовСуществуют три основных способа представления алгоритмов, каждый из которых рассчитан на понимание алгоритма человеком:
Рассмотрим особенности каждого из этих способов. Словесное описание представляет собой текст, в котором на некотором разговорном языке, например, русском, по пунктам записана последовательность действий. Строгие требования к форме такой записи не предъявляются, однако существуют определенные рекомендации, выполнение которых облегчает понимание алгоритма. В качестве простых примеров рассмотрим словесные описания алгоритмов решения уравнения х+2=3х-4 и неравенства х>1/.х. Исключительно в целях удобства будем нумеровать действия, чтобы было удобно ссылаться на каждое отдельное действие по номеру пункта. Для наглядности каждый пункт снабдим записью результата. Алгоритм 1. Решения уравнения х+2=3х-4:
Пункты 1 и 8 не обозначают какие-либо действия, так принято отмечать границы алгоритма. Можно указывать в отдельном пункте не одно действие, а группу простых действий: Алгоритм 1а. Решения уравнения х+2=3х-4:
Можно использовать известный метод решения линейного уравнения в качестве стандартной задачи. Алгоритм решения стандартной задачи называется подпрограммой. Примечание: если алгоритм решения некоторой задачи не является общеизвестным, его можно применить как подпрограмму, но тогда он должен быть представлен отдельно. Алгоритм 1б. Решения уравнения х+2=3х-4:
Решение неравенства основано на применении известного метода интервалов. Алгоритм 2. Решения неравенства х>1/.х.
Приведем пример более сложного алгоритма, основанного на рассмотрении различных допустимых ситуаций. Алгоритм 3: Решение уравнения aх2+bх+с=0 при любых значениях a,b.c.
Тогда 3а. Если b=0 Тогда 3б. Если с=0 Тогда 3в. Записать: Ответ: х(-,) Иначе 3г. Записать: Ответ: х Иначе 3д. Вычислить значение (-с/b) и записать: Ответ: х= значение(-с/b) Иначе 3е. Вычислить дискриминант d=b2-4ac 3ж. Если d<0 Тогда 3з. Записать: Ответ: х Иначе 3и. Вычислить и записать: Ответ: х1= значение((–b+  )/2/a) 3к. Вычислить и записать: Ответ: х2= значение((–b- )/2/a)
Нумерация действий в этом примере условная. В состав действия п.3 входит большая группа действий, нумерация которых может проводиться по-другому. Почему запись напоминает лестницу? Сравним эту запись с записью этого же алгоритма без отступов: Алгоритм 3а: Решение уравнения aх2+bх+с=0 при a,b.c – любые числа.
Если b=0 Тогда Если с=0 Тогда Записать: Ответ: х(-,) Иначе Записать: Ответ: х Иначе Вычислить значение (-с/b) и записать: Ответ: х= значение(-с/b) Иначе Вычислить дискриминант d=b2-4ac Если d<0 Тогда Записать: Ответ: х Иначе Вычислить и записать: Ответ: х1= значение((–b+ )/2/a) Вычислить и записать: Ответ: х2= значение((–b- )/2/a)
В каком из алгоритмов (3 или 3а) легче разобраться? Ответ оставляем на усмотрение читателя. Однако следует иметь в виду, что для облегчения понимания алгоритма, представленного в виде текста, считается общепринятым показывать отступами вложенность действий друг в друга. Напоследок приведем запись алгоритма для решения этой же задачи с применением подпрограмм: Алгоритм 3в: Решение уравнения aх2+bх+с=0 при a,b.c – любые числа.
1.1. Начало подпрограммы 1.2. Если с=0 Тогда Записать: Ответ: х(-,) Иначе Записать: Ответ: х 1.3. Конец подпрограммы.
2.1. Начало подпрограммы. 2.2. Вычислить значение (-с/b) и записать: Ответ: х= значение(-с/b) 2.3. Конец подпрограммы.
3.1. Начало подпрограммы. 3.2. Вычислить дискриминант d=b2-4ac 3.3. Если d<0 Тогда Записать: Ответ: х Иначе Вычислить и записать: Ответ: х1= значение((–b+ )/2/a) Вычислить и записать: Ответ: х2= значение((–b- )/2/a) 3.4. Конец подпрограммы.
Тогда . Если b=0 Тогда Выполнить подпрограмму 1 Иначе Выполнить подпрограмму 2 Иначе Выполнить подпрограмму 3
Как нетрудно видеть, такой способ записи сложного алгоритма наиболее удобен для восприятия и понимания. Здесь реализованы принципы блочного построения программ. Описание на алгоритмическом языке отличается от словесного описания тем, что каждое выполняемое действие представляется оператором конкретного языка программирования. Поэтому нельзя записывать группу действий, если для такой группы нет оператора. В остальном, включая и принцип выделения вложенности операторов друг в друга отступами, эти способы весьма сходны. Описание алгоритма с помощью структурной схемы (устаревшее – блок-схемы) основано на применении элементов – графических фигур, обозначающих определенные действия. Основными фигурами являются овал, параллелограмм, прямоугольник, ромб и прямоугольник с двойными боковыми сторонами. О   Начало   вал означает начало или конец, что именно – пишется внутри него. П Ввод х  араллелограмм означает ввод или вывод данных, что именно – пишется внутри него. П     X:=a+b рямоугольник означает простое действие или группу простых действий. Название действий пишется внутри. Р y>0? Да Нет    омб означает развилку с одним входом и двумя выходами, помеченными «Да» и «Нет». Активен тот выход, который соответствует ответу на вопрос, поставленный внутри ромба и на который можно ответить только «Да» и «Нет». П  Вычисление модуля  рямоугольник с двойными боковыми сторонами означает подпрограмму. Внутри пишется назначение или название подпрограммы. Элементы структурной схемы связываются отрезками прямых линий, указывающими связи между элементами. Элементы «Начало» и «Конец» имеют по одной связи, вниз и вверх соответственно, элементы «Ввод», «Вывод», «Простые действия» имеют по две связи: сверху и снизу. Элемент «Развилка» имеет одну связь вверху (вход) и обязательно две выходные связи, расположенные в любых двух из трех остальных вершин. Элементы располагаются так, что последовательность выполнения элементов соответствует преимущественному перемещению по схеме сверху вниз и дополнительному перемещению слева направо. В больших структурных схемах элементы размещают в ячейках таблицы. Ячейки имеют двойную индексацию – по горизонтали и вертикали – для удобства ссылок на каждую из них и друг на друга. П |
| Шаг | Значение х | Значение y |
| Начальные значения | 3 | 7 |
| x=x+y | 10 | 7 |
| y:=x-y | 10 | 3 |
| x:=x-y | 7 | 3 |
| Конечные значения | 7 | 3 |
На первом шаге можно выполнить не сложение, а вычитание:
| Шаг | Значение х | Значение y |
| Начальные значения | 3 | 7 |
| x=x-y | -4 | 7 |
| y:=x+y | -4 | 3 |
| x:=y-х | 7 | 3 |
| Конечные значения | 7 | 3 |
В качестве упражнения предлагаем читателям записать значение линейной комбинации в переменную y. Заметим, что нельзя применять операции умножения и деления (почему?).
Р
Начало
Ввод х,y,z
Вывод х,y,z
Конец
x>y?
Нет Да
Обмен значений
x и y
Начало
Ввод х,y
x>y?
Нет Да
Обмен значений
x и y
x>z?
Нет Да
Обмен значений
x и z
y>z?
Нет Да
Обмен значений
y и z
Вывод х,y
Конец
ассмотренный алгоритм применяется в одном из способов решения другой стандартной задачи, которая называется сортировкой значений и также имеет широкое применение: поменять местами значения элементов последовательности так, чтобы значения выстроились в порядке не убывания (или не возрастания).
Слева представлен алгоритм для сортировки по не убыванию двух значений, справа – для трех значений. Для сортировки по не возрастанию надо заменить везде знаки сравнения противоположными. Эти же алгоритмы решают и другую задачу: вывести два (три) значения в порядке не убывания (или не возрастания). При этом количество сравнений определяется формулой N*(N-1)/2, где N – число элементов последовательности, и при N=4 будет равно 6, а сам алгоритм имеет регулярную последовательную структуру. Если такую задачу решать методом выделения и вывода экстремального значения по всем элементам, а затем выделять и выводить экстремальное значение среди остальных элементов, количество сравнений определится формулой N!=1*2*3*…*N и при N=4 будет равно 24, а сам алгоритм будет иметь вид широкого дерева. Алгоритм, реализующий этот метод, здесь не представлен ввиду его трудоемкости и может явиться темой самостоятельных упражнений.
Алгоритм решения стандартной задачи накопления суммы чисел представлен в примере алгоритма повтора ранее. Для накопления произведения чисел в этом алгоритме надо заменить операцию сложения операцией умножения, а переменной S присвоить начальное значение, равное 1.
Широко применяемая в разных ситуациях стандартная задача поиска максимального или минимального значения среди элементов последовательности может быть решена способом сортировки, после чего остается взять значение первого или последнего элемента (в каком случае какого?). Если же не допускается изменение порядка следования значений элементов последовательности, используется метод текущего максимума (минимума). Для этого вводится вспомогательная переменная, в которой на каждом шаге фиксируется уже найденное (текущее) экстремальное значение. Сравнивая на каждом шаге в цикле текущее экстремальное значение со значением очередного элемента последовательности, принимаем решение о его замене или сохранении. Представление алгоритма в виде структурной схемы предлагается читателю в качестве упражнения.
Среди задач, связанных с делимостью чисел нацело, особо важное место занимает задача нахождения наибольшего общего делителя (НОД) для двух натуральных чисел. Эту задачу можно решать методом перебора, то есть подозревать в каждом натуральном числе, начиная с 2 и заканчивая половиной максимального из заданных чисел, искомую величину. Те из проверяемых чисел, для которых хотя бы один остаток от деления заданных чисел на него не равен нулю, имеют алиби и не являются общими делителями. Среди остальных же, являющихся общими делителями, остается найти максимальное число. Для этого надо запоминать каждый новый делитель в одной и той же вспомогательной переменной (чем-то похоже на поиск экстремального значения?). Если же вести поиск общих делителей в обратном порядке, первый же найденный общий делитель окажется наибольшим, то есть искомым.
Однако быстрее можно найти НОД, используя алгоритм, известный еще со времен древней Греции. Этот алгоритм приведен ниже.
Алгоритм поиска НОД:
Начало.
Ввод значений x и y.
Если xy Тогда
Если x>y Тогда x:=x-y
Иначе y:=y-x
Возврат к действию 3.
Иначе Вывод значения x.
Конец.
Если проверку на равенство проводить не в начале цикла, а в конце, при одинаковых исходных числах цикл окажется «бесконечным».
Поиск наименьшего общего кратного (НОК) для двух натуральных чисел можно также выполнить методом перебора. Последовательно проверять следует натуральные числа, начиная от наибольшего из заданных до произведения заданных чисел. Такое упражнение могут выполнить те, кто не уверен, что произведение НОД и НОК равно произведению заданных чисел.
В качестве последнего упражнения посчитайте, сколько стандартных алгоритмов представлено здесь словесным описанием.
Примечание. Алгоритмы обмена значений наглядно демонстрируют правило неопределенности в компьютерных программах: один метод требует больше памяти для дополнительной переменной, зато выполняется только операциями пересылки, то есть быстрее, другой алгоритм, не требуя дополнительной памяти, выполняется медленнее, поскольку в нем применяются дольше выполняемые арифметические операции.