Базовые алгоритмические структуры

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

Базовые алгоритмические структуры

• следование
• ветвление
• цикл

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

Следование

Базовая структура "следование". Образуется последовательностью действий, следующих одно за другим:

Алгоритмический язык	Язык блок-схем
действие 1 действие 2 … действие n

Ветвление

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

Структура ветвление существует в четырех основных вариантах:

• если-то;
• если-то-иначе;
• выбор;
• выбор-иначе.

Запись ветвления выполняется в двух формах: полной и неполной.
Полная форма:

Неполная форма:

Пример: найти наименьшее из трех чисел.
1 вариант решения:

2 вариант решения:

 

Цикл

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

 

Виды циклов

• С предусловием (пока)
• С постусловием (до)
• С параметром

Цикл "пока" (цикл с предусловием):

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

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

Цикл с параметром, или цикл со счетчиком, или арифметический цикл - это цикл с заранее известным числом повторов. Исполнение цикла начинается с выполнения действия. Таким образом тело цикла будет реализовано хотя бы один раз. После этого происходит проверка условия. Поэтому цикл "до" называют циклом с постусловием. Если условие не выполняется, то происходит возврат к выполнению действий. Если условие истинно, то осуществляется выход из цикла. Таким образом условие цикла "до" - это условие выхода. Для предотвращения зацикливания необходимо предусмотреть действия, приводящие к истинности условия.
В блоке модификации указывается закон изменения переменной параметра. Xo - начальное значение параметра, h - шаг, Xn - последнее значение параметра.

Для создания циклов с параметром необходимо использовать правила:

1. Параметр цикла, его начальное и конечное значения и шаг должны быть одного типа

2. Запрещено изменять в теле цикла значения начальное, текущее и конечное для параметра

3. Запрещено входить в цикл минуя блок модификации

4. Если начальное значение больше конечного, то шаг - число отрицательное

5. Из цикла можно выйти не закончив его, тогда переменная параметр сохраняет свое последнее значение.

Примеры алгоритмов

Примеры линейных алгоритмов

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

Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?

1. Ввести v1, v2, v3, t1, t2, t3. 2. S1:= v1 * t1. 3. S2:= v2 * t2. 4. S3:= v3 * t3. 5. S:= S1 + S2 + S3. 6. Вывести значение S. 7. Конец.

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

Пример 2. Дано натуральное трехзначное число n, в записи которого нет нулей. Составить алгоритм, который возвращает значение ИСТИНА, если верно утверждение: "число n кратно каждой своей цифре", и ЛОЖЬ — в противном случае.

1. Ввести число n 2. A:= n mod 10 {разряд единиц} 3. B:= n div 100 {разряд сотен} 4. C:= n div 10 mod 10 {десятки} 5. L:= (n mod A=0) and (n mod B=0) and (n mod C=0) 6. Вывод L 7. Конец

На приведенной выше схеме DIV и MOD соответственно операции деления нацело и получения остатка от целочисленного деления. В фигурных скобках записаны пояснения (комментарии) к операторам.

7.5.2. Примеры алгоритмов типа "ветвление"

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

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

1. Ввести x. 2. Если x£–12, то y:=–x^2 3. Если x<0, то y:=x^4 4. y:= x–2 5. Вывести y 6. Конец

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

Пример 2. Дано натуральное число n. Если число нечётное и его удвоение не приведет к выходу за 32767 (двухбайтовое целое число со знаком), удвоить его, иначе — оставить без изменения.

Чтобы удовлетворить условию удвоения, число n должно быть нечетным и меньше 16384.

1. Ввести число n 2. Если число n нечетное и меньше 16384, то n:= n * 2 3. Вывод n 4. Конец

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

Примеры циклов

Если какие-либо операторы необходимо выполнить несколько раз, то их не переписывают каждый раз заново, а организуют цикл.
Пример 1. Подсчитать количество нечетных цифр в записи натурального числа n.

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

1. Ввести число n 2. K:= 0 {подготавливаем счётчик} 3. Если n = 0, переход к п. 7 4. Если n mod 10 mod 2 = 1, то K:= K +1 5. n:= n div 10 6. Переход к п. 3 7. Вывод K 8. Конец

Задача решена двумя способами. Слева решение оформлено с использованием цикла с предусловием, справа — с постусловием.

Пример 2. Дана последовательность, общий член которой определяется формулой Вычислить при n >2 сумму тех ее членов, которые больше заданного числа e.

 

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

1. Ввести e 2. S:= 0 3. A:= 1/4 4. n:= 3 5. Сравнить А с e. Если A>=e, переход к п. 10 6. S:= S + A 7. A:= (n-1)/(n*n) 8. n:= n + 1 9. Переход к п. 5 10. Вывод S 11. Конец

В рассмотренных выше примерах количество повторений заранее неизвестно. В первом оно зависит от количества цифр в записи натурального числа, во втором — от числа e.

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

Пример 3. Найти произведение первых k натуральных чисел, кратных трём.

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

1. Ввод k 2. P:= 1 {здесь накапливаем произведение} 3. T:= 0 {здесь будут числа, кратные 3} 4. I:= 1 5. Если I > k, переход к п. 10 6. T:= T + 3 7. P:= P * T 8. I:= I + 1 9. Перейти к п. 5 10. Вывод P 11. Конец

Этапы разработки программ

Процесс разработки ПО включает в себя следующие этапы

1. Постановка задачи

2. Разработка алгоритма

3. Составление исходной программы

4. Перевод исходной программы в машинные коды

5. Вычисление и обработка результатов

Постановка задачи

· Формулировка цели

· Формализация (математическая постановка)

· Выбор (или разработка) метода решения
Для решения задачи надо знать, что дано, что следует получить и какие действия и в каком порядке следует для этого выполнить. Предписание, определяющее порядок выполнения действий над данными с целью получения искомых результатов, и есть алгоритм, т.е. описание последовательности действий, однозначно приводящих от исходных данных к искомому результату. Формулировка задачи должна исключать какую-либо неопределенность в задании исходных данных и устанавливать область их допустимых значений. Состав исходной информации должен быть достаточен для решения поставленной задачи. Так, например, нельзя построить треугольник, зная только два его параметра. Задание трех его углов тоже не позволяет найти однозначное решение. Алгоритм, как правило, должен приводить к решению задачи за конечное число шагов или предусматривать прекращение бесконечных циклов при выполнении определенных условий.
Решение задач должно начинаться с их точной постановки.
Постановка задачи - это четкое выделение того, что требуется, и того, что дано
Дано → Найти
Следующий этап - определение способа решения задачи.
Способ решения - это набор действий, позволяющих получить требуемое из исходного:
исходное → способ → результаты
Результат правильный, если он отвечает требованиям. Получение результатов - главное в решении любых задач. Отсутствие или неправильность результатов говорит о неуспехе деятельности.
Результат неправильный, если он не соответствует требованиям. Однако при отсутствии четких требований невозможно однозначно судить о правильности или неправильности результатов.
Составление исходной программы
Для того чтобы ПК смог выполнить алгоритм, необходимо разъяснить ему, что и как следует делать. А ПК разговаривает на языке двоичных кодов: 1 или 0, есть сигнал - нет сигнала. Выдавать инструкции процессору на языке его команд - дело весьма непростое. Первые элементы автоматизации процесса написания программ были связаны с заменой числовых кодов машинных операций их мнемоническими символьными обозначениями. Например, команда сложения содержимого двух ячеек памяти вместо сугубо числового кода 01 0100 0101 0102 превращалась в более осмысленное действие типа ADD 0100,0101,0102. Почти сразу же стало ясно, что использование естественной числовой нумерации ячеек памяти становится неразумной преградой между обозначениями переменных решаемой задачи и их эквивалентами в виде числовых адресов. Почему бы не возложить на специальную программу чисто механическую работу по замене символьных обозначений исходных и промежуточных данных задачи на их машинные адреса? И тогда очередной пункт алгоритма, выражавшийся простой формулой z = х + у, превращался в достаточно наглядную и близкую по смыслу команду ADD X,Y,Z. На первом этапе развитие этих идей сдерживало отсутствие устройств ввода/вывода, которые могли бы обрабатывать алфавитно-цифровую информацию. Как только аппаратные средства позволили преодолеть это препятствие, неотъемлемой частью программного обеспечения ЭВМ стали системы, получившие название Автокодов или Ассемблеров.
Следующий бастион, который был взят сторонниками автоматизации тяжелого ручного труда по составлению программ, - укрупнение и стандартизация операций, встречавшихся при решении различных задач. Операции, входившие в состав машинных команд, представляли собой слишком микроскопические действия, на которые приходилось разлагать более понятные человеку процедуры. Так появились алгоритмические языки, каждая строка которых могла быть автоматически трансформирована в цепочку эквивалентных машинных команд. И этот труд по сию пору с честью выполняют многочисленные "переводчики" (трансляторы, компиляторы) и "исполнители" (интерпретаторы).
Программирование заключается в записи алгоритма на языке программирования и отладке программы. Текст программы записывается в текстовом редакторе, затем программа компилируется - переводится транслятором (переводчиком) в машинные коды и запускается на выполнение. Процесс отладки программы начинается с выявления:

· - синтаксических ошибок в тексте (неверно записанных операторов),

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

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

Программы трансляторы бывают двух типов:

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

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