Cześć.
Mam do napisania funkcję własną, która oblicza wartość symbolu Newtona. Zastanawiam się, czy wykorzystanie trójkąta Pascala to dobre rozwiązanie? Może ktoś zna lepsze?
Pozdrawiam.
0
0
nie wiem czy to lepsze ale można to liczyć ze wzoru
0
1: /// Author & Copyright : Peter Luschny
2: /// Created: 2010-02-01
3: /// License: LGPL version 2.1 or (at your option)
4: /// Creative Commons Attribution-ShareAlike 3.0
5:
8: using System;
9: using System.Numerics;
10: using Math.Primes;
11: using FastFactorial;
12: using MathUtils;
13:
14: namespace Math.FastFactorial {
15:
16: class Program {
17:
18: static BigInteger NaiveBinomial(int n, int k)
19: {
20: var f = new FactorialPrimeSwing();
21: var fn = f.Factorial(n);
22: var fk = f.Factorial(k);
23: var fnk = f.Factorial(n - k);
24: return fn / (fk * fnk);
25: }
26:
27: static void Main()
28: {
29: for(int n=0; n < 100;n++)
30: for (int k = 0; k <= n; k++)
31: {
32: BigInteger b = NaiveBinomial(n, k);
33: BigInteger c = FastBinomial.Binomial(n, k);
34: if (b != c)
35: {
36: Console.WriteLine("NB(" + n + "," + k + ") = " + b);
37: Console.WriteLine("FB(" + n + "," + k + ") = " + c);
38: Console.ReadLine();
39: }
40: Console.WriteLine("C(" + n + "," + k + ") = " + c);
41: }
42: Console.ReadLine();
43: }}
44:
45:
46: public class FastBinomial {
47:
48: private FastBinomial() { }
49:
50: public static BigInteger Binomial(int n, int k)
51: {
52: if (0 > k || k > n)
53: {
54: throw new System.ArgumentException(
55: "Binomial: 0 <= k and k <= n required, but n was "
56: + n + " and k was " + k);
57: }
58:
59: if ((k == 0) || (k == n)) return BigInteger.One;
60: if (k > n / 2) { k = n - k; }
61: int fi = 0, nk = n - k;
62:
63: int rootN = (int)System.Math.Floor(System.Math.Sqrt(n));
64: int[] primes = new PrimeSieve(n).GetPrimeCollection(2, n).ToArray();
65:
66: foreach (int prime in primes) // Equivalent to a nextPrime() function.
67: {
68: if (prime > nk)
69: {
70: primes[fi++] = prime;
71: continue;
72: }
73:
74: if (prime > n / 2)
75: {
76: continue;
77: }
78:
79: if (prime > rootN)
80: {
81: if (n % prime < k % prime)
82: {
83: primes[fi++] = prime;
84: }
85: continue;
86: }
87:
88: int r = 0, N = n, K = k, p = 1;
89:
90: while (N > 0)
91: {
92: r = (N % prime) < (K % prime + r) ? 1 : 0;
93: if (r == 1)
94: {
95: p *= prime;
96: }
97: N /= prime;
98: K /= prime;
99: }
100: if (p > 1) primes[fi++] = p;
101: }
102:
103: return Xmath.Product(primes, 0, fi);
104: }
105: }}
106:
0
int **trojkatPascala;
trojkatPascala= new int *[n];
for (int j=0;j<n;j++)
{
trojkatPascala[j]=new int [j+1];
trojkatPascala[j][0]=1;
trojkatPascala[j][j]=1;
for (int i = 0; i<j-1; i++) trojkatPascala[j][i+1]=trojkatPascala[j-1][i]+trojkatPascala[j-1][i+1];
}
Nie uważasz, że to jest szybsze...
Ktoś zna coś szybszego?
0
nie wiem jak to się ma do szybkości ale dla tego kodu co podałem benchmarki są następujące:
Testing binomial: (400000,133333)
ParallelBinomial: 0.015 sec
PrimeBinomial: 0.026 sec
GMP5Binomial: 4.938 sec
Testing binomial: (1600000,533333)
ParallelBinomial: 0.078 sec
PrimeBinomial: 0.125 sec
GMP5Binomial: 91.063 sec
Testing binomial: (6400000,2133333)
ParallelBinomial: 0.422 sec
PrimeBinomial: 0.610 sec
GMP5Binomial: 1733.750 sec
0
Jak napisać kod programu, który oblicza wartość symbolu Newtona korzystając z trójkąta Pascala?
0
Przykład i wyjaśnienia: http://www.brpreiss.com/books/opus5/html/page460.html