Chuyển số m thành n với ít phép toán nhất trong C++

Cho hai số m, n. Chuyển m thành n bằng ít phép toán nhất. Phép được phép: nhân 2 hoặc trừ 1.

Ví dụ

m=5, n=11 → 5 phép toán

Thuật toán đệ quy

• Nếu m == n: 0 phép
• Nếu m > n: chỉ có thể trừ 1 → m-n phép
• Nếu m ≤ 0 và n > 0: không thể chuyển đổi → -1
• Nếu n lẻ: phải làm n+1 (nghịch đảo của trừ 1) → 1 + convert(m, n+1)
• Nếu n chẵn: phải làm n/2 (nghịch đảo của nhân 2) → 1 + convert(m, n/2)

Chương trình C++

#include <bits/stdc++.h> 
using namespace std; 

int convert(int m, int n) {
    if (m == n) return 0;
    if (m > n) return m - n;
    if (m <= 0 && n > 0) return -1;
    if (n % 2 == 1)  // n lẻ
        return 1 + convert(m, n + 1);
    else  // n chẵn
        return 1 + convert(m, n / 2);
}

int main() {
    int m = 5, n = 11;
    cout << "Minimum number of operations: " << convert(m, n);
    return 0;
}

Kết quả

Minimum number of operations: 5

Trace ví dụ m=5, n=11

convert(5,11): 11 lẻ → 1 + convert(5,12)
convert(5,12): 12 chẵn → 1 + convert(5,6)
convert(5,6): 6 chẵn → 1 + convert(5,3)
convert(5,3): 5>3 → 5-3=2
Tổng: 1+1+1+2 = 5 phép
Đường đi: 5 → 10 → 9 → 18 → 17 → ... (nghịch đảo)