Cần có số lần di chuyển tối thiểu nhất định để N chia hết cho 25 bằng C ++.

Tuyên bố vấn đề

Cho một số N không có số 0 ở đầu. Nhiệm vụ là tìm số nước đi tối thiểu cần thiết để N chia hết cho 25. Ở mỗi nước đi, người ta có thể hoán đổi hai chữ số liền kề bất kỳ và đảm bảo rằng tại bất kỳ thời điểm nào số không được chứa bất kỳ số 0 nào ở đầu. Nếu không thể lấy N chia hết cho 25 thì in ra -1

Nếu N =5071 thì cần 4 lần di chuyển để nó chia hết cho 25

5071 → 5701 → 7501 → 7510 → 7150

Thuật toán

1. Iterate over all pairs of digits in the number. Let the first digit in the pair is at position ‘i’ and the second is at position ‘j’.
2. Place these digits to the last two positions in the number
3. If the number has a leading zero. Find the leftmost nonzero digit and move it to the first position.
4. If the current number is divisible by 25 then update the answer with the number of swaps

Ví dụ

#include <iostream>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;
int requiredMoves(long long n){
   string str = to_string(n);
   int ans = INT_MAX;
   int len = str.size();
   for (int i = 0; i < len; ++i) {
      for (int j = 0; j < len; ++j) {
         if (i == j)
            continue;
      string temp = str;
      int cnt = 0;
      for (int k = i; k < len - 1; ++k) {
         swap(temp[k], temp[k + 1]);
         ++cnt;
      }
      for (int k = j - (j > i); k < len - 2; ++k) {
         swap(temp[k], temp[k + 1]);
         ++cnt;
      }
      int pos = -1;
      for (int k = 0; k < len; ++k) {
         if (temp[k] != '0') {
            pos = k;
            break;
         }
      }
      for (int k = pos; k > 0; --k) {
         swap(temp[k], temp[k - 1]);
         ++cnt;
      }
      long long num = atoll(temp.c_str());
      if (num % 25 == 0)
         ans = min(ans, cnt);
      }
   }
   if (ans == INT_MAX)
      return -1;
   return ans;
}
int main(){
   int n = 5071;
   cout << "Minimum required moves: " << requiredMoves(n) << endl;
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Minimum required moves: 4