Конструирование алгоритмов
Последовательное построение алгоритма
Существуют различные методы конструирования (разработки, построения) алгоритмов. Мы познакомимся с одним из них — методом последовательного построения (уточнения) алгоритма. Иначе он называется методом разработки «сверху вниз», нисходящим методом или методом пошаговой детализации.
Процесс последовательного построения алгоритма выглядит следующим образом.
На первом шаге мы считаем, что перед нами совершенный исполнитель, который «всё знает и всё умеет». Поэтому достаточно определить исходные данные и результаты алгоритма, а сам алгоритм представить в виде единого предписания — постановки задачи (рис. 2.4).
Рис. 2.4. Линейный алгоритм, являющийся результатом первого этапа детализации задачи
Если исполнитель не обучен исполнять заданное предписание, то необходимо представить это предписание в виде совокупности более простых предписаний (команд).
• задачу разбивают на несколько частей, каждая из которых проще всей задачи;
Блок-схемы для начинающих (Блок схемы алгоритмов)
• решение каждой части задачи формулируют в отдельной команде, которая также может выходить за рамки системы команд исполнителя;
• при наличии в алгоритме предписаний, выходящих за пределы возможностей исполнителя, такие предписания вновь представляются в виде совокупности ещё более простых предписаний.
Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.
Объединяя полученные предписания в единую совокупность выполняемых в определённой последовательности команд, получаем требуемый алгоритм решения исходной задачи.
Разработка алгоритма методом последовательного уточнения для исполнителя Робот
Вы уже знакомы с исполнителем Робот. Он действует на клетчатом поле, между клетками которого могут быть стены.
Система команд исполнителя Робот:
В одном условии можно использовать несколько команд, применяя логические операции И, ИЛИ, НЕ.
Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.
Составим алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.
Представим план действий Робота следующими укрупнёнными шагами (модулями):
Детализируем каждый из пяти модулей.
1. Чтобы закрасить все клетки коридора, находящиеся левее Робота, прикажем Роботу шагнуть влево и выполнить цикл — ПОКА:
нц пока сверху стена и снизу стена закрасить; влево
Под управлением этого алгоритма Робот закрасит все клетки коридора, находящиеся левее от него, и окажется в клетке левее коридора.
2. Командой вправо вернём Робота в коридор. Наша задача — вернуть Робота в исходную клетку. Эта клетка — первая незакрашенная клетка, находящаяся правее Робота. Поэтому пока занимаемая Роботом клетка оказывается закрашенной, будем перемещать его вправо.
нц пока клетка закрашена вправо
Под управлением этого алгоритма Робот окажется в исходной клетке.
3. Выполнив команду вправо, Робот пройдёт исходную клетку и займёт клетку правее исходной. Теперь можно закрашивать клетки коридора, расположенные правее исходной.
нц пока сверху стена и снизу стена закрасить; вправо
4. Так как, выполнив предыдущий алгоритм, Робот оказался правее коридора, командой влево вернём его в коридор. Возвращение в исходную клетку обеспечивается алгоритмом:
нц пока клетка закрашена влево
5. По команде закрасить Робот закрашивает исходную клетку. Полностью программа управления Роботом выглядит так:
Вспомогательные алгоритмы
При построении новых алгоритмов нередко возникают ситуации, когда в разных местах алгоритма необходимо выполнение одной и той же последовательности шагов обработки данных. Для такой последовательности шагов создают отдельный алгоритм, называемый вспомогательным. В качестве вспомогательных могут использоваться алгоритмы, ранее разработанные для решения других задач.
Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.
Пример 1 . В среде КуМир составим алгоритм для исполнителя Робот, под управлением которого он нарисует узор:
Начальное положение Робота отмечено звёздочкой. В алгоритме использован вспомогательный алгоритм фигура.
При представлении алгоритмов с помощью блок-схем для обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс» (рис. 2.5), внутри которого записывается название (имя) вспомогательного алгоритма, после которого в скобках перечисляются параметры — входные данные и результаты.
Рис. 2.5. Блок «предопределённый процесс»
Вспомогательный алгоритм делает структуру алгоритма более понятной.
Пример 2 . Вспомним алгоритм вычисления степени с натуральным показателем у = а n . Соответствующая блок-схема:
Степень с целым показателем у = а х , где х — целое число, а ≠ 0 вычисляется так:
В приведённой записи дважды фигурирует вычисление степени с натуральным показателем. Поэтому в алгоритм вычисления степени с целым показателем можно включить вызов вспомогательного алгоритма вычисления степени с натуральным показателем. Соответствующая блок-схема:
Алгоритм, представленный на блок-схеме, является основным по отношению к вызываемому в нём вспомогательному алгоритму.
Параметрами используемого вспомогательного алгоритма являются величины а, n, у. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать.
Команда вызова вспомогательного алгоритма исполняется следующим образом (рис. 2.6):
1) формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
2) для заданных входных данных исполняются команды вспомогательного алгоритма;
3) полученные результаты присваиваются переменным с именами фактических результатов;
4) осуществляется переход к следующей команде основного алгоритма.
Рис. 2.6. Схема выполнения команды вызова вспомогательного алгоритма
Алгоритм, в котором прямо или косвенно содержится ссылка на него же как на вспомогательный алгоритм, называют рекурсивным.
Рассмотрим несколько примеров рекурсивных алгоритмов.
Пример 3 . Алгоритм вычисления степени с натуральным показателем п для любого вещественного числа а можно представить в виде рекурсивного:
Число а в степени n (n-я степень числа а) есть не что иное, как произведение а n-1 • а; в свою очередь, а n-1 = а n-2 • а и т. д.
Пример 4 . Рекурсивный алгоритм положен в основу эффективного решения головоломки «Ханойская башня».
Интерактивная игра «Ханойские башни» (195747) поможет вам вспомнить условие и алгоритм решения головоломки (http://sc.edu.ru/).
Пример 5 . Рассмотрим алгоритм построения геометрической фигуры, которая называется снежинкой Коха. Шаг процедуры построения состоит в замене средней трети каждого из имеющихся отрезков двумя новыми такой же длины, как показано на рисунке:
С каждым шагом фигура становится всё причудливее. Граница снежинки Коха — положение кривой после выполнения бесконечного числа шагов.
Попробуйте подсчитать, сколько рёбер в границе снежинки Коха после четвёртого шага; после пятого шага.
Источник: skobelevserg.jimdofree.com
Принципы разработки алгоритмов и программ
Человеку в жизни и практической деятельности приходится решать множество различных задач. Решение каждой из них описывается своим алгоритмом, и разнообразие этих алгоритмов очень велико. Тем не менее можно выделить лишь три основных вида алгоритмов (для краткости далее будем называть их просто: линейные, разветвляющиеся и циклические алгоритмы):
Линейный алгоритм – алгоритм, в котором порядок действий фиксирован и каждое действие выполняется только один раз. Разветвляющийся алгоритм–алгоритм, порядок действий в котором зависит от некоторых условий. Разнообразие же алгоритмов определяется тем, что любой алгоритм распадается на части, фрагменты и каждый фрагмент представляет собой алгоритм одного из трех указанных видов. Поэтому важно знать структуру каждого из алгоритмов и принципы их составления.
Отметим, что алгоритм заварки чая, приведенный выше, является по своей структуре линейным, алгоритм задачи 4.1. — разветвляющимся. Примером циклического алгоритма может служить алгоритм начисления зарплаты согласно правилу задачи 4.1, но не для одного сотрудника, а для группы, например, из 20 человек, т. е. алгоритм, в котором многократно выполняются одни и те же операции.
Рассмотрим суть упомянутых принципов на конкретной задаче.
Даны длины двух катетов прямоугольного треугольника. Определить периметр этого треугольника. Требуется составить алгоритм решения задачи.
1. Выделяем исходные данные и результаты (это первое, что должен содержать алгоритм, согласно правилам его записи). Исходные данные: А, В — длины катетов. Результат: Р — периметр треугольника.
2. Согласно определению: «Алгоритм — это метод решения задачи…». Следовательно, далее нужно выбрать метод решения задачи — и это самое главное! («нельзя сварить бульон из курицы, не имея курицы»). А зная метод, надо изложить его в соответствии с правилами записи алгоритмов, т. е. сначала разбить его на этапы. В нашем случае метод решения задачи на ЭВМ такой:
Решение задачи, как видим, состоит из IV этапов.
Далее изображаем каждый из указанных этапов в виде определенной геометрической фигуры (блока) и соединяем их стрелками. В результате получаем схему алгоритма задачи (см. рис. 4.2).
Можно сформулировать общие правила построения схемы алгоритма задачи (иногда их называют «Основные принципы алгоритмизации»):
1. Выявить исходные данные, результаты, дать им имена.
2. Выбрать метод (порядок) решения задачи.
3. Разбить метод решения задачи на этапы (с учетом возможностей ЭВМ).
4. Изобразить каждый этап в виде соответствующего блока схемы алгоритма и указать стрелками порядок их выполнения.
5. В полученной схеме при любом варианте вычислений:
— предусмотреть выдачу результатов или сообщений об их отсутствии;
— обеспечить возможность после выполнения любой операции так или иначе перейти к блоку Останов (к выходу схемы).
Рис. 4.2 Схема алгоритма задачи
Введение в вычислительные сети
1.1. Сети: основные понятия
Телематика – это новая научно-техническая дисциплина, предметом которой являются методы и средства передачи информации на расстояния, существенно превышающие линейные размеры площади, занимаемой участниками связи. Название дисциплины произошло из частей слов “телекоммуникации” и “информатика”.
Коммуникационная сеть – система, состоящая из объектов, осуществляющих функции генерации, преобразования, хранения и потребления продукта, называемых пунктами (узлами) сети, и линий передачи (связей, коммуникаций, соединений), осуществляющих передачу продукта между пунктами.
Отличительная особенность коммуникационной сети – большие расстояния между пунктами по сравнению с геометрическими размерами участков пространства, занимаемых пунктами. В качестве продукта могут фигурировать информация, энергия, масса, и соответственно различают группы сетей информационных, энергетических, вещественных. В группах сетей возможно разделение на подгруппы. Так, среди вещественных сетей могут быть выделены сети транспортные, водопроводные, производственные и др. При функциональном проектировании сетей решаются задачи синтеза топологии, распределения продукта по узлам сети, а при конструкторском проектировании выполняются размещение пунктов в пространстве и проведение (трассировка) соединений.
Информационная сеть – коммуникационная сеть, в которой продуктом генерирования, переработки, хранения и использования является информация.
Вычислительная сеть – информационная сеть, в состав кoторой входит вычислительное оборудование. Компонентами вычислительной сети могут быть ЭВМ и периферийные устройства, являющиеся источниками и приемниками данных, передаваемых по сети. Эти компоненты составляют оконечное оборудование данных (ООД, или DTE – Data Terminal Equipment). В качестве ООД могут выступать ЭВМ, принтеры, плоттеры и другое вычислительное, измерительное и исполнительное оборудование автоматических и автоматизированных систем.
Терминал – устройство, предназначенное для взаимодействия пользователя с вычислительной системой или сетью ЭВМ. Состоит из устройства ввода (чаще всего это клавиатура) и одного или нескольких устройств вывода (дисплей, принтер и т.д.).
Под узлом будем понимать компоненты вычислительной сети, являющиеся источниками и приемниками данных, передаваемых по сети.
Собственно пересылка данных происходит с помощью сред и средств, объединяемых под названием среда передачи данных. Объединение в сеть ЭВМ осуществляется с помощью кабелей различного типа. Кабели подсоединяются к компьютеру через специальное устройство, называемое сетевой картой (сетевым адаптером), которая вставляется в слот расширения на материнской плате компьютера. Для построения сети используются и другие сетевые устройства различной сложности.
Подготовка данных, передаваемых или получаемых ООД от среды передачи данных, осуществляется функциональным блоком, называемым аппаратурой окончания канала данных (АКД, или DCE – Data Circuit-Terminating Equipment). АКД может быть конструктивно отдельным или встроенным в ООД блоком. ООД и АКД вместе представляют собой станцию данных, которую часто называют узлом сети. Примером АКД может служить модем.
Вычислительные сети классифицируются по ряду признаков. В зависимости от расстояний между связываемыми узлами различают вычислительные сети:
территориальные – охватывающие значительное географическое пространство; среди территориальных сетей можно выделить сети региональные и глобальные, имеющие соответственно региональные или глобальные масштабы; региональные сети иногда называют сетями MAN (Metropolitan Area Network), а общее англоязычное название для территориальных сетей – WAN (Wide Area Network);
локальные (ЛВС) – охватывающие ограниченную территорию (обычно в пределах удаленности станций не более чем на несколько десятков или сотен метров друг от друга, реже на 1…2 км); локальные сети обозначают LAN (Local Area Network);
корпоративные (масштаба предприятия) – совокупность связанных между собой ЛВС, охватывающих территорию, на которой размещено одно предприятие или учреждение в одном или нескольких близко расположенных зданиях.
Особо выделяют единственную в своем роде глобальную сеть Internet. Это всемирная компьютерная сеть, сеть сетей, объединяющая посредством межсетевых интерфейсов многие сети. Internet охватывает американский континент, Европу, Азию. Некоторые сети, входящие в состав Internet, сами по себе велики, другие имеют свои подсети. В настоящее время сеть Internet объединяет более 2,5 млн. компьютеров многих стран мира и доступна нескольким десяткам миллионов пользователей.
С технической точки зрения Internet – объединение транснациональных компьютерных сетей, работающих по самым разнообразным протоколам, связывающим всевозможные типы компьютеров, физически передающих данные по телефонным проводам и оптоволокну, через спутники и радиомодемы. Координацию сети осуществляет Центр информационных сетей при Стенфордском исследовательском институте в Менло Парк, Калифорния.
На российском рынке глобальных вычислительных сетей наиболее активно и эффективно функционируют следующие сетевые структуры: РОСПАК, GLASNET, РЕЛКОМ, ИНФОТЕЛ.
Различают интегрированные сети, неинтегрированные сети и подсети. Интегрированная вычислительная сеть (интерсеть) представляет собой взаимосвязанную совокупность многих вычислительных сетей, которые в интерсети называются подсетями.
В автоматизированных системах крупных предприятий подсети включают вычислительные средства отдельных проектных подразделений. Интерсети нужны для объединения таких подсетей, а также для объединения технических средств автоматизированных систем проектирования и производства в единую систему комплексной автоматизации. Обычно интерсети приспособлены для различных видов связи: телефонии, электронной почты, передачи видеоинформации, цифровых данных и т.п., и в этом случае они называются сетями интегрального обслуживания.
Развитие интерсетей заключается в разработке средств сопряжения разнородных подсетей и стандартов для построения подсетей, изначально приспособленных к сопряжению.
Подсети в интерсетях объединяются в соответствии с выбранной топологией с помощью блоков взаимодействия. Топология – геометрическое отображение отношений в сети. В зависимости от топологии соединений узлов различают сети шинной (магистральной), кольцевой, звездной, иерархической, произвольной структуры. Топологии сетей будут рассмотрены ниже.
В зависимости от способа управления различают сети:
“клиент/сервер” – в них выделяется один или несколько узлов (серверы), выполняющих в сети управляющие или специальные обслуживающие функции, а остальные узлы (клиенты) являются терминальными, в них работают пользователи;
одноранговые – в них все узлы равноправны; поскольку в общем случае под клиентом понимается объект (устройство или программа), запрашивающий некоторые услуги, а под сервером – объект, предоставляющий эти услуги, то каждый узел в одноранговых сетях может выполнять функции и клиента, и сервера.
Наконец появилась сетецентрическая концепция, в соответствии с которой пользователь имеет лишь дешевое оборудование для обращения к удаленным компьютерам, а сеть обслуживает заказы на выполнение вычислений и получение информации, т.е. пользователю не нужно приобретать программное обеспечение для решения прикладных задач, ему нужно лишь платить за выполненные заказы. Подобные компьютеры называют тонкими клиентами или сетевыми компьютерами.
В зависимости от того, одинаковые или неодинаковые ЭВМ применяют в сети, различают сети однотипных ЭВМ, называемые однородными, и разнотипных ЭВМ – неоднородные (гетерогенные). В крупных автоматизированных системах, как правило, сети оказываются неоднородными.
В зависимости от прав собственности на сети последние могут быть сетями общего пользования (public) или частными (private). Среди сетей общего пользования выделяют телефонные сети ТфОП (PSTN – Public Switched Telephone Network) и сети передачи данных (PSDN – Public Switched Data Network).
Сети также различают в зависимости от используемых в них протоколов и по способам коммутации.
Статьи к прочтению:
- Принципы разработки алгоритмов и программ для решения прикладных задач
- Принцип однородности памяти
Основные этапы создания сайта
Похожие статьи:
- Принципы разработки алгоритмов и программ для решения прикладных задач ОПЕРАЦИОНАЛЬНЫЙ ПОДХОД В настоящее время создание алгоритмов — написание программ для электронных вычислительных машин — стало видом человеческой…
- Основные принципы разработки и анализа алгоритмов При построении алгоритма для сложной задачи используют системный подход -использованием декомпозиции (нисходящее проектирование сверху-вниз) и синтеза…
Источник: csaa.ru
Разработка алгоритма. Информатика 8 класс
Задание на повторение
Что такое проблема?
Проблема – форма научного отображения
проблемной ситуации. Проблема
формулируется как выражение необходимости
изучения и практических действий,
направленных на выявление причин и на их
разрешение.
4.
Установите соответствие
Как называется программа,
которая отображает структуру и
взаимосвязи между элементами
объекта ?
Как называется условный
образ объекта в виде
компьютерных диаграмм,
таблиц, схем, изображений,
анимационных фрагментов?
Что является эффективным
средством для решения
различных задач из
окружающего мира?
Модель
Моделирование
Алгоритм
5.
Со способами разработки
алгоритмов разветления вы
познакомились в 7 классе.
На этом уроке мы начнём
рассмотрение разработки
алгоритмов
с простейшего — линейного
Перед разработкой программы необходимо
уточнение постановки проблемы в соответствии с условием
задачи.
На следующем этапе начнётся уточнение всех условий,
которые должны будут быть рассмотрены для решения
задачи.