Метод при котором сложная задача разбивается на несколько более простых получившиеся задачи сводятся
Вы уже убедились в том, что выделение вспомогательных алгоритмов – мощное средство, облегчающее решение сложных задач. Но использовать его можно не только так, как мы делали это до сих пор, выделяя вспомогательные алгоритмы из практически уже готовых алгоритмов. Гораздо более эффективным является другой метод, который называется методом пошаговой детализации или последовательного построения алгоритмов. Об этом методе и пойдет речь.
Давайте составим для Кенгуренка алгоритм рисования на листе бумаги слова РОБОТ – (высота каждой буквы – 4 см, ширина – 1 см, расстояние между буквами – 1 см).
Попробуем сначала записать весь алгоритм с ходу:
Уф. А ведь мы всего лишь описали, как рисовать букву Р. Если продолжать в том же духе, то получится очень длинный и нерациональный алгоритм. К тому же он наверняка будет содержать ошибки, которые трудно обнаружить, глядя на эту запись.
Традиционный метод составления алгоритмов в данном случае, как видите, малоэффективен. Попробуем иначе подойти к решению задачи. Ясно, что Кенгуренок должен последовательно нарисовать буквы Р, О, Б, О, Т. Таким образом, наша задача разбивается на пять этапов:
Считая, что вспомогательные алгоритмы рисования букв уже составлены, запишем сразу основной алгоритм:
Теперь можно приступить к составлению вспомогательных алгоритмов. При этом нужно позаботиться о двух вещах. Во-первых, чтобы Кенгуренок правильно нарисовал отдельные буквы, а во-вторых, чтобы, выполнив основной алгоритм, он сложил из них слово РОБОТ. Иначе говоря, надо заботиться не только о рисовании самих букв, но и об их «стыковке». Это напоминает строительство дома: надо заботиться не только о качестве кирпичей, но и о том, чтобы между ними не оставалось щелей. Таким образом, основной алгоритм предъявляет дополнительные требования к «стыковке» вспомогательных алгоритмов.
В нашем случае эти требования могут быть, например, такими. Будем считать, что Кенгуренок начинает рисование каждой буквы с ее левой нижней точки, глядя вправо. Каждый из вспомогательных алгоритмов должен выводить Кенгуренка в исходную позицию для рисования следующей буквы.
Записав основной алгоритм и определив требования к вспомогательным алгоритмам, мы «спустились» на более низкий уровень в решении задачи, упростили себе дальнейшую работу. Однако алгоритмы рисования отдельных букв тоже не так уж просты (вспомните нашу попытку написать алгоритм рисования буквы Р). Значит, составление каждого из них также целесообразно разбить на несколько этапов, «спустившись» еще ниже. И так далее, до тех пор, пока задачи очередного уровня не окажутся совсем простыми. Итак, продолжим «спуск».
Легко обнаружить общий элемент у букв Р, О и Б. Назовем его Угол. Вы без труда напишете вспомогательный алгоритм рисования «угла».
Воспользовавшись этим алгоритмом, а также алгоритмом Направо (см. задачу № 10), можно записать каждый из пяти вспомогательных алгоритмов. Вот, например, вспомогательный алгоритм Р:
процедура Р
сделай Угол
сделай Направо
сделай Направо
конец процедуры
Остальные вспомогательные алгоритмы напишите самостоятельно.
Метод, при котором сложная задача разбивается на несколько более простых, получившиеся задачи сводятся к еще более простым и так далее, называется методом пошаговой детализации. Этот метод универсален. Он всегда применяется в тех случаях, когда требуется спроектировать сложный объект, будь то большой алгоритм, прокатный стан, интегральная микросхема или пятилетний план. Да и вообще решение каждой более или менее сложной задачи проводится методом пошаговой детализации.
Конструирование алгоритма. Рекурсивный алгоритм — 1 вариант
Внимание! Все тесты в этом разделе разработаны пользователями сайта для собственного использования. Администрация сайта не проверяет возможные ошибки, которые могут встретиться в тестах.
В тесте рассматриваются вопросы последовательного построения алгоритма методом детализации + задача на рекурсивный алгоритм
Система оценки: 5** балльная
Список вопросов теста
Вопрос 1
Алгоритм, целиком используемый в составе другого алгоритма, называется…
Варианты ответов
- циклическим
- основным
- вспомогательным
- линейным
Вопрос 2
Метод, при котором сложная задача разбивается на несколько более простых, получившиеся задачи сводятся к еще более простым и т. д., называется …
Варианты ответов
- методом разработки «сверху вниз»
- методом разработки «снизу вверх»
- итерационным методом
- восходящим методом
Вопрос 3
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (n + 1), при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.
Вопрос 4
Известен рост каждого из n учеников 9А класса и m учеников 9Б класса. Опишите укрупненными блоками алгоритм сравнения среднего роста учеников этих классов.
Варианты ответов
- Определить средний рост учеников первого класса
- Определить средний рост учеников второго класса
- Сравнить средний рост учеников двух классов, 9А и 9Б классов
Вопрос 5
Исполнитель Удвоитель из числа -3 получил число 11, используя только одну команду «прибавь 1». Сколько команд выполнил Удвоитель?
9_1.1. Информатика 2023. Конструирование алгоритмов
Внимание! Все тесты в этом разделе разработаны пользователями сайта для собственного использования. Администрация сайта не проверяет возможные ошибки, которые могут встретиться в тестах.
9 класс. Информатика. Тест «Конструирование алгоритмов»
Система оценки: 5 балльная
Список вопросов теста
Вопрос 1
Дан массив из 100 целых чисел. Необходимо найти разность между количеством максимальных и минимальных элементов, содержащихся в этом массиве. Укажите возможный план действий по решению этой задачи:
Варианты ответов
- • Найти значение максимального элемента массива
• Найти значение минимального элемента массива
• Найти количество максимальных элементов массива
• Найти количество минимальных элементов массива
• Найти разность между количеством максимальных и минимальных элементов массива - • Найти количество максимальных элементов массива
• Найти значение максимального элемента массива
• Найти значение минимального элемента массива
• Найти количество минимальных элементов массива
• Найти разность между количеством максимальных и минимальных элементов массива - • Найти значение максимального элемента массива
• Найти количество минимальных элементов массива
• Найти количество максимальных элементов массива
• Найти значение минимального элемента массива
• Найти разность между количеством максимальных и минимальных элементов массива
Вопрос 2
Метод, при котором алгоритм сначала формулируется в «крупных» блоках (командах), которые могут быть непонятны исполнителю (не входят в его систему команд), а затем происходит детализация, и все блоки подробно расписываются с использованием команд, понятных исполнителю, называется …
Варианты ответов
- методом разработки «снизу вверх»
- итерационным методом
- методом пошаговой детализации
- восходящим методом
Вопрос 3
Параметры, используемые при конкретном обращении к вспомогательному алгоритму, называются …
Варианты ответов
- фактическими
- формальными
Вопрос 4
Алгоритм, в котором прямо или косвенно содержится ссылка на него же, как на вспомогательный алгоритм, называют…
Варианты ответов
- линейным
- рекурсивным
- основным
- циклическим
Вопрос 5
Укажите рекурсивные объекты:
Варианты ответов
Вопрос 6
Имена и типы переменных, которые заявлены в качестве формальных параметров, объявляются внутри вспомогательного алгоритма по тем же правилам, что и для основного алгоритма. Такие переменные называются .
Варианты ответов
- локальными
- глобальными
Вопрос 7
Функция S(n) вычисляется по следующему алгоритму:
S(1) = 1,
S(n) = 2· S(n — 1) при натуральном n > 1.
Чему равно значение функции S(8)?
Вопрос 8
Укажите порядок построения линейного алгоритма, являющегося результатом первого этапа детализации задачи.
Варианты ответов
- Начало
- Исходные данные
- Постановка задачи
- Результат
- Конец
Вопрос 9
Алгоритм, целиком используемый в составе другого алгоритма, называется…
Варианты ответов
- линейным
- вспомогательным
- основным
- циклическим
Вопрос 10
Метод, при котором сложная задача разбивается на несколько более простых, получившиеся задачи сводятся к еще более простым и т. д., называется …
Варианты ответов
- методом разработки «сверху вниз»
- методом разработки «снизу вверх»
- восходящим методом
- итерационным методом
4. Разработка алгоритмов методом пошаговой детализации
Одним из основных методов решения сложной задачи в любой области человеческой деятельности является метод декомпозиции, когда сложная задача разбивается на несколько более простых задач — на подзадачи. Этот процесс продолжается до тех пор, пока выделенные после очередной декомпозиции подзадачи не будут упрощены настолько, что их в состоянии будут решать конкретные исполнители. Процесс декомпозиции можно изобразить графически: Аналогичный подход используется и при разработке программ, а метод, использующий его, получил название метода пошаговой детализацииили метода нисходящего проектирования программы. При методе пошаговой детализации алгоритм решения исходной задачи представляется как совокупность более простых алгоритмов, которые, в свою очередь, разбиваются на еще более простые и т.д. Выделенные алгоритмы могут быть как не имеющими законченного функционального назначения, так и функционально независимыми. В первом случае выделяется часть алгоритма, которую проще разработать отдельно и затем вставить в исходный алгоритм. Во втором случае выделенные алгоритмы можно проектировать как самостоятельные задачи и оформлять на языке программирования в виде подпрограмм. Как известно, подпрограмма не решает всей задачи, она – часть программы, реализующая строго определенные функции. Разработка подпрограммы должна начинаться с разработки внешней спецификации, в которой обязательно выделяются входные и выходные данные, которые в языках программирования называются соответственно входными и выходными параметрами. Некоторые входные данные могут быть одновременно и выходными, т.е. допускать изменение значений в подпрограмме. Во внешней спецификации также обязательно фиксируются ограничения на значения входных аргументов, которые отражаются в разделе “Аномалии входных данных”. Реакции подпрограммы на аномалии рекомендуется обеспечивать через ее выходные данные. Процесс пошаговой детализации алгоритма конечен, а число шагов зависит от сложности задачи и квалификации разработчика. Его рекомендуется завершать тогда, когда на очередном шаге получается текст, запись которого на языке программирования не представляет проблем для разработчика. В пределе этот процесс можно завершить тогда, когда каждая строка алгоритма может быть заменена одним оператором языка программирования.
4.1. Структура алгоритма
Запись каждой детализации должна быть оформлена так, как это изображено ниже: (а) – для случая несамостоятельной части алгоритма; (б) – для случая алгоритма, выделяемого в самостоятельную подпрограмму. План алгоритма “Название” Внутренние переменные: Начало Конец (а) Алгоритм“Название” Входные переменные: Выходные переменные: Внутренние переменные: Начало Конец (б) Отметим, что для случая (а) раздел внутренних переменных вставляется только в том случае, если при разработке указанного плана недостаточно внутренних переменных алгоритма предшествующего уровня. В любом случае данные переменные являются глобальными для этой части алгоритма. Глобальнымипеременными считаются такие, которые определены для алгоритма верхнего уровня, с которого осуществляется переход на текущий уровень. Примечание. В дальнейшем с целью сокращения записи вместо слов “план алгоритма” будет употребляться одно слово “план”.
30.04.2013 286.21 Кб 39 Глава01-02.doc
30.04.2013 102.91 Кб 17 Глава03.doc
30.04.2013 183.81 Кб 18 Глава04.doc
30.04.2013 74.24 Кб 16 Глава05.doc
30.04.2013 130.56 Кб 15 Глава06.doc
30.04.2013 153.09 Кб 15 Глава07.doc
30.04.2013 49.66 Кб 15 Глава08.doc
30.04.2013 87.55 Кб 15 Глава09.doc
Ограничение
Для продолжения скачивания необходимо пройти капчу: