[算法]问一道ACM练习题

soloforce

某君曾考我的一道ACM习题，今天偶然想起，试做了一下，也不知道对不对，向大家求证一下
题目很简单:
[color="Red"]求 12345678987654321! 这个超大整数末尾有几个0
注意，是求大整数的阶乘末尾的0的个数; 如 100! 的末尾有24个0

如果你觉得数字太大，那就求一下 123454321! 的末尾有几个0吧。关键是思路。



下面是我的答案：
12345678987654321!  末尾有 3086419746913569 个0
123454321! 末尾有 30863575 个0

DoDo

10=2*5
由于2的出现次数绝对比5多, 因此只要考查尾数为5及0的数, 计算它们的因子中5的数量
因此写出了如下的代码

2. #include <stdio.h>
4. int main(void)
5. {
6.         unsigned long int N = 123454321;
7.         printf("%d! has ", N);
8.         unsigned long int n = 0;
9.         unsigned long int i = 0;
10.         while (N > 5) {
11.                 n += N /= 5;
12.         }
13.         printf("%d zero at tail\n", n);
14.         return 0;
15. }

复制代码

它的计算时间

2. rf@RemoteFish:~/src/t$ time ./a.out
3. 123454321! has 30863575 zero at tail
5. real    0m0.002s
6. user    0m0.001s
7. sys     0m0.001s

复制代码

但是它还不能回答楼主的问题, 因为它不能处理 "大数", 因此又改出了下面的版本, 利用字符串进行计算

2. #include <stdio.h>
3. #include <string.h>
5. /*
6. * s / 5
7. * 如果结果位数减 1 则返回 1, 否则返回 0
8. */
9. int div(char s[], int n)
10. {
11.         int i = 0;
12.         int mod = 0;
13.         for (i = n - 1; i >= 0; i--) {
14.                 int t = s[i] + 10 * mod;
15.                 s[i] = t / 5;
16.                 mod = t % 5;
17.         }
18.         return s[n - 1] == 0;
19. }
21. /* d = d + s */
22. int add(char d[], int nd, char s[], int ns)
23. {
24.         int n = (nd < ns) ? nd : ns;
25.         int i;
26.         int x = 0;
27.         for (i = 0; i < n; i++) {
28.                 d[i] = d[i] + s[i] + x;
29.                 if (d[i] >= 10) {
30.                         d[i] -= 10;
31.                         x = 1;
32.                 } else x = 0;
33.         }
34.         if (nd > ns) {
35.                 while (1) {
36.                         d[i] = d[i] + x;
37.                         if (d[i] >= 10) d[i] -= 10;
38.                         else break;
39.                         i++;
40.                 }
41.                 if (i < nd) i = nd;
42.         } else {
43.                 for ( ; i < ns; i++) {
44.                         d[i] = s[i] + x;
45.                         if (d[i] >= 10) d[i] -= 10;
46.                         else break;
47.                 }
48.                 for ( ; i < ns; i++) {
49.                         d[i] = s[i];
50.                 }
51.         }
52.         return i;
53. }
55. int main(void)
56. {
57.         char buf[800] = "";
58.         char * src = buf;
59.         char res[100] = "";
60.         int src_len = 0;
61.         int res_len = 0;
62.         int i;
63.         memset(res, 0, sizeof(res));
65.         printf("input the number: ");
66.         scanf("%s", src);
67.         src_len = strlen(src);
69.         for (i = 0; i < (src_len + 1) / 2; i++) {
70.                 int t = src[i] - '0';
71.                 src[i] = src[src_len - i - 1] - '0';
72.                 src[src_len - i - 1] = t;
73.         }
75.         while ((src_len -= div(src, src_len)) > 0) {
76.                 res_len = add(res, res_len, src, src_len);
77.         }
79.         for (i = res_len - 1; i >= 0; i--) {
80.                 printf("%d", res[i]);
81.         }
82.         printf("\n");
83.         return 0;
84. }

复制代码

它的计算时间

2. rf@RemoteFish:~/src/t$ time ./a.out
3. input the number: 12345678987654321
4. 3086419746913569
6. real    0m7.257s
7. user    0m0.002s
8. sys     0m0.000s

复制代码

其中输入数据花了一点时间, 真正的计算时间是 user 部分

写的不好, 大家见笑了

DoDo

为了考查它的计算能力, 我又试了一个更大一点的数, 如下. 求证. 不知原题的数据规模及时间要求为多大

2. rf@RemoteFish:~/src/t$ time ./a.out
3. input the number: 1234567890987654321234567890987654321234567890987654321
4. 308641972746913580308641972746913580308641972746913541
6. real    0m19.097s
7. user    0m0.001s
8. sys     0m0.002s

复制代码

soloforce

DoDo兄强！l
我的思路也是这样的，看因子5的数量。
原题的规模就是 12345678987654321! ， 时间要求记得是0.1s, 看来根本不需要那么长呢

DoDo

呵呵, 自从上了大学就再未做过这类题了, 昨天看到此题, 马上就勾起了我的兴趣, 可惜花了好久才做完, 而且还没有进行严格的测试. 看来脑子长时间不用果然就生锈了

本版块虽然人气不旺, 但偶有帖子却大都是值得仔细研究和思考的.
毕竟一个论坛的价值不是只在于人气的, 呵呵

stylev

算法一：

#include <stdio.h>
#include <stdlib.h>

/*题目：求n！中末尾含有多少个0


*提示：
*采用从1乘到n，每乘一个数判断一次，若后面有0则去掉后面的0，并记下去掉的0的个数。
*我们是求后面的0的个数，与前面一些数无关，为了不超出数的表示范围，去掉前面与0无
*关的数，只保留2位有效数，当乘完n次后就得到0的个数。
*/

int main()
{
  int n,i,product=1,count=0;
  printf("请输入n！算式中n的值：");
  scanf("%d",&n);
  
  for(i=1;i<=n;i++){
      product*=i;                    //1*2*3……*n
      while(product%10==0){
            count++;                 //计算0的个数
            product/=10;           
      }                              //这里会遇到有多个0的情况，比如：24*25 。
      product%=100;
  }
  printf("结果有%d个0。\n",count);
  
  system("AUSE");   
  return 0;
}
//////////////////////////////////////////////////////////////////
算法二：
#include <stdio.h>
#include <stdlib.h>

/*题目：求n！中末尾含有多少个0


*提示：
*第一种方法能得到正确的结果，可是运行的次数太多了，
*在1×2×3×...×n这些数中有些与生成0无关的数（如3、7、9、13等）可以不考虑进去，
*其实影响生成0的数只有2的倍数和5的倍数，如在1到9这些数中只有2×5，4×5，6×5，8×5，这些数能生成0，
*从这些数中我们还可以看出，真正影响生成0的是5的倍数，这些数的分解数含2的数显然多于含5的数，
*因此我们可以得出这样一个结论：n！的分解数中有多少个5，末尾就有多少个0。
*这样就可以使外面的大循环的次数减少五分之四。
*/

int main()
{
  int n,i,num,count=0;
  printf("请输入n！算式中n的值：");
  scanf("%d",&n);
  
  for(i=5;i<=n;i=i+5){
      count++;               
      num=i/5;                  
      while(num%5==0){
            count++;
            num/=5;
      }                          //处理5*5的数
  }
  
  printf("结果有%d个0。\n",count);
  
  system("AUSE");   
  return 0;
}
//////////////////////////////////////////////////////////////////
算法三：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/*题目：求n！中末尾含有多少个0


*提示：
*第二种方法是把含5的数转变成含0的数，再求0的个数，
*我们已经知道n！的分解数中有多少个5就有多少个0，我们可不可以直接求5的个数呢？答案是肯定的。
*这种方法就是根据含5的个数求0的个数，用层层剥皮法。
*先以5为步长，执行一次循环，进行第一次剥皮，求出含5的个数（个数为n/5取整），
*通过第一次剥皮5，10，15，20，25，30...变成1，2，3，4，5，6...
*再以5 2为步长，执行第二次循环，进行第二次剥皮，求出含5 2的个数（个数为n/25取整），
*在第一次剥皮后25，50，75，100，125，150……这些数变成5，10，15，20，25，30……
*再经过第二次剥皮就变成1，2，3，4，5，6……再以5 3为步长……直到步长大于或等于n退出循环。
*/

int main()
{
  int n,i,step,count=0;
  printf("请输入n！算式中n的值：");
  scanf("%d",&n);
  
  for(step=1;step<=n;step++){
      if(pow(5,step)>n)break;
      for(i=pow(5,step);i<=n;i=i+pow(5,step)){
            count++;
      }
  }
  
  printf("结果有%d个0。\n",count);
  
  system("AUSE");   
  return 0;
}

DoDo

stylev 兄的思想是正确的, 但是算法的优化还不足, 而且以 C 固有数据类型是无法保存题目中的大数及其结果的

另外, stylev 兄是用 Dev-Cpp 的吧

earth

昨晚做了一下，由于考虑不周全，先删之，以免误导大家

earth

1. #include <stdio.h>
2. #include <math.h>
3. int main(void)
4. {
5. unsigned char sdata[800];
6. long data[100]={0};
7. int str_len=0,dat_len=0,sum_len;
8. int i,j;
9. printf("Please enter the data:");
10. scanf("%s",&sdata);
11. printf("\n");
12. str_len=strlen(sdata);
13. dat_len=((str_len/8)*8==str_len)?(str_len/8):(str_len/8+1);
14. for(i=0;i<dat_len;i++)
15.         {int tmp;
16.         tmp=str_len-i*8-1;
17.         for(j=0;j<8;j++)
18.                 {if(tmp-j<0) break;
19.                 data[i]+=(sdata[tmp-j]-'0')*pow(10,j);
20.                 }
21.         }
22. long sum[100]={0};
23. while(dat_len>0)
24.         {dat_len=div(data,dat_len);
25.         add(data,sum,dat_len);
26.         }
27. sum_len=1;
28. for(i=99;i>0;i--)
29.         if(sum[i]>0)
30.                 {sum_len=i+1;
31.                 break;
32.                 }
33. printf("There are ");
34. printarray(sum,sum_len);
35. printf(" zeros at the end\n");
36. return 1;
37. }
38. void add(long data[], long sum[],int dat_len)
39. {
40. int i;
41. for(i=0;i<dat_len;i++)
42.         {int tmp1,tmp2;
43.         tmp1=data[i]+sum[i];
44.         tmp2=tmp1/100000000;
45.         sum[i+1]+=tmp2;
46.         sum[i]=tmp1-tmp2*100000000;
47.         }
48. }
50. int div(long data[],int dat_len)
51. {int i;
52. for(i=dat_len-1;i>0;i--)
53.         {int tmp;
54.         tmp=data[i]/5;
55.         data[i-1]+=(data[i]-tmp*5)*100000000;
56.         data[i]=tmp;
57.         }
58. data[0]=data[0]/5;
59. if(data[dat_len-1]==0) return (dat_len-1);
60. else
61. return dat_len;
62. }
64. void printarray(long data[],int dat_len)
65. {if(dat_len==1) printf("%ld",data[0]);
66. else
67.         {printf("%ld",data[dat_len-1]);
68.         int i;
69.         for(i=dat_len-2;i>=0;i--) printf("%08ld",data[i]);
70.         }
71. }

复制代码

1. [earth@localhost programming]$ gcc -o acm2 acm2.c -lm
2. acm2.c: 在函数 ‘main’ 中：
3. acm2.c:13: 警告：隐式声明与内建函数 ‘strlen’ 不兼容
4. acm2.c: 在顶层：
5. acm2.c:40: 警告：与 ‘add’ 类型冲突
6. acm2.c:26: 警告：‘add’ 的上一个隐式声明在此
7. acm2.c:66: 警告：与 ‘printarray’ 类型冲突
8. acm2.c:35: 警告：‘printarray’ 的上一个隐式声明在此
9. [earth@localhost programming]$ time ./acm2
10. Please enter the data:12345678987654321
12. There are 3086419746913569 zeros at the end
14. real    0m8.403s
15. user    0m0.000s
16. sys     0m0.000s
17. [earth@localhost programming]$ time ./acm2
18. Please enter the data:123456789009998776662134871264891249126419236417937187171972318919619834796378197391274211341481842189318528319461783468129743913193741294713412487186518932
20. There are 30864197252499694165533717816222812281604809104484296792993079729904958699094549347818552835370460547329632079865445867032435978298435323678353121796629625 zeros at the end
22. real    0m18.337s
23. user    0m0.000s
24. sys     0m0.000s

复制代码

zhenghj1024

其实只要实现了长整数运算，这题满简单的

随手写的scheme代码：

1. 
   
2. (define (num-of-zero n)
   
3.   (let ((num (floor (/ n 5))))
   
4.   (if (< num 1)
   
5.       0
   
6.       (+ num (num-of-zero num)))))
   

复制代码