Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
СМОЛЕНСКИЙ КОЛЛЕДЖ ТЕЛЕКОММУНИКАЦИЙ
(филиал) ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕНННОГО ОБРАЗОВАТЕЛЬНОГО БЮДЖЕТНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»
|
УТВЕРЖДАЮ Зам. директора по УПР _____________ И. В. Иванешко «___» ___________ 2012г |
РАССМОТРЕНО на заседании цикловой комиссии математических и программно - вычислительных дисциплин «___»___________2012г. Председатель комиссии __________Мохнач О.А. |
По дисциплине: Теория алгоритмов
Наименование работы: Схема Горнера и возведение в степень.
Для специальности: 230115
Работа рассчитана на 2 часа
Составлена преподавателем Мохнач О.А.
г. Смоленск
2012 г.
2. ЛИТЕРАТУРА Конспект.
3. ВОПРОСЫ ДЛЯ ДОМАШНЕЙ ПОДГОТОВКИ:
4. ОБОРУДОВАНИЕ: ПЭВМ
5. ЗАДАНИЕ.
5.1. Разработать программу, вычисляющую значение многочлена в точке x n-го порядка. Написать комментарии к каждой строчке программы.
5.2. Проверить получившиеся решения, решив задачу вручную или в математическом пакете (например, Маткад).
5.3.* Применить полученный алгоритм к вычислению степени числа.
6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Повторить правила техники безопасности:
При работе и техническом обслуживании ПК необходимо соблюдать следующие меры предосторожности:
• Запрещается во время работы ПК размыкать и замыкать разъемные соединения.
• источники света должны быть расположены так, чтобы не засвечивать экран монитора, не создавать резких бликов на экране и не светить из-за монитора в глаза человека, работающего с ПК;
Не кладите на монитор бумагу, ткани и прочее, что может нарушить вентиляцию.
Включение ПК должно производиться в следующей последовательности:
Перед выключением компьютера завершите все работающие программы и подождите 1-2 сек. (это необходимо, если на ва шем ПК предусмотрено кэширование дисков). Далее необходимо:
• выключить системный блок;
• выключить принтер (если он был включен);
• выключить монитор.
6.2. Задать одномерный массив размерности n с коэффициентами многочлена любым способом.
6.3. Реализовать алгоритм Горнера.
6.4. Вывести и проверить результаты.
6.6. Оформить отчет.
8.1. Понятие и цель алгоритма Горнера.
8.2. Применимость алгоритма Горнера.
9. ПРИЛОЖЕНИЕ
Схема Горнера и возведение в степень
В этом разделе мы рассмотрим задачу вычисления значения полинома
в заданной точке х и ее важный частный случай — вычисление хп. Полиномы об разуют наиболее важный класс функций благодаря множеству хороших свойств, с одной стороны, и возможности их применения для аппроксимации других ти пов функций, — с другой. Задача эффективной работы с полиномами актуальна несколько столетий, и за последние 50 лет были сделаны новые открытия в этой области. Несомненно, наиболее важным из них было быстрое преобразование Фурье. Практическая важность этого замечательного алгоритма, основанного на представлении алгоритмов при помощи их значений в специально выбранных точках, настолько велика, что некоторые ученые счита ют его наиболее важным алгоритмическим открытием всех времен.
Схема Горнера
Схема Горнера (Homer's rule) — один из старых, но очень элегантных и эффек тивных алгоритмов для вычисления полиномов. Он назван по имени британского математика В. Горнера (W. G. Horner), который опубликовал этот алгоритм в на чале 19 века.
Схема Горнера — хороший пример использования метода изменения пред ставления. Эта новая формула получается из (6.1) путем последова тельного вынесения х за скобки с образованием полиномов с уменьшающимися степенями:
Для вычисления значения полинома в точке х это значение надо просто подста вить в формулу. Глядя на нее, трудно поверить, что это и есть эффективный алгоритм вычисления значения полинома, однако ее неприглядность — не более чем внешний вид, и, как вы увидите, нет необходимости в такой записи полинома: все, что нам надо, — это список коэффициентов полинома.
Вычисления вручную проще организовать при помощи таблицы, состоящей из двух строк. Первая содержит коэффициенты полинома (включая те из них, которые равны 0, — если таковые имеются), перечисленные в порядке от старшего ап к младшему ао. Вторая строка используется для хранения промежуточных результатов (за исключением первой записи, которая просто равна ап). После такой инициализации очередная запись в таблице вычисляется как последнее значение, умноженное на х, плюс коэффициент из первой строки. Последняя запись таблицы, вычисленная таким способом, и есть искомое значение полинома.
Пример 1. Вычисление р (х) = 2х4 — х3 + Зх2 + х — 5 в точке х = 3.
|
Коэффициенты |
2 |
-1 |
3 |
1 |
-5 |
|
х = 3 |
2 |
3-2 + (-1)=5 |
3 • 5 + 3 = 18 |
3 • 18 + 1 = 55 |
3-55+(-5) = 160 |
Чтобы оценить, насколько эффективен алгоритм схемы Горнера, рассмотрим только первый член полинома степени п: апхп. Вычисление только одного этого члена методом грубой силы потребует п умножений, в то время как схема Горне ра, кроме этого члена, вычисляет еще п — 1 других членов и при этом использует то же количество умножений! Неудивительно, что схема Горнера — оптимальный алгоритм для вычисления полиномов без предварительной обработки полиноми альных коэффициентов.
Бинарное возведение в степень
Поразительная эффективность схемы Горнера сводится на нет, будучи приме ненной к вычислению ап, т.е. значению хп при х — а. Фактически в этом частном случае алгоритм вырождается в алгоритм, основанный на применении грубой си лы, — в умножение значения а само на себя, с бессмысленными прибавлениями О между умножениями. Поскольку вычисление ап (на самом деле ап mod m) явля ется основной операцией в ряде важных алгоритмов проверки чисел на простоту и алгоритмов шифрования, мы рассмотрим два важных алгоритма вычисления an, которые основаны на идее изменения представления. Оба они используют бинар ное представление показателя степени п, но один из них обрабатывает бинарную строку слева направо, а другой — справа налево.
Пусть п =bl... bi... bo — битовая строка, представляющая положительное целое п в двоичной системе счисления. Это означает, что значение п может быть вычислено как значение полинома
Давайте вычислим значение этого полинома с использованием схемы Горне ра — мы увидим, как из него вытекает способ вычисления степени
Таким образом, после инициализации переменной-аккумулятора значением а можно сканировать битовую строку, представляющую показатель степени, при каждом сканировании нового бита возводя значение аккумулятора в квадрат и, ес ли сканируемый бит равен 1, дополнительно умножая полученный квадрат на ве личину а. Это наблюдение приводит нас к следующему методу вычисления ап — бинарному возведению в степень слева направо (left-to-right binary exponentiation).
Пример 2. Вычислим a13 при помощи алгоритма бинарного возведения в степень слева направо. Здесь п = 13 = 11012- Таким образом, мы имеем
|
Биты п |
1 |
1 |
0 |
1 |
|
Аккумулятор |
a |
О Q a2 • a = a3 |
(a3)2 |
(а6)2 -а = а13 |