Program C++ untuk mengalih keluar aksara daripada rentetan angka supaya ia boleh dibahagikan dengan 8

Diberikan nombor dalam bentuk rentetan, kita perlu mencari tempat untuk menjadikannya boleh dibahagikan dengan lapan selepas memadamkan sifar atau lebih elemen Dalam erti kata lain, kita perlu mencari sama ada terdapat urutan rentetan, yang boleh dibahagi dengan 8. Kembalikan rentetan yang diubah suai atau -1 jika tidak boleh.

Mengikut peraturan boleh bahagi, sebarang nombor yang tiga digit terakhirnya boleh dibahagi dengan 8 juga boleh dibahagi dengan 8. Sebagai contoh, 56992992 dan 476360 boleh dibahagikan dengan 8, tetapi 2587788 tidak. Jika hasilnya adalah integer, nombor asal boleh dibahagi dengan 8.

Mari kita lihat beberapa senario input yang menerangkan kaedah secara terperinci −

Jika input yang dihantar kepada kaedah ialah rentetan berangka yang mengandungi sebarang subrentetan boleh bahagi dengan 8, maka dalam senarai hasil kita boleh dapatkan subrentetan boleh bahagi dengan 8−

Input: 2567992
Result: 56

Jika input kepada kaedah ialah rentetan berangka yang tidak mengandungi sebarang subrentetan dibahagikan dengan 8, output akan dikembalikan sebagai −

Input: 77777777777
Result: -1

Algoritma

• Input rentetan diulang, menyemak sama ada mana-mana subrentetan ialah gandaan 8.

• Jika terdapat sebarang subrentetan berbangkit hadir dalam input, subrentetan dikembalikan sebagai output.

• Jika subrentetan ditemui, atur cara ditamatkan, jika tidak, ulangi langkah 2 sehingga subrentetan ditemui.

• Jika tiada subrentetan dalam input yang boleh dibahagikan dengan 8, output yang dikembalikan ialah -1.

Contoh

Dalam program C++ di bawah, kami mengambil dua rentetan, satu boleh ditukar kepada rentetan boleh dibahagikan dengan 8 dan satu lagi tidak boleh, dan mencari output dalam setiap kes. Kita boleh lelaran daripada 0 hingga 1000 dalam gandaan 8 seperti 0, 8, 16, 24, 32...1000 dan menyemak sama ada nombor ini wujud sebagai urutan rentetan yang diberikan.

#include <iostream>
using namespace std;
int checkIfSubstringExist(string req, string given) {
   int index = 0;
   for (char ch : given) {
      if (req[index] == ch) {
         index++;
      }
   }
   return index == (int)req.size();
}
string solve(string s) {
   for (int i = 0; i < 1e3; i += 8) {
      string num = to_string(i);
      if (checkIfSubstringExist(num, s)) {
         return num;
      }
   }
   return "-1";
}
int main() {

   // the string “95256” can be converted to a string divisible by 8
   // the string “74516” cannot be converted to a string divisible by 8
   // let’s run our code to find the output in each case
   string s1 = "95258", s2="74516";
   cout << solve(s1) << "\n" << solve(s2) << endl;
   return 0;
}

Output

8
16

Seperti yang anda lihat dalam output di atas, 9525 dialih keluar daripada 95258, dan 745 dialih keluar daripada 74516 untuk menjadikan nombor kiri boleh dibahagikan dengan 8.

Kesimpulan

Seperti yang kita lihat, selepas pemerhatian mudah, kita hanya perlu menyemak sama ada subset itu wujud. Kami menyemak sama ada rentetan mengandungi urutan, dalam kes paling teruk ia menyemak keseluruhan rentetan. Oleh itu, jika kita diberi rentetan berangka panjang n, kerumitan masa kes terburuk ialah O(126*n), iaitu O(n).

Atas ialah kandungan terperinci Program C++ untuk mengalih keluar aksara daripada rentetan angka supaya ia boleh dibahagikan dengan 8. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!