Bilangan pergerakan minimum yang diperlukan untuk membuat palindrom rentetan dengan menambah semua aksara subrentetan

Dalam bidang sains komputer dan pengaturcaraan, adalah sangat penting untuk menemui algoritma yang cekap untuk menyelesaikan masalah. Masalah yang menarik ialah mengenal pasti bilangan operasi minimum yang diperlukan untuk menukar rentetan menjadi palindrom dengan menambahkan semua aksara dalam subrentetan. Artikel ini meneroka dua cara untuk mendekati masalah ini menggunakan bahasa pengaturcaraan C++.

tatabahasa

Sebelum kita menyelami kaedah ini, mari kita tentukan sintaks fungsi yang akan kita gunakan −

int minMovesToMakePalindrome(string str);

Algoritma

• Matlamat kami adalah untuk meminimumkan bilangan pergerakan apabila menukar rentetan kepada palindrom - masalah ini diselesaikan oleh algoritma kami melalui peringkat utama berikut −

• Pertama, cipta dua pembolehubah penunjuk dari kedua-dua belah rentetan Penunjuk kiri bermula dari permulaan rentetan, dan penunjuk kanan bermula dari penghujung rentetan.

• Teruskan proses kami selagi had konfigurasi membenarkan iaitu sekali salah satu penunjuk melepasi hentian yang lain −

• Apabila nilai watak adalah sama, teruskan mendekatkan kedua-dua penunjuk. Apabila nilai aksara berbeza, nilai aksara di sebelah kanan dinaikkan (mengikut perbezaannya) sebelum melakukan sebarang operasi selanjutnya. Peningkatan ini adalah berkadar dengan perbezaan antara 'a' dan 'c', jadi jika str[kanan] bersamaan dengan 'c' dan str[kiri] sama dengan 'a', kami menambah str[kanan] sebanyak 2 (kerana 'a '- 'c'=2). Kemas kini kiraan langkah dengan sewajarnya.

• Apabila bahagian kiri lebih besar daripada bahagian kanan, tali akan menjadi palindrom.

Kaedah 1: Brute force cracking

Dalam kaedah ini, kami akan mempertimbangkan semua subrentetan yang mungkin dan mengira bilangan minimum pergerakan yang diperlukan untuk setiap subrentetan. Akhir sekali, kami akan mengembalikan minimum semua pergerakan yang dikira.

Contoh

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int length = str.length();

   for (int i = 0; i < length / 2; i++) {
      moves += abs(str[i] - str[length - i - 1]);
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

Output

Minimum moves to make the string palindrome: 6

Penjelasan

Penjelasan

Fungsi yang dipanggil minMovesToMakePalindrome telah dicipta yang menukar rentetan input str menjadi palindrom dengan bilangan pergerakan minimum yang diperlukan. Kami menerangkan cara ia berfungsi dengan beberapa arahan langkah demi langkah:

Kami memulakan pembolehubah pergerakan kepada 0, yang bertanggungjawab untuk menjejaki jumlah pergerakan yang diperlukan. - Memandangkan pembolehubah panjang merekodkan panjang str rentetan input, langkah seterusnya kami ialah menggunakan gelung for untuk mengulang separuh daripada rentetan supaya kedudukan simetri tidak bertindih. - Akhir sekali, di dalam gelung ini, abs(str[i] - str[length - i - 1]) mengira perbezaan mutlak antara dua aksara akhir.

Perbezaan yang dikira mewakili bilangan pergerakan yang diperlukan untuk menjadikan aksara pada kedudukan tersebut sama. Kami menambah perbezaan ini pada kiraan pergerakan.

Selepas mengulangi semua kedudukan yang diperlukan, kami menyimpan jumlah bilangan minimum pergerakan yang diperlukan dalam pembolehubah bergerak. Kami mengembalikan nilai ini.

Dalam fungsi utama, kami memulakan rentetan str dengan nilai "abcde". Kemudian, kami memanggil fungsi minMovesToMakePalindrome, melepasi str sebagai parameter. Bilangan minimum pergerakan yang dikembalikan disimpan dalam pembolehubah minMoves. Akhirnya, kami mencetak hasilnya ke konsol.

Kaedah 2: Kaedah penunjuk berganda yang optimum

Kaedah ini menggunakan dua penunjuk untuk melintasi dari kedua-dua hujung rentetan pada masa yang sama. Dengan mengambil kira kecekapan, kami menggunakan teknik untuk menukar rentetan menjadi palindrom yang melibatkan penambahan dan pemadanan aksara secara progresif dari kedua-dua hujung input. Pendekatan ini meminimumkan operasi yang tidak perlu dan membolehkan penukaran yang lebih pantas tanpa menjejaskan ketepatan atau kefungsian.

Contoh

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int left = 0;
   int right = str.length() - 1;

   while (left <= right) {
      moves += abs(str[right] - str[left]);
      left++;
      right--;
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

Output

Minimum moves to make the string palindrome: 6

Penjelasan

Penjelasan

Matlamat contoh kod di bawah adalah untuk menggunakan pendekatan dua mata yang optimum untuk menentukan bilangan minimum pergerakan yang diperlukan untuk menukar rentetan yang diberikan kepada palindrom.

Untuk mencapai matlamat ini, kami mencipta fungsi yang dipanggil minMovesToMakePalindrome. Fungsi ini menerima hujah rentetan dan mengembalikan jumlah bilangan pergerakan yang diperlukan. Pertama, kami menetapkan pembolehubah yang digunakan untuk mengira bilangan pergerakan kepada 0 dan memulakan penunjuk kiri dan kanan: penunjuk kiri bermula dari permulaan rentetan input (indeks 0) dan penunjuk kanan bermula dari penghujung (index str. panjang() - 1).

Gelung while kami berulang sehingga kiri lebih besar daripada atau sama dengan kanan untuk merangkumi semua elemen dalam rentetan. Dalam setiap lelaran, kita dapati perbezaan antara aksara dalam kedudukan kiri dan kanan dengan menggunakan abs(str[kanan] - str[kiri]), yang mewakili berapa banyak pergerakan yang diperlukan untuk menjadikan kedua-dua aksara ini sama. Kami menambah nilai perbezaan ini pada kaunter larian kami untuk mendapatkan jumlah bilangan pergerakan.

Semasa kita bergerak ke arah tengah rentetan input, naikkan penunjuk kiri dan kurangkan penuding kanan. Sebaik sahaja tiada pertindihan antara penunjuk kiri dan kanan, kami menukar rentetan kepada palindrom.

Pada ketika ini, kami mengembalikan kiraan jumlah pergerakan yang disimpan dalam 'gerakan' Dalam main() langkah yang sama diikuti seperti sebelum ini di mana kami mengisytiharkan rentetan input baharu 'abcde' panggilan minMovesToMakePalindrome dengan hujah ini yang mengembalikan jumlah pergerakan minimum. kira nilai yang diberikan kepada pembolehubah baharu 'minMoves' sebelum mencetak nilai ini pada konsol.

Kesimpulan

Dalam teks berikut, dua alternatif dibentangkan, bertujuan untuk memberikan cerapan dan jawapan yang berpotensi kepada halangan mengira bilangan pergerakan yang diperlukan untuk menukar rentetan tertentu kepada palindrom dalam subrentetan melalui operasi aksara. Satu kaedah, dipanggil kaedah brute force, merangkumi semua subrentetan yang mungkin, manakala kaedah lain, dipanggil kaedah dua mata optimum, sangat mengurangkan bilangan pergerakan yang diperlukan. Pengekod boleh menggunakan mekanisme ini dengan mudah untuk menyelesaikan halangan yang serupa dan memperbaiki penyelesaiannya.

Atas ialah kandungan terperinci Bilangan pergerakan minimum yang diperlukan untuk membuat palindrom rentetan dengan menambah semua aksara subrentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!