Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

Узнайте стоимость индивидуальной работы!

Вы нашли то, что искали?

Вы нашли то, что искали?

Да, спасибо!

0%

Нет, пока не нашел

0%

Узнайте стоимость индивидуальной работы

это быстро и бесплатно

Получите скидку

Оформите заказ сейчас и получите скидку 100 руб.!


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

Тип Реферат
Предмет Математика
Просмотров
1511
Размер файла
78 б
Поделиться

Ознакомительный фрагмент работы:

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

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

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

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

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

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

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

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

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

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

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

Аn=Аn-1n-2n-3 A4n-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)

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

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

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

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

Докажем предположение, что P2n=(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 главных диагоналей.

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

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

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


Нет нужной работы в каталоге?

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

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

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

avatar
Математика
История
Экономика
icon
145460
рейтинг
icon
3086
работ сдано
icon
1335
отзывов
avatar
Математика
Физика
История
icon
142040
рейтинг
icon
5871
работ сдано
icon
2651
отзывов
avatar
Химия
Экономика
Биология
icon
94768
рейтинг
icon
2025
работ сдано
icon
1268
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
53 538 оценок star star star star star
среднее 4.9 из 5
ИрНИТУ
Спасибо за реферат.Но хотелось бы посоветовать Вам выполнять оформление правильно. Вы ег...
star star star star star
ИМ.ВИТТЕ
Спасибо Алексей, за быструю и качественную работу! Обязательно буду обращаться еще! Всем р...
star star star star star
ДВГУПС
Отличный исполнитель!!! Рекомендую!!! Работа без замечаний!!! Преподаватель принял к защит...
star star star star star

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

создайте модель данных в веб-приложении Django и примените изменения в...

Решение задач, Средства програмной разработки

Срок сдачи к 17 июня

только что

реферат в соответствии с требованиями

Реферат, история государства и права России

Срок сдачи к 28 июня

1 минуту назад
1 минуту назад

чертеж компас а3

Чертеж, Инженерная графика

Срок сдачи к 18 июня

1 минуту назад

написать научную статью

Статья, Уголовная политика

Срок сдачи к 17 июля

1 минуту назад
3 минуты назад

Требований нет.

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

Срок сдачи к 30 июня

3 минуты назад

Сделать презентацию на по английскому

Презентация, Английский язык

Срок сдачи к 19 июня

4 минуты назад

Решить 6 задач по 4 варианта

Лабораторная, строительные машины

Срок сдачи к 20 июня

4 минуты назад

Произвести расчет и построить блок схему в Java.

Контрольная, Информатика в приложении к отрасли

Срок сдачи к 19 июня

5 минут назад

Сделать чертежи в Компас 3D.

Чертеж, Основы компьютерного инжиниринга.

Срок сдачи к 19 июня

5 минут назад

Ответить на несколько вопросов

Ответы на билеты, История

Срок сдачи к 19 июня

5 минут назад

Помощь на экзамене

Онлайн-помощь, Математика

Срок сдачи к 17 июня

6 минут назад
7 минут назад

Написать доклад по плану для защиты ВКР

Доклад, Юриспруденция

Срок сдачи к 18 июня

7 минут назад
7 минут назад

Необходимо написать приговор судебного заседания

Другое, Юриспруденция

Срок сдачи к 27 июня

8 минут назад

расчетно-графическую работу вариант 8

Контрольная, Теоретическая и прикладная механика, механика

Срок сдачи к 18 июня

8 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

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

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно