Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1541034
  • 博文数量: 327
  • 博客积分: 10000
  • 博客等级: 上将
  • 技术积分: 3556
  • 用 户 组: 普通用户
  • 注册时间: 2005-04-05 21:28
个人简介

东黑布衣,流浪幽燕。 真诚善良,值得信赖。

文章分类

全部博文(327)

我的朋友

分类: BSD

2018-02-06 22:12:49




  1. // 172fact_trail_zero.cpp

  2. #include "stdafx.h"
  3. #include <stdio.h>
  4. #include <time.h>
  5. #include <windows.h>
  6. /*
  7.  = a*10^k = a* (5^k*2^k)
  8. */

  9. int trailingZeroes0(int n)
  10. {
  11.    int sum=0;
  12.    int i;
  13.    for(i=1;i<=n;i++){
  14.       int x=i;
  15.       while(x%5==0){
  16.          x/=5;
  17.          sum++;
  18.       }
  19.    }
  20.    return sum;
  21. }


  22. int trailingZeroes1(int n)
  23. {
  24.    int sum=0;
  25.    int i;
  26.    for(i=5;i<=n;i+=5){
  27.       int x=i;
  28.       while(x%5==0){
  29.          x/=5;
  30.          sum++;
  31.       }
  32.    }
  33.    return sum;
  34. }
  35. /*
  36. 5 10 15 20 25 30 35 小于等于35的数当中有多少5的倍数? 答案是35/5 = 7
  37. 1 2 3 4 5 6 7
  38. */
  39. int trailingZeroes2(int n)
  40. {
  41.    int sum=0;
  42.    int i;
  43.    while(n>0){
  44.       sum+=n/5;
  45.       n/=5;
  46.    }
  47.    return sum;
  48. }

  49. int trailingZeroes3(int n)
  50. {
  51.    return n == 0 ? 0 : n / 5 + trailingZeroes3(n / 5);
  52. }

  53. int main(int argc, char* argv[])
  54. {
  55.    int n;
  56.    int oput;
  57.    int t;
  58.    scanf("%d",&n);
  59.    do{
  60.       t=GetTickCount();
  61.       oput=trailingZeroes0(n);
  62.       t=GetTickCount()-t;
  63.       printf("0st func time %dms, Trailing zeroes is %d\n",t,oput);
  64.       t=GetTickCount();
  65.       oput=trailingZeroes1(n);
  66.       t=GetTickCount()-t;
  67.       printf("1st func time %dms, Trailing zeroes is %d\n",t,oput);
  68.       t=GetTickCount();
  69.       oput=trailingZeroes2(n);
  70.       t=GetTickCount()-t;
  71.       printf("2nd func time %dms, Trailing zeroes is %d\n",t,oput);
  72.       t=GetTickCount();
  73.       oput=trailingZeroes3(n);
  74.       t=GetTickCount()-t;
  75.       printf("3nd func time %dms, Trailing zeroes is %d\n",t,oput);
  76.       scanf("%d",&n);
  77.    }while(n!=0);
  78.    return 0;
  79. }

  80. /*
  81. 1808548329
  82. 10
  83. */

1999999999
0st func time 9812ms, Trailing zeroes is 499999988
1st func time 4321ms, Trailing zeroes is 499999988
2nd func time 0ms, Trailing zeroes is 499999988
3nd func time 0ms, Trailing zeroes is 499999988









阅读(1328) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~