Примеры комбинации основных алгоритмических структур

Ветвящийся процесс, включающий в себя две ветви, называется простым (рис. 9.3). Если ветвь S 1 либо S 2 тоже представляет собой структуру «ВЕТВЛЕНИЕ », то ветвящийся процесс называют сложным. Сложный ветвящийся процесс содержит более двух ветвей.

Пример. Рассмотрим пример сложного ветвящегося вычислительного процесса.

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

a x, если x < 1

Y (x)= x ², если 1 ≤ x ≤ 3

, если x > 3

для x = 0,1, x = 2,5, x = 16, a = 1.

Схема алгоритма решения представлена на рисунке 9.21.

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

Как видно из схемы алгоритма, здесь одна структура «Ветвление» вложена внутрь другой. При x < 1 блоки выполняются в следующей последовательности: 1, 2, 3, 7, 8, 9. Таким образом, если x < 1, в блоке 7 вычисляется . При 1 ≤ x ≤ 3 последовательность выполнения блоков: 1, 2, 3, 4, 6, 8, 9. Следовательно, если 1 ≤ x ≤ 3 в блоке 6 будет вычислено . Если x >3, блоки выполняются в следующей последовательности: 1,2, 3, 4, 5, 8, 9, т.е. при x > 3, в блоке 5 будет вычислено . Полученные результаты соответствуют условию задачи.

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

Пример. Фрагмент блок-схемы алгоритма, описывающий процесс «цикл в цикле», представлен на рисунке 9.23. Данный фрагмент описывает алгоритм вычисления таблицы Пифагора.

Таблица Пифагора.

1*1 1*2 1*3 1*4 1*5 1*6 1*7 1*8 1*9 1*10

2*1 2*2 2*3 2*4 2*5 2*6 2*7 2*8 2*9 2*10

3*1 3*2 3*3 3*4 3*5 3*6 3*7 3*8 3*9 3*10

4*1 4*2 4*3 4*4 4*5 4*6 4*7 4*8 4*9 4*10

5*1……………………………………………………………

6*1……………………………………………………………

7*1…………………………………………………………….

8*1…………………………………………………………….

9*1…………………………………………………………….

10*1 10*2 10*3 10*4 10*5 10*6 10*7 10*8 10*9 10*10

Обозначим строку – i, а столбец – j. Внутри внутреннего цикла элемент таблицы Пифагора равен i * j.

Чтобы вывести на экран монитора 1-ю строку, следует составить простой цикл, представленный на рисунке 9.22.

Рис. 9.22. Визуальное представление алгоритма, выводящего на экран 1-ю строку таблицы Пифагора

Выполним алгоритм последовательно.

	Блок 1. j=1.
цикл	Блок 2. Вывод i * j =1*1. Блок 3. j = j +1=1+1=2. Блок 4. j ≤ 10?, 2≤ 10? Да, следовательно, после блока 4 выполняется блок 2.
цикл	Блок 2. Вывод i * j =1*2. Блок 3. j = j +1=2+1=3. Блок 4. j ≤ 10?, 3≤ 10? Да, следовательно, после блока 4 выполняется блок 2.

Таким же образом последовательность блоков 2, 3 и 4 будет повторяться для j=3, 4, 5, 6, 7, 8, 9.

…………………………………………….

цикл	Блок 2. Вывод i * j =1*10. Блок 3. j = j +1=10+1=11. Блок 4. j ≤ 10?, 11 ≤ 10? Нет, следовательно, после блока 4 произойдёт окончание простого цикла.

Чтобы вычислить все 10 строк, нужно менять строку i. Для этого данный простой цикл по параметру j (столбец) нужно вставить внутрь внешнего цикла по параметру i (строка) (рис. 9.23).

Рис. 9.23. Визуальное представление алгоритма сложного цикла

с количеством вложений, равным двум

Представим последовательное выполнение алгоритма в следующем наглядном виде:

i = 1 j =1 вывод i * j =1*1;

j =2 вывод i *j=1*2;

j =3 вывод i * j =1*3;

………………………..

j =10 вывод i * j =1*10.

j = j +1=10+1=11 11 ≤ 10? Нет, следовательно, после блока 5 выполняется блок 6, который увеличивает параметр i = i +1=1+1=2, переходим ко второй строке. Внутренний цикл по параметру j (столбец) повторяется для параметра i = 2, т.е. для второй строки.

i = 2 j = 1 вывод i * j = 2*1;

j =2 вывод i * j = 2*2;

J = 3 вывод i * j = 2*3;

…………………………

J = 10 вывод i * j = 2*10.

Таким же образом повторяется выполнение цикла для 3, 4, 5, 6, 7, 8, 9 и 10 строки.

После этого i принимает значение 11, проверяется условие 1 ≤ 10, условие не выполняется, и происходит окончание циклического процесса.

Визуальное представление алгоритма сложного цикла с количеством вложений, равным двум, можно представить с использованием символа «Подготовка» (рис. 9.24).

Рис. 9.24. Визуальное представление алгоритма сложного цикла с количеством вложений, равным двум, с использованием символа «Подготовка»

9.11 Вопросы и тестовые задания для самоконтроля

1. Выберите правильную последовательность этапов решения задач на компьютере:

A. выбор и обоснование метода решения;

B. постановка задачи;

C. отладка программы;

D. математическое описание задачи;

E. решение задачи на компьютере и анализ результатов;

F. алгоритмизация вычислительного процесса;

G. составление программы.

Ответы:

1) 1 – B, 2 – D, 3 – A, 4 – F, 5 –- G, 6 – C, 7 – E;

2) 1 – А, 2 – B, 3 – C, 4 - D, 5 – E, 6 – F, 7 – G;

3) 1 – D, 2 – B, 3 – A, 4 – G, 5 – F, 6 – C, 7 – E;

4) 1 – B, 2 – D, 3 – A, 4 – G, 5 – F, 6 – C, 7 – E;

2. На этапе отладки программы:

1) проверяется корректность работы программы.

2) формулируется цель решения задачи;

3) соотношения между величинами, определяющими результат, выражаются посредством математических формул;

4) составляется алгоритм решения задачи согласно действиям, задаваемым выбранным методом решения;

5) алгоритм решения задачи переводится на конкретный язык программирования;

6) определяется состав входных данных.

3. Является ли отсутствие синтаксических ошибок свидетельством правильности программы?

1) Нет, после устранения синтаксических ошибок должна быть проверена логика работы программы в процессе её выполнения с конкретными исходными данными.

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

4. На этапе алгоритмизации вычислительного процесса:

1) выполняется проектирование алгоритма решения задачи согласно действиям, задаваемым выбранным методом решения;

2) соотношения между величинами, определяющими результат, выражаются посредством математических формул;

3) проверяется корректность работы программы;

4) алгоритм решения задачи переводится на конкретный язык программирования;

5) формулируется цель решения задачи;

6) определяется состав входных данных.

5. На этапе составления программы:

1) алгоритм решения задачи переводится на конкретный язык программирования;

2) определяется состав входных данных;

3) соотношения между величинами, определяющими результат, выражаются посредством математических формул;

4) выполняется проектирование алгоритма решения задачи согласно действиям, задаваемым выбранным методом решения;

5) формулируется цель решения задачи;

6) проверяется корректность работы программы.

6. Деятельность, направленная на выявление ошибок в программе, называется:

1) тестирование;

2) отладка;

3) композиция;

4) программирование.

7. Деятельность, направленная на устранение ошибок в программе, называется:

1) отладка;

2) тестирование;

3) композиция;

4) программирование.

8. Язык программирования, допускающий непосредственное исполнение программы, написанной с помощью данного языка, называется:

1) машинным;

2) функциональным;

3) процедурным;

4) логическим.

9. Выявленное на этапе отладки программы нарушение формы записи программы приводит к сообщению об ошибке:

1) синтаксической;

2) орфографической;

3) грамматической;

4) логической.

10. Алгоритм – это:

1) понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели;

2) правила выполнения определённых действий;

3) указание на выполнение действий;

4) набор команд для компьютера;

5) протокол вычислительной сети.

11. Какой из документов является алгоритмом?

1) инструкция по получению денег в банкомате;

2) правила техники безопасности;

3) список группы;

4) расписание занятий.

12. К свойствам алгоритма относятся:

A. дискретность;

B. уникальность;

C. неопределённость;

D. массовость;

E. детерминированность (определённость);

F. результативность;

G. стохастичность;

H. формальность.

Ответы:

1) A, D, E, F, H;

2) D, A, B, F, H;

3) A, B, C, D, E;

4) A, B, C, D, E, F;

5) A, B, C, D, E, F, H;

6) A, B, C, D, E, F, G, H.

13. Свойство алгоритма − дискретность – заключается в том, что:

1) алгоритм всегда состоит из последовательности дискретных шагов;

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

3) алгоритм обеспечивает решение не одной конкретной задачи, а некоторого класса задач;

4) алгоритм должен состоять из команд, не допускающих произвола в толковании;

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

14. Свойство алгоритма − массовость – заключается в том, что:

1) алгоритм обеспечивает решение не одной конкретной задачи, а некоторого класса задач;

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

3) любой исполнитель, строго выполняя инструкции, получает необходимый результат;

4) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов и привести к определённому результату;

5) алгоритм должен состоять из команд, не допускающих произвола в толковании.

15. Свойство алгоритма − определённость (детерминированность, точность) – заключается в том, что:

1) алгоритм должен состоять из команд, не допускающих произвола в толковании;

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

3) любой исполнитель, строго выполняя инструкции, получает необходимый результат;

4) алгоритм обеспечивает решение не одной конкретной задачи, а некоторого класса задач;

5) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов и привести к определённому результату.

16. Свойство алгоритма − результативность – заключается в том, что:

1) при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов и привести к определённому результату;

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

3) любой исполнитель, строго выполняя инструкции, получает необходимый результат;

4) алгоритм обеспечивает решение не одной конкретной задачи, а некоторого класса задач;

5) алгоритм должен состоять из команд, не допускающих произвола в толковании.

17. Свойство алгоритма − формальность – заключается в том, что:

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

2) алгоритм должен состоять из команд, не допускающих произвола в толковании;

3) алгоритм всегда состоит из последовательности дискретных шагов;

4) алгоритм обеспечивает решение не одной конкретной задачи, а некоторого класса задач;

18. Укажите наиболее полный перечень способов записи алгоритмов:

1) словесный, графический, псевдокод, программный, табличный;

2) словесный, псевдокод;

3) графический, табличный, программный;

4) словесный, программный.

19. Средством записи алгоритмов не являются:

1) блок-схемы;

2) псевдокоды;

3) языки программирования;

4) словесно-формульная запись;

5) компиляторы.

20. Как называется графическое представление алгоритма:

1) блок-схема;

2) последовательность формул;

3) таблица;

4) словесное описание;

5) псевдокод?

21. На рисунках представлены части блок-схемы. В каком порядке они расположены?

1) 1 − предикатная; 2 − объединяющая; 3 − функциональная;

2) 1 − объединяющая; 2 − предикатная; 3 − функциональная;

3) 1 − функциональная; 2 − объединяющая; 3 − предикатная;

4) 1 −объединяющая; 2 − функциональная; 3 − предикатная;

5) 1 − предикатная; 2 − функциональная; 3 − объединяющая;

6) 1 − функциональная; 2 − предикатная; 3 − объединяющая.

22. Сколько выходов содержит данный блок:

23. Сколько выходов содержит данный блок:

24. При использовании метода структурной алгоритмизации используются понятия:

A. Следование;

B. Альтернатива (ветвление);

C. Итерация (цикл);

D. Подготовка.

Ответы:

1) A, B, C;

2) A, B, D;

3) A, B;

4) B, C, D;

5) C, D.

25. На рисунках представлены базовые управляющие алгоритмические структуры. В каком порядке они расположены?

1) 1 − «Следование»; 2 − «Ветвление»; 3 − «Цикл с постусловием»; 4 − «Цикл с предусловием»;

2) 1 − «Следование»; 2 − «Цикл с постусловием»; 3 − «Ветвление»; 4 − «Цикл с предусловием»;

3) 1 − «Следование»; 2 − «Ветвление»; 3 − «Цикл с предусловием»; 4 − «Цикл с постусловием»;

4) 1 − «Ветвление»; 2 − «Следование»; 3 − «Цикл с постусловием»; 4 − «Цикл с предусловием»;

5) 1 − «Цикл с постусловием»; 2 − «Ветвление»; 3 − «Следование»; 4 − «Цикл с предусловием».

26. Алгоритм линейной структуры:

1) содержит линейную последовательность связанных друг с другом блоков;

2) содержит блок «решение»;

3) содержит структуру «ветвление»;

4) содержит предикатную вершину.

27. Назовите базовую управляющую структуру, реализующую линейный вычислительный процесс:

28. Назовите базовую управляющую структуру, реализующую разветвляющийся вычислительный процесс:

29. Определите значение переменной Y после выполнения фрагмента алгоритма в каждом из следующих случаев: если 1) a = 3 и b = 9; 2) a = 4 и b = 3. 3) a = 7 и b = 7.

30. Назовите базовую управляющую структуру, реализующую циклический вычислительный процесс:

31. Утверждение, что операция в теле цикла будет выполнена хотя бы один раз, относится к циклу:

1) с постусловием;

2) с предусловием;

3) с параметром;

4) табулирования функции.

32. В тестовом задании 9.3 представлен фрагмент циклического алгоритма, записанный в словесно-формульном виде. Представьте данный алгоритм в графической форме. Какая разновидность базовой циклической структуры реализована в данном алгоритме:

1) с постусловием;

2) с предусловием;

3) с параметром;

4) табулирования функции?

33. В тестовом задании 9.5 представлен фрагмент циклического алгоритма, записанный в словесно-формульном виде. Представьте данный алгоритм в графической форме. Какая разновидность базовой циклической структуры реализована в данном алгоритме:

1) с предусловием

2) с постусловием;

3) с параметром;

4) табулирования функции?

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

35. Укажите, какие результаты будут выведены на экран монитора при выполнении следующего фрагмента алгоритма:

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

1) x = 0.5; 2) x = 1.5; 3) x = 3; 4) x = 5:

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

Тот же алгоритм, представленный с помощью символа «подготовка»: 1) 1 2 3 2 4 6 3 6 9 4 8 12; 2) 1 2 3 3 6 9 2 4 6 4 8 12; 3) 1 2 3 4 3 6 9 2 4 6 8 12; 4) 1 2 3 4 2 4 6 8 3 6 9 12; 5) 1 2 3 3 6 9 2 6 8 4 9 12.