Формула Пика

Площадь фигуры, нарисованной «по клеточкам» (более формально, имеющей вершины в целочисленных узлах решётки), можно вычислить несколькими способами. Формула Пика – один из них.

Собственно формула: S = a/2 + b – 1, где a – количество точек (или целочисленных узлов решётки, кому как нравится) на сторонах, b – количество точек внутри многоугольника.

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

P.S. Рисунок взят отсюда: http://www.etudes.ru/ru/etudes/pick/

5
Не знаю, зачем это тут. Но выкидывать жалко, написано же уже...
Очень интересно ^^
Не так уж и трудно самому посчитать площадь этой фигуры.
Вот тебе задачка.<br />
Сколько прямоугольников можно образовать из этих линий?
Кто нибудь насчитает сколько здесь прямоугольников? Если квадраты тоже прямоугольники. Ответы в личку.
JetFightzer, спасибо :)
qwertyMAN Клавиатурович, 1. Полезно иногда знать несколько способов сделать что-то.<br />
2. С формулой Пика это сделать скорее проще.<br />
3. Для кого я писала фразу &quot;Основное применение формулы связано не с подсчетом площадей конкретных фигур, а с решением различных задач о ломаных на клетчатой бумаге&quot;?<br />
А к примерам придираться явно бессмысленно.
qwertyMAN Клавиатурович, ну, несложный (если достаточно хорошо знать комбинаторику, конечно) подсчет дает для квадрата n*n формулу (n(n+1)/2)^2, что при n=4 равно 100 прямоугольников. Правильно?
qwertyMAN Клавиатурович, а, кажется, до меня дошло, к чему это ты :D<br />
Хорошо, прости, ты во многом прав насчет ЭВМ :)
Rikka 10, я комбинаторику не изучал скорее всего, я вообще не изучал математику дальше 9 класса школы. Зато вывел формулу (n!)^2 для решения этой задачи.<br />
А вот задача по сложнее, если честно конкретной формулы вывести во 2 задачи не удалось, только алгоритм который выполняет ЭВМ.<br />
Нужно посчитать сколько образуется треугольников с помощью всех линий. И будет круто если тебе удастся формулу получить.
qwertyMAN Клавиатурович, комбинаторику в среднестатистической общеобразовательной школе вообще хорошо не изучают, насколько я знаю. С другой стороны, можно попробовать её поизучать по книгам (благо хорошей литературы по математике хватает). Кстати, программистам ведь нужна по крайней мере дискретная математика и комбинаторика (в общем смысле, то есть включающая теорию графов и прочие хорошие вещи), разве нет?<br />
Ну, для треугольника со стороной n (если стороны маленьких треугольников по единице) у меня получилась формула (n^3+5n-3)/3, которая для 4 выдаёт 27 треугольников (а при n=1,2,3 она даже точно работает, если я умею считать).
Rikka 10, в том то и дело, я не программист. Если мне что то нужно, например написать физику неупругого удара, то я стану разбираться и изучать то что в школе не изучил. а так формулу не стану использовать, пока не разберусь в её работе. Может и полезно было бы по изучать комбинаторику, но пока что она мне не нужна.<br />
Кстати как выводится эта формула?
qwertyMAN Клавиатурович, ура, я дописала вывод формулы! :)<br />
<br />
Назовем треугольник прямым, если у него одна из вершин &quot;смотрит&quot; строго вверх, и обратным - если одна из вершин &quot;смотрит&quot; строго вниз.<br />
<br />
Посчитаем сначала количество прямых треугольников. Треугольников со стороной один - 1+2+3+...+n=n(n+1)/2 (сочувствую, но тебе придётся либо мне поверить, либо прочитать страницу 14 &quot;Математической индукции&quot; Шеня; если, конечно, ты этого не знаешь...). Со стороной два - 1+2+...+(n-1)=(n-1)n/2. И так далее, со стороной i (i&lt;(n+1)) - (n-(i-1))(n-(i-2))/2. Получаем всего прямых треугольников n(n+1)/2 + (n-1)n/2 + (n-2)(n-1)/2 +...+ 1*2/2. Тут я предположила, что это равно n(n+1)(n+2)/6, и доказала это с помощью мат.индукции (это выглядит меньшей магией, если привыкнуть решать задачи на мат.индукцию; кстати, у Шеня может где-то быть эта формула, но я не искала).<br />
<br />
Хорошо, посчитаем теперь количество обратных треугольников. Треугольников со стороной один - 1+2+...+(n-1)=(n-1)n/2. Треугольников со стороной два - 1+2+...+(n-3)=(n-3)(n-2)/2. (На этом моменте я обнаружила у себя ошибку в первоначальной формуле, ну да считаем дальше). Треугольников со стороной три - 1+2+...+(n-5)=(n-5)(n-4)/2. И так далее, треугольников со стороной i (i&lt;(1+n/2)) - (n-(2i-1))(n-(2i-2))/2. Получаем всего обратных треугольников - n(n-1)/2 + (n-3)(n-2)/2 +...+ 1*2/2 = n(n+2)(2n-1)/24 для четного n или n(n-1)/2 + (n-3)(n-2)/2 +...+ 2*3/2 = (n-1)(n+1)(2n+3)/24 для нечетного n (тут произошла совсем магия, которую мне лень объяснять, тем более что я сейчас вообще с теорией множеств пытаюсь разобраться).<br />
<br />
Теперь весь этот ужас складываем, и получаем:<br />
Для нечетного n - (n+1)(2n^2+3n-1)/8<br />
Для четного n - n(n+2)(2n+1)/8
qwertyMAN Клавиатурович, а теперь вопрос: не наврала ли я где-то ещё?
Rikka 10, проблематично выводится формула. Мне удалось лишь написать алгоритм на двух-трёх циклах который по идее находил решение, но всё же одна формула лучше чем алгоритм.
qwertyMAN Клавиатурович, проблематично выводятся только формулы сумм (хотя с ними мне повезло как раз). Может, существует и более красивое решение, я не лучший решатель комбинаторных задач. Что за алгоритм (хотя бы примерная идея)?
× Пришло новое сообщение