Symbol Newtona: Różnice pomiędzy wersjami

Przykładowa procedura w [[Pascal (język programowania)|Pascalu]]:

 

function WspNewtona( n, k : integer ) : integer;

var

WspNewtona := wynik;

end;

 

Przykładowy predykat w [[Prolog (język programowania)|Prologu]]:

 

silnia(0, 1) :- !.

silnia(1, 1) :- !.

 

npok(N, K, X) :- silnia(N, X1), silnia(K, X2), NK is N-K, silnia(NK, X3), X is X1 / (X2 * X3).

 

Procedura ta działa szybko i z minimalnym kosztem pamięciowym – wymaga tylko dwu pomocniczych zmiennych (a po dodatkowym usprawnieniu nie potrzebowałaby żadnych). Drobną wadą tego sposobu jest niewielki nadmiar w trakcie obliczeń: maksymalna wartość pośrednia, otrzymana przed ostatnim dzieleniem przez <math>k,</math> jest <math>k</math>-krotnie większa od ostatecznego wyniku. To oznacza, że metody tej nie da się wykorzystać „do granic pojemności” typu całkowitego: maksymalna wiarygodna wartość obliczana tym sposobem zawsze będzie <math>k</math>-krotnie niższa od największej wartości całkowitej dostępnej w danym komputerze, kalkulatorze bądź języku programowania.

 

Poniżej przedstawiona jest procedura [[Rekurencja|rekurencyjna]], pozbawiona tej wady.

function WspNewtonaRek( n, k : integer ) : integer;

begin

WspNewtonaRek := WspNewtonaRek( n-1, k-1 ) + WspNewtonaRek( n-1, k );

end;

 

Implementacja rekurencyjna bez użycia silni w [[Prolog (język programowania)|Prologu]]:

symbolnewtona(N, K, fail) :- K > N, !.

symbolnewtona(K, K, 1) :- !.

symbolnewtona(N, 0, 1) :- !.

symbolnewtona(N, K, X) :- N1 is N-1, K1 is K-1, symbolnewtona(N1, K1, X1), symbolnewtona(N1, K, X2), X is X1 + X2, !.

 

Ten sposób opiera się wprost na rekurencyjnym wzorze: