資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究將M和N透過重複新增自身除數（除了1和自身）的方式變成相等所需的最小移動次數
簡介
尋找將兩個給定數字M和N透過重複新增任何數字的除數（除了1和數字本身）的方式變成相等的最小移動次數的問題，可以在不使用動態規劃的情況下解決。在這個問題中，我們需要設計能夠最小化達到指定統一性所需的移動次數的方法。展示了兩種解決此問題的方法：貪心演算法、質因數分解。這些方法使用不同的策略來識別公因子並最佳化使數字增加的方法，為了研究這些非動態規劃方法，我們將深入瞭解解決此問題其他有效策略。
方法 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
方法 2：質因數分解
演算法
步驟 1 − 定義使用者自定義函式 minMoves()。
步驟 2 − 找出 M 和 N 的質因數分解。
步驟 3 − 遍歷 M 的質因子，並檢查它們是否出現在 N 的質因子中。
步驟 4 − 如果找到一個公有的質因子，則將 M 和 N 都除以該質因子。
步驟 5 − 將 movesCount 增加該質因子的值。
步驟 6 − 使用 if 語句檢查 M 是否等於 N，如果否，則將 movesCount 增加 2。
此步驟用於計算達到相同數字所需的額外移動次數。
步驟 7 − 返回 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) 來識別公約數並最小化所需的移動次數。質因數分解方法將兩個數字分解為質數並檢查公有因子。蠻力法有效地搜尋特定範圍內的除數。雖然這些方法不使用動態規劃，但它們提供瞭解決問題並找到所需最小移動次數的有效方法。透過應用這些方法，我們將最佳化使用特定除數達到兩個數字相等的方法。
58 次瀏覽
