Comptez le nombre de nombres à N chiffres qui n'ont pas de préfixe donné

Le problème ici est de déterminer le nombre total de caractères « 0 » à « 9 » contenus dans une chaîne de longueur N, en fournissant un entier N et un tableau de préfixes de chaîne pre[] tel qu'il n'y en ait aucun dans ceux-ci. chaînes Un contenant le préfixe fourni. Le but de cet article est d'implémenter un programme qui trouve le nombre de nombres à N chiffres qui n'ont pas de préfixe donné.

En langage de programmation C, un ensemble de chaînes distinctes est appelé un tableau car un tableau est une combinaison linéaire d'un ensemble d'éléments de données de type similaire.

Comme nous le savons déjà, la chaîne est un tableau unidimensionnel caractère par caractère qui se termine par un caractère vide ou nul.

Exemple Exemple 1

Supposons l'entrée N = 2,

The given prefix, pre = {“1”}

Output obtained: 90

Explication

Ici, sauf {"01", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", Tous Les chaînes à 2 chiffres sauf "21", "31", "41", "51", "61", "71", "81", "91"} sont valides.

Exemple Exemple 2

Prenons la valeur d'entrée N = 3 comme exemple.

The given prefix, pre = {“56”}

Output obtained: 990

Explication

Ici, tout sauf {"560", "561", "562", "563", "564", "565", "566", "567", "568", "569"} chaînes à 3 chiffres sont tous valables.

Exemple Exemple 3

Regardons une entrée N = 1,

The given prefix, pre = {“6”}

Output obtained: 9

Explication

Toutes les chaînes à 1 chiffre ici sont valides sauf {"6"}.

Énoncé du problème

Implémentez un programme pour trouver le nombre de N chiffres qui n'ont pas de préfixe donné.

Méthode

Pour trouver le nombre de N chiffres sans donner de préfixe donné, on utilise la méthode suivante.

Solution à ce problème et trouver le chemin vers N nombre de chiffres qui n'a pas le préfixe donné

Considérant qu'il existe 10 options de caractères pour chaque position dans la chaîne, il y a (10N) chaînes potentielles au total. Au lieu de compter le nombre total de chaînes souhaitées, soustrayez le nombre total de chaînes dont vous ne voulez pas. La fusion de préfixes avec les mêmes caractères initiaux en un préfixe plus long avant l'itération peut entraîner la suppression de certains doublons.

Algorithme

Algorithme de recherche pour compter N chiffres qui n'ont pas le préfixe donné suivant

• Première étape − Démarrer

• Étape 2 - Définir une fonction pour compter le nombre total de chaînes de longueur N qui ne contiennent pas le préfixe donné

• Étape 3 - Calculez le nombre total de chaînes existantes

• Étape 4 - Créez un tableau et les compteurs a et aCount et insérez-y ces préfixes

• Étape 5 − Créez un nouveau tableau de chaînes de préfixes

• Étape 6 - Itérer pour chaque personnage de départ

• Étape 7 - Parcourez le tableau pour calculer le préfixe de taille minimale

• Étape 8 - Maintenant, mettez tous ces préfixes minimaux dans un nouveau tableau de préfixes

• Étape 9 - Itérer sur de nouveaux préfixes

• Étape 10 - Déduire les chaînes indésirables

• Étape 11 − Imprimez les résultats obtenus

• Étape 12 − Arrêtez

Exemple : programme C

Il s'agit d'une implémentation de programme C de l'algorithme ci-dessus pour trouver le nombre de N chiffres qui n'ont pas de préfixe donné.

#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX_LENGTH 10

// Function to calculate total strings of length N without the given prefixes
int totalStrings(int N, char pre[][MAX_LENGTH], int pre_Count){

   // Calculate total strings present
   int total = (int)(pow(10, N) + 0.5);
   
   // Make an array and counter a and aCount respectively and insert these prefixes with same character in the array
   char a[10][MAX_LENGTH];
   int aCount[10] = {0};
   for (int i = 0; i < pre_Count; i++)    {
      int index = pre[i][0] - '0';
      strcpy(a[index] + aCount[index] * MAX_LENGTH, pre[i]);
      aCount[index]++;
   }
   
   // Make a new array of prefixes strings
   char new_pre[pre_Count][MAX_LENGTH];
   int new_pre_count = 0;
   
   // Iterating for  each of the starting //character
   for (int x = 0; x < 10; x++){
      int m = N;
      
      // Iterate over the array to calculate minimum size prefix
      for (int j = 0; j < aCount[x]; j++){
         int p_length = strlen(a[x] + j * MAX_LENGTH);
         m = (m < p_length) ? m : p_length;
      }
      
      // now take all these minimum prefixes in the new array of prefixes
      for (int j = 0; j < aCount[x]; j++){
         int p_length = strlen(a[x] + j * MAX_LENGTH);
         if (p_length <= m){
            strcpy(new_pre[new_pre_count], a[x] + j * MAX_LENGTH);
            new_pre_count++;
         }
      }
   }
   
   // Iterating through the new prefixes
   for (int i = 0; i < new_pre_count; i++){
   
      // Subtract the unwanted strings
      total -= (int)(pow(10, N - strlen(new_pre[i])) + 0.5);
   }
   return total;
}

// The main function
int main(){
   int N = 5;
   char pre[][MAX_LENGTH] = {"1", "0", "2"};
   int pre_Count = sizeof(pre) / sizeof(pre[0]);
   printf("%d\n", totalStrings(N, pre, pre_Count));
   return 0;
}

Sortie

70000

Conclusion

De même, nous pouvons trouver le nombre de N chiffres qui n'ont pas le préfixe donné.

Dans cet article, le défi consistant à faire en sorte qu'un programme trouve un nombre à N chiffres qui n'a pas de préfixe donné est résolu.

Le code de programmation C est fourni ici avec l'algorithme pour trouver le nombre de nombres à N chiffres qui n'ont pas de préfixe donné.

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!