Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

Опыт использования ЭВМ на уроках математики

равен 0).
      П7. Разделить поэлементно RR и QR на первый ненулевой элемент QR (для
его определения можно воспользоваться функцией СТЕПЕНЬ) и закончить (RR и
QR содержат числитель и знаменатель дроби).
      Отметим, что время работы можно сократить, убрав пересылки в П3.
Правда, при этом увеличивается число шагов
      2. Делимость чисел. Приведем пример межпредметных связей, когда
математические формулы и теоремы используются для оценки алгоритма. Мы
разберем задачу, связанную с теоремой Лагранжа. Алгоритм ее решения
несложен, но дает возможность познакомить школьников с проблемами анализа
алгоритмов. Эти проблемы наряду с тестированием незаслуженно обходятся не
только в школьных, но и в вузовских курсах программирования.
      Теорема Лагранжа утверждает, что каждое натуральное число может быть
представлено в виде суммы четырех квадратов целых чисел. Она доказывается
конструктивно, т. е. дается алгоритм построения такого разбиения для любого
числа.
      Доказательство опирается на понятие вычетов по простому модулю и может
быть изучено сильным учеником на факультативных занятиях или по книге.
Будем рассматривать только упорядоченные по убыванию разложения, тогда при
N =i2 + j2 + k2 + l2 выполняется i(  j(  k(  l. Тогда верно i2( N и i2 (
N/4, т. е. i принадлежит отрезку [[pic]/2, [pic]] . Поскольку j, k и l не
превышает i, общее число комбинаций можно оценить сверху [pic]Точную оценку
дает формула
      [pic]
      Приведем теперь алгоритм, позволяющий получить все упорядоченные
разложения данного числа.
      КВАДРАТЫ.
      К1. для всех i от [pic]до [pic]/2 выполнить К2—К8.
      К2. S1 (i2. Если N=S1, то вывести (i).
      КЗ. для j от i до 0 выполнить К4—К8.
      К4. S2(S1+j2, Если N=S2, то вывести (i, j).
      К5. для k от j до 0 выполнить Кб—К8.
      К6. S3(S2+k2, Если N =S3, то вывести (i, j, k).
      К7. для l от k до 0 выполнить К8.
      К8. Если N=S3+l2 то вывести (i, j, k, 1} и перейти к К5 со следующим
значением k.
      В этом алгоритме i, j, k и I пробегают целые значения в
соответствующих интервалах. S1, S2, S3 введены для сокращения объема
вычислений. Выполнение шага К8 можно прекращать при нахождении первого
значения, удовлетворяющего условию, поскольку не может быть двух
разложений, отличающихся только последним числом. Небольшая модификация
алгоритма позволяет организовать работу до нахождения первого разложения.
Эта программа может быть использована для численного решения многих
статистических задач: распределение чисел, представляемых в виде суммы 1,
2, 3, 4 квадратов, как функция N, число различных представлений в требуемом
виде, а также проверить приведенную нами оценку числа комбинаций.
      3. Решение алгебраических уравнений с рациональными коэффициентами.
Обычно в школьной практике уравнения вида аоxn+a1 xn-1+ +…+an=0 имеют
рациональные коэффициенты. В этом случае имеется эффективный алгоритм
нахождения всех рациональных корней. Прежде чем разбирать его, отметим, что
умножение на НОК знаменателей коэффициентов позволяет сделать их целыми
числами. Если старший коэффициент отличен от единицы, то умножим уравнение
на a0n-1и сделаем подстановку у=аох. Таким образом, мы всегда можем считать
все коэффициенты целыми, а ставший равным 1.
      В алгебре доказывается, что все рациональные решения такого уравнения
являются целыми числами, и при том делителями свободного члена. Разумеется,
у уравнения могут быть и иррациональные корни.
      Работу можно существенно сократить, если воспользоваться модификацией
схемы Горнера.
      Пусть а — корень уравнения, тогда по теореме Безу
      xn+a1xn-1+…+an=(x-a)(xn-1+c1xn-2+…+cn-1).
      Запишем это тождество в виде
      xn+a1xn-1+…+an=(x-a)(-b0xn-1-b1xn-2-…-bn-1)
      и приравняем коэффициенты при одинаковых степенях:
      an=abn-1; an-1=abn-2-bn-1; …;a1=ab0-b1; 1=-b0
      Все числа ai и bi являются целыми, поэтому an,an-1+bn-1,… делятся на
а. Значит, если хоть один из коэффициентов bi окажется нецелым, то
проверяемое число не может быть корнем. Отметим также, что по теореме Безу
при x=1 и х=-1 a0+a1+…+an делится на а-1, а ao-a1+…+(±)an  делится на а+1.
Обе суммы вычисляются один раз в начале работы. Эти два условия позволяют
сразу отбросить «лишние» делители.
      В более общем виде этот метод позволяет находить разложение на
множители многочлена с рациональными коэффициентами.
      Пусть f (х)—многочлен с целыми коэффициентами. Предположим, что он
является произведением многочленов g (х) и Н (х). При любом целом х из f
(x)=g (х) h (х) следует, что f (х) делится на g(x). Пусть т—степень
многочлена g(x). Возьмем m+l различных целых значений х, например
0,1—1,2... g (х) вполне задается своими значениями в этих точках, которые
являются делителями значений f (х) в тех же точках. Итак, все возможные
делители степени не выше m с целыми коэффициентами многочлена f (х)
определяются различными комбинациями делителей чисел f (0), f (1), f (-
1),... .
      Не разбирая алгоритм подробно, перечислим основные этапы работы.
      1. Вычислить f (0), f (1), ... (m+1—значение) (если f (х)— многочлен
степени n, то т достаточно взять равным п/2).
      2. Рассмотреть все возможные комбинации делителей f (0), f (1), ...,
взятых с обоими знаками.
      3. Для каждой комбинации (do, d1, ..., dm) найти коэффициенты
многочлена g (х), принимающего в точках 0,1,-1... значения do, d1, ..., dm.
      4. Если f (х) делится нацело на g (х), то задача решена, иначе перейти
к анализу следующей комбинации.
      Последовательно применяя этот алгоритм, можно найти разложение
многочлена на неприводимые множители. Эта задача демонстрирует связь
представления многочлена как алгебраической структуры и функциональной
зависимости, а также практическое приложение этой связи.
      4. Комбинаторика. Одним из важнейших применений комбинаторики является
программирование, где, например, перестановки и их свойства существенно
используются для анализа различных алгоритмов сортировки информации.
Сортировкой называется расположение ранее неупорядоченной информации
(массива, файла) в порядке возрастания или убывания. Понятие возрастания
(порядка) широко применяется в моделировании конкретных задач. Кроме
обычного порядка на множестве чисел «число а больше числа &», можно назвать
упорядочение букв в алфавите, слов в словаре. Иногда информация
упорядочивается по какой-то одной части, или, как обычно говорят, по одному
полю. Например, информация об учащихся (журнал) упорядочена по фамилиям.
Считается, что в мире более четверти всего машинного времени тратится на
сортировку. Поэтому важно грамотно выбирать метод сортировки в зависимости
от конкретной задачи, т. е. проводить анализ эффективности алгоритмов.
Неупорядоченное множество можно рассматривать как некоторую перестановку
упорядоченного, поэтому свойства перестановок определяют числовые
характеристики алгоритмов сортировки.
      Далее для простоты изложения под перестановкой понимается перестановка
без повторений чисел 1, 2, ..., n, обозначаемая (a1, a2, ..., an).
Следующие основные понятия, часто выходящие за пределы школьного курса
математики, приводят к интересным алгоритмам.
      Упорядочение множества перестановок. На множестве перестановок можно
определить порядок. Будем говорить, что одна перестановка больше другой,
если до какого-то элемента они совпадают, а следующий в первой больше, чем
во второй. Например, (4, 2, 3, 1) больше, чем (4, 2, 1, 3). Такой порядок
называется лексикографическим. Будем говорить, что одна перестановка
непосредственно следует за другой, если она больше ее, и не существует
третьей перестановки, которая была бы меньше первой, но больше второй.
Вышеприведенные перестановки непосредственно следуют одна за другой.
Построим алгоритм, позволяющий по данной перестановке построить
непосредственно следующую. Если применить его последовательно, начиная с
наименьшей перестановки (1, 2, ...), то можно получить все перестановки.
Такой генератор перестановок может использоваться для численного анализа
различных алгоритмов сортировки и во многих других приложениях.
12345
скачать работу

Опыт использования ЭВМ на уроках математики

 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ