Сколько треугольников на картинке?

Question

[Иван]

Как, зная длину стороны такого треугольника, найти число изображенных треугольников (для примера выше ответ 13)?

Comments

[Иван]

Перебор всех комбинаций не предлагать :)

[Иван]

И как вообще на любом языке программирования задавать такие «треугольные массивы»?

[Максим Васильев]

А в реугольном массиве предполагается хранить только маленькие треугольники? Или вообще все?

[Иван]

@qmax про треугольный массив я погорячился, здесь ведь не нужно хранить значение каждого треугольника.

Answer 1

[Максим Васильев]

ДЛЯ ПОТОМКОВ: не верьте всему, что пишут в интернетах! это решение неправильное!

При увеличении стороны треугольника на 1
C(i+1) =
C(i) /* все треугольники предыдущей фигуры (которая со стороной i) */
+ 2i+1 /* треугольники со стороной 1, пририсованные к одной из сторон предыдущей фигуры*/
+ i /* треугольники со стороной 2 накладывающиеся на предыдущую на 1 */
+ i-1 /* треугольники со стороной 3 накладывающиеся на предыдущую на 2*/
+ i-2 /* треугольники со стороной 4 накладывающиеся на предыдущую на 3*/
+ итд до нуля (тоесть до i-i)

Comments

[Иван]

Спасибо.

Answer 2

[Иван]

По алгоритму @qmax написал функцию:

function countTriangles($sideLength) {
    $count = 0;
    for ($i = 0; $i < $sideLength; $i++) {
        $count += (2 * $i) + 1;
        for ($j = 0; $j < $i; $j++)
            $count += $i - $j;
    }
    return $count;
}

Вроде бы работает правильно.

График (длина стороны от 0 до 100):

Comments

[Максим Васильев]

Таки, всё можно свернуть в формулу:
C(n)
= C(n+1) + 2i+1 + Sum(i-1 ... 0)
= C(n+1) + Sum(i+1 ... 0)
= C(n+1) + (i^2 + i)/2

[Иван]

@qmax дьявол, как ты это делаешь?!

[Максим Васильев]

Математика! :)

Answer 3

[Sergey Lerg]

Интересно посмотреть на график такой зависимости.

Comments

[Иван]

@Lerg написал выше

[Sergey Lerg]

@0neS Спасибо

Answer 4

[Mrrl]

Если искать ответ в виде формулы - то [n*(n+2)*(2*n+1)/8]
Там для чётных и нечётных n получаются разные серии, поэтому приходится брать целую часть (или мудрить с (-1)^n).