Program C untuk mencari bilangan sisipan minimum untuk membentuk palindrom

Palindrom ialah rentetan yang sama dengan penyongsangannya. Diberi rentetan, kita perlu mencari bilangan minimum aksara sewenang-wenang yang disisipkan yang diperlukan untuk menjadikan rentetan itu sebagai palindrom. Kami akan melihat tiga pendekatan: pertama pendekatan rekursif, kemudian kami akan menghafal penyelesaian ini, dan akhirnya, kami akan melaksanakan pendekatan pengaturcaraan dinamik.

Kaedah rekursif

Contoh

#include <stdio.h> // library for input and output
#include <limits.h> // library to get the integer limits 
#include <string.h> // library for strings 
// function to find the minimum of two number 
// as it is not present in the c language 
int findMin(int a, int b){ 
   if(a < b){
      return a;
   } else{
      return b;
   }
}
// creating the function to find the required answer we will make recursive calls to it 
int findAns(char str[], int start, int end){
   // base condition
   if (start > end){
      return INT_MAX;
   }
   else if(start == end){
      return 0;
   }
   else if (start == end - 1){
      if(str[start] == str[end]){
         return 0;
      }
      else return 1;
   }	
   // check if both start and end characters are the same make callson the basis of that 
   if(str[start] == str[end]){
      return findAns(str,start+1, end-1);
   } else{
      return 1+ findMin(findAns(str,start,end-1), findAns(str,start+1,end));
   }
}
// main function 
int main(){
   char str[] = "thisisthestring"; // given string
   printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str,0,strlen(str)-1));
   return 0;
}

Output

The minimum number of insertions required to form the palindrome is: 8

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(2^N) kerana kami membuat pilihan untuk setiap sisipan, dengan N ialah saiz rentetan yang diberikan.

Kerumitan ruang kod di atas ialah O(N), iaitu, apabila digunakan dalam panggilan rekursif.

Kaedah ingatan

Contoh

#include <stdio.h> // library for input and output
#include <limits.h> // library to get the integer limits 
#include <string.h> // library for strings 

int memo[1005][1005]; // array to store the recursion results 
// function to find the minimum of two number 
// as it is not present in the c language 
int findMin(int a, int b){ 
   if(a < b){
      return a;
   } else{
      return b;
   }
}
// creating the function to find the required answer we will make recursive calls to it 
int findAns(char str[], int start, int end){
   // base condition
   if (start > end){
      return INT_MAX;
   }
   else if(start == end){
      return 0;
   }
   else if (start == end - 1){
      if(str[start] == str[end]){
         return 0;
      }
      else return 1;
   }
   // if already have the result 
   if(memo[start][end] != -1){
      return memo[start][end];
   }	
   // check if both start and end characters are same make calls on basis of that 
    if(str[start] == str[end]){
      memo[start][end] =  findAns(str,start+1, end-1);
   } else{
        memo[start][end] =  1+ findMin(findAns(str,start,end-1), findAns(str,start+1,end));
   }
   return memo[start][end];
}
int main(){
   char str[] = "thisisthestring"; // given string	
   //Initializing the memo array 
   memset(memo,-1,sizeof(memo));
   printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str,0,strlen(str)-1));	
   return 0;
}

Output

The minimum number of insertions required to form the palindrome is: 8

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N^2) kerana kami menyimpan hasil yang telah dikira.

Kerumitan ruang kod di atas ialah O(N^2) kerana kami menggunakan ruang tambahan di sini.

Kaedah pengaturcaraan dinamik

Contoh

#include <stdio.h> // library for input and output
#include <limits.h> // library to get the integer limits 
#include <string.h> // library for strings 
    
// function to find the minimum of two number 
// as it is not present in the c language 
int findMin(int a, int b){ 
   if(a < b){
      return a;
   } else{
      return b;
   }
}
// creating a function to find the required answer 
int findAns(char str[], int len){
   // creating the table and initialzing it 
   int memo[1005][1005]; 
   memset(memo,0,sizeof(memo));	
   // filling the table by traversing over the string 
   for (int i = 1; i < len; i++){
      for (int start= 0, end = i; end < len; start++, end++){
         if(str[start] == str[end]){
            memo[start][end] = memo[start+1][end-1];
         } else{
              memo[start][end] = 1 + findMin(memo[start][end-1], memo[start+1][end]);
         }
      }
   }
   // return the minimum numbers of interstion required for the complete string 
      return memo[0][len-1];
}
int main(){
   char str[] = "thisisthestring"; // given string	
   // calling to the function 
   printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str, strlen(str)));	
   return 0;
}

Output

The minimum number of insertions required to form the palindrome is: 8

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N^2) kerana kami menggunakan bersarang untuk gelung di sini.

Kerumitan ruang kod di atas ialah O(N^2) kerana kami menggunakan ruang tambahan di sini.

Kesimpulan

Dalam tutorial ini, kami melaksanakan tiga kaedah untuk mencari bilangan sisipan minimum yang diperlukan untuk menjadikan rentetan tertentu sebagai palindrom. Kami melaksanakan kaedah rekursif dan kemudian menghafalnya. Akhirnya, kami melaksanakan kaedah jadual atau kaedah pengaturcaraan dinamik.

Atas ialah kandungan terperinci Program C untuk mencari bilangan sisipan minimum untuk membentuk palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!