пятница, 11 июня 2010 г.

Количество треугольников

Сколько треугольников?
Внутри квадрата случайным образом поставили точку и соединили ее с вершинами квадрата. Далее каждую новую точку соединяли отрезками с вершинами квадрата и уже поставленными точками так, чтобы количество связей было максимальным, но отрезки не пересекались. При этом место расположения каждой новой точки выбиралось случайно, но не могло находиться на стороне квадрата или уже проведенном отрезке. В итоге, получилась сеть из элементарных треугольников. Под элементарным понимается треугольник, который не разбит на более мелкие треугольники. Например, количество элементарных треугольников для случая с десятью точками (на рисунке) легко посчитать. А сколько элементарных треугольников получится для N точек?

5 комментариев:

  1. mr-raz-dva, например, для случая с двумя точками эта формула уже не подходит.

    ОтветитьУдалить
  2. Эйч, верно.
    Одно из решений этой задачи такое:
    Сумма всех углов вокруг всех точек будет равна 360*N. Сумма углов квадрата равна 360. Таким образом, сумма всех углов всех треугольников будет равна 360*N+360.
    А так как сумма углов одного треугольника составляет 180 градусов, то общее количество треугольников легко вычислить (360*N+360)/180 = 2*N+2.

    ОтветитьУдалить
  3. 1 точка - 4 треу = 2*(1+1)

    после добавления новой точки какой-то треу разбивается на 3 новых, т.е после каждой новой точки количество треу увеличивается на 2 = 3(новых) - 1(старый) =>

    2 точки - 4+2=6 треу = 2*(2+1)
    ...
    N точек - 2*(N+1) треу

    ОтветитьУдалить