Итерационные и рекурсивные алгоритмы. Реккурентные соотношения.

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

Рекурсией называется ситуация, когда какой-то алгоритм прямо или через другой алгоритм вызывает себя в качестве вспомогательного. Сам алгоритм при этом называется рекурсивным. Эти алгоритмы возникают в тех случаях, когда исходную задачу удается свести к точно такой же задаче, но с другими аргументами или в другой обстановке.

При каждом рекурсивном вызове процедуры – функции создается новый «прямоугольник» в памяти для размещения в нем вызываемого алгоритма, т.е. процедуры. По завершению алгоритма его прямоугольник стирается из памяти и ЭВМ возвращается к предыдущему прямоугольнику алгоритма.

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

Если необходимо вычислить сумму значений некоторой функции при различных значениях аргумента, то целесообразно использовать цикл, в котором не только вычисляется текущее значение ф-ции, но и накапливается их сумма путём прибавления полученного слагаемого к сумме предыдущих. Формула, используемая для накопления имеет вид: . При первом выполнении цикла вычисляется значение , которое должно быть равно у₁.Поэтому начальному значению суммы перед циклом следует присвоить значение 0. Аналогично накапливается и произведение, с той лишь разницей, что для накопления исп-ся ф-ла , а начальное значение произведения должно быть равно 1.

Вычисление суммы бесконечного ряда с заданной точностью является типичной задаченй, исользующей итерационный цикл, так как заранее неизвестно, при каком члене ряда будет достигнута требуемая точность. Выход из цикла осуществляется по условию достижения требуемой точности. Для решения алгебраических и трансцендентных уравнений, аналитическое решение которых не удаётся получить, используют приближённые итерационные методы (последовательных приближений). При этом решение разбивается на 2 этапа: 1) определение грубого значения корня; 2) уточнение значения корня.

Уточнение значения корня рассматривается на примерах метода итераций и метода половинного деления. При изложеии этих методов предполагается, что известен интервал , внутри которого осуществляется поиск корней.

Сущность метода итераций заключается в том, что исходное уравнение представляется в виде X=F(x). Если в интервале между приближённым значением корня х₀ и значением корня уравнения х выполняется условие , то метод даёт возможность вычислить значение корня с заданной точностью . Если это условие не выполняется, то надо перейти к обратной ф-ции. Новое значение корня вычисляется через предыдущее по формуле . Повторяя процесс для х₁, х₂, х₃, …, можно вычислить корень с заданной точностью, которая определяется с помощью выражения .

Т. Итерационная последовательность сходится при любом начальном приближении , если для уравнения , имеющего 1 корень на этом отрезке, вып-ся условия: 1) - определена и дифференцируема на ; 2)

 

23. Основные понятия объектно-ориентированного программирования.

Технология работы в среде Visual Basic базируется на идеях объектно-ориентированного и визуального программирования. Идея объектно-ориентированного программи­рования состоит в инкапсуляции (объединении) данных и спосо­бов их обработки (методов) в тип, который называют объектом. Примерами объектов могут быть элементы управления в окне: кнопки, списки, текстовые поля и т.п. Среда визуального про­граммирования Visual Basic - это графическая автоматизирован­ная оболочка над объектно-ориентированной версией языка Бейсик. Если в языке Бейсик структурные единицы – данные, команды, то здесь такой структурной единицей является визуальный объект, который называется компонентом. Автоматизация программирования достигается длагодаря возможности переносить компонент на форму (в программу) с палитры компонентов и изменять его свойства, не внося вручную изменений в программный код.

Формой называют компонент, обладающий свойствами окна Windows и предназначенный для расположения на нём других компонентов. Компоненты служат для организации диалога с пользователем. Это кнопки, списки, текстовые поля, изображения, конструктор меню. Они отображаются на экране во время выполнения программы.

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

Событием (Event) называется характеристика класса объектов, описывающая внешнее воздействие, на которое реагирует объект этого класса во время работы приложения.

Объектно-ориентированное программирование основано на следующей идее: программы управляются событиями.

Объектно-ориентированное программирование базируется на трёх ключевых концепциях – инкапсуляции, наследовании и полиморфизме. Объединение данных с методами в одном типе (классе) называется инкапсуляцией. Инкапсуляция позволяет ограничивать доступ к данным объектов и реализации методов классов. В результате у программистов появляется возможность использования готовых классов вс своих приложениях на основе только описаний этих классов.

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

В большинстве случаев методы базового класса у классов-наследников приходится переопределять. Все переопределяемые методы по написанию (названию) будут совпадать с методами базового объекта, однако компилятор по типу объекта (его классу) распознаёт, какой конкретно метод надо использовать. Такое свойство объектов переопределять методы наследуемого класса и корректно их использовать называется полиморфизмом.

Для различных методик ООП характерны следующие черты: объект описывается как модель некоторой сущности реального мира; объекты, для которых определены места хранения, рассматриваются во взаимосвязи, применительно к ним создаются программные модули системы. В процессе объектно-ориентированного анализа: осуществляется идентификация объектов и их свойств; устанавливается перечень операций (методов обработки), выполняемых над каждым объектом, в зависимости от его состояния (событий); определяются связи между объектами для образования классов; устанавливаются требования к интерфейсу с объектами. Выделено четыре этапа ООП: * разработка диаграммы аппаратных средств системы обработки данных, показывающей процессоры, внешние устройства, вычислительные сети и их соединения; * разработка структуры классов, описывающей связь между классами и объектами; * разработка диаграмм объектов, показывающих взаимосвязи с другими объектами; * разработка внутренней структуры программного продукта. Процесс разработки ПО с использованием ООП включает четыре этапа: 1) Анализ и уточнение спецификаций: Цель этапа - мак­симально полное описание задачи. На этом этапе выполняют анализ пред­метной области задачи, определяют важнейшие особенности поведения объектов (описание абст­ракций). По результатам разрабатывают диаграмму объектов ПП, на которой показывают основные абстракции (объек­ты) предметной области и сообщения, передаваемые между ними. 2) Проектирование: Различают: логическое проектирование, при котором принимаемые решения прак­тически не зависят от условий эксплуатации (разработка структуры клас­сов: определяются поля для хранения составляющих состояния объектов и алгоритмы методов, реализующих аспекты поведения объектов. Результат: иерархия или диаграмма классов, отражающая взаимосвязи классов, и описание структуры каждого класса.); физическое проектирование, при котором приходится принимать во внимание указанные факторы.Физическое проектирование включает объединение реализаций классов в модули, выбор схемы их подключения, определение способов взаимодействия с оборудованием, с ОП или другим ПО. 3) Реализация: Это процесс поэтапной реализации и под­ключения классов к проекту. При этом начинают с создания основной программы или проекта буду­щего ПП. Затем реализуют и подключают классы так, чтобы создать грубый, но, по возможности, работающий прототип будущей системы. Полученный вариант системы также тестируют и отлаживают. Процесс продолжают до реализации всех возможностей системы. 4) Модификация: Это процесс добавления новых фун-х возможностей или изменение сущ-х свойств системы. Простота модификации позволяет сравнительно легко адаптировать программные системы к изменяющимся условиям экс-ии, что увели­чивает время жизни систем, на разработку которых затрачиваются огромные временные и материальные ресурсы. Сущ-м является то, что при использовании ООП объект или группа объектов могут разр-ся отдельно, и => их проек-е может находиться на различных этапах

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. Итерационные методы (метод Якоби, метод Зейделя, метод релаксации)