Program Python: Cari bilangan putaran minimum yang diperlukan untuk mendapatkan rentetan sebenar?

Memahami cara mengendalikan rentetan dengan cekap ialah tugas pengaturcaraan asas yang boleh meningkatkan prestasi kod anda dengan ketara. Mencari bilangan putaran minimum yang diperlukan untuk menghasilkan rentetan yang dikehendaki daripada rentetan yang diputar ialah cabaran yang menarik dalam manipulasi rentetan. Situasi seperti pemprosesan teks, kriptografi dan pemampatan data selalunya melibatkan masalah ini.

Pertimbangkan kes di mana rentetan diputar ke kanan dengan jumlah tertentu. Matlamatnya adalah untuk mencari bilangan putaran minimum yang diperlukan untuk menukar rentetan kembali kepada bentuk asalnya. Dengan mencari penyelesaian kepada masalah ini, kita boleh mengetahui lebih lanjut tentang struktur rentetan dan mendapatkan maklumat yang berguna.

Artikel ini akan melihat dua kaedah untuk menentukan bilangan putaran minimum yang diperlukan untuk mengembalikan rentetan asal daripada rentetan yang diputar. Python, bahasa pengaturcaraan yang fleksibel dan popular yang terkenal dengan kebolehbacaan dan kemudahan penggunaannya, akan digunakan untuk mempraktikkan teknologi ini.

Kaedah

Untuk mencari dalam Python untuk mendapatkan bilangan putaran minimum rentetan sebenar, kita boleh mengikuti dua kaedah -

• Gunakan kekerasan.

• Gunakan sambil gelung dalam fungsi yang ditentukan pengguna.

Mari kita periksa dua kaedah ini -

Kaedah 1: Gunakan kekerasan

Gunakan kaedah brute force untuk memutarkan rentetan pertama dalam semua kedudukan yang mungkin dan kemudian membandingkan rentetan kedua dengan rentetan pertama yang diputar. Kami menjejaki bilangan putaran minimum yang diperlukan untuk mendapatkan rentetan kedua dengan mengulangi semua putaran yang boleh dilaksanakan. Selepas gelung berakhir, jika pembolehubah putaran minimum masih infiniti, adalah mustahil untuk mendapatkan rentetan kedua dengan memutar rentetan pertama. Jika tidak, kami mengembalikan bilangan putaran minimum yang diperlukan. Kerumitan masa kaedah ini ialah O(n^2), dengan n ialah panjang rentetan pertama.

Algoritma

Langkah-langkah untuk mencari bilangan putaran minimum dalam Python untuk mendapatkan rentetan sebenar adalah seperti berikut -

Langkah 1- Buat fungsi yang mengambil dua rentetan sebagai input.

Langkah 2- Buat pembolehubah dengan nilai awal infiniti untuk menjejaki bilangan putaran minimum yang diperlukan.

Langkah 3- Lelaran melalui nilai yang mungkin dari 0 hingga panjang rentetan pertama.

Langkah 4- Rentetan pertama hendaklah diputar mengikut kedudukan indeks semasa. Ini mengesahkan bahawa rentetan kedua dan rentetan yang diputar adalah sama. Jika ya, tukar nilai pembolehubah kepada nilai minimum antara nilai minimum semasa dan indeks semasa.

Langkah 5− Jika pembolehubah putaran minimum masih ditetapkan kepada infiniti, kembalikan -1 (menunjukkan bahawa tidak mungkin untuk mendapatkan rentetan kedua dengan memutar rentetan pertama).

Langkah 6- Jika tiada, kembalikan pembolehubah putaran minimum.

Contoh

def min_rotations_bf(s1, s2):
   min_rotations = float('inf')

   for i in range(len(s1)):
      rotated = s1[i:] + s1[:i]
      if rotated == s2:
         min_rotations = min(min_rotations, i)

   if min_rotations == float('inf'):
      return -1
   else:
      return min_rotations


# Example usage
s1 = "program"
s2 = "grampro"
bf_result = min_rotations_bf(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations (Brute Force):", bf_result)

Output

String 1: program
String 2: grampro
Minimum rotations (Brute Force): 3

Kaedah 2: Menggunakan gelung sementara dalam fungsi yang ditentukan pengguna

Apa yang berfungsi ialah menggunakan rentetan bercantum untuk mengesahkan bahawa rentetan kedua wujud, dan bukannya melakukan putaran rentetan eksplisit. Jika rentetan kedua tidak boleh diambil dengan putaran rentetan pertama kerana dua rentetan adalah panjang yang berbeza, kita kembalikan -1. Dengan menentukan sama ada rentetan kedua ialah subrentetan rentetan bercantum, kita boleh mengetahui berapa banyak putaran yang diperlukan untuk memisahkan rentetan kedua daripada rentetan yang pertama. Untuk menentukan bilangan putaran minimum, jika rentetan kedua ditemui sebagai subrentetan, kami mengira indeks dan membahagikannya dengan panjang rentetan pertama. Kerumitan masa kaedah ini ialah O(n), dengan n ialah panjang rentetan pertama.

Algoritma

Langkah-langkah untuk mencari bilangan putaran minimum dalam Python untuk mendapatkan rentetan sebenar adalah seperti berikut -

Langkah 1- Buat fungsi yang mengambil dua rentetan sebagai input.

Langkah 2- Jika panjang kedua-dua tali tidak sama, kembalikan -1 (kerana rentetan kedua tidak boleh diperolehi dengan memutarkan rentetan pertama).

Langkah 3- Buat rentetan sementara dengan menggabungkan rentetan pertama dengan dirinya sendiri.

Langkah 4 - Jika rentetan kedua ialah subrentetan rentetan sementara, kembalikan bilangan putaran minimum yang diperlukan sebagai indeks rentetan kedua dalam rentetan sementara dibahagikan dengan panjang rentetan pertama.

Langkah 5− Jika tidak, kembalikan -1.

Contoh

def min_rotations_efficient(s1, s2):
   if len(s1) != len(s2):
      return -1

   rotations = 0
   n = len(s1)

   # Check for left rotations
   while rotations < n:
      if s1 == s2:
         return rotations
      s1 = s1[1:] + s1[0]
      rotations += 1

   # Check for right rotations
   s1 = s1[-1] + s1[:-1]
   rotations = 1

   while rotations <= n:
      if s1 == s2:
         return rotations
      s1 = s1[-1] + s1[:-1]
      rotations += 1

   return -1
# Example usage
s1 = "program"
s2 = "grampro"
efficient_result = min_rotations_efficient(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations ", efficient_result)

Output

String 1: program
String 2: grampro
Minimum rotations  3

Kesimpulan

Dalam artikel ini, kami melihat dua kaedah untuk mengira bilangan putaran minimum yang diperlukan untuk menukar rentetan yang diberikan kepada rentetan lain. Kaedah kedua menggunakan rentetan bercantum untuk memeriksa sama ada rentetan kedua wujud, manakala kaedah brute force memutar rentetan pertama setiap bilangan kedudukan yang boleh dilaksanakan. Seseorang boleh memilih strategi terbaik untuk menyelesaikan masalah ini dalam Python bergantung pada saiz input dan kecekapan yang diperlukan. Terima kasih kepada kaedah ini, anda kini boleh mengira bilangan putaran minimum yang diperlukan untuk mengekstrak rentetan sasaran daripada rentetan yang diberikan.

Atas ialah kandungan terperinci Program Python: Cari bilangan putaran minimum yang diperlukan untuk mendapatkan rentetan sebenar?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!