надо разрезать пиццу на заданное число кусков)

[DiemonStar]

Если n - число разрезов(линий), а k - число кусков, тогда:

k >= n+1 - минимальное
k <= (n+1)*n/2 и максимальное количество кусков получаемых заданным количеством разрезов.

одно из основных условий для получения заданного количества кусков - количество пересечений между разрезами (l) внутри данной фигуры.

и это количество должно быть равно:

l = k - (n + 1) - т.е. каждое пересечение добавляет ещё один кусок...

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

[Serge_Bliznykov]

DiemonStar, откуда такая формула для максимума?
ну и, согласно вашей формуле
(n+1)*n/2
при n=6 можно получить 7*3 = 21 кусок

Вы не могли бы набросать графическую схемку, где видно, при каких разрезах возникает максимальное число кусков ?

[Аватар]

(n+1)*n/2 та же формула, что в #16, только единица потеряна
например для 2: (2+1)*2/2=3, а нужно 4.

DiemonStar +1 за идею построения, сам думал, но не пришла в голову

[Serge_Bliznykov]

Аватар,
ребят, не дайте мне совсем с ума сойти на этой задаче, растолкуйте недогадливому:
первое.

2 разреза - от 3 до 4
3 разреза - от 4 до 7
4 разреза - от 5 до 10
5 разрезов - от 6 до 17

это правильные расчёты?
покажите, пожалуйста, как тремя разрезами получить 7 кусков (ну, или как 5 разрезами получить 17 кусков)

второе.

та же формула, что в #16, только единица потеряна

С(2,n) + C(1,n) + C(0,n)
при n=5 получаем 10 + 5 + 1 (на самом деле в сочетаниях ноль - бессмысленен и не может быть, но ладно, в формулу его можно подставить) = 16
так сколько кусков можно получить 5-ю разрезами? 16 или 17 ?

а при n=4 по формуле получаем 6 + 4 + 1 = 11 кусков.
так сколько кусков можно получить 4-ю разрезами?


очень прошу тех, кто разобрался, нарисовать схемки разрезов (для получения максимального числа кусков).

Заранее благодарю.

[evg_m]

максимальное число кусков для 3 и 4 разрезов
каждая линия пересекается с каждой
Закрашенная область центральный многоугольник (с не параллельными сторонами) о котором шла речь у DiemonStar
2.jpg
P.S. параллельность сторон можно использовать как один из способов вывода точки пересечения за пределы круга.

[DiemonStar]

очень прошу тех, кто разобрался, нарисовать схемки разрезов (для получения максимального числа кусков).

максимально количество кусков получается при максимальном количестве точек пересечения. т.е:
- 2 разреза могут пересечься максимум 1 раз (у двух прямых одна точка пересечения)
- три разреза могут пересечься максимум 3 раза (три прямые образуют треугольник)
- четыре разреза - шесть раз пересекутся ( данный треугольник пересекаем ещё одной линией и получаем +3 точки пересечения)
и т.д.
т.е. получается арифметическая прогрессия с шагом 1 - каждое новое значение пересечений увеличивается на число существующих разрезов (максимальное количество точек пересечения одной линии с n-1 линий = n-1)

частный случай - пятиконечная звезда и "пицца" радиусом большим длины луча - деление по 10 точкам пересечения на 16 кусков.



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

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

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

[Аватар]

C(0,n) физически конечно бессмысленно, но в математике для удобства расчетов и формул комбинаторики принято считать, что C(n,n)=C(0,n)=1. Абстрактная схема разрезов - берем плоскость и N не параллельных прямых, в одной точке пересечения не более двух прямых, обводим окружностью, включающую в себя все точки пересечения.

Для 6 - 22 http://2yxa.ru/golovolomka/?otv=364

[DiemonStar]

(n+1)*n/2 та же формула, что в #16, только единица потеряна

каюсь, забыл саму пиццу добавить - отсчёт же с 1 начинается.

Вариант для 6 разрезов = 22 куска
http://s018.radikal.ru/i528/1202/99/a8f71fcb56b3.jpg

т.е. основные условия достижения максимума - все линии должны пересекаться и точки пересечения должны лежать в нашей области

[Serge_Bliznykov]

большое спасибо за объяснения.
Немного посветлело...

[iris_ka]

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