Материал: Мансуров. Основы программирования в среде Lazarus. 2010

Глава 1 Основы программирования

____________________________________________________________________

языки программирования, или машинные языки, в которых каждое утвержде-

ние имеет абсолютно точный смысл.

Запись алгоритма на языке программирования называется программой.

3) Алгоритм должен иметь некоторое число входных данных, т.е. величин,

объектов заданных ему до начала работы. Эти данные берутся из некоего кон-

кретного множества объектов.

4) Алгоритм имеет одну или несколько выходных величин, т.е. величин,

имеющих вполне определенное отношение к входным данным. 5) Эффективность

От алгоритма требуют, чтобы он был эффективным. Это означает, что все операции, которые необходимо произвести в алгоритме, должны быть доста-

точно простыми, чтобы их в принципе можно было выполнить точно и за ко-

нечный отрезок времени с помощью карандаша и бумаги.

Следует отметить, что для практических целей "финитность" является наиболее важным требованием – используемый алгоритм должен иметь не про-

сто конечное, а предельно конечное, разумное число шагов. Например, в прин-

ципе имеется алгоритм, определяющий, является ли начальное положение в иг-

ре в шахматы форсировано выигранным для белых или нет. Но для выполнения этого алгоритма требуется фантастически огромный промежуток времени.

Пусть имеется компьютер, обладающий быстродействием 100 млн. операций в секунду. Тогда этот компьютер будет выполнять алгоритм в течение 1023 лет.

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

11

1.1 Понятие алгоритма.

____________________________________________________________________

Пример алгоритма.

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

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

1.Рассмотреть А как первое число и В как второе число. Перейти к п.2.

2.Сравнить первое и второе числа. Если они равны, то перейти к п.5. Если нет, то перейти к п.3.

3.Если первое число меньше второго, то переставить их местами. Перейти

кп.4.

4.Вычесть из первого числа второе и рассмотреть полученную разность как новое первое число. Перейти к п.2.

5.Рассмотреть первое число как результат.

Стоп.

Этот набор правил является алгоритмом, т.к. следуя ему, любой человек умеющий вычитать, может получить наибольший общий делитель для любой пары чисел. Следуя этому алгоритму, найдем НОД чисел 544 и 119.

А 544 В 119

1)

544

119

425

А425 В 119

2)425

119

306

12

Глава 1 Основы программирования

____________________________________________________________________

А306 В 119

3)306

119

187

А187 В 119

АB

Меняем местами

А119 В 68

6)119

68

51

А51 В 68

A B

А68 В 51

8)68

51

17

13

1.1 Понятие алгоритма.

____________________________________________________________________

А34 В 17

11)34

17

17

А=В=17=НОД

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

ние структуры алгоритма, в котором каждый этап или шаг процесса переработ-

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

Эти фигуры соединяются между собой линиями со стрелками, отобра-

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

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

Приняты определенные стандарты графических обозначений. Так, прямо-

угольник обозначает вычислительные действия, в результате которых изменя-

ются значения данных. Ромбом обозначают этап разветвления алгоритма. Вы-

бор одного из двух возможных направлений дальнейшего счета производится в зависимости от выполнения условия, записанного в ромбе. Овалом обозначают начало и конец алгоритма. В параллелограммах записывают процедуры ввода и вывода данных. Запишем алгоритм Евклида в виде блоксхемы:

14

Глава 1 Основы программирования

____________________________________________________________________

начало

да

A=B

нет

нет

A<B

да

C=A

A=B

B=C

НОД

A=A-B

конец

Рис. 1.1. Алгоритм Евклида

Существуют и другие способы записи алгоритмов. В частности, достаточ-

но распространены записи алгоритмов на так называемых псевдоязыках. Псев-

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

мирования ALGOL-60, ALGOL-68, которые в настоящее время не используют-

ся). Примером такого псевдоязыка служит язык описания алгоритмов, приме-

няемым в школах. Некоторые псевдоязыки более близки к машинным языкам,

так называемые ассемблеры. Примером такого языка описания алгоритмов служит язык, предложенный Д. Кнутом в его знаменитой книге "Искусство программирования" [9].

Итак, чтобы решить какую либо задачу, нужно придумать алгоритм ее ре-

шения и записать его в том или ином виде. Этот процесс называется алгоритми-

зацией. Но в таком виде компьютер алгоритм не сможет выполнить. Следует

15