Проект "Схема Горнера"

Здравствуйте.

Позвольте представиться: ученики 11 а класса лицея №4.  Мы оба  учимся  в профильном физико-математическом  классе.  Информатику изучаем  со 2 класса, программирование - с 9 класса.

Теперь о проекте. Все началось довольно обычно. На уроках по математике мы изучали тему «Многочлены». Находили значения многочленов в заданной точке, делили многочлены, находили корни многочленов. Наряду с разными схемами работы с многочленами, познакомились и со схемой Горнера, которая позволяет находить корни многочленов.

Если говорить вообще о многочленах, то следует отметить, что в необозримом царстве функций многочлены занимают, на первый взгляд, очень скромное место. Однако это первое впечатление обманчиво.

Многочлены, действительно, предельно просты: на слайде представлена  алгебраическая запись многочлена

        1)

которая является одновременно и формулой для вычисления  его значения.

Согласитесь,  выражения типа  cos x, sin x, log х  намного лаконичнее, но с вычислительной точки зрения они бессодержательны: для вычисления этих функций нужны специальные приближённые формулы (или таблицы, составленные с помощью тех же формул). Как правило, в таких формулах появляются многочлены: например, если мы вспомним ряд Тейлора – Макларена для функции cos, то снова встретимся с многочленом:  (СЛАЙД)

Итак, оказывается, что вычислять многочлены приходится часто, а значит важно

научиться делать это как можно проще, а еще лучше постараться автоматизировать этот процесс.  Это  нас и заинтересовало.

А когда учитель по информатике предложила   заняться разработкой проекта мы решили вплотную заняться этим вопросом.

И тут то и началось самое интересное! Изучая, материалы по данной теме, мы  узнали, что эру создания компьютерной математики принято отсчитывать с начала 60-х годов.

Именно тогда в вычислительной технике возникла новая ветвь компьютерной математики, не совсем точно, но зато броско названная компьютерной алгеброй.

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

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

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

Большинство же пользователей заинтересовано в том, чтобы правильно выполнить конкретные аналитические преобразования, вычислить производную или первообразную

заданной функции, найти корни полинома, умножить многочлен на многочлен, перевести число в нужную систему счисления и т. д., а вовсе не в детальном и сложном математическом и логическом описании задачи для компьютера. Здесь та же ситуация, что и с телевизором, радиоприемником или факсом: большинство из нас пользуются этими аппаратами, вовсе не интересуясь тем, как именно они выполняют свои довольно сложные функции.

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

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

Поиск же готовых   программ для работы с многочленами показал, что их не так уж и  много, да и все они являются какими – то недоработанными.

Поняв эту истину, мы    попробовали сделать    попытку   в создании такой программы, которая была бы понятна и проста в использовании и могла бы пригодиться широкому кругу пользователей, не являющихся профессионалами в компьютерной алгебре.

Поэтому мы  поставили перед собой следующую цель:

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

Для достижения поставленной цели необходимо решить следующие задачи:

• Подобрать  и изучить литературу по темам:  «Многочлены», «Схема Горнера», «Исследование функции, представленной в форме многочлена»;
• Продолжить изучение   приемов  программирования на языке  Delphi;
• Используя  знания по перечисленным выше темам разработать комплекс алгоритмов, реализующих основные операции с многочленами;
• Дать рекомендации по применению данного комплекса.

Найти описание способов  работы с многочленами не составляло  труда, они известны всем. А вот когда началось программирование,  тут - то и начались наши настоящие  проблемы.  

(ПРограмма)

Дело в том, что  например, при вычислении корней многочленов компьютер никак не хотел работать с обыкновенными дробями, все норовил перевести их в десятичные дроби, а вот этого –то нам как раз и не  нужно было. Например, если корень равнялся ¼, то это еще куда ни шло, так как значение этой дроби – рациональное число, а вот если, например, 5/3, как быть, если эта дробь – иррациональное число.

(ПРИМЕР 1.)                 3х +5       (одновременно на калькуляторе показываем результат)

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

А чтобы определить, является ли дробь корнем, нужно было привести все значения, полученные при построении схемы Горнера к общему знаменателю и при необходимости, сократить.

(пример 2)  

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

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

(пример 3)              10 степень:    старший член =10; свободный =  - 10

***А как объяснить компьютеру, что такое подобные члены, которые появляются при умножении многочленов? 

(ПРИМЕР 4)      

2)  =

Чтобы вы не сомневались в правильности вычислений, приведем  совсем уж простой пример:

3)  5 * x = 5x+0

*** Следующий модуль нашего  комплекса  позволяет провести исследование функции, заданное многочленом любого порядка.

 (ПРИМЕР 5)    степень 2,    1-ый коэффициент – 1 (квадратное уравнение), линейное уравнение: степень – 1, 1-ый коэф – 5.

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

Известно,  что  формула перевода чисел из  любой  позиционной  системы  счисления  в десятичную выглядит следующим образом:

         где         b[i]  - это цифры числа,

                        q - основание системы счисления,

                        n - степень, которая указывает на то, в каком разряде стоит данная цифра, т. е. общая      Формула любого числа в десятичной системе счисления имеет следующий вид:  

А многочлен в общем виде представляется в таком виде:

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

(пример 5)   Основание – 16,  число FFFF

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

(СЛАЙД) Разработанная нами программа может быть использована при изучении программирования (операции с массивами, динамическое создание компонент), при изучении математики (нахождение корней многочлена), для перевода чисел из различных позиционных систем счисления в десятичную (не прибегая к возведению в степень), и надеемся может быть полезна широкому кругу пользователей, не являющихся профессионалами в компьютерной алгебре.