求高手解决下列问题，用C语言实现！

2025-02-26 23:46:29

推荐回答（2个）

回答1：

#include
#include
#include
long fun(long n)
{
long m=1;
if(n==0) return 1;
while(n>0)
{
m*=n;
n--;
}
return m;
}
void main()
{
long i,j,m[100],n[100],num=0,k,len;
char str[200];
printf("请输入n m的值(0 0表示结束)：\n");
while(1)
{
scanf("%ld%ld",&n[num],&m[num]);
if(n[num]==0) break;
if(m[num]>n[num])
{
i=m[num];
m[num]=n[num];
n[num]=i;
}
num++;
}
for(i=0;i {
k=fun(n[i])/fun(n[i]-m[i]);
ltoa(k, str, 2);
len=strlen(str);
k=0;
for(j=len-1;j>0;j--)
if(str[j]=='0') k++;
else break;
printf("%d\n",k);
}
}

回答2：

#include 
 
int f(int n) {
    int count = 0;
    while (n) {
        count += n /= 2;
    }
    return count;
}
 
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m), n | m) {
        printf("%d\n", f(n) - f(n - m));
    }
    return 0;
}

　　以上是我见过的最优算法实现。下面是解释：

　　阶乘n!（1<=n<=1000000）用不同进制表示时末尾0的个数：由于阶乘增长得很快，故不能用直接相乘的方法求得。若用大整数相乘的方法，也不太行，因为时间复杂度太高。这里给出了一种方法，可以通过如下原理反复的除以5（对于十进制数来说是5）得到最后的结果：

　　原理是：

　　假如你把1×2×3×4×……×N中每一个因数分解质因数，结果就像：

　　1 × 2 ×3 × (2 × 2) × 5 × (2 × 3)× 7 × (2 × 2 ×2) ×……

　　10进制数结尾的每一个0都表示有一个因数10存在——任何进制都一样，对于一个M进制的数，让结尾多一个0就等价于乘以M。

　　10可以分解为2 × 5——因此只有质数2和5相乘能产生0，别的任何两个质数相乘都不能产生0，而且2，5相乘只产生一个0。

　　所以，分解后的整个因数式中有多少对(2, 5)，结果中就有多少个0，而分解的结果中，2的个数显然是多于5的，因此，有多少个5，就有多少个(2, 5)对。

　　所以，讨论1000的阶乘结尾有几个0的问题，就被转换成了1到1000所有这些数的质因数分解式有多少个5的问题。

　　同理，对于2进制，有多少个2，就有多少个0。

　　固有如下代码：

for(i = 1; i <= n; i++)  
{  
    int num = 0;temp = i;  
    while(temp % 5 ==0)  
    {  
        num++;  
        temp /= 5;  
    }  
}

　　评价一下这个代码，这个肯定是不要从1开始循环的，只有5的倍数才能够被5整除，所以，所以修改后如下：

int numOfZero(int n)  
{  
    int num = 0, i, temp;  
    for(i=5; i<=n; i+=5)  
    {  
        temp = i;  
        while(0 == temp%5)  
        {  
            temp /= 5;  
            num++;  
        }  
    }  
    return num;  
}

　　可不要小看这个改动，如果是10亿次运算，立马降低到2亿。显然，这个还是不符合OJ上的时间要求。要运行2亿次。肯定超时。所以还需要改进。把时间复杂度降下来！

　　下面是《编程之美》一书上的第二种思路：

　　公式：Z = [N/5] +[N/5^2] +[N/5^3] + …（不用担心这会是一个无穷的运算，因为总存在一个K，使得5^K > N，[N/5^K]=0。）

　　公式中，[N/5]表示不大于N 的数中5 的倍数贡献一个5，[N/5^2]表示不大于N 的数中5^2的倍数再贡献一个5，……下面是代码：

int numOfZero(int n)  
{  
    int num = 0, i;  
    for(i=5; i<=n; i*=5)  
    {  
        num += n/i;  
    }  
    return num;  
}

OK，到此结束。

最新问答

作烤瓷牙，钛合金的，一般多少钱一颗

今天孩子放心回来就有点流鼻涕，是感冒了吗，宝宝感冒用药该怎么选择呢，亲们有推荐的吗

胃病会变癌吗？

怪坡现象是为什么？

吴奇隆这种头发怎么弄？

王蓉的新歌“好乐day”为什么遭到网友们一顿恶批？

《铁血战士2018》到底烂到什么程度，我们还得这样来说！

你为什么说谎谁会唱啊唱给我听听吧 ~ 高潮部分我确实hold不住 - -

我男朋友是穆斯林，阿拉伯人，如果我不加入穆斯林而和他结婚，婚后会有什么坏影响？

嘴唇厚大怎么变薄，