在最少的步骤中使用乘2或除以3生成任何数字？

Question

在最少的步骤中使用乘2或除以3生成任何数字？知道如何有效地解决这个问题吗？我在考虑动态规划，但不确定。例如，我认为得到7的最佳解决方案是通过2*2*2*2*2/3/3=7，我指的是C++或Java中的整数除法。谢谢!

Answer 1

这是一个BFS动态规划解决方案。

#! /usr/bin/env python
wanted = 7
found = {1: None}
added = [1]
while True:
    new_added = []
    for x in added:
        if 2*x not in found:
            found[2*x] = [x, 2]
            new_added.append(2*x)
        if x/3 not in found:
            found[x/3] = [x, 3]
            new_added.append(x/3)
    if wanted in found:
        break
    # This magic line copies new_added over the added array.
    added[:] = new_added

answer = []
path = [wanted]
while path[-1] != 1:
    node = found[path[-1]]
    path.append(node[0])
    answer.append(node[1])

print([x for x in reversed(answer)])
print([x for x in reversed(path)])

这是一个解释。

BFS意味着广度优先搜索。在这种情况下，我们通过长度为1，2，3等的所有路径进行并行搜索，直到完成为止。

动态编程是指存储已完成的工作记录的各种方法中的任何一种，这样我们就可以避免工作，或者返回到已经完成的工作。

在本例中，found是所有数字的记录，我们找到了一条通往那里的整数的路径，以及要使用的操作。added是我们在上次传递时找到的所有整数的记录。new_added是我们在这次传递中找到的所有整数。

因此，我们从一个记录开始，说我们知道如何到达1。然后在每一次传递中，我们获取所有刚刚添加的记录，看看我们通过乘以2或除以3得到了什么新记录。

一旦找到目标我们就停下来。然后是一个通过found找到返回到1的路径的问题。这给了我们答案，但顺序相反--路径的末尾在列表的开头。所以逆转它，我们就有答案了。

我把它展示为我们访问的所有数字的记录和操作的记录。

Answer 2

--编辑:找不到最短的解决方案--

在描述了下面的算法之后，我被告知它找不到最短的解。

我的想法是从我们的数字N开始，重复乘以3(考虑整数除以3对乘积所带来的不确定性范围)，并检查两个幂是否存在于当前的不确定性范围内。

例如，对于N=7：

• Range0 =7.7，范围内没有2的幂
• Range1 =21.23，范围内无2次方
• Range2 =63.71，2的幂为2^6 = 64，在这个范围内，所以解是2^6 / 3^2 = 7。

我不确定每个自然数N都能这样到达。所以算法可能不会终止。

而且我觉得中间数甚至对于小N值也会变得相当大，所以可能需要一个BigInteger实现。

如果N= 2^a / 3^b，则该算法将在O(a+b)中运行。

具有64位整数的Java程序：

package test;

public class TwoThreePower {

    static void printPowers(int n) {
        int exp3 = 0;
        long rangeMin = n;
        long rangeMax = n;
        int exp2 = 0;
        long power2 = 1;
        while(true) {
            if (power2 < rangeMin) {
                power2 = power2 * 2;
                exp2 = exp2 + 1;
            } else if (power2 <= rangeMax) {
                System.out.println(String.format("%d is 2^%d / 3^%d", n, exp2, exp3));
                return;
            } else {
                rangeMin = rangeMin * 3;
                rangeMax = rangeMax * 3 + 2;
                exp3 = exp3 + 1;
            }
        }
    }

    public static void main(String[] args) {
        for (int i=1; i<100; i++) {
            printPowers(i);
        }
    }
}

这在n=40上已经失败了，所以我创建了(可读性较低的) BigInteger版本：

package test;

import java.math.BigInteger;

public class BigTwoThreePower {

    public static final BigInteger TWO = BigInteger.valueOf(2);
    public static final BigInteger THREE = BigInteger.valueOf(3);

    static void printPowers(int n) {
        int exp3 = 0;
        BigInteger rangeMin = BigInteger.valueOf(n);
        BigInteger rangeMax = rangeMin;
        int exp2 = 0;
        BigInteger power2 = BigInteger.ONE;
        while(true) {
            if (power2.compareTo(rangeMin) < 0) {
                power2 = power2.multiply(TWO);
                exp2 = exp2 + 1;
            } else if (power2.compareTo(rangeMax) <= 0) {
                System.out.println(String.format("%d is 2^%d / 3^%d", n, exp2, exp3));
                return;
            } else {
                rangeMin = rangeMin.multiply(THREE);
                rangeMax = rangeMax.multiply(THREE).add(TWO);
                exp3 = exp3 + 1;
            }
        }
    }

    public static void main(String[] args) {
        for (int i=1; i<100; i++) {
            printPowers(i);
        }
    }
}

以下是N=1到99的结果：

1 is 2^0 / 3^0
2 is 2^1 / 3^0
3 is 2^5 / 3^2
4 is 2^2 / 3^0
5 is 2^4 / 3^1
6 is 2^9 / 3^4
7 is 2^6 / 3^2
8 is 2^3 / 3^0
9 is 2^8 / 3^3
10 is 2^5 / 3^1
11 is 2^13 / 3^6
12 is 2^10 / 3^4
13 is 2^18 / 3^9
14 is 2^7 / 3^2
15 is 2^23 / 3^12
16 is 2^4 / 3^0
17 is 2^20 / 3^10
18 is 2^9 / 3^3
19 is 2^17 / 3^8
20 is 2^44 / 3^25
21 is 2^6 / 3^1
22 is 2^14 / 3^6
23 is 2^22 / 3^11
24 is 2^30 / 3^16
25 is 2^11 / 3^4
26 is 2^19 / 3^9
27 is 2^46 / 3^26
28 is 2^8 / 3^2
29 is 2^16 / 3^7
30 is 2^62 / 3^36
31 is 2^24 / 3^12
32 is 2^5 / 3^0
33 is 2^13 / 3^5
34 is 2^59 / 3^34
35 is 2^21 / 3^10
36 is 2^48 / 3^27
37 is 2^10 / 3^3
38 is 2^56 / 3^32
39 is 2^18 / 3^8
40 is 2^64 / 3^37
41 is 2^45 / 3^25
42 is 2^7 / 3^1
43 is 2^53 / 3^30
44 is 2^15 / 3^6
45 is 2^80 / 3^47
46 is 2^42 / 3^23
47 is 2^23 / 3^11
48 is 2^69 / 3^40
49 is 2^31 / 3^16
50 is 2^12 / 3^4
51 is 2^58 / 3^33
52 is 2^39 / 3^21
53 is 2^20 / 3^9
54 is 2^66 / 3^38
55 is 2^47 / 3^26
56 is 2^9 / 3^2
57 is 2^74 / 3^43
58 is 2^55 / 3^31
59 is 2^17 / 3^7
60 is 2^82 / 3^48
61 is 2^63 / 3^36
62 is 2^44 / 3^24
63 is 2^25 / 3^12
64 is 2^6 / 3^0
65 is 2^52 / 3^29
66 is 2^33 / 3^17
67 is 2^14 / 3^5
68 is 2^79 / 3^46
69 is 2^60 / 3^34
70 is 2^41 / 3^22
71 is 2^22 / 3^10
72 is 2^68 / 3^39
73 is 2^49 / 3^27
74 is 2^30 / 3^15
75 is 2^11 / 3^3
76 is 2^76 / 3^44
77 is 2^57 / 3^32
78 is 2^38 / 3^20
79 is 2^19 / 3^8
80 is 2^84 / 3^49
81 is 2^65 / 3^37
82 is 2^130 / 3^78
83 is 2^46 / 3^25
84 is 2^27 / 3^13
85 is 2^8 / 3^1
86 is 2^73 / 3^42
87 is 2^54 / 3^30
88 is 2^35 / 3^18
89 is 2^16 / 3^6
90 is 2^81 / 3^47
91 is 2^146 / 3^88
92 is 2^62 / 3^35
93 is 2^43 / 3^23
94 is 2^24 / 3^11
95 is 2^89 / 3^52
96 is 2^154 / 3^93
97 is 2^70 / 3^40
98 is 2^51 / 3^28
99 is 2^32 / 3^16