时间戳

首页 > 解决方案 > 查找所有整数 p 和 q 的优化方法，使得 2^p*3^q 具有给定的十进制长度

java - 查找所有整数 p 和 q 的优化方法，使得 2^p*3^q 具有给定的十进制长度

问题描述

找出 和 的所有可能组合，a使得b的小数位数r是给定的数字N。

标签： javaalgorithmmathlogic

解决方案

这个问题很自然地推广到找到所有p, q在2^p * 3^qaminimum和 a之间的问题maximum。哪里min = 10^N和max = 10^(N+1) - 1。

我会讲算法，也会讲长度为 2 的特殊情况作为例子。

第一步是生成一个 2 的幂数组，直到您通过max。换句话说[1, 2, 4, 8, 16, 32, 64, 128]。每当您看到某种形式的东西时，2^p就可以使用数组查找来计算它。

接下来我们找到min_pandmax_p这样min_p <= p <= max_p我们有min <= 2^p <= max。我们通过从数组的末尾向后搜索，直到我们max_p向后找到更多来做到这一点min_p。在我们的例子中，min_p = 4和max_p = 6。

现在我们开始q=0并进行如下操作。

q = 0
pow = 1
while 0 <= max_p:
    for p between min_p and max_p:
        add (p, q) to the answer

    pow *= 3
    q += 1
    # We want min_p to stop at 0
    while 0 < min_p and min < pow * 2^(min_p - 1):
        min_p -= 1
    # max_p going below 0 is how we know to stop.
    while 0 <= max_p and max < pow * 2^max_p:
        max_p -= 1

在我们的示例中，这将按如下方式工作：

min_p = 4, max_p = 6
q = 0
add (4, 0), (5, 0), (6, 0) to answer
q = 1
min_p = 2
max_p = 5
add (2, 1), (3, 1), (4, 1), (5, 1) to answer
q = 2
min_p = 0
max_p = 3
add (0, 2), (1, 2), (2, 2), (3, 2) to answer
q = 3
min_p = 0
max_p = 1
add (0, 3), (1, 3) to answer
q = 4
min_p = 0
max_p = 0
add (0, 4) to answer
q = 5
min_p = 0
max_p = -1
finish

我们现在的答案是：

(4, 0), (5, 0), (6, 0), (2, 1), (3, 1), (4, 1), (5, 1),
(0, 2), (1, 2), (2, 2), (3, 2), (0, 3), (1, 3), (0, 4)

也就是说：

16, 32, 64, 12, 24, 48, 96, 18, 36, 72, 27, 54, 81

推荐阅读