19072-1 (607684), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

К1. для всех i от до /2 выполнить К2—К8.

К2. S1 i2. Если N=S1, то вывести (i).

КЗ. для j от i до 0 выполнить К4—К8.

К4. S2S1+j2, Если N=S2, то вывести (i, j).

К5. для k от j до 0 выполнить Кб—К8.

К6. S3S2+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, ...), то можно получить все перестановки. Такой генератор перестановок может использоваться для численного анализа различных алгоритмов сортировки и во многих других приложениях.

СЛЕДУЮЩАЯ ПЕРЕСТАНОВКА.

С1. Для i от n-1 с шагом -1 до 1 выполнить

если a(i)

Закончить (исходная перестановка максимальна).

С2. (найти наименьшее число, большее а (i)).

Для j от п с шагом — 1 выполнить

если a(i)

СЗ. Переставить а (i) и а (j)

С4. (перевернуть конец перестановки)

Для k от 1 до (n-i)/2 переставить a(i+k) и a(n—k+1)

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

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

Циклы. Перестановку можно рассматривать как функцию, определенную на множестве чисел (1,2, ..., n) со значениями в том же множестве. Этот подход позволяет перенести на перестановки многие понятия теории функций, а также теории групп, поскольку перестановки с естественно определенным умножением образуют группу. Чтобы отличать этот подход от предыдущего, будем применять двустрочное обозначение

Перестановку можно задавать как произведение циклов. Вышеприведенная перестановка есть произведение циклов (1, 4) и (3, 2), т. е. 1 переходит в 4, 4 в 1, 2 в 3, а 3 в 2. Конечно, разложение в циклы не однозначно, поскольку ту же перестановку можно записать в виде (3, 2) (4,1). Однако на самом деле это «те же самые» циклы, и можно определить понятие канонической записи, при которой такое разложение будет однозначным (ср. каноническую запись многочлена). Отметим, что в канонической записи скобки можно опустить, поскольку они восстанавливаются однозначно.

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

Пусть задано некоторое произведение циклов. Как их перемножить? Тривиальный алгоритм прослеживает каждый элемент через все циклы. Например, если перемножаются циклы (1, 3, 6, 7) (2, 3, 4) (1, 5, 4) (6, 1, 4, 5) (2, 7), то 1 переходит в 3. 3 в 4, 4 в 1, 1 в 4, 4 неподвижно, окончательно 1 переходит в 4. Но при таком подходе придется просматривать всю формулу п раз. Существует алгоритм, позволяющий решить задачу за один просмотр формулы. Создадим вспомогательный массив Л, в начале содержащий единичную перестановку (1, 2, .... п). Будем просматривать формулу с конца, т. е. справа налево. Если очередной символ не скобка, запомним его в М, а элемент, ранее находившийся в М, поместим на его место. При символе ")", отмечающем границу цикла, в М отправляем 0 и позицию следующего числа временно запомним в KС, пока не дойдем до конца цикла — символа "(" и не узнаем, во что оно переходит.

ЦИКЛ.

Ц1. (создать массив A) для i от 1 до п A(i) i

Ц2. Взять следующий элемент (просмотр справа налево) х

если х="(", то перейти к Ц4

если х число, то перейти к Ц3(j — индекс х в A)

если х=")" то M0 и перейти к Ц2

если формула исчерпана, то закончить (A— искомая перестановка)

ЦЗ. если M=0 (первый элемент после ")"), то К j, М A(j), перейти к Ц2

Ц4. A (k) M, перейти к Ц2.

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

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

5. Выпуклые фигуры. Многие приложения, например задачи линейного программирования, приводят к необходимости строить выпуклую оболочку множества точек. Для этого достаточно найти такое подмножество данного множества точек, являющихся вершинами выпуклого многоугольника, который содержит все остальные точки множества. Легко доказать, что с точностью до порядка вершин такой многоугольник единствен. Точка принадлежит выпуклому многоугольнику, если она и все его вершины лежат по одну сторону от любого его ребра. Здесь и далее под «лежать по одну сторону» понимается принадлежность одной полуплоскости, т. е. включается и случай, когда точка лежит на прямой.

Задача построения выпуклой оболочки n точек решается по индукции. При трех точках решение очевидно. Пусть построена выпуклая оболочка первых п точек. Возьмем n +1-ю точку. Если она принадлежит построенному многоугольнику, то она не меняет выпуклой оболочки. В противном случае ее нужно включить в многоугольник. Ребра, разделяющие эту точку и вершины многоугольника, расположены в многоугольнике последовательно. Пусть (Ai,Ai+1) (Ai+1, Ai+2) …

…(Aj-1,Aj) — такая последовательность. Если она состоит из одного ребра (Ai,Ai+1), то точка включается между вершинами Ai и Ai+1, иначе вершины Ai+1, ..., Aj-1 заменяются на An+1. Таким образом мы можем получить выпуклую оболочку любого числа точек.

При составлении программы трудность представляет обработка «замыкания многоугольника», ребра (AK,A1). Остальные ребра обрабатываются в цикле по номеру вершины. Чтобы не обрабатывать данное ребро отдельно, полезно продублировать его в конце массива. Отметим также, что при осуществлении алгоритма приходится то вставлять очередную вершину в список вершин многоугольника, то удалять из него одну или несколько точек. Это приводит нас к проблеме хранения списка в памяти. Вершины многоугольника образуют типичный список с двумя связями — предыдущая и последующая вершины. Возможно несколько вариантов решения. Можно удаляемые вершины отмечать каким-либо значением, и тогда при необходимости вставить новую вершину достаточно сдвинуть небольшой фрагмент массива до ближайшего пустого места. Другой способ связан с применением таблицы ссылок.

С очевидными изменениями этот алгоритм обобщается на случай выпуклых многогранников.

Мы рассмотрели задачи из нескольких разделов математики, представляющих различные аспекты межпредметных связей курса ОИВТ и математических курсов. Методически продуманный в этом смысле отбор заданий для практики по программированию позволяет наряду с изучением информатики активизировать и углубить знания учащихся по математике. При этом математические понятия и теоремы используются для разработки и доказательства правильности алгоритмов и для их анализа, т. е. приобретают практический, прикладной характер.

Заключение

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

Однако у большинства любознательных ребят интерес к ЭВМ часто сводится лишь к желанию как можно скорее «нажимать на кнопочки», «получать смешные картинки», играть с компьютером в «Морской бой»

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

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

Ребята с большим интересом узнали, что написанная в 1854 г. книга Дж. Булля «Основы логики высказываний» за целый век до появления ЭВМ явилась незаменимым помощником в создании логических элементов ЭВМ, языков программирования. На занятия по логическим элементам ЭВМ мы обычно приглашаем инженера-электронщика. Многие школьники, интересующиеся электроникой, самостоятельно готовят сообщения о работе триггера, о схемах совпадения, отрицания, логического умножения, логического сложения и т. д.

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

Список литературы

Абрамов С.А. Математические построения и программирование.– М., 1987г.

Пикан В.В. и др. Из опыта обучения геометрии в 6 классе. – М., 1983г.

Брудно А.Л., Каплан Л.И. Олимпиады по программированию для школьников. – М., 1985г.

Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы – М., 1976г.

Кузнецов Э.И., Шерпаев Н.В. Элименты информатики на уроках геометрии. – М., Просвещение 1987г.

Мейерович Л.Н. Межпредметные связи курсов «ОИВТ» и «Математика» при выборе задач для практике по программированию – М., Просвещение 1987г.

Левина Е.С. Развитие познавательного интереса учащихся к информатике – М., Просвещение 1987г.

Для подготовки данной работы были использованы материалы с сайта http://www.ed.vseved.ru/

Приложение

ЯЗЫК БЕЙСИК

Характеристики

Список файлов курсовой работы