[T.....d]

#informatyka #programowanie #matematyka #polibaza

Ktoś potrafi napisać pseudokod dla algorytmu obliczającego dwumian Newtona rekurencyjnie? Te w internecie są bez użycia silni i jakoś nie wierzę, że to ma tak wyglądać

[japer]

@TwardyDziad: C(n,k)=C(k-1,n-1)+C(k,n-1)

Warunek zatrzymujący to C(n,n)=C(0,n)=1

[T.....d]

@japer:

int newton(int n ,int k)

11 {

12 if ( n==k || k==0 )

13 return 1;

14 else

15 return newton(n-1,k-1)+newton(n-1,k);

16 }

[japer]

@TwardyDziad: n == 0 popraw

Tak jest dobrze. Nawiasem mówiąc, ten sposób obliczania symbolu Newtona jest bardzo nieefektywny.

[Patres]

@TwardyDziad: W swoich folderach mam coś takiego:

(DiZ)-dwumian Newtona

NEWT-DiZ(n,k)

if (k = 0) OR (n = k)

return 1

else

return NEWT-DiZ(n-1,k-1)+NEWT-DiZ(n-1,k)

/////////////////

(PD)-dwumian Newtona

NEWT-PD(n,k)

utwórz tablicę B[0..n][0..k]

for i<-0 to n do

for j<-0 to MIN(i,k) do

if(j = 0) OR (j = i) then

else

return B[n][k]

/////////////////

[japer]

@TwardyDziad: A, pardon, będzie k==0

[T.....d]

@japer: chyba czaje. po którejś tam iteracji będziemy mieli

newton(n-1,k-1)+newton(n-1,k)+newton(n-2,k-2)+newton(n-2,k)+newton(n-3,k-3)+newton(n-3,k)//==n==k

tylko ten dwumian oparty jest na silni, no i jak on oblicza wartości 234/2*3 np. jak cały czas się rozbija aż n==k?

[b.....h]

@TwardyDziad: zara ci dam kod ze szkoly

[b.....h]

@TwardyDziad: wybacz, mam tylko iteracyjnie, ale ci sie przyda :D

http://ideone.com/HqEa6g

[japer]

@TwardyDziad: Komputer będzie dążyć w rekursji do osiągnięcia zatrzymania.

Przedstawia się to tak. Mamy zbiór A, zabieramy jeden element x. Ten zbiór nazwijmy A'.

Teraz zastanówmy się, ile będą równe kombinacje w zbiorze A' w przypadku, gdy weźmiemy pod uwagę pozostałe elementy x i gdy wszystkie wywalimy.

Dla części z x'ami wygląda to tak: Gdy oznaczymy kombinację K i odpowiednio K', to kombinacja K dla k elementów można nazwać sumą kombinacji

[T.....d]

@japer: a tak działa to w maszynie ;p

[japer]

A teraz podaj 100 po 34. :>

[japer]

@TwardyDziad:

[T.....d]

@japer: dobre trolo!