Zählen Sie die Anzahl der N-stelligen Nummern, die kein bestimmtes Präfix haben

Das Problem hierbei besteht darin, die Gesamtzahl der Zeichen „0“ bis „9“ zu bestimmen, die in einer Zeichenfolge der Länge N enthalten sind, indem eine Ganzzahl N und ein Zeichenfolgenpräfix-Array pre[] bereitgestellt werden, sodass es keine Eins gibt, die das enthält bereitgestelltes Präfix. Der Zweck dieses Artikels besteht darin, ein Programm zu implementieren, das die Anzahl der N-stelligen Zahlen ermittelt, die kein bestimmtes Präfix haben.

In der Programmiersprache C wird ein Satz unterschiedlicher Zeichenfolgen als Array bezeichnet, da ein Array eine lineare Kombination eines Satzes von Datenstücken ähnlichen Typs ist.

Wie wir bereits wissen, handelt es sich bei der Zeichenfolge um ein zeichenweises, eindimensionales Array, das mit einem Leer- oder Nullzeichen endet.

Beispiel Beispiel 1

Nehmen wir an, dass die Eingabe N = 2 ist,

The given prefix, pre = {“1”}

Output obtained: 90

Erklärung

Hier, außer {"01", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", Alle 2-stellige Zeichenfolgen außer „21“, „31“, „41“, „51“, „61“, „71“, „81“, „91“} sind gültig.

Beispiel Beispiel 2

Nehmen wir als Beispiel den Eingabewert N = 3.

The given prefix, pre = {“56”}

Output obtained: 990

Erklärung

Hier alles außer {"560", "561", "562", "563", "564", "565", "566", "567", "568", "569"} dreistellige Zeichenfolgen sind alle gültig.

Beispiel Beispiel 3

Sehen wir uns eine Eingabe N = 1 an,

The given prefix, pre = {“6”}

Output obtained: 9

Erklärung

Alle einstelligen Zeichenfolgen hier sind gültig, außer {"6"}.

Problemstellung

Implementieren Sie ein Programm, um die Anzahl der N-stelligen Zahlen zu ermitteln, die kein bestimmtes Präfix haben.

Methode

Um die Anzahl der N Ziffern ohne Angabe eines bestimmten Präfixes zu ermitteln, verwenden wir die folgende Methode.

Lösen Sie dieses Problem und finden Sie den Weg zu N Ziffern, die nicht das angegebene Präfix haben

Wenn man bedenkt, dass es für jede Position in der Zeichenfolge 10 Zeichenoptionen gibt, gibt es insgesamt (10N) potenzielle Zeichenfolgen. Anstatt die Gesamtzahl der gewünschten Zeichenfolgen zu zählen, subtrahieren Sie die Gesamtzahl der nicht gewünschten Zeichenfolgen. Das Zusammenführen von Präfixen mit denselben Anfangszeichen zu einem längeren Präfix vor der Iteration kann dazu führen, dass einige Duplikate entfernt werden.

Algorithmus

Suchalgorithmus zum Zählen von N Ziffern, der nicht das folgende Präfix hat

• Erster Schritt − Start

• Schritt 2 – Funktion definieren, um die Gesamtzahl der Zeichenfolgen der Länge N zu zählen, die das angegebene Präfix nicht enthalten

• Schritt 3 – Berechnen Sie die Gesamtzahl der vorhandenen Strings

• Schritt 4 – Erstellen Sie ein Array und die Zähler a und aCount und fügen Sie diese Präfixe darin ein

• Schritt 5 - Erstellen Sie ein neues Präfix-String-Array

• Schritt 6 – Iterieren Sie für jedes Startzeichen

• Schritt 7 – Durchlaufen Sie das Array, um das Präfix mit der Mindestgröße zu berechnen

• Schritt 8 – Fügen Sie nun alle diese minimalen Präfixe in ein neues Präfix-Array ein

• Schritt 9 – Über neue Präfixe iterieren

• Schritt 10 – Unerwünschte Zeichenfolgen abziehen

• Schritt 11 − Drucken Sie die erhaltenen Ergebnisse aus

• Schritt 12 − Stopp

Beispiel: C-Programm

Dies ist eine C-Programmimplementierung des obigen Algorithmus, um die Anzahl der N Ziffern zu ermitteln, die kein bestimmtes Präfix haben.

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

Ausgabe

70000

Fazit

Ähnlich können wir die Anzahl der N Ziffern ermitteln, die nicht das angegebene Präfix haben.

In diesem Beitrag wird die Herausforderung gelöst, ein Programm dazu zu bringen, eine N-stellige Anzahl zu finden, die kein bestimmtes Präfix hat.

C-Programmiercode wird hier zusammen mit dem Algorithmus bereitgestellt, um die Anzahl der N-stelligen Zahlen zu ermitteln, die kein bestimmtes Präfix haben.

Das obige ist der detaillierte Inhalt vonZählen Sie die Anzahl der N-stelligen Nummern, die kein bestimmtes Präfix haben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!