Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Разбиения выпуклого многоугольника

Название: Разбиения выпуклого многоугольника
Раздел: Рефераты по математике
Тип: реферат Добавлен 17:20:47 19 марта 2003 Похожие работы
Просмотров: 1537 Комментариев: 2 Оценило: 5 человек Средний балл: 2.8 Оценка: неизвестно     Скачать

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

Определение: назовем правильным разбиением выпуклого n-угольника на треугольники диагоналями, пересекающимися только в вершинах n-угольника.

Пусть P1 , P2 , … ,Pn –вершины выпуклого n-угольника, Аn - число его правильных разбиений. Рассмотрим диагональ многоугольника Pi Pn .В каждом правильном разбиение P1 Pn принадлежит какому-то треугольнику P1 Pi Pn , где1<i<n. Следовательно, полагая i=2,3, … , n-1, мы получаем (n-2) группы правильных разбиений, включающие все возможные случаи.

Пусть i=2 – одна группа правильных разбиений, которая всегда содержит диагональ P2 Pn .Число разбиений, входящих в эту группу совпадает с числом правильных разбиений (n-1) угольника P2 P3 …Pn, то есть равно Аn-1 .

Пусть i=3 – одна группа правильных разбиений, которая всегда содержит диагональ P3 P1 и P3 Pn . Следовательно, число правильных разбиений, входящих в эту группу, совпадает с числом правильных разбиений (n-2)угольника P3 P4 …Pn, то есть равно Аn-2.

При i=4 среди треугольников разбиение непременно содержит треугольник P1 P4 Pn .К нему примыкают четырехугольник P1 P2 P3 P4 и (n-3)угольник P4 P5 …Pn.Число правильных разбиений четырехугольника равно A4, число правильных разбиений (n-3) угольника равно

Аn-3. Следовательно, полное число правильных разбиений, содержащихся в этой группе, равно

Аn-3 A4. Группы с i=4,5,6,… содержат Аn-4 A5, Аn-5 A6, … правильных разбиений.

При i=n-2 число правильных разбиений в группе совпадает с числом правильных разбиений в группе с i=2,то есть равно Аn-1.

Поскольку А12 =0, А3 =1, A4 =2 и т.к. n³ 3, то число правильных разбиений равно:

А n= А n-1 n-2 n-3 A4 n-4 A5 + … + A 5 А n-4 + A4 А n-3 + А n-2 + А n-1.

Например:

A 5 = A4 + А3 + A4 =5

A6 = A5 + А4 + А4 + A5 =14

A7 = A6 + А5 + А4 * А45 + A6 =42

A8 = A7 + А65* А4 + А4* А56 + A7 =132

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

Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых n-угольниках равно произведению количества разбиений на (n-3)

Докажем предположение, что P1 nn (n-3)

Каждый n-угольник можно разбить на (n-2) треугольника, из которых можно сложить (n-3) четырехугольника, причем каждый четырехугольник будет иметь диагональ. Но в четырехугольнике можно провести 2 диагонали, значит в (n-3) четырехугольниках можно провести (n-3) дополнительные диагонали. Значит, в каждом правильном разбиении можно провести (n-3) диагонали удовлетворяющих условию задачи.

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

Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых n-угольниках равно произведению количества разбиений на (n-4), где n ≥ 5

Докажем предположение, что P2 n =(n-4)Аn , гдеn ≥ 5.

n-угольник можно разбить на (n-2) треугольников из которых можно сложить (n-4) пятиугольника, в котором будут содержаться две непересекающиеся диагонали. Значит, найдется третья диагональ, которая пересекает две другие. Так как имеется (n-4) пятиугольника, значит, существует (n-4) дополнительные диагонали удовлетворяющих условию задачи.

П.2.3. Разбиение n-угольника, в котором дополнительные диагонали пересекают главные k раз.

Определение 1 :Главными диагоналями выпуклого n-угольника называются диагонали, которые разбивают его на треугольники, пересекаясь при этом только в вершинах n-угольника.

Замечание: их существует (n-3).

Определение 2 :Дополнительными диагоналями выпуклого n-угольника называются диагонали, которые в данном разбиении пересекают главные диагонали.

Замечание: их существует менее (n-3).

I.Определение k:


Будем выделять из выпуклого n-угольника

следующим образом: соединяем диагоналями через одну вершину данного n-угольника, причем выделением считается получение последующего a-угольника из предыдущего, используя не менее двух диагоналей. Выделение ведется до тех пор, пока не получится четырехугольник или треугольник (r = 4 или r = 3 (r – остаточный коэффициент)). Назовем каждое такое выделение циклом и введем величину, которая будет “считать” их (d). Для каждого d существует 2d+1 многоугольников, первый многоугольник для данного d ,будет (2d+1 +1)-угольником. Для первой половины (для данного d) многоугольников r = 3, для второй - r = 4. Последним многоугольником, для которого r = 3 будет (3×2d )-угольником. Окончательно получаем: r = 3, если nÎ[2d+1 +1; 3×2d ], в противном случае r = 4. За каждый цикл, если проводить дополнительные диагонали, будет добавляться по 2 пересечения и через d циклов число пересечений достигнет максимума в полученном данным способом разбиении. Обозначим это число буквой k.

Итак, за 1 цикл 2 пересечения, за 2 цикла – 4, за 3 – 6, очевидна арифметическая прогрессия с разностью 2, a1=2 и количество членов равным d; значит k=2+2(d-1)=2d – только в том случае, если конечной фигурой окажется треугольник. В противном случае k=2d+1, так как четырехугольник имеет собственную диагональ.

Рассчитаем d: т.к.: d=1, n [22 +1; 23 ]

d=2, n [23 +1; 24 ]

d=3, n [24 +1; 25 ]

Зависимость d от n- логарифмическая по основанию 2; становится очевидным равенство: d=[log2 (n-1)]-1. Выразим k через n:

k=2([log2 (n-1)]-1), если nÎ[2[log2(n-1)] +1; 3×2[log2(n-1)]-1 ]

или

k=2([log2 (n-1)]-1)+1= 2[log2 (n-1)]-1, если nÏ[2[log2(n-1)] +1; 3×2[log2(n-1)]-1 ]

Так как k – максимум пересечений, то уместны неравенства:

k≤2([log2 (n-1)]-1), если n Î [2[log2(n-1)] +1; 3 × 2[log2(n-1)]-1 ]

или (*)

k≤2[log2 (n-1)]-1, если n Ï [2[log2(n-1)] +1; 3 × 2[log2(n-1)]-1 ]

II . Найдем число дополнительных диагоналей ( m), которые пересекают главные не более k раз.

Выделим в данном выпуклом n-угольнике (k+3)-угольник (k+3)-угольник (если это возможно), зн.

уже ‘использовано’ (n+3)-2=k+1 всех

отбросили существующих треугольников

1 треугольник n-угольника (всего их (n-2)),потом добавили другой ‘отбросим’ крайний треугольник и реугольник и ‘добавим’ к получившейся фигуре еще опять получили один, имеющий общую с ней сторону, (k+3)-угольник ‘не использованный’ треугольник, тогда останется (k+2) не использованных треугольника, и так далее до тех пор, пока не ‘используем’ все (n-2)треугольника. Очевидна арифметическая прогрессия с разностью 1, am =n-2 и c количеством членов равным m. Получим:n-2=k+1+(m-1)<=>n-2=k+m<=>m=n-k-2-m=n-(k+2)Значит, в n-угольник можно вписать (k+3)угольник (n-(k+2))раз, то есть существуют такие (n-(k+2)) дополнительные диагонали, которые пересекут k главных диагоналей.

Окончательно получаем: Pk n =( n- (k+2))А n , где(*).

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

Скращук Дмитрий (г. Кобрин). Разбиения выпуклого многоугольника

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:23:46 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:17:19 24 ноября 2015

Работы, похожие на Реферат: Разбиения выпуклого многоугольника

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150311)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru