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

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

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

· ветвящегося алгоритма – алгоритма разветвляющейся структуры;

· циклического алгоритма – алгоритма циклической структуры.

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

команда 1; команда 2; . . . ; команда N;

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

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

На языке псевдокода соответствующая последовательность команд запишется в виде:

Ветвление «если-то» (рис.4) позволяет при соблюдении проверяемого в нем условия выполнить заданную цепочку действий: команды 1…N. При несоблюдении указанного условия команды 1…N пропускаются и сразу начинает выполняться следующая за ветвлением команда N+1.

На языке псевдокода вариант «если-то»запишется в виде:

Ветвление «выбор» (рис.5) позволяет выбрать одну из N имеющихся альтернатив - цепочек команд. Для каждой альтернативы сначала проверяется соответствующее ей условие, срабатывает та первая альтернатива, у которой оно выполнится. Если не выполнится ни одно из условий выбора – ни одна из N цепочек команд не сработает, а управление перейдет к следующей после ветвления команде.

На языке псевдокода вариант «выбор»запишется в виде:

Ветвление «выбор-иначе» (рис.6) предусматривает проверку условий только у первых N-1 альтернатив, а у последней N-й цепочки команд условие отсутствует. Если не сработает ни одна из первых N-1 альтернатив, то тогда автоматически выполнится N-я цепочка команд. Таким образом, в отличие от ветвления «выбор», здесь обязательно произойдет срабатывание одной из имеющихся N цепочек команд.

На языке псевдокода вариант «выбор-иначе»запишется в виде:

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

(а)

(б)

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

В заголовке цикла использованы следующие обозначения:

K – имя параметра цикла - переменной, выполняющей функцию счетчика числа повторов выполнения тела цикла;

k1 – начальное значение параметра цикла;

k2 – конечное значение параметра цикла;

k3 – шаг изменения параметра цикла после очередного выполнения тела цикла. Если этот параметр не указан, шаг изменения полагается равным 1.

Тело цикла составляют команды 1…N.

Такой тип цикла называется циклом с параметром.

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

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. В каких базовых типах циклических алгоритмов возможно зацикливание?

Контрольные задания по составлению алгоритмов

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

Пример 1.

Ввести три различных вещественных числа a, b, c и определить среди них максимальное и минимальное значения.

Решение.При составлении алгоритма решения задачи целесообразно воспользоваться стандартной конструкцией ветвления «выбор-иначе».

Всего имеется 7 альтернативных вариантов расчета, из которых первые 6 связаны соответственно с выполнением условий a>b>c, a>c>b, b>a>c, b>c>a, c>a>b, c>b>a, а последний 7-й вариант отражает случай ввода некорректных данных, когда среди величин a, b, c по крайней мере для двух были введены одинаковые значения.

Блок-схема алгоритма решения задачи представлена на рис.9. Соответствующий текст псевдокода с комментариями имеет вид:

Пример 2.

Ввести значения элементов таблицы вещественных чисел X[i,j] из m строк и n столбцов (m>0, n>0) и подсчитать сумму S всех отрицательных элементов таблицы.

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

В начальный момент перед вводом значений элементов таблицы искомая сумма S полагается равной нулю. В дальнейшем после ввода каждого очередного элемента таблицы X[i,j] происходит проверка значения элемента на отрицательность и, при необходимости – добавление этого значения в сумму S.

Блок-схема алгоритма решения задачи представлена на рис.10. Соответствующий текст псевдокода с комментариями имеет вид:

Список вариантов заданий:

1. Составить алгоритм, вводящий положительные целые числа K, L, M, N и, считая их массами гирь, выясняющий, можно ли все эти гири как-либо положить на обе чаши весов таким образом, чтобы весы оказались в равновесии.

2. Составить алгоритм, вводящий вещественные числа A, B, C, D и, рассматривая эти числа как координаты четырех точек на прямой, определяющий расстояние между двумя самыми близкими друг к другу точками.

3. Составить алгоритм, вводящий значения элементов таблицы вещественных чисел X[i,j] из m строк и n столбцов (m>0, n>0 вводятся в начале работы) и определяющий число Q всех отрицательных элементов этой таблицы.

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

5. Составить алгоритм, вводящий значения элементов K[i] последовательности n целых чисел (n>0 вводится в начале работы) и определяющий число maxpodp элементов в ее наиболее длинной невозрастающей подпоследовательности.

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

7. Составить алгоритм, вводящий значения элементов таблицы целых чисел K[i,j] из m строк и n столбцов (m>0, n>0 вводятся в начале работы) и определяющий номер imin той строки, в которой находится минимальный элемент таблицы.

8. Составить алгоритм, вводящий положительные целые числа K, L, M, N и, считая их массами гирь, выясняющий, можно ли как-либо уравновесить гирю с массой K, если гири с массами L, M, N можно класть каждую на любую из чаш весов.

9. Составить алгоритм, вводящий значения элементов таблицы целых чисел K[i,j] из m строк и n столбцов (m>0, n>0 вводятся в начале работы) и определяющий номер imax той строки, в которой находится максимальный элемент таблицы.

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

11. Составить алгоритм, вводящий три целых числа, который находит второе по величине число, если такое число существует, а в противном случае печатает фразу «требуемое число отсутствует».

12. Составить алгоритм, вводящий значения элементов таблицы вещественных чисел X[i,j] из m строк и n столбцов (m>0, n>0 вводятся в начале работы) и определяющий число P всех положительных элементов этой таблицы.

13. Составить алгоритм, вводящий вещественные числа A, B, C, D и, рассматривая эти числа как координаты точек на прямой, определяющий расстояние между двумя наиболее удаленными друг от друга точками.

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

15. Составить алгоритм, вводящий значения элементов K[i] последовательности n целых чисел (n>0 вводится в начале работы) и печатающий все элементы последовательности в порядке их невозрастания.

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

17. Составить алгоритм, вводящий значения элементов таблицы целых чисел K[i,j] из m строк и n столбцов (m>0, n>0 вводятся в начале работы) и определяющий номер jmin того столбца, в котором находится минимальный элемент таблицы.

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

19. Составить алгоритм, вводящий значения элементов K[i] последовательности n целых чисел (n>0 вводится в начале работы) и печатающий все элементы последовательности в порядке их неубывания.

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

21. Составить алгоритм, вводящий значения элементов K[i] последовательности n целых чисел (n>0 вводится в начале работы) и определяющий такой ее элемент K[sredn], что количество элементов, меньших K[sredn], совпадает с количеством элементов больших K[sredn]. Eсли же такого элемента K[sredn] в последовательности K[i] не окажется – напечатать фразу «требуемый элемент последовательности отсутствует».

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

23. Составить алгоритм, вводящий значения элементов таблицы целых чисел K[i,j] из m строк и n столбцов (m>0, n>0 вводятся в начале работы) и определяющий номер jmax того столбца, в котором находится максимальный элемент таблицы.

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

25. Составить алгоритм, вводящий значения элементов K[i] последовательности n целых чисел (n>0 вводится в начале работы) и определяющий число lokmax локальных максимумов в последовательности (элемент является локальным максимумом, если он не имеет ближайших соседей, больших, чем он сам).

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

27. Составить алгоритм, вводящий значения элементов K[i] последовательности n целых чисел (n>0 вводится в начале работы) и определяющий число maxpodp элементов в ее наиболее длинной неубывающей подпоследовательности.

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

29. Составить алгоритм, вводящий значения элементов K[i] последовательности n целых чисел (n>0 вводится в начале работы) и определяющий число lokmin локальных минимумов в последовательности (элемент является локальным минимумом, если он не имеет ближайших соседей, меньших, чем он сам).

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

ОГЛАВЛЕНИЕ

Введение. 3

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

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

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

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

Контрольные задания по составлению алгоритмов. 20

Не нашли, что искали? Воспользуйтесь поиском по сайту: