mathe 发表于 2009-3-4 18:01:53

我觉得直接10进制转2进制已经不错了

无心人 发表于 2009-3-4 18:04:55

:)

那这个帖子也可以结束了
呵呵

我想，算法就是先得到10进制末尾的0
10移位去掉0

再根据进制测试末位的2的幂次

如果达到最大，再考虑2移位测试

没有则直接结束

gxqcn 发表于 2009-3-4 20:40:42

谢谢大家。

其实我当前能想到的算法也是大家所说的，
把这个问题抛出来，只是想看看是否还存在特别精妙的算法。

把一个大整数转化成二进制形式是很快的，
也就是说当前的算法 getMax2Exp 是可行的，
但若求 getMax5Exp 呢？

即：如何快速计算一个大整数最多可被5的多少次方整除？

无心人 发表于 2009-3-5 08:32:33

也是我说的思路吧

先根据末尾确定一个幂

再根据最后若干位确定小幂次
一旦达到最大幂次
比如8或者9
再测试高位

无非是用5除

litaoye 发表于 2009-3-5 23:40:20

原帖由 无心人 于 2009-3-4 17:53 发表 http://bbs.emath.ac.cn/images/common/back.gif
楼上的想法完全不可行啊

是吗?那就PASS掉好了!我也只是瞎猜一下!呵呵!

gxqcn 发表于 2009-3-6 07:50:26

litaoye 的二分法思想也是可以考虑的。

但最好修正成 2^9、2^18、2^36、。。。这样的序列。

算法可以这样设计：
1、s = 数组A前端元素连续为0的个数；k = 1；
2、r = a、a、。。。、a 构成的大数最多可被2整除的次数
3、若 r >= 9*k 且 s+k<n，则 k = 2*k，goto 2；
4、否则，return (9*s + r)

其中第2步可以避免大整数高位的无效计算。

kon3155 发表于 2009-3-6 09:20:36

我觉得二分法也是可以的，因为问题本质上是一个在有序数列中查找某个数的问题，无疑二分法是最快的。

无心人 发表于 2009-3-6 11:17:17

:)

写出代码比较下

我想99%可能是在最末字即结束
所以看具体输入的数值的分布

gxqcn 发表于 2009-3-6 12:24:04

如果是在上述假设前提下，
16# 的算法就更具优势。

litaoye 发表于 2009-3-6 15:38:08

回复 16# gxqcn 的帖子

如果也可以考虑的话,就给了我很大的鼓舞呀!呵呵!再想想!

说个思路,不一定实用!可以先算一下Mod 9,这个好算,数位加和就行了!
这样可以相对在查找2^N的时候可以更明确1些,2^m % 9 是个循环!
页: 1 [2] 3 4
查看完整版本: 快速计算一个10进制整数最多可被2的多少次方整除？