3
Схема и структура блок схема известно читателям по курсам информатики.
Мы и в дальнейшем часто будем пользоваться
именно такой формой
представления алгоритмов. Так как при таком подходе легко логически
представить идею и сущность алгоритмов. А также из такой формы будет
легко перейти к одному из алгоритмических языков, то есть к программе
алгоритма.
В качестве самостоятельной работы составить блок-схему решения
квадратного уравнения с учетом возможных значений дискриминанта
и
в
соответствии с этим, оформить выдачу ответа.
Создание вычислительных машин было необходимым шагом
технического прогресса в связи с появлением широкого класса задач
требующих большой объем вычислений. Создание вычислительных машин в
свою очередь выдвинула проблему составления определенных инструкций
для управления работой вычислительных машин. Таким образом, появилась
необходимость проектирования алгоритмов для ВМ (вычислительных
машин) и составления программ в соответствии с этими алгоритмами.
Несмотря на большое быстродействие современных компьютеров
существуют и
появляются все новые задачи, требующие такого объема
вычисления, что не под силу даже современным ВМ. В ходе изложения мы
ещё не раз обратим внимание на класс таких задач.
Мы здесь приведем одну хорошо известную среди специалистов
задачу, связанную с шахматами: определить маршрут проходящий по
правилу хода конём от клетки А1 и приходя по всем клеткам шахматной
доски только по одному разу и возвращающуюся в исходную клетку А1.
Если изложить данную задачу в
терминах теории графов, то получим
Гамильтонов граф, вершины которого расположены на клетках шахматной
доски, а ребра графа - это линии соединяющие те клетки, по которым
движется шахматная фигура при совершении хода конем.
При этом число
возможных
вариантов
маршрутов
исчисляется
по
формуле
4
8
20
16
16
21
2 3 4
6
8
28 10 .
N
Как видно, даже в этой на вид простой
задаче мы сталкиваемся с таким огромным количеством вариантов. Если в
таком графе каждое ребро имеет определенную цену перехода и нам
необходимо из всех возможных маршрутов выбрать наименьший по цене
маршрут,
то
такая
задача
не
под
силу
даже
современным
быстродействующим ВМ. Вместе с тем для
сравнения мы должны хранить
информацию о каждом маршруте, для чего потребуется такой объем памяти,
для которого не хватит объема памяти ВМ. Поэтому при проектировании
4
алгоритмов мы должны оценивать их как по объему вычислений, так и по
объему памяти для реализации построенного алгоритма. В дальнейшем мы
будем оценивать каждый предложенный
алгоритм именно по этим
показателям.
Для иллюстрации изложенного подхода рассмотрим процесс
вычисления
значения
многочлена
в
некоторой
точке
0
.
х
х
:
1
0
1
1
...
n
n
n
n
n
P x
a x
a x
a
x
a
.
Определим
число
арифметических
операций для вычисления значения многочлена в точке
0
.
х
х
Первый
подход - вычисление в лоб, т.е. последовательное вычисление
арифметических операций. Число умножений
для каждого слагаемого
соответственно
1
1
2
... 1
.
2
n n
n
n
n
Число сложений
.
n
Всего
1
2
n
n
n
операций.
Второй подход - вычисление по схеме Горнера, когда многочлен
представляется в виде
0 0
1
0
2
0
1
0
...
...
.
n
n
n
P x
a x
a
x
a
x
a
x
a
При
этом число необходимых операций будет
n
умножений и
n
сложений.
Эффективность второго подхода очевидна.
Прежде чем переходить к проектированию
алгоритма решения
определенной задачи мы должны, предварительно, убедится в корректности
постановки задачи. Это означает, во-первых, существование решения задачи,
во-вторых, если нет особых оговорок, единственность решения. Для этого
необходимо наличие всех условий обеспечивающих существование и
единственность решения. Для иллюстрации рассмотрим следующую задачу:
На сумму 133 000 сумов необходимо купить 10 тетрадей по цене 5 000,
11 000 и 18 000 сумов. Определите количество каждого вида тетрадей.
Do'stlaringiz bilan baham: