c*****e
发帖数: 737 | | f*******n
发帖数: 12623 | 2 m / 1 * (m-1) / 2 * (m-2) / 3 ... * (m-n+1) / n | c*****e
发帖数: 737 | 3 are you sure this is correct?
【在 f*******n 的大作中提到】
: m / 1 * (m-1) / 2 * (m-2) / 3 ... * (m-n+1) / n
| z*y
发帖数: 1311 | 4 :are you sure this is correct?
at least could choose min(n, m-n) to start with
【在 f*******n 的大作中提到】
: m / 1 * (m-1) / 2 * (m-2) / 3 ... * (m-n+1) / n
| c*****e
发帖数: 737 | 5 that's not good enough as well.
【在 z*y 的大作中提到】
: :are you sure this is correct?
:
: at least could choose min(n, m-n) to start with
| f*******n
发帖数: 12623 | 6 well, do you think it is incorrect?
【在 c*****e 的大作中提到】
: are you sure this is correct?
| r****t
发帖数: 10904 | 7 你是想考大家 lgamma?
return exp(lgamma(m+1) - lgamma(m-n+1) - lgamma(n+1));
【在 c*****e 的大作中提到】
: 有什么高明的办法？
| d****n
发帖数: 1637 | 8 /*only works for small number */
/*die when integer overflow*/
#include
#include
int bico(int n, int k){
int t, i ,c ;
if (k>n) t=n, n=k, k=t;
if (k<0 ) return 0 ;
if (k>(n-k)) k=n-k;
c=1;
for(i=0;i
c*=(n-(k-(i+1))) , c/=(i+1);
return c ;
}
int main(int argc, char * argv[] ){
if(argc!=3) return -1;
int c;
c=bico(atoi(argv[1]) , atoi(argv[2]) ) ;
printf("bionomial %d\n", c);
} | d****n
发帖数: 1637 | 9 /*working with larger numbers but still die */
/**C(80, 20) is okay, which was not ok in previous version**/
#include
#include
#include
float
gammln (float xx)
//Returns the value ln[Ãxx)] for xx > 0.
{
//Internal arithmetic will be done in double precision, a nicety that
//you can omit if five-figure
//accuracy is good enough.
double x, y, tmp, ser;
static double cof[6] = { 76.18009172947146, -86.50532032941677,
24.01409824083091, -1.231739572450155,
0.1208650973866179e-2, -0.5395239384953e-5
};
int j;
y = x = xx;
tmp = x + 5.5;
tmp -= (x + 0.5) * log (tmp);
ser = 1.000000000190015;
for (j = 0; j <= 5; j++)
ser += cof[j] / ++y;
return -tmp + log (2.5066282746310005 * ser / x);
}
float
factln (int n)
//Returns ln(n!).
{
static float a[101]; //A static array is automatically
//initialized to zero.
//if (n < 0) nrerror("Negative factorial in routine factln");
if (n <= 1)
return 0.0;
if (n <= 100)
return a[n] ? a[n] : (a[n] = gammln (n + 1.0)); //In range of
table.
else
return gammln (n + 1.0); // Out of range of table.
}
float
bico (int n, int k)
//Returns the binomial coefficient n ,k as a floating-point number.
{
//float factln(int n);
return floor (0.5 + exp (factln (n) - factln (k) - factln (n - k)));
//The floor function cleans up roundoff error for smaller values of n
//and k.
}
int
main (int argc, char *argv[])
{
if (argc != 3)
return -1;
float c;
c = bico (atoi (argv[1]), atoi (argv[2]));
printf ("bionomial %.0f\n", c);
} | z*y
发帖数: 1311 | 10
How about this one?
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html
【在 c*****e 的大作中提到】
: that's not good enough as well.
| | | x******a
发帖数: 6336 | 11 can anybody help me check whether the following code works.
i tried small numbers seems ok. but I got
(80, 20) = 768304531155741577 seems not correct
thank you.
#include
using namespace std;
unsigned long combination(int const n, int const k)
{
if(k==0 ||k==n) return 1;
else
if(k==1) return n;
else
return (unsigned long) combination(n-1, k-1)*n/k;
}
int main()
{
int n;
int k;
cin >> n >>k;
cout << combination(n, k)<
return 0;
} | p***o
发帖数: 1252 | 12 >>> comb=lambda m,n: reduce(lambda x,y: x*(n+1-y)/y, range(1,m+1),1)
>>> comb(20,80)
3535316142212174320L
【在 x******a 的大作中提到】
: can anybody help me check whether the following code works.
: i tried small numbers seems ok. but I got
: (80, 20) = 768304531155741577 seems not correct
: thank you.
: #include
: using namespace std;
: unsigned long combination(int const n, int const k)
: {
: if(k==0 ||k==n) return 1;
: else
| c*******h
发帖数: 1096 | 13 最后一步 combination(n-1, k-1)*n 的时候溢出了
(79,19)是对的
【在 x******a 的大作中提到】
: can anybody help me check whether the following code works.
: i tried small numbers seems ok. but I got
: (80, 20) = 768304531155741577 seems not correct
: thank you.
: #include
: using namespace std;
: unsigned long combination(int const n, int const k)
: {
: if(k==0 ||k==n) return 1;
: else
| x******a
发帖数: 6336 | 14 thank you cockroach for comfirming this.
should I consider the greatest common divisor function
gcd(n, k)
rewrite
combination(n-1, k-1)*n/k
as
combination(n-1, k-1)*gcd(n,k)/k*n/gcd(n, k)
I think this will work out but need more time.
【在 c*******h 的大作中提到】
: 最后一步 combination(n-1, k-1)*n 的时候溢出了
: (79,19)是对的
| p*********t
发帖数: 2690 | 15 可以用递归吗？
【在 c*****e 的大作中提到】
: 有什么高明的办法？
| c*******h
发帖数: 1096 | 16 It may not worth the efforts. Since binomial coefficients grow fast,
it is quite unlikely that you can write a general purpose routine to
compute large coefficients. Know your objective before coding. For
example, if you only need a few digits of accuracy, use double
precision in combination with logarithm mapping. On the other hand,
if you need an accurate integral result, determine the number of
digits of the result before choosing the accurate integer data type.
【在 x******a 的大作中提到】
: thank you cockroach for comfirming this.
: should I consider the greatest common divisor function
: gcd(n, k)
: rewrite
: combination(n-1, k-1)*n/k
: as
: combination(n-1, k-1)*gcd(n,k)/k*n/gcd(n, k)
: I think this will work out but need more time.
| p**o
发帖数: 3409 | 17 In [6]: from scipy import misc
In [7]: float(misc.comb(800, 200))
Out[7]: 7.725180424308654e+193
In [8]: misc.comb(80, 20, exact=True)
Out[8]: 3535316142212174320L
In [9]: misc.comb(800, 200, exact=True)
Out[9]:
77251804243102249900492680663173121937380428827121913983653641771247184259
511395708778940396868688593938893892876285454025018169910
351416052742960313511746489365778233208840410665960743057530800L
source:
https://github.com/scipy/scipy/blob/master/scipy/misc/common.py | c*****e
发帖数: 737 | | f*******n
发帖数: 12623 | 19 m / 1 * (m-1) / 2 * (m-2) / 3 ... * (m-n+1) / n | c*****e
发帖数: 737 | 20 are you sure this is correct?
【在 f*******n 的大作中提到】
: m / 1 * (m-1) / 2 * (m-2) / 3 ... * (m-n+1) / n
| | | z*y
发帖数: 1311 | 21 :are you sure this is correct?
at least could choose min(n, m-n) to start with
【在 f*******n 的大作中提到】
: m / 1 * (m-1) / 2 * (m-2) / 3 ... * (m-n+1) / n
| c*****e
发帖数: 737 | 22 that's not good enough as well.
【在 z*y 的大作中提到】
: :are you sure this is correct?
:
: at least could choose min(n, m-n) to start with
| f*******n
发帖数: 12623 | 23 well, do you think it is incorrect?
【在 c*****e 的大作中提到】
: are you sure this is correct?
| r****t
发帖数: 10904 | 24 你是想考大家 lgamma?
return exp(lgamma(m+1) - lgamma(m-n+1) - lgamma(n+1));
【在 c*****e 的大作中提到】
: 有什么高明的办法？
| d****n
发帖数: 1637 | 25 /*only works for small number */
/*die when integer overflow*/
#include
#include
int bico(int n, int k){
int t, i ,c ;
if (k>n) t=n, n=k, k=t;
if (k<0 ) return 0 ;
if (k>(n-k)) k=n-k;
c=1;
for(i=0;i
c*=(n-(k-(i+1))) , c/=(i+1);
return c ;
}
int main(int argc, char * argv[] ){
if(argc!=3) return -1;
int c;
c=bico(atoi(argv[1]) , atoi(argv[2]) ) ;
printf("bionomial %d\n", c);
} | d****n
发帖数: 1637 | 26 /*working with larger numbers but still die */
/**C(80, 20) is okay, which was not ok in previous version**/
#include
#include
#include
float
gammln (float xx)
//Returns the value ln[Ãxx)] for xx > 0.
{
//Internal arithmetic will be done in double precision, a nicety that
//you can omit if five-figure
//accuracy is good enough.
double x, y, tmp, ser;
static double cof[6] = { 76.18009172947146, -86.50532032941677,
24.01409824083091, -1.231739572450155,
0.1208650973866179e-2, -0.5395239384953e-5
};
int j;
y = x = xx;
tmp = x + 5.5;
tmp -= (x + 0.5) * log (tmp);
ser = 1.000000000190015;
for (j = 0; j <= 5; j++)
ser += cof[j] / ++y;
return -tmp + log (2.5066282746310005 * ser / x);
}
float
factln (int n)
//Returns ln(n!).
{
static float a[101]; //A static array is automatically
//initialized to zero.
//if (n < 0) nrerror("Negative factorial in routine factln");
if (n <= 1)
return 0.0;
if (n <= 100)
return a[n] ? a[n] : (a[n] = gammln (n + 1.0)); //In range of
table.
else
return gammln (n + 1.0); // Out of range of table.
}
float
bico (int n, int k)
//Returns the binomial coefficient n ,k as a floating-point number.
{
//float factln(int n);
return floor (0.5 + exp (factln (n) - factln (k) - factln (n - k)));
//The floor function cleans up roundoff error for smaller values of n
//and k.
}
int
main (int argc, char *argv[])
{
if (argc != 3)
return -1;
float c;
c = bico (atoi (argv[1]), atoi (argv[2]));
printf ("bionomial %.0f\n", c);
} | z*y
发帖数: 1311 | 27
How about this one?
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html
【在 c*****e 的大作中提到】
: that's not good enough as well.
| x******a
发帖数: 6336 | 28 can anybody help me check whether the following code works.
i tried small numbers seems ok. but I got
(80, 20) = 768304531155741577 seems not correct
thank you.
#include
using namespace std;
unsigned long combination(int const n, int const k)
{
if(k==0 ||k==n) return 1;
else
if(k==1) return n;
else
return (unsigned long) combination(n-1, k-1)*n/k;
}
int main()
{
int n;
int k;
cin >> n >>k;
cout << combination(n, k)<
return 0;
} | p***o
发帖数: 1252 | 29 >>> comb=lambda m,n: reduce(lambda x,y: x*(n+1-y)/y, range(1,m+1),1)
>>> comb(20,80)
3535316142212174320L
【在 x******a 的大作中提到】
: can anybody help me check whether the following code works.
: i tried small numbers seems ok. but I got
: (80, 20) = 768304531155741577 seems not correct
: thank you.
: #include
: using namespace std;
: unsigned long combination(int const n, int const k)
: {
: if(k==0 ||k==n) return 1;
: else
| c*******h
发帖数: 1096 | 30 最后一步 combination(n-1, k-1)*n 的时候溢出了
(79,19)是对的
【在 x******a 的大作中提到】
: can anybody help me check whether the following code works.
: i tried small numbers seems ok. but I got
: (80, 20) = 768304531155741577 seems not correct
: thank you.
: #include
: using namespace std;
: unsigned long combination(int const n, int const k)
: {
: if(k==0 ||k==n) return 1;
: else
| | | x******a
发帖数: 6336 | 31 thank you cockroach for comfirming this.
should I consider the greatest common divisor function
gcd(n, k)
rewrite
combination(n-1, k-1)*n/k
as
combination(n-1, k-1)*gcd(n,k)/k*n/gcd(n, k)
I think this will work out but need more time.
【在 c*******h 的大作中提到】
: 最后一步 combination(n-1, k-1)*n 的时候溢出了
: (79,19)是对的
| p*********t
发帖数: 2690 | 32 可以用递归吗？
【在 c*****e 的大作中提到】
: 有什么高明的办法？
| c*******h
发帖数: 1096 | 33 It may not worth the efforts. Since binomial coefficients grow fast,
it is quite unlikely that you can write a general purpose routine to
compute large coefficients. Know your objective before coding. For
example, if you only need a few digits of accuracy, use double
precision in combination with logarithm mapping. On the other hand,
if you need an accurate integral result, determine the number of
digits of the result before choosing the accurate integer data type.
【在 x******a 的大作中提到】
: thank you cockroach for comfirming this.
: should I consider the greatest common divisor function
: gcd(n, k)
: rewrite
: combination(n-1, k-1)*n/k
: as
: combination(n-1, k-1)*gcd(n,k)/k*n/gcd(n, k)
: I think this will work out but need more time.
| p**o
发帖数: 3409 | 34 In [6]: from scipy import misc
In [7]: float(misc.comb(800, 200))
Out[7]: 7.725180424308654e+193
In [8]: misc.comb(80, 20, exact=True)
Out[8]: 3535316142212174320L
In [9]: misc.comb(800, 200, exact=True)
Out[9]:
77251804243102249900492680663173121937380428827121913983653641771247184259
511395708778940396868688593938893892876285454025018169910
351416052742960313511746489365778233208840410665960743057530800L
source:
https://github.com/scipy/scipy/blob/master/scipy/misc/common.py | b****y
发帖数: 169 | |
|
