极客笔记C++ 通过反复添加除1和数本身以外的任何因子使M和N相等所需的最小移动次数
介绍
可以通过不使用动态规划来解决找到使给定的两个数字M和N上升的最小移动次数的问题。在这个问题中，我们需要规划能够最小化达到指定一致性所需的移动次数的方法。有两种方法可以处理这个问题：贪婪算法，素数分解。这些方法利用不同的策略来识别公共因子并优化使数字上升的方法。为了研究这些非动态规划方法，我们将获得解决这个问题的替代策略的见解。
方法1：贪婪算法
算法
- 步骤1 − 创建一个函数gcd()，将变量movesCount初始化为0。
-
步骤2 − 利用欧几里得算法找到M和N的最大公约数（GCD）。
-
步骤3 − 如果GCD大于1，表示存在除1以外的公共因子。
-
步骤4 − 将movesCount增加GCD的值。将M和N分别除以GCD。
-
步骤5 − 如果M仍然不等于N，将movesCount增加2。
-
步骤6 − 这一步是为了计算达到相同数字所需的额外移动次数。
-
步骤7 − 将movesCount返回为创建M和N相等所需的最小移动次数。
示例
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int minMoves(int M, int N) {
int movesCount = 0;
int commonDivisor = gcd(M, N);
if (commonDivisor > 1) {
movesCount += commonDivisor;
M /= commonDivisor;
N /= commonDivisor;
}
if (M != N)
movesCount += 2;
return movesCount - 3;
}
//define main function
int main() {
int M = 10;
int N = 30;
int result = minMoves(M, N);
printf("Minimum number of moves required: %d\n", result);
return 0;
}
输出
Minimum number of moves required: 9
方法二：质因数分解
算法
-
第一步 - 定义用户自定义函数 minMoves()。
-
第二步 - 发现 M 和 N 的质因数分解。
-
第三步 - 通过 M 的质因数并检查它们是否在 N 的质因变量中显示。
-
第四步 - 如果找到了共同的质数计算，则将 M 和 N 分别除以该质数。
-
第五步 - 将 movesCount 的值增加该质数计算的值。
-
第六步 - 使用 if 语句检查 M 是否等于 N，并将 movesCount 增加2。
这一步是为了计算达到相同数值所需的额外移动次数。
- 第七步 - 以 movesCount 为结果，作为形成 M 和 N 相等所需的最少移动次数。
示例
#include <stdio.h>
int minMoves(int M, int N) {
int movesCount = 0;
for (int i = 2; i <= M; i++) {
while (M % i == 0 && N % i == 0){
M /= i;
N /= i;
movesCount += i;
}
}
if (M != N)
movesCount += 2;
return movesCount;
}
int main() {
int M = 10;
int N = 30;
int result = minMoves(M, N);
printf("Minimum number of moves required: %d\n", result);
return 0;
}
输出
Minimum number of moves required: 9
结论
贪婪算法的方法利用最大公约数（GCD）来识别公约数并最小化所需的移动。素因数分解的方法将两个数字分解为素数，并检查共同的因素。暴力搜索法在特定范围内高效地搜索因子。虽然这些方法不使用动态规划，但它们提供了解决问题和找到需要的最少移动次数的有效方法。通过应用这些方法，我们将优化通过仅使用特定的因子来实现两个数字之间的平等的方法。