Добавил:
Берегите себя и своих близких. По всем вопросам - пишите в мой вк, помогу чем смогу. Всем УЗС привет! Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
34
Добавлен:
25.11.2016
Размер:
396.15 Кб
Скачать

1

Часть 2. Основы программирования.

2.1. Алгоритмы.

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

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

Алгоритм — это упорядоченный набор однозначных выполнимых шагов.

Обратите внимание на то, что это определение утверждает,

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

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

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

2

Другое условие, содержащееся в определении алгорит-

ма, гласит, что шаги алгоритма должны быть однозначными,

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

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

Однако бесконечные процессы применяются на практике. Например, контроль состояния пациента в больнице или определение высоты, на которой находится самолет во время полета. Некоторые возразят, что в таких системах происходит просто повторение одного алгоритма, выполнение которого завершается, а затем автоматически повторяется. Другие посчитаю, что такие аргументы являются просто попыткой сохранить чрезмерно ограничивающее формальное определение. В любом случае, термин «алгоритм» часто используется в нестрогом прикладном смысле, но отношению к набору шагов, которые не обязательно определяют конечный процесс. Примером может служить алгоритм деления в столбик, который не определяет конечный процесс в случае деления, например, 1 на 3. Формально, в таких случаях термин «алгоритм» употребляется неправильно. [1]

Основные свойства алгоритмов:

1)понятность для исполнителя;

2)дискретность (процесс решения задачи представляется как последовательность выполнения простых шагов);

3)определенность (однозначность);

3

4)

конечность (должен приводить к решению

задачи за

 

конечное число шагов);

 

5)

универсальность (должен быть применим для

некоторого

 

класса задач, область применения алгоритма).

 

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

2.1.1. Представление алгоритма.

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

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

 

Например, элементами псевдокода могут быть:

1)

присваивание значения а в+2

2)

условие

if (условие) then (действие1) else (действие2)

3) исполнение действий, пока условие истинно while (условие) do (действие)

Программа является одним из видов представления алгоритма. Специалисты в области вычислительной техники используют термин «программа» по отношению к формальному представлению алгоритма, разработанному для прикладной вычислительной системы (для ЭВМ). Ранее мы определили процесс

4

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

Разработка программы состоит из двух этапов: создание лежащего в ее основе алгоритма и представление этого алгоритма в виде программы. Создание алгоритма является наиболее сложным шагом в процессе разработки программного обеспечения.

Процесс решения задач имеет творческую природу. Нестрогие этапы решения задач (были сформулированы Г.Пойа, 1945): 1) понять задачу, 2) разработать план решения задачи, 3) выполнить план, 4) оценить точность решения и его возможности как инструмента для решения других задач.

Чтобы сделать первый шаг в решении задачи, можно идти от обратного (например, развернуть сложенную фигуру оригами). Можно найти связанную задачу, которую легче решить или решение которой уже найдено, а затем попытаться применить это решение к текущей. Этот метод очень часто используется при составлении программ.

Еще один способ решения задачи – применить пошаговую детализацию, когда задача разбивается на несколько подзадач. Этот метод согласуется с такими понятиями, как движение от общего к частному, модульная структура, коллективное программирование.

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

5

Таблица 2.1. Обозначения в блок-схемах.

Название

 

Обозначение

Пояснение

п/п

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

Вычислительное

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

действие или их

 

 

 

 

 

 

 

 

 

последователь-

 

 

 

 

 

 

 

 

 

ность.

2

Решение

 

 

 

 

 

 

 

Проверка условия

 

 

 

 

 

 

 

 

 

(блок сравнения)

 

 

 

 

 

 

 

 

 

 

3

Модификация

 

 

 

 

 

 

 

Начало цикла с

 

(подготовка)

 

 

 

 

 

 

 

заданным числом

 

 

 

 

 

 

 

 

 

повторений

 

 

 

 

 

 

 

 

 

 

4

Документ

 

 

 

 

 

 

 

Печать

 

 

 

 

 

 

 

 

 

результатов

 

 

 

 

 

 

 

 

 

 

5

Ввод-вывод

 

 

 

 

 

 

 

Ввод данных с

 

 

 

 

 

 

 

 

 

клавиатуры, вывод

 

 

 

 

 

 

 

 

 

на экран дисплея

 

 

 

 

 

 

 

 

 

 

6

Пуск, останов

 

 

 

 

 

 

 

Начало, конец

 

 

 

 

 

 

 

 

 

 

7

Соединитель

 

 

 

 

 

 

 

Разрыв линии

 

 

 

 

 

 

 

 

 

потока

 

 

 

 

 

 

 

 

 

 

8

Комментарий

 

 

 

Печать

Пояснения, ком-

 

 

 

 

 

 

 

 

ментарий

 

 

 

 

 

результатов

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9

Попрограмма

 

 

 

 

 

 

 

Обращение к под-

 

 

 

 

 

 

 

 

(типовой про-

 

 

 

 

 

 

 

программе (про-

 

цесс)

 

 

 

 

 

 

 

цедуре)

 

 

 

 

 

 

 

 

 

 

 

6

2.1.2. Типовые структу-

ры алгоритмов.

Различают три типовые структуры алгоритмов: линейную; разветвленную; циклическую. Чаще всего алгоритмы решаемых задач состоят из отдельных частей, которые, в свою очередь, относятся к одной или другой типовой структуре.

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

Пример: Вычислить высоты треугольника со сторонами А, В, С по формулам:

 

2

 

 

 

2

 

 

 

h

 

p ( p A) ( p B) ( p C) ; h

 

p ( p A) ( p B) ( p C) ;

 

 

 

 

 

 

 

à

A

â

B

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

, где: p

A B C

- полу-

h

 

 

p ( p A)

( p

 

B) ( p C)

 

 

 

 

 

ñ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

C

 

 

 

 

 

 

 

 

 

 

 

 

 

 

периметр треугольника.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

начало

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

А, В, С

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

p

 

A B

C

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

t 2

 

( p A) ( p B) ( p C)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

h

 

 

t

; h

 

t

; h

 

t

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a

 

 

A

 

b

B

c

 

C

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ha , hb , hc

конец

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

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

7

ление должно идти по одной или другой ветви программы. На блок-схеме условие записывается внутри ромба из которого выходят две стрелки, при выполнении условия путь к следующей команде указывает линия с надписью «Да»; если условие не выполняется, по путь к следующей команде указывает стрелка с надписью «Нет».

Пример: Вычислить значения функции

z

x3

 

,

Sin(n x)

0,5

 

 

 

где: x и n - заданные параметры.

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

начало

x, n

y Sin(x n) 0,5

+

 

-

 

y

0

 

 

 

 

z

x3

 

 

y

Деление

 

 

на 0

x, n, z

Конец

Рис. 2.2. Блок-схема алгоритма разветвленной структуры.

8

Циклическая (итеративная) структура – использует-

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

При организации циклов необходимо:

1)задать начальное значение параметра цикла - переменной, которая будет изменяться при каждом повторении цикла;

2)изменить значение параметра цикла при каждом повторении цикла на шаг изменения;

3)проверить условие окончания этих повторений по значению этого параметра и перейти в начало цикла, если повторения ещё не закончены.

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

В цикле с предуcловием (while) – проверка условия завершения осуществляется до выполнения тела цикла. В цикле с постусловием (repeat) - до проверки условия завершения выполняется тело цикла.

Пример: Вычислить y

 

a3

при изменении

x от 0 до 3

a 2

x 2

 

 

 

сшагом 0,1.

Сизменением параметра x математическим способом и использованием блока сравнения блок–схема представлена на рис. 2.3 б) и в). Если в блок–схеме используется блок организации цикла, то эта блок – схема представлена на рис. 2.3 а).

 

 

 

 

 

9

 

 

 

 

начало

 

начало

 

 

начало

 

 

 

 

 

 

 

 

 

а

 

 

а

 

 

а

 

x=0

 

 

х=0

 

 

 

 

 

 

 

 

 

x=0,3,0.1

 

 

 

 

-

 

 

 

 

 

 

x<=3

 

 

y

a3

 

 

 

y

a3

a2

x2

 

+

a2

x2

 

 

 

a3

 

 

 

 

y

 

 

 

 

x,y

 

a2

x2

 

 

 

 

 

 

x,y

x

x

0.1

конец

 

 

 

 

 

x,y

конец

 

 

 

 

 

 

 

 

-

x

3

+

x x

0.1

 

конец

 

 

 

 

 

 

 

 

 

 

 

а)

 

б)

 

в)

 

Рис. 2.3. Алгоритмы циклической структуры.

2.1.3. Типовые алгоритмы.

Алгоритмы последовательного поиска, двоичного поиска, сортировки относятся к циклическим (итеративным) структурам.

Алгоритмы сортировки.

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

Сортировки методом простого выбора. Находят максимальный элемент в массиве из N элементов и меняют его местами с последним элементом (сортировка по возрастанию). Далее рассматривают массив без последнего элемента N-1. Общее количество сравнений пропорционально N2.

Сортировка методом поплавка. Рассматривается весь массив и максимальный элемент постепенно перемещается на последнее место. Затем рассматривают массив из N-1 элементов. Общее количество сравнений пропорционально N2.

10

Сортировка методом вставок. На i-м шаге считается, что первая часть массива, содержащая i-1 элемент, уже упорядочена. Далее берется i-й элемент, и для него подбирается j-е место в отсортированной части массива, такое, что упорядоченность не нарушается. i-й элемент помещается на это место, таким образом, что отсортированная часть массива увеличивается на один элемент. Общее количество сравнений пропорционально N2.

Алгоритмы поиска.

Алгоритм последовательного поиска последовательно рас-

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

Алгоритм двоичного поиска. Если массив упорядочен, то тогда можно использовать алгоритм бинарного (двоичного) поиска. По результату сравнения искомого значения со средним элементом массива из рассмотрения исключают первую или вторую половину списка, в зависимости от того больше или меньше «средний» (находящийся в середине списка) элемент искомого элемента. Для поиска в оставшейся части списка его тоже разбивают на две части и процедура повторяется. Таким образом, метод состоит в последовательном разделении рассматриваемого списка на сегменты до тех пор, пока не будет найден искомый элемент или поле поиска не сузится до пустого сегмента. Общее количество сравнений пропорционально log2N.

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

Во время выполнения процедуры, включающей рекурсию,

Соседние файлы в папке C++ программы НОВИКОВ