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

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

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

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

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-ю строку таблицы Пифагора

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

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

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

Чтобы вычислить все 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) алгоритм обеспечивает решение не одной конкретной задачи, а некоторого класса задач;

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

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.

38. Определите результат выполнения фрагмента алгоритма

вернуться к содержанию