Нужно найти 10 елемент,я так понимаю это прогрессия,совсем не могу разобраться?

Question

[lambardi]

Пусть t0 = 1; tk = t0tk-1 + t1tk-2 +… + tk-2t1 + tk-1t0 , k = 1,2, … Получить t10 .

Answer 1

[Elsper]

Записал задачу ты конечно ужасно. По такой записи ничего не понятно.

Решение вроде такое.

int[] allT = new int[11];
allT[0] = 1;
for (int i = 1; i < 11; i++)
{
    for (int i2 = 0; i2 < i; i2++)
    {
        allT[i] += allT[i2] * allT[i - i2-1];
    }
}

allT[10] равно 16796

Comments

[lambardi]

Очень благодарен

[insighter]

lambardi, помечай как ответ, если оно

Answer 2

[Wataru]

Можно последовательно найти t1, t2, t3 .. t9 и через них циклом подсчитать t10.

Нужно их хранить в массиве и тупо записать формулу в коде. Знак суммы становится циклом, в котором надо вычисленное через i выражение прибавлять к счетчику.

Такая реализация подсчета t(n) будет за O(n^2).

Если подумать, то можно быстрее. Во-первых, при умножении t0 на С, tk умножится на C^(k+1). Можно доказать по индукции. Теперь осталось подсчитать числа для t0=1 и домножить на t0^( n+1).

Если же выписать числа на бумажке, то можно заметить, что это числа Каталана, которые считаются по формуле
(2n)!/n!/(n+1)!

Итого, ответ - (2n)!/n!/(n+1)! * t0^(n+1)
При n=10 дает 16796.

Это уже можно подсчитать за O(n).