給定兩個非負整數 A 和 B，找到使它們同時相等的最小運算元。在一項操作中，您可以：
- 要么將 A 更改為 2*A
- 或將 B 更改為 2*B
- 或將 A 和 B 都更改為 A-1、B-1
例如：A = 7，B = 25
操作順序為：
- 6 24
- 12 24
- 24 24
我們不能在少于 3 次的操作中使它們相等
我在一周前的一次測驗中被問到這個編碼問題。想不出一個解決方案，它卡在我的腦海里。輸入 A 和 B 有點超過 10^12，所以很明顯我不能使用回圈，否則它將超過時間限制。
uj5u.com熱心網友回復：
一個緩慢但有效的解決方案：
- 如果它們相等，則停止。
- 如果其中之一為 0，則以失敗告終（如果不允許負數則無解）。
- 當兩者都大于 1 時，將兩者都減小。
- 現在較小的是1，另一個較大。
- 雖然較小的二進制表示較短，但較小的則加倍。
- 繼續第 1 步。
在第 4 步，最大值減小。在第 5 步中，絕對差值減小。因此最終演算法終止。
uj5u.com熱心網友回復：
這應該給出最佳解決方案。我們必須比較幾種不同的方法并采取最佳解決方案。
一種可行的解決方案是將較小的數字加倍，直到它低于較大的數字（可以是零倍）。然后計算（可能多次）加倍的較小數字和較大數字之間的差異。并多次減少數字。然后再將較小的數字翻倍。[如果數字從一開始就相等，則解決方案是微不足道的。]這給出了步驟的上限。
現在嘗試以下優化：
2a) 選擇一個介于 0 到迄今為止最佳解決方案的步數之間的數字 n。
2b) 選擇一個數字作為 A，一個數字作為 B（兩種可能）。
2c) 現在計算以下程式的應用步驟。
雙A n 次。
計算 2 (=m) 的最小冪，其中
B * 2^m >= A. m 應至少為 1。在混合基數（正確的術語？）系統中計算 A 與步驟 4 的乘積的差異，每個數字的位置
2^(n 1)-1值為31, 63, ... 從所有可能的表示中，數字必須具有最小的交叉和，例如 100 代表 7 是正確的，021 不是。旁注：對于最少的校驗和，主要是數字 0 和 1，最多一個數字 2，沒有其他數字。2 的右邊永遠不會有數字 1。）通過用零填充左側位置將數字表示為 m 位。如果數字不合適，請回傳步驟 2 進行其他選擇。
從步驟 6 中取出最重要的未處理數字，并執行盡可能多的遞減步驟。
雙B。
從 7 開始重復下一個數字；如果沒有更多的數字，則數字相等。
如果步驟數少于迄今為止的最佳解決方案，請選擇此作為建議的解決方案。
回傳第 2 步進行其他選擇。
在從 2 中進行所有選擇之后，我們應該得到具有最少步數的最優解。
以下示例來自答案的早期版本，其中 A 始終是較大的數字且 n=0，因此我們僅測驗一個選擇。
示例 17 和 65
Power of 2: 2^2=4; 4x17=68
Difference: 68-65=3
3 = 010=10 in base 7/3/1
Start => 17/65
Decrease. Double. => 32/64
Double. => 64/64
示例 18 和 67
Power of 2: 2^2=4; 4x18=72
Difference: 72-67=5
5 = 012=12 in base 7/3/1
Start => 18/67
Decrease. Double. => 34/66
Decrease. Decrease. Double. => 64/64
示例 10 和 137
Power of 2: 2^4=16; 16*10=160
Difference: 160-137=23
23 = 1101 in base 15/7/3/1
Start => 10/137
Decrease. Double. => 18/136
Decrease. Double. => 34/135
Double. => 68/135
Decrease. Double. => 134/134
uj5u.com熱心網友回復：
這是一個廣度優先搜索，它確實回傳了正確的答案，但可能不是找到它的最佳方法。也許它可以幫助其他人檢測模式。JavaScript 代碼：
function f(a, b) {
const q = [[a, b, [a, b]]];
while (true){
const [x, y, path] = q.shift();
if (x == y) {
return path;
}
if (x > 0 && y > 0) {
q.push([x-1, y-1, path.concat([x-1, y-1])]);
}
q.push([2*x, y, path.concat([2*x, y])]);
q.push([x, 2*y, path.concat([x, 2*y])]);
}
return [];
}
function showPath(path) {
let out1 = "";
let out2 = "";
for (let i = 0; i < path.length; i = 2) {
const s1 = path[i].toString(2);
const s2 = path[i 1].toString(2);
const len = Math.max(s1.length, s2.length);
out1 = s1.padStart(len, "0");
out2 = s2.padStart(len, "0");
if (i < path.length - 2) {
out1 = " --> ";
out2 = " --> ";
}
}
console.log(out1);
console.log(out2);
}
showPath(f(89, 7));轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489533.html
標籤：算法