c*****e
发帖数: 737 | 1 有啥好方法么？我被问到了，不过最后面试官说大致正确。 |
b*****c
发帖数: 1103 | 2 it is very big, hoho, usually we only need C(m,n) mod a very large prime No. |
c*****e
发帖数: 737 | 3 啥意思？
他要的是计算比如C(13,5)=1287
No.
【在 b*****c 的大作中提到】
: it is very big, hoho, usually we only need C(m,n) mod a very large prime No.
|
g*********e
发帖数: 14401 | |
c*****e
发帖数: 737 | 5 你是说m!(n-m)!/n!?这个面试官告诉你的。
【在 g*********e 的大作中提到】
: 不是有公式吗？还能比公式更快？
|
g*********e
发帖数: 14401 | 6
对啊。然后可以稍微减少点计算量。 C(m,n)=m*(m-1)*...*(m-n+1)/n!
一共2n次乘法。读书时候口算都是这么算的。
【在 c*****e 的大作中提到】
: 你是说m!(n-m)!/n!?这个面试官告诉你的。
|
c*****e
发帖数: 737 | 7 这么直接的话就不用问你了，n!很容易溢出的。
【在 g*********e 的大作中提到】
:
: 对啊。然后可以稍微减少点计算量。 C(m,n)=m*(m-1)*...*(m-n+1)/n!
: 一共2n次乘法。读书时候口算都是这么算的。
|
g*********e
发帖数: 14401 | 8
那你说说你的吧？
【在 c*****e 的大作中提到】
: 这么直接的话就不用问你了，n!很容易溢出的。
|
c*****e
发帖数: 737 | 9 我想了个超级复杂的，分解质因数，然后在计算结果。
不知道有啥合理的么，他要越不可能溢出越好。
【在 g*********e 的大作中提到】
:
: 那你说说你的吧？
|
S*****e
发帖数: 229 | 10 用(m-n+1)/n, (m-n)/(n-1) ... 这样乘起来应该就不会溢出了吧
【在 c*****e 的大作中提到】
: 这么直接的话就不用问你了，n!很容易溢出的。
|
|
|
g*********e
发帖数: 14401 | 11
你这个不行，每个结果可能是浮点数，丢失了最后的整数性质。
【在 S*****e 的大作中提到】
: 用(m-n+1)/n, (m-n)/(n-1) ... 这样乘起来应该就不会溢出了吧
|
c*****e
发帖数: 737 | 12 这个方法我提过，结果说不行，因为你最后还可能要round，如果这可以的话，你一开
始不如直接转double就没有溢出担心了。
【在 S*****e 的大作中提到】
: 用(m-n+1)/n, (m-n)/(n-1) ... 这样乘起来应该就不会溢出了吧
|
k*****y
发帖数: 744 | 13 c(M, N) =c(M-1, N) + c(M-1, N-1)
用递归
【在 c*****e 的大作中提到】
: 有啥好方法么？我被问到了，不过最后面试官说大致正确。
|
g*********e
发帖数: 14401 | 14
赞 递归+dp
O(n2)
【在 k*****y 的大作中提到】
: c(M, N) =c(M-1, N) + c(M-1, N-1)
: 用递归
|
c*****e
发帖数: 737 | 15 good idea,
可惜一开始那个人就告诉我m!(n-m)!/n!，我就往里面套了。
【在 k*****y 的大作中提到】
: c(M, N) =c(M-1, N) + c(M-1, N-1)
: 用递归
|
c*********t
发帖数: 2921 | 16 Here is the best way to compute C(n, m),
O(m)
int combin(int n, int m)
{
int val = 1;
int i;
//every iteration is like to compute C(n ,i)
for (i = 1; i <= m; i++) {
val *= n - (i - 1);
val /= i;
}
return val;
}
【在 c*****e 的大作中提到】
: 有啥好方法么？我被问到了，不过最后面试官说大致正确。
|
g*********e
发帖数: 14401 | 17
你这个会导致浮点数的啊 而且陈法运算O(m)并不比加法的O（n2)快吧
【在 c*********t 的大作中提到】
: Here is the best way to compute C(n, m),
: O(m)
: int combin(int n, int m)
: {
: int val = 1;
: int i;
: //every iteration is like to compute C(n ,i)
: for (i = 1; i <= m; i++) {
: val *= n - (i - 1);
: val /= i;
|
c*********t
发帖数: 2921 | 18 你没有看懂我的注释。
C(n,1) = n/1
C(n, 2) = C(n, 1) * (n-1)/2
C(n, 3) = C(n, 2) * (n - 2) /3
,etc,......
【在 g*********e 的大作中提到】
:
: 你这个会导致浮点数的啊 而且陈法运算O(m)并不比加法的O（n2)快吧
|
c*****e
发帖数: 737 | 19 looks better
【在 c*********t 的大作中提到】
: Here is the best way to compute C(n, m),
: O(m)
: int combin(int n, int m)
: {
: int val = 1;
: int i;
: //every iteration is like to compute C(n ,i)
: for (i = 1; i <= m; i++) {
: val *= n - (i - 1);
: val /= i;
|
c****p
发帖数: 6474 | 20 #include
#include
int C(int m, int n)
{
int *A, *B;
int tmp;
int i, j, k;
if((m <=0 ) || (n <=0 ))
return -1;
if(n == 1)
return m;
if(n == m)
return 1;
if(m - n < n)
n = m - n;
A = malloc(n*sizeof(int)); // A = {m, m - 1, .... m - n + 1}
B = malloc((n-1)*sizeof(int)); // B = {2, 3, ... n}
for(i = 0; i
{
A[i] = m - i;
B[i] = i + 2;
}
A[n-1] = m - n + 1;
//i = 0; j = 0;
for(i = 0; i < n - 1; i++)
{
if(B[i] != 1)
{
tmp = B[i]; // tmp must be a prime
// Divide B[i]...B[n-2] with tmp
// until none of them cant be divided any longer
// Whenever a division happens,
// find an element in A that can be divided.
// Such an element must be somewhere starting
// from A[k]
k = 0;
for(j = i; j < n - 1; j++)
{
if((B[j] == 1) || (B[j] % tmp))
continue;
while(!(B[j] % tmp))
{
B[j] /= tmp;
while(A[k] % tmp)
k++;
A[k] /= tmp;
}
}
}
}
// by now B[i] = 1 for i=0..n-2
// get the result by multiplying elements in A
tmp = 1;
for(i = 0; i < n; i++)
tmp *= A[i];
free(A);
free(B);
return tmp;
}
int main()
{
int m, n;
int tmp;
scanf("%d %d", &m, &n);
if(n>m)
{
tmp = m;
m = n;
n = tmp;
}
printf("C(%d,%d) = %d\n",m,n,C(m,n));
return 0;
}
【在 c*****e 的大作中提到】
: 有啥好方法么？我被问到了，不过最后面试官说大致正确。
|
|
|
c****p
发帖数: 6474 | 21 这个好。。。
【在 c*********t 的大作中提到】
: Here is the best way to compute C(n, m),
: O(m)
: int combin(int n, int m)
: {
: int val = 1;
: int i;
: //every iteration is like to compute C(n ,i)
: for (i = 1; i <= m; i++) {
: val *= n - (i - 1);
: val /= i;
|
g*********e
发帖数: 14401 | 22
o soga
【在 c*****e 的大作中提到】
: looks better
|
x********3
发帖数: 160 | 23 这样做就保证了不会有浮点数的。
【在 g*********e 的大作中提到】
:
: o soga
|
r****t
发帖数: 10904 | 24 是我白痴了么？组合数是 combination 对吧？是你标题和这公式都各自反了，还是问的是倒数，还是我脑子坏了？
【在 c*****e 的大作中提到】
: 你是说m!(n-m)!/n!?这个面试官告诉你的。
|
r****t
发帖数: 10904 | 25 这个以前板上有贴过的，月经题了。
【在 c*****e 的大作中提到】
: 这个方法我提过，结果说不行，因为你最后还可能要round，如果这可以的话，你一开
: 始不如直接转double就没有溢出担心了。
|
a****a
发帖数: 186 | 26 mark~
【在 c*********t 的大作中提到】
: Here is the best way to compute C(n, m),
: O(m)
: int combin(int n, int m)
: {
: int val = 1;
: int i;
: //every iteration is like to compute C(n ,i)
: for (i = 1; i <= m; i++) {
: val *= n - (i - 1);
: val /= i;
|
r****t
发帖数: 10904 | 27 in Python, for C(N,k) 这个是标准写法，至少 loop 到 min (k, N-k) 才对。
val = 1L
for j in xrange(min(k, N-k)):
val = (val * (N-j)) // (j+1) # j+1 because I started from 0
同时，对大组合数都应该用 gamma func 算才对。
【在 c*********t 的大作中提到】
: Here is the best way to compute C(n, m),
: O(m)
: int combin(int n, int m)
: {
: int val = 1;
: int i;
: //every iteration is like to compute C(n ,i)
: for (i = 1; i <= m; i++) {
: val *= n - (i - 1);
: val /= i;
|
r****t
发帖数: 10904 | 28 这个 mod 大素数又该怎么做呢？
No.
【在 b*****c 的大作中提到】
: it is very big, hoho, usually we only need C(m,n) mod a very large prime No.
|
p*i
发帖数: 411 | 29 mod everywhere
like what is essential in cracking many of the interview street problems
【在 r****t 的大作中提到】
: 这个 mod 大素数又该怎么做呢？
:
: No.
|
r****t
发帖数: 10904 | 30 got u. Thanks! 经验之谈好！
interview street 听说难，想等基础学好了再做。
【在 p*i 的大作中提到】
: mod everywhere
: like what is essential in cracking many of the interview street problems
|
|
|
c*****e
发帖数: 737 | 31 想了一下，依旧有问题，可能提前溢出。
也就是答案在不溢出的情况下，你的计算过程中已经溢出了。
【在 c*********t 的大作中提到】
: 你没有看懂我的注释。
: C(n,1) = n/1
: C(n, 2) = C(n, 1) * (n-1)/2
: C(n, 3) = C(n, 2) * (n - 2) /3
: ,etc,......
|
t**i
发帖数: 314 | 32 增加一个步骤，a=min(n, m-n) 然后求C(m, a)
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 c*****e 的大作中提到】
: 想了一下，依旧有问题，可能提前溢出。
: 也就是答案在不溢出的情况下，你的计算过程中已经溢出了。
|
j****b
发帖数: 108 | 33 需要那么复杂么？我觉得还是dp就可以了啊
public static void main(String[] args) {
int n=600;
int m=3;
int c[][] = new int[n+1][m+1];
for(int i=0; i<=n; i++){
for(int j=0; j<=m; j++){
if(j==0)
c[i][j] = 1;
else if(i==j)
c[i][j] = 1;
}
}
for(int i=2; i<=n; i++){
for(int j=1; j<=m; j++){
c[i][j] = c[i-1][j] + c[i-1][j-1];
if(c[i][j]<0){
System.out.println("Overflow");
return;
}
}
}
System.out.println(c[n][m]);
} |
c*****e
发帖数: 737 | 34 这个似乎也会提前溢出。。。
【在 j****b 的大作中提到】
: 需要那么复杂么？我觉得还是dp就可以了啊
: public static void main(String[] args) {
: int n=600;
: int m=3;
: int c[][] = new int[n+1][m+1];
: for(int i=0; i<=n; i++){
: for(int j=0; j<=m; j++){
: if(j==0)
: c[i][j] = 1;
: else if(i==j)
|
c****p
发帖数: 6474 | 35 我的那个不溢出。但是比这个慢。
【在 c*****e 的大作中提到】
: 想了一下，依旧有问题，可能提前溢出。
: 也就是答案在不溢出的情况下，你的计算过程中已经溢出了。
|
c****p
发帖数: 6474 | 36 今天逛街的时候想了一下，可以这么改进：
每次运算的时候都是这样的形式：
old_result * k / j
如果 k % j == 0，那么 new_result = old_result * (k/j);
否则new_result = old_result / j * k;
【在 c*****e 的大作中提到】
: 想了一下，依旧有问题，可能提前溢出。
: 也就是答案在不溢出的情况下，你的计算过程中已经溢出了。
|
