Алгоритм решения любой вычислительной задачи можно описать, используя комбинации из следующих трех стандартных базовых конструкций алгоритмов:
· последовательного алгоритма – алгоритма линейной структуры;
· ветвящегося алгоритма – алгоритма разветвляющейся структуры;
· циклического алгоритма – алгоритма циклической структуры.
Алгоритм линейной структуры – это объединение всех действий в единую цепь, в которой каждое последующее действие строго и однозначно следует за предыдущим действием (рис.2). На языке псевдокода соответствующая последовательность команд запишется в виде:
команда 1; команда 2;...; команда N;
Алгоритм разветвляющейся структуры – содержит проверку одного либо нескольких условий, по результатам которой происходит переключение на один из возможных двух либо один из возможных нескольких вариантов дальнейшего развития процесса. Различают четыре вида ветвящегося алгоритма.
Ветвление «если-то-иначе» (рис.3) встречается на практике наиболее часто. В нем присутствует проверка одного условия, по результатам которой происходит выбор между двумя возможными цепочками дальнейших действий.
На языке псевдокода соответствующая последовательность команд запишется в виде:
если Условие то команда 1;...; команда M иначе команда 2;...; команда N все;
Ветвление «если-то» (рис.4) позволяет при соблюдении проверяемого в нем условия выполнить заданную цепочку действий: команды 1…N. При несоблюдении указанного условия команды 1…N пропускаются и сразу начинает выполняться следующая за ветвлением команда N+1.
На языке псевдокода вариант «если-то» запишется в виде:
если Условие то команда 1;...; команда N все; команда N+1;
|
|
|
Ветвление «выбор» (рис.5) позволяет выбрать одну из N имеющихся альтернатив - цепочек команд. Для каждой альтернативы сначала проверяется соответствующее ей условие, срабатывает та первая альтернатива, у которой оно выполнится. Если не выполнится ни одно из условий выбора – ни одна из N цепочек команд не сработает, а управление перейдет к следующей после ветвления команде.
На языке псевдокода вариант «выбор» запишется в виде:
Ветвление «выбор-иначе» (рис.6) предусматривает проверку условий только у первых N-1 альтернатив, а у последней N-й цепочки команд условие отсутствует. Если не сработает ни одна из первых N-1 альтернатив, то тогда автоматически выполнится N-я цепочка команд. Таким образом, в отличие от ветвления «выбор», здесь обязательно произойдет срабатывание одной из имеющихся N цепочек команд.
На языке псевдокода вариант «выбор-иначе» запишется в виде:
выбор при условие 1: команды 1 при условие 2: команды 2............ при условие N-1: команды N-1 иначе команды N все;Алгоритм циклической структуры обеспечивает повторение операции или группы операций при выполнении некоторого условия, называемого условием цикла. Такое повторение может быть многократным, но не должно быть бесконечным. Если повторение продолжается сколь угодно много раз, то говорят о зацикливании алгоритма. При реализации на компьютере зацикливание приводит к необходимости прервать цикл, не дожидаясь его формального завершения.
|
|
(а)
нц пока Условиекоманда 1; команда 2;...; команда N кц; команда N+1;(б)
нц команда 1; команда 2;...; команда N пока Условие кц; команда N+1;
В тех случаях, когда число повторов выполнения тела цикла заранее известно, для отображении цикла удобно использовать блок модификатор (табл.1), в котором размещается заголовок цикла (рис.8).
В заголовке цикла использованы следующие обозначения:
K – имя параметра цикла - переменной, выполняющей функцию счетчика числа повторов выполнения тела цикла;
k1 – начальное значение параметра цикла;
k2 – конечное значение параметра цикла;
k3 – шаг изменения параметра цикла после очередного выполнения тела цикла. Если этот параметр не указан, шаг изменения полагается равным 1.
Тело цикла составляют команды 1…N.
Такой тип цикла называется циклом с параметром.
На языке псевдокода цикл с параметром отображается с помощью команды для: Нц для К от k1 до k2 шаг k3 команда 1; команда 2;...; команда N кц; команда N+1;
Контрольные вопросы
1. Каково происхождение слова «алгоритм»?
2. Какой цели служит формализация понятия «алгоритм»?
3. Каково определение понятия «вычислительный алгоритм»?
4. В чем состоит свойство массовости вычислительного алгоритма?
5. В чем состоит свойство конечности вычислительного алгоритма?
6. В чем состоит свойство определенности вычислительного алгоритма?
7. В чем состоит свойство детерминированности вычислительного алгоритма?
8. Каковы формы представления вычислительного алгоритма?
9. В чем заключается вербальная форма записи алгоритма, каковы ее недостатки?
10. Что собой представляет запись алгоритма в форме блок-схемы?
11. Какие геометрические фигуры используются для обозначения блоков на блок-схемах алгоритмов, какой тип действий связан с каждой из фигур?
12. В чем состоят преимущества и недостатки представления алгоритма в виде блок-схемы?
13. Что собой представляет запись алгоритма в форме псевдокода?
14. В чем состоит назначение основных ключевых слов псевдокода?
15. Какие разделы в записи псевдокода являются обязательными?
16. На какой стадии разработки алгоритма эффективно использование псевдокода?
17. Какая форма представления алгоритма в наибольшей степени соответствует его реализации в виде компьютерной программы?
18. Каковы базовые структуры вычислительных алгоритмов?
19. Какой алгоритм называется последовательным?
20. Какой алгоритм называется ветвящимся?
21. Каким образом реализуется стандартная конструкция ветвления «если-то»?
22. Каким образом реализуется стандартная конструкция ветвления «если-то-иначе»?
23. Каким образом реализуется стандартная конструкция ветвления «выбор»?
24. Каким образом реализуется стандартная конструкция ветвления «выбор-иначе»?
25. В каких случаях результатом ветвления становится пропуск команды или блока команд?
26. Какой алгоритм называется циклическим?
27. Каким образом реализуется цикл с предусловием?
28. Каким образом реализуется цикл с постусловием?
29. Каким образом реализуется цикл с параметром?
30. В каком из базовых типов цикла возможна ситуация, когда ни разу не выполнится тело цикла?
31. В каком из базовых типов цикла число повторов выполнения тела цикла точно задается заранее?
32. В чем выражается зацикливание алгоритма?
33. В каких базовых типах циклических алгоритмов возможно зацикливание?