这是我最近遇到的一个问题-
假设我有 3 个整数 k,m,n。我必须以最少的操作次数从k达到m,并且可能的操作是-
你可以乘ķ通过ñ。
您可以将k减少 2。
您可以将k减少 1。
此外,这 3 个操作可以按任意顺序执行。
有多种方法可以尝试这种方法 - 无论是递归还是动态方法。但是我找到了一个有趣的解决方案,它没有实现它们,而且我很难破译它。这是参考代码-
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);
好吧,我真的很抱歉不能包含注释,因为我无法掌握这段代码。有人可以浏览一遍代码,并解释这段代码实际上是如何工作的吗?会有很大的帮助!(顺便说一句,代码运行良好!)
因此,该算法的主要作用如下:
x = n - (m - 1) % n - 1;
通过将 x 添加到 m,我们将使 m 成为 n 的偶数倍,或者保持 m 原样,如果它已经是 1。
您可以将 k 乘以 n。您可以将 k 减少 2。您可以将 k 减少 1
这意味着如果我们将这些规则应用于 m 那么它们应该是这样的(如果我错了,请纠正我):
您可以将 m 除以 n。您可以将 m 增加 2。您可以将 m 增加 1
因此,对于这一步,我们需要将计数值增加“x / 2 + x % 2”
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 执行所有操作。因此,您需要“颠倒”规则(就像我上面所做的那样)然后用“新”规则集分析代码,并确定它基本上已经遵循了“新”规则集。巧合,我不这么认为!
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句