Общая формула существует ли для...

laki

Аналог
http://ru.wikipedia.org/wiki/%C1%E8%ED%EE%EC_%CD%FC%FE%F2%EE...
тока (a+b+c) в степени n?

SPARTAK3959

(a+b+c)^n=\sum{i+j+k=n,i\ge 0,j\ge 0,k\ge 0}a^ib^jc^k\frac{n!}{i!j!k!}

laki

бля а человеческим языком
:confused:

mkrec

да-да, она называется "полиномиальная формула". и при чем здесь девелопмент?

pitrik2

[math] $(a+b+c)^n=\sum_{i+j+k=n,i\ge 0,j\ge 0,k\ge 0}a^ib^jc^k\frac{n!}{i!j!k!}$ [/math]

kruzer25

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

mkrec

да и ваще, между прочим, эта формула сама собой очевидна :)

kruzer25

Ну вотмне она так сходу в голову за десять секунд не пришла :confused:

mkrec

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

laki

и при чем здесь девелопмент?

запрогать ее надо

kruzer25

Да я понимаю, как её вывести за пару минут, есть ещё, по крайней мере, один способ.
Но от этого формула не становится очевидной ;)

kruzer25

$res = 0;

for($i=0;$i<$n;$i++) {

for($j=0;$j<$n-$i;$j++) {

//for($k=0;$k<$n-$i-$j;$k++) {

$k = $n-$i-$j;

//$res += pow($a,$i) + pow($b,$j) + pow($c,$k);

$res += getBayda($i,$j,$k)*pow($a,$i)*pow($b,$j)*pow($c,$k)

//}

}

}

А не легче ли написать $res = pow($a+$b+$c,$n)?
Или это у вас задачи на "работе с ЭВМ"?

geja_03

Это что за офигенная хня написана у тебя в code?

kruzer25

Это называется цикл. :o

nikita270601

Сравни формулу и свой код. :)

geja_03

Не подскажешь, как твой цикл связан с предыдущей формулой

nikita270601

Или ты просто решил показать пример цикла в PHP?
Можно было и проще пример подобрать, я полагаю!

geja_03



res=0;

#pragma omp parallel for private(i,j,k) reduction(+:res)

for (i = 0; i < n; i++) {

j=0;

k=n-i;

do

{

res += fac(n) * pow(a,i) * pow(b,j) * pow(c,k) / (fac(i) * fac(j) * fac(k;

++j;

--k;

} while (j<n-i)

}

#pragma omp end parallel for

Вроде так.
ЗЫ fac - это функция считающая факториал. Насколько я помню в стандартных билиотеках C ее нет.

zya369

я вообще не понимаю что надо - если ф-ию, получающую a,b,c и возвр-ую (a+b+c)^n то


return pow(a+b+c, n)

:confused:

geja_03

Сверху есть формула, видимо левую часть нада, правая вроде как проблем ни для кого не представляет

zya369

т.е. задача стоит так: посчитать (a+b+c)^n через жопу?

geja_03

Вот тут возник поинтереснее вопрос: как посчитать (a+b+c)!/(a! * b! * c!) менее трудозатратно чем считать напрямую. Потому как впрямую придется ограничивать себя не очень большим n, чтобы значение факториала не выходило за границу допустимых значений, плюс к этому деление довольно тяжелая операция...

geja_03

ага, кстати через жопу этот процесс можно распараллелить

kruzer25

Бля, протупил, сейчас пофикшу. :o

kruzer25

(a+b+c)!/(a!*b!*c!) = (a!*a+b)!/a!)*a+b+c)!/(a+b)!/(a!*b!*c!) = (a!/a!)*a+b)!/(a!*b!*a+b+c)!/a+b)!*c! = a+1)*(a+2)*...*b/(1*2*...*b * b+1)*(b+2)*...*c/(1*2*...*c.
Наименее затратный способ, наверное.

geja_03

Ну считать факториал произведениями это непозволительная роскошь. Тут замечательно константный массив подойдет типа fac[0]=1, fac[1]=1, fac[2]=2....
Я думаю посчитать отдельно (a+b+c)!/max(a,b,c)!, потом разделить на произведение двух оставшихся факториалов. Но это только позволит немного поднять порог n, а собственно, скорее всего, выйдет накладнее по производительности.

vall

f(a, b, c) = f(a-1, b, c) + f(a, b-1, c) + f(a, b, c-1)

kruzer25

Я думаю посчитать отдельно (a+b+c)!/max(a,b,c)!, потом разделить на произведение двух оставшихся факториалов
...а если произведение не влезет - то делить по отдельности.
А если делить по отдельности - то можно и (a+b+c)!/max(a,b,c)! разделить на две части.
Конечно, тут никакого особого прироста в производительности не будет, зато с ограничениями на размер числа меньше проблем.

geja_03

Точняк!
Помню же, что был какой-то способ.

geja_03

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

zya369

какая наз нагрузка на кусок кода, который заведомо работает пиздец как неоптимально? :shocked:

geja_03

Ну если звезды зажигаются, значит это кому-нибудь нужно... В смысле этот изврат нужен же зачем то, а если нужен, то вдруг он нужен много раз, а если он нужен много раз, то любая оптимизация не помешает с учетом того, что код очень тяжелый.

SCIF32

можно так писать
[math] $(a+b+c)^n=\sum_{i+j+k=n,i\ge 0,j\ge 0,k\ge 0}a^ib^jc^k\frac{n!}{i!j!k!}$ [/math]
[math]  (a+b+c)^n=\sum_{i+j+k=n,i\ge 0,j\ge 0,k\ge 0}a^ib^jc^k\frac{n!}{i!j!k!}

[/math]

yolki

сначала вычисляем сумму. потом сумму возводим в степень N за [math][res=120]$[\log_2N]$[/math] операций

SCIF32

и еще немного пиара... (правые левые круглые скобки поленился выставлять)
[math]$$\frac{(a+b+c)!}{(a!*b!*c!)} = \frac{ (a!*(\frac{(a+b)!}{a!})*(\frac{(a+b+c)!}{(a+b)!}}{(a!*b!*c!)} = (\frac{a!}{a!})*(\frac{(a+b)!}{(a!*b!)})*(\frac{(a+b+c)!}{a+b)!*c!)}) = (\frac{(a+1)*(a+2)*\dots*b}{(1*2*...*b})* (\frac{(b+1)*(b+2)*\dots*c}{(1*2*\dots*c)})$$[/math]


[math]$$\frac{(a+b+c)!}{(a!*b!*c!)} =

\frac{ (a!*(\frac{(a+b)!}{a!})*(\frac{(a+b+c)!}{(a+b)!}}{(a!*b!*c!)} =

(\frac{a!}{a!})*(\frac{(a+b)!}{(a!*b!)})*(\frac{(a+b+c)!}{a+b)!*c!)}) =

(\frac{(a+1)*(a+2)*\dots*b}{(1*2*...*b})* (\frac{(b+1)*(b+2)*\dots*c}{(1*2*\dots*c)})$$[/math]

geja_03

Чет не понял идею

kruzer25

этот изврат нужен же зачем то, а если нужен, то вдруг он нужен много раз
Этот изврат, скорее всего, нужен только для того, чтобы сдать задачу с таким извращённым условием преподу.
Соответственно, этот изврат нужен только один раз - сдать и забыть, как кошмарный сон.

kruzer25

Идея - в том, что лобовая формула (считаем сумму, возводим её в нужную степень) - и есть оптимизация (а возводить в степень можно за время порядка logN - допустим, для возведения в 100 степень - пишем в результат единицу, возводим в квадрат, ещё раз в квадрат, умножаем результат на эту четвёртую степень, возводим три раза в квадрат, умножаем результат на получившуюся тридцать вторую степень, возводим в квадрат, умножаем результат на получившуюся шестьдесят четвёртую степень - теперь в результате лежит сотая степень).

geja_03

А какая тут связь с сабжевой формулой?

kruzer25

Даёт тот же результат, гораздо быстрее. Это и есть оптимизация, вообще-то - найти самый быстрый алгоритм из тех, которые решают поставленную задачу "даны a, b и c, посчитать (a+b+c)^n"

geja_03

Лучшая оптимизация разложение не использовать вообще...

kruzer25

А я про что?

geja_03

Ну в-общем понятно, говорим об одном и том же, но на разных языках. Ждем комментариев автора по этому поводу

Makc500

а ты с какого факультета?

laki

подсчет вероятности в конечных узлах триномиального дерева ;) типа вероятность того как мы можем прийти в конечный узел. в статье предлагается алгоритм O(n*n) n-глубина дерева

laki

там есть x надо power его посчитать ;) :grin:

kruzer25

Ну так зачем настолько через жопу?

laki

это не ко мне а к китайцам. это они этот ебучий алгоритм придумали.если считать для каждого конечного узла то сложность задачи будет O(n*n*n).

geja_03

А как в данном случае пригождается эта формула?

laki

(a+b+c)^n = ... + x^2*a + x*b + c + ...
условно говоря получаем полином
x^2*a + x*b + c = P(-1)*x^2+P(0)*x + P(1)
а отсюда находим вероятности P(l где l - номер конечного узла. узлов получается 2*n+1
P(-1) = a
P(0) = b
P(1) = c

geja_03

Что-то странное у тебя записано в первой формуле. Откуда берется x и почему степени a,b,c равны 1 а не n

laki

описал вкратце
вот то что нужно сделать
Оставить комментарий
Имя или ник:
Комментарий: