100的阶层真的算不出来吗?

2015/09/08 21:45
阅读数 8

今天看到一个蛮有意思的题,是问“100!”的尾数有多少个零。

尾数有多少个零,实际上指的是从这个数的最后一个不为0的数的下一个(也就是0)开始计数,一直到最后一个数(这些数自然都是0)有多少个0。

好吧,也就是说13330330000的尾数有4个零……

一个整数若含有因子5,则必然在求解100!时产生一个0,也就是说我们从5开始for循环,每次循环都给加上5,然后计数器加1。同时如果该整数还能被25整除,计数器还应该再加上1。(关于这段话的详细解释请看下文)

因此代码如下:

#include<stdio.h>

int main()
{
    int a,count =0;
    for(a=5;a<=100;a+=5)
    {
        ++count;
        if(!(a%25))
            ++count;
    }
    printf("100!的尾数有%d个零。\n",count);
    return 0;
}

题目后面进一步问了如何求出任意N!的尾数有多少个零。

#include<stdio.h>

int main()
{
    int n;
    printf("请输入N:\n");
    scanf("%d",&n);
    if(n<0)
        printf("%d的阶层无意义。\n",n);
    else if(n<=4)
        printf("%d的阶层的尾数没有零。\n");
    else
    {
        int a,count =0;
        for(a=5;a<=n;a+=5)
        {
            ++count;
            if(!(a%25))
                ++count;
        }
        printf("100!的尾数有%d个零。\n",count);
    }
    return 0;
}

本文就这样结束了吗?

题目的解答中有这么一段话:先求出100!的值,然后数一下末尾有多少个零。事实上,由于计算机所能表示的整数范围有限,这是不可能的。

首先,什么叫计算机所能表示的整数范围?应该叫int等数据类型的整数范围有限才对,计算机嘛……撑死了只能说不能存储而非不能表示。

另外100的阶层真的求不出来吗?请往下读。

我的博客中有大量关于Lisp,或者说Scheme的博文,使用这个语言,几行代码就能搞定了不是吗?欢迎阅读我的其他博文……

(define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))
;Value: fact

1000的阶层也能求,截图为证……

这里写图片描述

闲得无聊,以下是10000的阶层,大家可以继续算更大的数,哈哈……

………………

我发现这个CSDN博客写上这么多数字之后博客没法提交,有异常……没办法,只能上传了……下载后觉得有意思记得回来点赞哦……

传送门:10000的阶层

有网友私信问我,为什么一个整数若含有因子5,则必然在求解100!时产生一个0。这里所说的一个整数,自然是在求100的阶层时需要计算的从1到100这些整数。我下列出一些等式:

1x2=2 2x3=6 6x4=24 24x5=120 120x6=720 720x7=5040 5040x8=40320 40320x9=362880 362880x10=3628800 3628800x11=39916800 3991680x12=479001600 47900160x13=6227020800 622702080x14=87178291200 8717829120x15=1307674368000 …… ……

看到上式就会发现每次尾部增加0都是因为成了一个因子是5的整数。那么一直乘到100都会是这样吗?当然是。但这样就能证明?显然不能。

我们来看看各个整数的最后一个数:

如果是0的话,也就是说是乘以10或者20、30之类的,那么肯定会加上一个0。而且它也是5的倍数。

如果是1的话,无论乘以谁显然都不可能得到10。(这里的谁是指的的上面那些式子中的乘号左边的数的最后一个不为0的数。

如果是2的话,乘以5会得到10。

如果是4、6、8的话乘以5也会得到10。

如果是3、7、9的话就和1一样不会得到10。(得不到10也就无法增加一个0)

那么为什么是5而不是2、4、6、8呢?因为对于任何一个大于1的数的阶层而言,它的最后一个不为0的数必然是偶数。这又是为什么呢?因为最起码一开始就成了2,结果变成了偶数,而偶数乘以偶数为偶数,偶数乘奇数还是偶数…… 而2、4、6、8都必须和5相乘才可以得到10,以至于增加一个0。

那么5呢?5乘以任意一个偶数不都可以增加一个0吗,比如所10、20、30、40等等。

那么这个问题就得到了较为具体的解答。该网友还问了,为什么一个整数有25的因子,就需要计数再加1呢,很显然25是两个5的乘积呀。那么又为什么不考虑5的三次方也就是125呢?因为我们只乘到了100呀,100的阶层嘛。

如果不信我们就来验算一下呗……

#include<stdio.h>

int main()
{
    int a,count =0;
    for(a=5;a<=200;a+=5)
    {
        ++count;
        if(!(a%25))
        {
            ++count;
            if(!(a%125))
                ++count;
        }

    }
    printf("200!的尾数有%d个零。\n",count);
    return 0;
}

还有截图为证哦……

这里写图片描述

后来还看到一个题目,和这个也类似,需要求的是100的阶层的结果的数字中从左到右第一个四位的质数。

代码来源于网络以及别人的解答,感觉这里还是蛮巧妙地。

// C# Code
    public static class Program
    {
        public static void Main(string[] args)
        {
            string fac100 = Factorial(100).ToString("F0");
            Console.WriteLine("The factorial of 100 is : {0}", fac100);

            for (int i = 0; i <= fac100.Length - 4; i++)
            {
                string substr = fac100.Substring(i, 4);
                if (CheckPrime(Convert.ToInt32(substr)))
                {
                    Console.WriteLine("The expected result found and it is : " + substr);
                    return;
                }
            }       
            Console.WriteLine("No result as expected!!");
        }

        public static double Factorial(int n)
        {
            double result = 1;
            for (int i = 1; i <= n; i++)        
                result *= i;    
            return result;
        }                   

        public static bool CheckPrime(int n)
        {
            if (n == 1 || n == 2)           
                return true;        
            int squareRoot = Convert.ToInt32(Math.Sqrt(n));
            for (int i = squareRoot; i > 1; i--)                   
                if (n % i == 0)                           
                    return false;     
            return true;
        }
    }
// C++ Code
#include <iostream>
#include <math.h>
using namespace std;

double Factorial(int n)
{
    double result = 1;
    for (int i = 1; i <= n; i++)
        result *= i;
    return result;
}

bool CheckPrime(long n)
{
    if (n == 1 || n == 2)
        return true;
    long squareRoot = (long)sqrt(n);
    for (long i = squareRoot; i > 1; i--)
        if (n % i == 0)
        return false;
    return true;
}

int main(int argc, char *argv[])
{
    char buf[1024] = { '\0' };
    sprintf_s(buf, "%.f", Factorial(100));
    cout << "The factorial of 100 is : " << buf << endl;

    char substr[5] = { '\0' };
    for (int i = 0; i <= strlen(buf) - 4; i++)
    {
        memcpy(substr, buf + i, 4);
        if (CheckPrime(atol(substr)))
        {
            cout << "The expected result found and it is : " << substr << endl;
            return 0;
        }
    }
    cout << "No result as expected!!";
    return 0;
}
// C Code
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

double Factorial(int n)
{
    double result = 1;
    int i;
    for (i = 1; i <= n; i++)
        result *= i;
    return result;
}

bool CheckPrime(long n)
{
    if (n == 1 || n == 2)
        return true;
    long squareRoot = (long)sqrt(n);
    long i;
    for (i = squareRoot; i > 1; i--)
        if (n % i == 0)
        return false;
    return true;
}

int main(int argc, char *argv[])
{
    char buf[1024] = { '\0' };
    sprintf(buf, "%.f", Factorial(100));
    printf("The factorial of 100 is : %s\n",buf);

    char substr[5] = { '\0' };
    int i;
    for (i = 0; i <= strlen(buf) - 4; i++)
    {
        memcpy(substr, buf + i, 4);
        if (CheckPrime(atol(substr)))
        {
            printf("The expected result found and it is : %s\n",substr);
            return 0;
        }
    }
    printf("No result as expected!!\n");
    return 0;
}


欢迎大家点击左上角的“关注”或右上角的“收藏”方便以后阅读。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp

版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

展开阅读全文
打赏
0
0 收藏
分享
加载中
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部