求二项式因子的算法

Dear 丶 2022-07-12 12:36 150阅读 0赞

组合数C(n, k)的求法:

1. 浮点数迭代法

缺点: 当数比较大的时候, 可能结构不够精确.

使用公式

![$$\{n+1/choose k+1\} = \{n+1/over k+1\}\{n/choose k\}$$][n_1_choose k_1_ _ _n_1_over k_1_n_choose k]

\#include <iostream> using namespace std; int main() \{ long double n, k, ans; while(cin >> n >> k && (n || k))\{ ans = 1; if(k > n/2) k = n - k; for(long double i=0; i<k; i++) ans \*= (n-i)/(k-i); cout.precision(0); cout << fixed << ans << endl; \} \}

或:

\#include <iostream> using namespace std; \_\_int64 c(\_\_int64 n, \_\_int64 k) \{ if(k == 0 || n==k) return 1; else return c(n-1, k-1)\*n/k; \} int main() \{ \_\_int64 n,k; while (scanf("%I64d%I64d", &n, &k)!=EOF && (n+k)) \{ if(2\*k > n) k = n-k; printf("%I64d/n", c(n,k)); \} return 0; \}

2. 动态规划法

缺点: 对空间有较大的要求.

具体为:

<table>                            
 <tbody> 
  <tr> 
   <td align="CENTER"><em>n</em></td> 
   <td align="CENTER"><img src="http://www.brpreiss.com/books/opus4/html/img1956.gif" alt="tex2html_wrap_inline69039" width="18" height="27" align="MIDDLE"></td> 
   <td align="CENTER"><img src="http://www.brpreiss.com/books/opus4/html/img1957.gif" alt="tex2html_wrap_inline69041" width="19" height="27" align="MIDDLE"></td> 
   <td align="CENTER"><img src="http://www.brpreiss.com/books/opus4/html/img1958.gif" alt="tex2html_wrap_inline69043" width="18" height="27" align="MIDDLE"></td> 
   <td align="CENTER"><img src="http://www.brpreiss.com/books/opus4/html/img1959.gif" alt="tex2html_wrap_inline69045" width="19" height="27" align="MIDDLE"></td> 
   <td align="CENTER"><img src="http://www.brpreiss.com/books/opus4/html/img1960.gif" alt="tex2html_wrap_inline69047" width="18" height="27" align="MIDDLE"></td> 
   <td align="CENTER"><img src="http://www.brpreiss.com/books/opus4/html/img1961.gif" alt="tex2html_wrap_inline69049" width="19" height="27" align="MIDDLE"></td> 
   <td align="CENTER"><img src="http://www.brpreiss.com/books/opus4/html/img1962.gif" alt="tex2html_wrap_inline69051" width="18" height="27" align="MIDDLE"></td> 
   <td align="CENTER"><img src="http://www.brpreiss.com/books/opus4/html/img1963.gif" alt="tex2html_wrap_inline69053" width="19" height="27" align="MIDDLE"></td> 
  </tr> 
 </tbody> 
 <tbody> 
  <tr> 
   <td align="CENTER">0</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
  </tr> 
  <tr> 
   <td align="CENTER">1</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
  </tr> 
  <tr> 
   <td align="CENTER">2</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">2</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
  </tr> 
  <tr> 
   <td align="CENTER">3</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">3</td> 
   <td align="CENTER">3</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
  </tr> 
  <tr> 
   <td align="CENTER">4</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">4</td> 
   <td align="CENTER">6</td> 
   <td align="CENTER">4</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
  </tr> 
  <tr> 
   <td align="CENTER">5</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">5</td> 
   <td align="CENTER">10</td> 
   <td align="CENTER">10</td> 
   <td align="CENTER">5</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">&nbsp;</td> 
   <td align="CENTER">&nbsp;</td> 
  </tr> 
  <tr> 
   <td align="CENTER">6</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">6</td> 
   <td align="CENTER">15</td> 
   <td align="CENTER">20</td> 
   <td align="CENTER">15</td> 
   <td align="CENTER">6</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">&nbsp;</td> 
  </tr> 
  <tr> 
   <td align="CENTER">7</td> 
   <td align="CENTER">1</td> 
   <td align="CENTER">7</td> 
   <td align="CENTER">21</td> 
   <td align="CENTER">35</td> 
   <td align="CENTER">35</td> 
   <td align="CENTER">21</td> 
   <td align="CENTER">7</td> 
   <td align="CENTER">1</td> 
  </tr> 
 </tbody>  
 <p><strong>Table:</strong>&nbsp;Pascal's Triangle</p>  
</table>

\#define MAXSIZE 10000 long cnr(int n, int r) \{ long c\[MAXSIZE\]; int i, j; for (i = 0; i <= r; i++) c\[i\] = 1; for (i = 1; i <= n-r; i++) for (j = 1; j <= r; j++) c\[j\] += c\[j-1\]; return c\[r\]; \}

3.快速算法

还有一种快速算法, 在<<C语言名题精选百则>>上有所叙述.

下面展示一道题:

pku 3219 Binomial Coefficients

求C(n, k)的最后一位是0，还是1(即结果是奇数还是偶数).

这道题采用一步一步的优化的演示方法.

可以注意到k<=n<2^31, k,n如此之大, 肯定不能用上面的方法, 也不必用, 因为他只需要知道结构是奇数还是偶数.

那判断C(n,k) = A(n,k)/A(k,k)的分母分子个含有2这个因子的个数的多少,相减即可.

\#include <iostream> using namespace std; //方法一: //利用c(n, k) = c(n-1,k-1)+c(n-1,k)的原始方法 //int c(int n, int k) //\{ // if(k==0 || n==k) // return 1; // else // return (c(n-1,k-1)+c(n-1,k))&1; //\} //奇(1)\*奇(1)=奇(1), 偶(0)\*奇(1)=偶(0), 偶(0)\*偶(0)=偶(0) \[求积为&\] //奇(1)+奇(1)=偶(0), 偶(0)+奇(1)=奇(1), 偶(0)+偶(0)=偶(0) \[求和为^\] //方法二: //利用c(n, k) = ∑c(k,i)\*c(n-k, i) (i∈\[0, k\], 且n>=2\*k)的快速求组合数算法 //int c(int n, int k) //\{ // if(k == 0 || k == n) // return 1; // // if(2\*k > n) // k = n-k; // int ret = 1; // for(int i = 1; i <= k; ++i) // ret ^= c(k, i)&c(n-k, i); // return ret; //\} //方法三: //利用C(n,k) = A(n,k)/A(k,k), 求分子和分母因子2的个数的方法. int cal(int n) \{ int cnt = 0; int c = 2; while(n) \{ n >>= 1; cnt += n; \} return cnt; \} int main() \{ unsigned int n, k; while(scanf("%d%d", &n, &k) != EOF) \{ if(k == 0 || n == k) \{ printf("1/n"); continue; \} if(2\*k > n) k = n-k; int cnt1 = cal(n); int cnt2 = cal(n-k); int cnt3 = cal(k); printf("%d/n", (cnt1-cnt2)>cnt3?0:1); \} return 0; \}

[n_1_choose k_1_ _ _n_1_over k_1_n_choose k]: /images/20220712/2bb3e4d3b23f40b583002a2693cced7f.png