Programme C pour trouver le nombre minimum d'insertions pour former un palindrome

Un palindrome est une corde égale à son inversion. Étant donné une chaîne, nous devons trouver le nombre minimum de caractères arbitraires insérés requis pour faire de la chaîne un palindrome. Nous verrons trois approches : d'abord l'approche récursive, puis nous mémoriserons cette solution, et enfin, nous mettrons en œuvre l'approche de programmation dynamique.

Méthode récursive

Exemple

#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;
}

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(2^N) car nous effectuons une sélection pour chaque insertion, où N est la taille de la chaîne donnée.

La complexité spatiale du code ci-dessus est O(N), c'est-à-dire lorsqu'il est utilisé dans des appels récursifs.

Méthode de mémoire

Exemple

#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;
}

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N^2) car nous stockons les résultats déjà calculés.

La complexité spatiale du code ci-dessus est O(N^2) car nous utilisons ici de l'espace supplémentaire.

Méthode de programmation dynamique

Exemple

#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;
}

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N^2) car nous utilisons ici des boucles for imbriquées.

La complexité spatiale du code ci-dessus est O(N^2) car nous utilisons ici de l'espace supplémentaire.

Conclusion

Dans ce tutoriel, nous avons implémenté trois méthodes pour trouver le nombre minimum d'insertions requis pour faire d'une chaîne donnée un palindrome. Nous avons implémenté la méthode récursive puis l'avons mémorisée. Enfin, nous avons implémenté la méthode tabulaire ou la méthode de programmation dynamique.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!