快速计算一个10进制整数最多可被2的多少次方整除？

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 发表楼上的想法完全不可行啊

是吗?那就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[s+1]、。。。、a[s+k-1] 构成的大数最多可被2整除的次数 3、若 r >= 9*k 且 s+k~~

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

如果也可以考虑的话,就给了我很大的鼓舞呀!呵呵!再想想! 说个思路,不一定实用!可以先算一下Mod 9,这个好算,数位加和就行了! 这样可以相对在查找2^N的时候可以更明确1些,2^m % 9 是个循环!

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 快速计算一个10进制整数最多可被2的多少次方整除？

回复 16# gxqcn 的帖子