锐客网

  1. 首页 > it技术 > >

组合数与二进制

题目描述 在组合数学中，我们学过排列数。从n个不同元素中取出m（m<=n）个元素的所有排列的个数，叫做从n中取m的排列数，记为p(n, m)。具体计算方法为p(n, m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)! (规定0!=1).当n和m不是很小时，这个排列数是比较大的数值，比如p(10,5)=30240。如果用二进制表示为p(10,5)=30240=( 111011000100000)b，也就是说，最后面有5个零。我们的问题就是，给定一个排列数，算出其二进制表示的后面有多少个连续的零。
输入描述:

输入包含多组测试数据，每组测试数据一行。 每行两个整数，n和m，0
输出描述:
对于每个输入，输出排列数p(n, m)的二进制表示后面有多少个连续的零。每个输出放在一行。

示例1
输入 复制
10 5 6 1 0 0

输出 复制
5 1

解题思路：1000！的阶乘是很大的，所以不能蛮干。二进制后面的0的个数是根据数中有几个能被2整除的因数，例如：7*6*5*4中6=2*3，4=2*2，有三个2，所以最终转换为二进制的时候就有3个0
#include int we(int n) { int p=0; while(n) { if(n%2==0) { p++; //记录有几个2 } else { break; } n=n/2; } return p; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=-1) { if(n==0) break; int cnt=0; for(int i=n; i>=n-m+1; i--) { cnt+=we(i); } printf("%d\n",cnt); } }

【组合数与二进制】

    推荐阅读


    上一篇：一句SQL实现MYSQL的递归查询

    下一篇：Flink Table & SQL AppendStreamTableSink、RetractStreamTableSink、UpsertStreamTableSink