Wikipedia

Symbol Newtona: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
DKnoto (dyskusja | edycje)
3 edycje
kat.
DKnoto (dyskusja | edycje)
3 edycje
Refaktoring przykładów w Javie.
Linia 145:
long symbolNewtona(final long N, final long K)
{
assert( N >= 0);
assert( K >= 0);
 
if (N < K)
return 0L;
 
if (K == 0 || K == N)
return 1L;
 
if (K == 1 || K == N - 1)
return N;
 
long wynik = 1L;
try
{
forfinal (long imaxK = 1L;Math.min(K, iN <=- K); i++)
for (long i = 1L; i <= maxK; i++)
wynik = Math.multiplyExact(wynik, (N - i + 1)) / i;
}
Linia 168 ⟶ 175:
Drugi przykład w [[Java (język programowania)|Javie]] daje poprawne wyniki dla dowolnych dodatnich danych wejściowych:
<syntaxhighlight lang=java>
BigInteger symbolNewtona(final intlong N, final intlong K)
{
assert( N >= 0);
assert( K >= 0);
 
if (N < K)
return BigInteger.valueOf(0);
 
if (K == 0L || K == N)
return BigInteger.valueOf(1);
 
if (K == 1L || K == N - 1L)
return BigInteger.valueOf(N);
 
BigInteger result = BigInteger.valueOf(1);
 
forfinal (intlong imaxK = 1;Math.min(K, iN <=- K); i++)
for (long i = 1L; i <= maxK; i++)
result = result.multiply(BigInteger.valueOf(N - i + 11L)).divide(BigInteger.valueOf(i));
 
return result;
}
</syntaxhighlight>
Ta druga metoda jest efektywna czasowo i pamięciowo, jest tylko około trzy razy wolniejsza od wersji poprzedniej. W obu metodach sprawdzane są przypadki szczególne oraz zoptymalizowano liczbę pętli dla <math>K > N / 2</math> korzystając z faktu, iże pamięciowofunkcja ta jest symetryczna.
 
Przykładowy predykat w [[Prolog (język programowania)|Prologu]]:
Źródło: „https://pl.wikipedia.org/wiki/Symbol_Newtona”