Мансуров. Основы программирования в среде 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

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

____________________________________________________________________

представить этот алгоритм в таком виде, чтобы компьютер мог его выполнить.

Для этого нужно, во-первых, разбить алгоритм на элементарные операции, на-

зываемые инструкциями или командами, которые умеет выполнять компьютер,

и, во-вторых, записать каждую такую операцию на языке, понятом компьюте-

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

Процесс разработки программы называется программированием. А человек,

выполняющий эту работу - программистом. При этом следует различать про-

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

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

лятор переводит ее в программу на машинном языке, которую и исполняет компьютер.

Программирование – это научная дисциплина. Если бы процессы про-

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

граммирование, как таковое, не было бы научной дисциплиной. Но дело об-

стоит не так. Существуют общие методы, которые позволяют, постепенно расчленяя задачи на подзадачи, сводить их решение, в конечном счете, к

некоторым элементарным операциям (чаще всего к элементарным арифме-

тическим операциям), подобно тому, как разбирая совершенно непохожие сложные механизмы, мы обнаруживаем, что они состоят из одинаковых де-

талей и узлов, только по разному соединенных (напр. подшипники, болты,

гайки и т.д.). Из этого, конечно, не следует, что процесс программирования не содержит в себе элементов творчества. Составление программы, такой же творческий процесс, что и разработка сложного механизма из заданных на-

боров деталей.

Основное назначение алгоритмов заключается в их фактическом вы-

полнении тем или иным исполнителем. Т.е. алгоритм составляется для того,

чтобы он был выполнен для решения какой либо задачи. В качестве испол-

нителя может выступать кто угодно – человек, станок с ЧПУ, компьютер и т.д.

16

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

____________________________________________________________________

В силу своей природы, компьютеры стали наиболее распространенными ис-

полнителями алгоритмов. Собственно они и были придуманы для того, чтобы с их помощью исполнять алгоритмы.

Назначение компьютеров, таким образом, состоит в фактическом испол-

нении алгоритмов, разработанных человеком.

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

"как бы самостоятельно", это неверно!

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

кетами, сочинения музыки, игры в шахматы, а компьютер лишь исполняет этот алгоритм. Таким образом, компьютер это помощник, инструмент чело-

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

плановый. С помощью компьютера человек может решать самые разнооб-

разные задачи.

Рассмотрим пример разработки алгоритма.

1.1.2 Задача о поездах и мухе

Рассмотрим задачу, которую мы позаимствовали из [11] и рассмотрим на этом примере основные приемы и способы составления алгоритмов. Пусть два города A и B удалены на расстояние d=600 км. Одновременно из каждого горо-

да отходят поезда в направлении друг другу. Поезд вышедший из города А имеет скорость v1=40 км/ч, а из В – имеет скорость v2=60 км/ч. Одновременно из пункта А вылетает исключительно быстрая муха со скоростью v=200 км/ч и летит на встречу поезду вышедшего из пункта В. При встрече с ним муха дела-

ет поворот и летит обратно навстречу с поездом, идущему из А. Когда она его встретит, муха снова делает поворот и летит в обратном направлении. Так про-

должается до тех пор, пока поезда не встретятся.

17

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

____________________________________________________________________

Задание.

1)определить длину различных отрезков пути, которые пролетит муха

2)определить общее расстояние, которое пролетит муха

На второй вопрос легко ответить: поезда встретятся через 600/(40+60)=6

часов, а муха за это же время пролетит расстояние 200*6=1200 км. Но оставим в стороне эту хитрость, и будем решать задачу в «лоб».

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

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

схемы. С чего нужно составлять блок-схему? Как правило, блок-схема начина-

ется с ввода исходных данных и начальных установок, т.е. определение началь-

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

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

Какие идеи сразу приходят в голову?

Самая простая идея заключается в том, чтобы производить действия сле-

дующим образом:

1)вычислить длину первого отрезка пути, который пролетит муха

2)вычислить длину второго отрезка и прибавить к предыдущему

3)вычислить длину третьего отрезка и сложить с ранее полученной суммой

и т.д.

Мы можем этот процесс представить в виде

18

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

____________________________________________________________________

Sстар=0

Вычисление 1-го отрезка x1

Sнов. = Sстар. + x1

Sстар. = Sнов.

Вычисление 2-го отрезка x2

Sнов. = Sстар. + x2

Sстар. = Sнов.

и т.д.

Рис. 1.2. Первый вариант алгоритма

Тут же возникает вопрос: т.к. схема должна иметь конечную длину, то нужно средствами рисунка выразить понятие повторения, кроме того, надо ука-

зать какие величины нужно вывести на экран. Отсюда схему перечерчиваем в виде:

Sстар=0

i=1

Вычисление i-го отрезка xi

Sнов. = Sстар. + xi

Sстар. = Sнов.

xi, Sнов

i=i+1

Рис. 1.3. Второй вариант алгоритма

19

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

____________________________________________________________________

Случается, что когда некоторая последовательность операций закончена,

необходимо бывает вернуться и повторить эти операции. Это называется цик-

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

вторений n, а также заданы все исходные данные, тогда блок-схема примет вид:

начало

Ввод d,v1,v2,n,v

Sстар=0

i=1

Вычисление i-го отрезка xi

Sнов. = Sстар. + xi

Sстар. = Sнов.

xi, Sнов.

i=i+1

да

i≤n

нет

конец

Рис. 1.4. Третий вариант алгоритма

20