[語法] 自己寫的計算Cn取m 在奇怪的地方會出錯

看板C_and_CPP作者tw00088437 (喵貓 loves fish)時間16年前 (2009/11/07 19:33)推噓1(1推 0噓 9→)

留言10則, 4人參與討論串1/2 (看更多)

要求是輸入n,m 輸出Cn取m(組合) 且答案在long long的範圍內我是寫了三個函式第一個(common)先找出最大公因數第二個(meowth)利用common把(n-m+1)/m化簡為最簡分數然後正式計算的第三個函式CNM用recursion ( C(n,m)=C(n,m-1)*(n-m+1)/m) 因為先把n-m+1和m化簡過了所以先除在乘既不會爆也不會有小數對於大部分的數都成功了例如 100 things taken 6 at a time is 1192052400 exactly. 18 things taken 6 at a time is 18564 exactly. 可是像 20 things taken 5 at a time is 48 exactly. (正確應該是15504) 出來就是錯的不知道為什麼會有些對有些錯@@ 或許是我pass by reference用的不熟? code如下#include<iostream> using namespace std; unsigned long long c,d; void meowth(int *,int *); int common(int,int); long long CNM(int,int); int main() { while(cin>>c>>d) { if(c==0&&d==0) break; cout<<c<<" things taken "<<d<<" at a time is "<<CNM(c,d)<<" exactly."<<endl; } return 0; } void meowth(int * a,int *b) { int e=common(*a,*b); *a/=e; *b/=e; } int common(int c,int d) { while((c%=d) && (d%=c)); return c+d; } long long CNM(int e,int f) { if(f<=e/2) { if(f==0) return 1; else { int x=e-f+1; meowth(&x,&f); return (CNM(e,f-1)/f*x); } } else { if(f==e) return 1; else { int y=f+1; int z=e-f; meowth(&y,&z); return (CNM(e,f+1)/z*y); } } } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.104.180

→

hilorrk

11/07 20:56, , 1^F

11/07 20:56, 1^F

→

bleed1979

11/07 21:12, , 2^F

11/07 21:12, 2^F

→

tw00088437

11/07 21:17, , 3^F

11/07 21:17, 3^F