Алгоритм решения задачи в виде псевдокода

начало

ввод а, n, pi

s = 0

цикл i = 1 до n

конец цикла

s = s * pi

вывод s

конец

 

 

Контрольные вопросы.

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

2. Свойства алгоритма.

3. Основные элементы блок-схем.

4. Типы циклических алгоритмов.

5. Правила составления рекуррентной формулы.

 

 

 

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

 

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

 

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

Линейный поиск. Элементы проверяются последовательно, по одному, до тех пор, пока нужный элемент не будет найден. Для массива из N элементов требуется, в среднем, (N+1)/2 сравнений (вычислительная сложность Оср(N)). Легко программируется, подходит для коротких массивов.

Двоичный (бинарный) поиск. Применим, если массив заранее отсортирован (по возрастанию ключей). Ключ поиска сравнивается с ключом среднего элемента в массиве. Если значение ключа поиска больше, то та же самая операция повторяется для второй половины массива, если меньше - то для первой. Операция повторяется до нахождения нужного элемента. На каждом шаге диапазон элементов в поиске уменьшается вдвое. Требуется, в среднем, (log2N+1)/2 сравнений (вычислительная сложность Оср(log2N)). Применяется для поиска (многократного) в больших массивах.

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

Сортировка (упорядочение) - переразмещение элементов данных в возрастающем или убывающем порядке. При выборе метода сортировки необходимо учитывать число сортируемых элементов (N) и до какой степени элементы уже отсортированы

Критерии оценки метода сортировки:

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

- эффективность использования памяти

 

 

 

где S(N) - объем памяти, занимаемый элементами данных до сортировки, DS(N) - объем дополнительной памяти, требуемой в процессе сортировки.

Сортировка методом выборки

Принцип. Из массива выбирается наименьший элемент и помещается на место первого элемента массива, затем выбирается наименьший элемент из оставшихся и помещается во второй элемент массива и т.д.

Рис. 8. Принцип сортировки методом выборки.

 

С использование псевдокода это можно записать как:

 

Ввести массив A(1..N)

for J = 1,N-1,1

do

Мин.Эл. = А(J)

Индекс Мин.Эл. = J

for I = J+1,N,1

do

if A(I) < Мин.Эл.

then

Мин.Эл. = A(I)

Индекс Мин.Эл. = I

end-if

end-do

A(Индекс Мин.Эл.) = A(J)

A(J) = Мин.Эл.

end-do

Вывести A(1..N)

Требуется, в среднем, N(N+1)/2 сравнений (вычислительная сложность O(N²), не зависит от начальной упорядоченности). Дополнительная память не нужна.

Сортировка включением

Принцип. Элементы выбираются по очереди и помещаются в нужное место.

Рис. 9. Принцип сортировки методом включения.

С помощью псевдокода это запишется следующим образом:

Ввести массив A(1..N)

for I = 2,N,1

do

Temp = А(I)

A(0) = Temp

J = I-1

while A(J) > Temp

do

A(J+1) = A(J)

J = J-1

end-do

A(J+1) = Temp

end-do

Вывести A(1..N)

Требуется, в среднем, (N-1)(N/2+1)/2 сравнений (вычислительная сложность О_ср(N²)).{ О_{сравнения} } Скорость данного метода зависит от начальной упорядоченности массива. Не требуется дополнительной памяти.

Сортировка обменами

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

Рис. 10. Принцип сортировки обменами.

 

С помощью псевдокода это запишется следующим образом:

Ввести массив A(1..N)

K = 1, I = 1

while K <> 0

do

K = 0

for J = 1,N-I,1

do

if A(J) > A(J+1)

then

T = A(J),

A(J) = A(J+1),

A(J+1) = T, K = K+1

end-if

end-do

I = I +1

end-do

Вычислительная сложность данного метода сильно зависит от исходного расположения элементов. Минимальное значение числа сравнений – N-1 в полностью отсортированном массиве, максимальное – (N²-N)/2 при начальной сортировке в обратном порядке. Средняя вычислительная сложность Оср(N²). Дополнительная память не требуется.

Сортировка распределением (метод корзин).

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

Каждый элемент массива А (1..N) - совокупность цифр С1С2С3…Сm, где m - количество цифр максимального элемента (если какой-то элемент содержит меньше цифр, то он слева дополняется нулями).

 

Рис. 11. Принцип сортировки распределением.

 

 

Средняя вычислительная сложность Оср(N log₂N) и лучше, если m (число цифр) мало. Требуется дополнительный массив размером N, и еще массив размером 10, в котором подсчитывается число элементов с выделяемой цифрой 0,1,…9.

Быстрая сортировка

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

Алгоритм процедуры разбиения массива А(1..N) пороговым элементом, находящимся сначала на месте А(1).

С помощью псевдокода это запишется следующим образом:

{Процедура разбиения массива A(1..N) пороговым элементом V}

V = A(1), K = 2, J = N

while K < J

do

if A(K) < V

then

K = K + 1

Else

if A(J) < V

then

Temp = A(K), A(K) = A(J)

A(J) = Temp

end-if

J = J – 1

end-if

end-do

if A(K) >= V

then

K = K – 1

end-if

Temp=A(1),A(1)=A(K),A(K)=Temp

 

Рис. 12. Принцип быстрой сортировки.

 

Средняя вычислительная сложность - Оср(N log₂N). Большое значение имеет выбор значения порогового элемента. В частности, если исходный массив близок к отсортированному, то при выборе пороговым элементом первого элемента (как в примере) вычислительная сложность алгоритма будет О(N2). Желательно, чтобы пороговый элемент в конечном итоге разделил массив приблизительно на две равные части.

Сортировка слиянием

Принцип. Два отсортированных массива соединяются в один массив таким образом, чтобы и он стал отсортированным.

Алгоритм слияния отсортированных массивов B(1..M) и C(1..L) в массив A(1..M+L) заключается в следующем. В качестве А(1) выбираем наименьший из В(1) и С(1). Если это В(1), то в качестве А(2) - наименьший из В(2) и С(1) и т.д.

С помощью псевдокода это запишется следующим образом:

Ввести массивы B(1..M),С(1..L)

I = 1, J = 1

for K = 1,M+L,1

do

if I > M

then

A(K) = C(J), J = J + 1

else

if J > L

then

A(K) = B(I), I = I + 1

else

if B(I) < C(J)

then

A(K) = B(I),I = I + 1

else

A(K) = C(J),J = J + 1

end-if

end-if

end-if

end-do

Если имеется один неотсортированный массив А(1..N), то его можно рассматривать как совокупность N отсортированных массивов, каждый из которых состоит из одного элемента. Первый шаг - слияние массивов попарно, затем объединение пар в четверки и т.д.

Средняя вычислительная сложность алгоритма - Оср(N log₂N). Требуется дополнительный массив, содержащий N элементов.

Рис. 13. Принцип алгоритма сортировки слиянием.

 

Контрольные вопросы.

1. Алгоритм линейного поиска.

2. Алгоритм двоичного (бинарного) поиска.

3. Что такое сортировка.

4. Критерии оценки метода сортировок.

5. Принцип сортировки методом выборки.

6. Принцип сортировки включением.

7. Принцип сортировки обменами.

8. Принцип сортировки распределением.

9. Принцип быстрой сортировки.

10. Принцип сортировки слиянием.

 

 

 

 

Глава 4. Этапы разработки программного обеспечения

 

4.1. Этапы разработки программного обеспечения

 

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

Этапы разработки ПО можно представить в следующем виде:

 

Рис. 14. Этапы разработки ПО.

 

На первом этапе первичным документом является постановка задачи, объединяющая:

- общую характеристику задачи (назначение, экономическая эффективность, структура объектов);

- описание входных данных (структура и способ поступления);

- описание выходных данных;

- существующие к данному моменту алгоритмы получения выходных данных на основе входных;

- источники разработки (откуда появилась вся информация).

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

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

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

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

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

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

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

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

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

Причины выпуска новых версий (модификаций) ПО:

· необходимость исправления ошибок, выявленных в процессе эксплуатации;

· необходимость совершенствования, например, улучшения интерфейса или расширения состава, выполняемых функций;

· изменение среды (появление новых технических средств и/или программных продуктов).

 

4.2. Понятие “язык программирования”

 

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

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

 

КОД	АДРЕСНАЯ ЧАСТЬ

 

Адресная часть содержит адреса (номера) ячеек памяти, в которых расположены операнды, и адрес ячейки, куда следует поместить результат

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

Ассемблер – программа, преобразующая мнемонику языка ассемблера непосредственно в двоичные представления машинных команд. Языки ассемблера – машинно-зависимые языки, языки низкого уровня, в которых одна команда соответствует одной машинной команде.

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

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

Критерии оценки (выбора) языка программирования:

· легкость чтения программ (особенно важна с точки зрения эксплуатации и сопровождения программ);

· легкость создания программ в выбранной области;

· надежность (т.е. насколько программа соответствует своему предназначению в любых условиях).

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

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

FORTRAN (FORmula TRANslator). Считается первым компилируемым языком высокого уровня. В основном используется для программ, выполняющих естественнонаучные и математические расчеты. Одна из особенностей этого языка (вплоть до диалекта FORTRAN 90) было то, что типы и ячейки памяти для всех переменных фиксировались до выполнения программы. В процессе выполнения программы новые переменные не вводились, и распределение памяти не производилось. Отсюда невозможность создания рекурсивных подпрограмм, трудность реализации динамических структур

COBOL (COmmon Business Oriented Language, 1960 г.). Структура и словарь близки к обычному английскому языку. Является основным языком в США для обработки данных в таких учереждениях как банки и страховые компании. Раздел данных – сильная сторона языка COBOL, тогда как раздел процедур – относительно слабая (в частности, отсутствует достаточное число функций).

BASIC (Beginner’s All-purpose Symbolic Instruction Code). Исходный BASIC имел только 14 операторов и один тип данных – числа с плавающей точкой. Был очень популярным языком для микрокомпьютеров в конце 70-х и начале 80-х годов, т.к. был легок для изучения начинающими и не требователен к ресурсам компьютера. Важнейшим аспектом была его ориентация на использование удаленного доступа к компьютеру посредством терминала. Ранние версии не были средством написания серьезных программ значительного размера. Возрождение языка BASIC произошло в начале 90-х годов с выходом языка Visual BASIC (Microsoft, 1991).

ALGOL (ALGOrithmic Language). Язык ALGOL – результат попытки создания универсального языка. В этом языке была формализована концепция типов данных, реализована идея составных операторов. В диалекте ALGOL 60 была введена концепция блочной структуры, что позволяло программистам локализовать части программы, вводя разные области видимости. Имелась возможность передавать параметры подпрограммам по значению и по имени, а также создания рекурсивных процедур. Были доступны динамические массивы (ALGOL 68), т.е. массивы, диапазон индексов которых задавался переменной, которая могла менять свое значение во время работы программы. Свыше 20 лет ALGOL оставался единственным официальным средством представления алгоритмов в научной литературе. Недостатки: некоторые его свойства были слишком гибкими, отсутствовали операторы ввода-вывода.

 

4.3. Императивные языки

 

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

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

Ada (1980 г.). Происходит от Pascal, но заметно сложнее его. Содержит средства выделения в отдельные модули объектов данных, обеспечивает поддержку использования абстракции данных в структуре программы. Содержит обширные средства обработки исключительных ситуаций. Программные блоки в языке Ada могут быть настраиваемые. Язык также обеспечивает параллельное выполнение особых программных блоков, которые называются заданиями.

Modula-2 (1981 г.). В сравнении с Pascal добавлена поддержка модулей. Имеются абстрактные типы данных, возможность использования процедур как типов, низкоуровневые средства системного программирования и сопрограммы.

 

4.4. Объектно-ориентированные языки программирования

 

Объектно-ориентированные языки программирования в наибольшей степени способны реализовать технологию объектно-ориентированного программирования, которая основана на объектной декомпозиции.

SmallTalk (1980 г.). Основные идеи происходят от первого ООЯ SIMULA 67. Программными модулями языка SmallTalk являются объекты – структуры, объединяющие локальные данные и набор операций (методы), которые доступны другим объектам. Метод определяет реакцию объекта на определенное сообщение, соответствующее данному методу. Абстракциями объектов являются классы. Экземпляры классов – объекты программы. Имеется иерархия классов. Подклассы наследуют функциональные возможности и переменные родительского класса, имея возможность добавлять новые функциональные возможности, а также изменять или скрывать унаследованные.

С++. Представляет собой надстройку над языком Си, поддерживающую большинство возможностей, открытых языком SmallTalk (т.е. С++ - это объединение императивного и объектно-ориентированного языков). Поддерживается наследование и множественное наследование, когда класс имеет несколько родительских классов. Операторы в языке С++ могут перегружаться, а подпрограммы - настраиваться. Динамическое связывание обеспечивается функциями виртуального класса.. Язык С++ практически полностью совместим с языком С. Недостатки: объемность и сложность.

 

4.5. Смешанные языки

 

Смешанные языки, созданные путем введения в соответствующий императивный язык объектно-ориентированный поддержки: Oberon (1987 г.) Delphi (1995 г.), Ada 95 (1995).

Java. Является непосредственным наследником С++. Отличается от него отсутствием некоторых потенциально ненадежных механизмов, а также тем, что устранены любые, не относящиеся к объектно-ориентированному программированию, средства. Нет возможности написания на языке Java независимых подпрограмм, т.е. все подпрограммы являются методами и определяются в классах. Отсутствует множественное наследование, присущее, в частности, языку С++, – причина нередких ошибок. В языке Java можно создавать параллельные процессы, которые называются потоками. Все объекты в этом языке – динамические. Существует механизм неявного удаления объектов из динамической памяти. Повышение надежности, в частности, связано с отказом от части приведений типов, проверки диапазонов изменения индексов. Особенность языка Java состоит также в использовании особого вида трансляции – динамической кодогенерации.

LISP (LISt Processing). Разрабатывался в связи с работами в области искусственного интеллекта. В чистом языке LISP (1958 г.) существовало только два типа структур данных: атомы и списки. Списки представляли собой совокупность узлов, каждый из которых представляет собой два указателя. Первый указывает на представление атома, т.е. на его символьное или числовое значение, а второй – на следующий элемент списка.
Все вычисления в этом языке, который разрабатывался как язык функционального программирования, производятся путем применения функций к аргументам. Итеративные процессы определяются с помощью рекурсивных функций.

Prolog (PROgramming LOGig, 1972 г.) – язык логического программирования, основная идея которого состоит в использовании формальной логической записи для сообщения компьютеру вычислительных процессов. Программирование в нем является непроцедурным. Программы не устанавливают точно, как должен вычисляться результат, а только описывают его форму. Транслирующая система сама должна выбрать нужный порядок выполнения команд, который приведет к желаемому результату. Логическое программирование было использовано, главным образом, в системах управления реляционными базами данных, экспертных системах и обработке текстов на естественных языках.

 

4.6. Поколения языков программирования

 

· 1 GL (время появления – 40-50 гг.). Языки машинных команд. Первый ассемблер, который позволял задавать названия команд в символическом виде и указывать числа не только в двоичном, но и в десятичном или шестнадцатеричном формате.

· 2GL (конец 50-х – начало 60-х гг.). Символический ассемблер, включающий понятие переменной.

· 3GL (60-е годы). Универсальные языки высокого уровня (FORTRAN, COBOL, ALGOL, Pascal, C и др.) Современные среды программирования (например, Delphi, Visual BASIC, Java Development Kit) включают поддержку объектно-ориентированной технологии, набор визуальных инструментов для скоростной разработки приложений (RAD), библиотеку визуальных компонент (VCL) и другие инструменты.

· 4 GL (начало 70-х г.). Непроцедурные языки, ориентированные на конкретную область применения (в отличие от универсальных языков 3GL), в частности, на работу с базами данных. Команды языков 4GL ближе к обычному языку, нежели у 3GL:

FIND ALL RECORDS WHERE NAME IS "SMITH"

Типичный пример языка 4GL – SQL (Structured Query Language).

· 5 GL (наст. время). В том числе, системы создания программ, ориентированные на непрограммиста.

·

4.7. Принципы трансляции (компилятор и интерпретатор)

 

Трансляция - перевод программы, написанной на языке программирования, в последовательность машинных команд.

 

 

Контрольные вопросы.

1. Что такое программное обеспечение?

2. Этапы разработки программного обеспечения.

3. Понятие «язык программирования».

4. История развития языков программирования.

5. Что такое трансляция программы.

 

 

 

Глава 5. Элементы языка СИ

 

5.1. Алфавит, идентификаторы, служебные слова

 

5.1.1. Используемые символы

Лексема – единица текста программы, которая при компиляции воспринимается как единое целое и по смыслу не может быть разделена на более мелкие элементы.

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

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

Прописные буквы латинского алфавита	A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Строчные буквы латинского алфавита	a b c d e f g h i j k l m n o p q r s t u v w x y z
Символ подчеркивания	_

2. Группа прописных и строчных букв русского алфавита и арабские цифры

 

Прописные буквы русского алфавита	А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Э Ю Я
Строчные буквы русского алфавита	а б в г д е ж з и к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я
Арабские цифры	0 1 2 3 4 5 6 7 8 9

 

3. Знаки нумерации и специальные символы

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

Символ	Наименование	Символ	Наименование
,	запятая	)	круглая скобка правая
.	точка	(	круглая скобка левая
;	точка с запятой	}	фигурная скобка правая
:	двоеточие	{	фигурная скобка левая
?	вопросительный знак	<	меньше
'	апостроф	>	больше
!	восклицательный знак	[	квадратная скобка
|	вертикальная черта	]	квадратная скобка
/	дробная черта	#	номер
\	обратная черта	%	процент
~	тильда	&	амперсанд
*	звездочка	^	логическое не
+	плюс	=	равно
-	мину	"	кавычки

4. Управляющие и разделительные символы

К той группе символов относятся: пробел, символы табуляции, перевода строки, возврата каретки, новая страница и новая строка. Эти символы отделяют друг от друга объекты, определяемые пользователем, к которым относятся константы и идентификаторы. Последовательность разделительных символов рассматривается компилятором как один символ (последовательность пробелов).

Идентификатор. Последовательность букв, цифр и символов подчеркивания “_”, начинающаяся с буквы или подчеркивания.

Прописные и строчные буквы различаются. Идентификаторы могут иметь любую длину, но компилятор учитывает не более 31-го символа от начала идентификатора. В некоторых еще более жесткое – не более 8 символов.

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