[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖

批处理脚本实现C语言趣味编程百例007:阶乘尾数零的个数

要求用BAT脚本实现:100!的尾数有多少个零

加分:1个技术分或者10个PB

*问题分析与算法设计
    可以设想:先求出100!的值,然后数一下末尾有多少个零。事实上,与上题一样,由于计算机所能表示的整数范围有限,这是不可能的。
    为了解决这个问题,必须首先从数学上分析在100!结果值的末尾产生零的条件。不难看出:一个整数若含有一个因子5,则必然会在求100!时产生一个零。因此问题转化为求1到100这100个整数中包含了多少个因子5。若整数N能被25整除,则N包含2个因子5;若整数N能被5整除,则N包含1个因子5。

*程序说明与注释
  1. #include<stdio.h>
  2. int main()
  3. {
  4. int a,count =0;
  5. for(a=5;a<=100;a+=5) //循环从5开始,以5的倍数为步长,考察整数
  6. {
  7. ++count; //若为5的倍数,计数器加1
  8. if(!(a%25)) ++count; //若为25的倍数,计数器再加1
  9. }
  10. printf("The number of 0 in the end of 100! is: %d.\n",count); //打印结果
  11. return 0;
  12. }
复制代码
*运行结果
The number of 0 in the end of 100! is: 24.

*问题进一步讨论

本题的求解程序是正确的,但是存在明显的缺点。程序中判断整数N包含多少个因子5的方法是与程序中的100有关的,若题目中的100改为1000,则就要修改程序中求因子5的数目的算法了。

*思考题

修改程序中求因子5的数目的算法,使程序可以求出任意N!的末尾有多少个零。

本帖最后由 CrLf 于 2012-3-7 03:04 编辑
  1. @echo off
  2. set max=100
  3. :lp
  4. set /a "num+=(max/=5)"
  5. if %max% neq 0 goto lp
  6. echo %num%
  7. pause
复制代码
写完后发现三人思路竟不谋而合...

TOP

  1. @echo off
  2. set /a N=100,M=N
  3. :LP
  4. SET /A M/=5,T+=M
  5. IF %M% EQU 0 (ECHO %T%)ELSE GOTO :LP
  6. pause
复制代码

TOP

本帖最后由 plp626 于 2012-3-5 22:01 编辑
  1. @echo off
  2. call:f 10000 ans
  3. set ans
  4. pause
  5. :f <int> <ret> //求%1阶乘尾数的零个数;f(n)=f(n/5)+n/5;f([1,4])=0
  6. set/a #1=%1
  7. if %#1%==0 (set %2=0)else call:f %1/5 %2&set/a %2+=%1/5
复制代码

TOP

当0 < n < 5时,f(n!) = 0;
当n >= 5时,f(n!) = k + f(k!), 其中 k = n / 5(取整)

算法题
http://www.chinaunix.net/jh/23/926848.html

TOP

返回列表