使用指定的操作将一个数字转换为另一个数字。需要一些帮助

Question

这是我最近遇到的一个问题-

Suppose I've 3 integers k,m,n. I have to reach m from k in minimum number of operations, and the operations possible are-
You can multiply k by n.
You can decrease k by 2.
You can decrease k by 1.
Also, these 3 operations can be performed in any order.

有多种方法可以尝试这一点 - 递归或动态方法。但是我找到了一个有趣的解决方案，但它们都没有实现，而且我很难破译它。下面是参考代码-

        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int m = sc.nextInt();
        int n = sc.nextInt();
        int count = 0;
        int x = 0;
        while (k < m) {
            if (m % n == 0) {
                m = m / n;
                count++;
            } else {
                x = (n - (m % n));
                m += (x) / 2 * 2 + (x) % 2;
                count += x / 2 + x % 2;
            }
        }
        if (k > m) {
            count += (k - m) / 2 + (k - m) % 2;
        }
        System.out.println(count);

嗯，我真的很抱歉不能包含评论，因为我无法掌握这段代码。有人可以通过代码一次，并解释这段代码实际上是如何工作的吗？会有很大的帮助！（顺便说一下，代码运行正常！）

Answer 1

编辑 2：查看我的其他答案以获得完整解释 ()

编辑：您可以将算法本身缩短为：

while (k < m) {
    m += n - (m - 1) % n - 1;
    m /= n;
}

但我还没有计算出计数值

上一个： 这是一个评论版本（重新格式化也有很大帮助）：

    Scanner sc = new Scanner(System.in);

    int k = sc.nextInt();
    int m = sc.nextInt();
    int n = sc.nextInt();
    
    sc.close();

    int count = 0, x;
    while (k < m) { // Loop while k is smaller then m (meaning our end goal for m is to be smaller or equal to k) (since k will not change inside of the while loop we know that m must change)
        if (m % n == 0) { // Check if m divided by n has NO remainder, if so do the division and increase count by one
            m = m / n;
            count++;
        } else { // If not then...
            // ...subtract the remainder from n and store it in x. X now contains the number which you would need to add to m to make 'm % n == 0' (the if statement) result in true
            x = (n - (m % n));

            // In here we do 'x / 2 * 2' first which will result in even value (rounding x to its lower even value. eg. x = 5 would become 4. Since we are using integers) which we then add to m.
            // Then we also add the missing '1' to m to make the if statement in the next loop result in true
            // I tested this algorithm btw. it does not change the value of x:
            /*
                for (int x = 0; x < 5000; x++) {
                    boolean same = x == (x / 2 * 2 + x % 2);
                    System.out.println(x + " -> " + same);
                }
                Result: same is always true
            */
            m += x / 2 * 2 + x % 2; // This line can be simplified to 'm += x;'
            
            // Then we add half of the x and a 0 or a 1 to count
            count += x / 2 + x % 2;
        }
    }
    if (k > m) { // This will run always if k is not eual to m
        
        // This line is almost equal to this one: 'count += x / 2 + x % 2;'
        // except, that every x was replaced by '(k - m)'
        
        count += (k - m) / 2 + (k - m) % 2;
    }
    
    // Then we print out count
    System.out.println(count);

Answer 2

所以该算法主要做的事情如下：

将当前 m 舍入为 n 的偶数倍，但前提是 m 已经不是 n 的偶数倍，然后将 m 除以 n。第一部分可以使用以下行完成（如果 m 已经是 n 的偶数倍，它将导致 0）：

x = n - (m - 1) % n - 1;

通过将 x 加到 m，我们将使 m 成为 n 的偶数倍，或者如果 m 已经是一，则保持原样。

但是我们也可以使用 x 来计算执行的操作数。

You can multiply k by n. You can decrease k by 2. You can decrease k by 1

意味着如果我们将这些规则应用于 m 那么它们应该是这样的（如果我错了请纠正我）：

You can divide m by n. You can increase m by 2. You can increase m by 1

所以每次我们将 m 舍入到 n 的下一个偶数倍时，我们基本上说我们将 m 的值增加 2 'x / 2 times'，但由于这仅在 x 为偶数时有效，我们也可以说我们如果 x 不是偶数，则将 m 额外增加 1。

So for this step we need to increase our count value by 'x / 2 + x % 2'

现在我们已经完成了这个，我们需要将 m 除以 n（正如我对 m 而不是 k 的倒置规则所说，您现在可以这样做）。 m 除以 n 后，我们需要将计数器加 1，因为我们执行了一次操作。

这里是完整的压缩代码：

int count = 0, x;
while (k < m) {
    x = n - (m - 1) % n - 1;
    m = (m + x) / n;
    count += x / 2 + x % 2 + 1;
}
if (k > m) {
    count += (k - m) / 2 + (k - m) % 2;
}

结论：

此算法对 m 而不是规则建议的 k 执行所有操作。因此你需要“颠倒”规则（就像我上面做的那样）然后你用你的“新”规则集分析代码，发现它基本上已经遵循了你的“新”规则集。巧合，我不这么认为！

使用指定的操作将一个数字转换为另一个数字。需要一些帮助

Convert a number to another number using specified operations. Need some help regarding this

java

recursion

dynamic-programming

这里是完整的压缩代码：

结论：