Tìm số bước tối thiểu để đến M từ N trong C ++

Giả sử chúng ta có hai số nguyên N và M. Chúng ta phải tìm số bước tối thiểu để đến M từ N, bằng cách thực hiện các phép toán đã cho -

• Nhân số x với 2, do đó x sẽ là 2 * x
• Trừ một số cho số x, vì vậy số sẽ là x - 1

Nếu N =4 và M =6, thì đầu ra sẽ là 2. Vì vậy, nếu chúng ta thực hiện phép toán số 2 trên N, thì N trở thành 3, sau đó thực hiện phép toán số một trên giá trị cập nhật của N, do đó nó trở thành 2 * 3 =6. Vì vậy, số bước tối thiểu sẽ là 2.

Để giải quyết vấn đề này, chúng tôi sẽ tuân theo các quy tắc sau -

• Chúng ta có thể đảo ngược vấn đề, giống như chúng ta lấy số N bắt đầu từ M, vì vậy hai phép toán mới sẽ là
• 
  
  • Chia số cho 2 khi nó là số chẵn,
  • thêm 1 với số
• Bây giờ số lượng hoạt động tối thiểu sẽ là
  • nếu N> M, trả về sự khác biệt giữa chúng, vì vậy số bước sẽ thêm 1 vào M, cho đến khi nó trở thành N
  • Ngược lại, khi N

Ví dụ

#include<iostream>
using namespace std;
int countMinimumSteps(int n, int m) {
   int count = 0;
   while(m > n) {
      if(m % 2 == 1) {
         m++;
         count++;
      }
      m /= 2;
      count++;
   }
   return count + n - m;
}
int main() {
   int n = 4, m = 6;
   cout << "Minimum number of operations required: " << countMinimumSteps(n, m);
}

Đầu ra

Minimum number of operations required: 2