Golomb-Sequenz

Kolumbianische Folge – Die Columbus-Folge ist eine nicht abnehmende Folge von ganzen Zahlen, wobei der Wert des n-ten Elements die Häufigkeit ist, mit der die ganze Zahl n in der Folge vorkommt.

Einige Begriffe der Columbus-Sequenz sind:

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9 , 9, 10, 10, 10, 10, …

Hier können wir sehen, dass das 5. Element 3 ist und 5 auch dreimal in der Sequenz vorkommt.

Item 6 ist 4 und 6 erscheint auch 4 Mal in der Sequenz.

Eigenschaften der Columbus-Folge – Der erste Term der Sequenz ist 1 und der n-te Term ist 1 + die Anzahl der Terme in der Sequenz, die kleiner oder gleich dem n-n-ten Term sind.

Problemstellung

Gegeben eine ganze Zahl n. Finden Sie die ersten n Terme in der Columbus-Folge.

Beispiel 1

Input: n = 4

Output: [1, 2, 2, 3]

Beispiel 2

Input: n = 7

Output: [1, 2, 2, 3, 3, 4, 4]

Methode 1: Rekursion verwenden

Unter Verwendung der Eigenschaften der Columbus-Folge ist der erste Term der Folge 1. Um den n-ten Term zu finden, verwenden wir die folgende Eigenschaft: Der n-te Term ist 1 + die Anzahl der Terme kleiner oder gleich dem n – n-ten Term in der Sequenz.

Anwenden dieser Methode in einer rekursiven Funktion: Wenn das n-te Element die kleinste positive ganze Zahl ist, die nicht früher als n - golomb(golomb(n - 1)) Mal in der Sequenz vorkommt, dann stellen Sie sicher, dass diese Eigenschaft erfüllt ist, wobei golomb ( ) besteht darin, die rekursive Funktion des n-ten Termes der Columbus-Folge zu finden.

Pseudocode

procedure golomb (n)
   if n == 1
      ans = 1
   end if
   ans = 1 + golomb(n - golomb(golomb(n - 1)))
end procedure
procedure golombSeq (n)
   seq[n] = {0}
   for i = 1 to n
      seq[i - 1] = golomb(i)
   ans = seq
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm verwenden wir die Rekursion, um die Columbus-Folge zu finden.

#include <bits/stdc++.h>
using namespace std;

// Function to find golomb number
int golomb(int n){

   // First element is 1
   if (n == 1) {
      return 1;
   }
   
   // Satisfying property of golomb sequence for the nth number
   return 1 + golomb(n - golomb(golomb(n - 1)));
}

// Function to generate golomb sequence
vector<int> golombSeq(int n){
   vector<int> seq(n, 0);
   for (int i = 1; i <= n; i++){
      seq[i - 1] = golomb(i);    
      }
   return seq;
}
int main(){
   int n = 15;
   vector<int> seq = golombSeq(n);
   cout << "Golomb sequence up to " <<n << " terms: ";
   for (int i = 0; i < n; i++)    {
      cout << seq[i] << " ";
   }
   return 0;
} 

Ausgabe

Golomb sequence up to 15 terms: 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6

Zeitliche Komplexität – O(n^2), da jedes Element durch rekursive Berechnung des vorherigen Elements berechnet wird.

Raumkomplexität – O(n)

Methode 2: Rekursion mit Memoisierung

Um uns an den rekursiven Code zu erinnern, erstellen wir eine Karte, um die zuvor im obigen Code rekursiv berechneten Werte zu speichern. Überprüfen Sie dann bei der Berechnung jeder Zahl zunächst, ob die vorherige Zahl berechnet wurde. Wenn ja, verwenden Sie das vorherige Berechnungsergebnis, andernfalls führen Sie die Berechnung durch.

Pseudocode

golomb (n, t)
   if n == 1
      ans = 1
   end if
   if n is present in t
      ans = t[n]
   end if
   ans = 1 + golomb(n - golomb(golomb(n - 1, t), t), t)
   t[n] = ans
end procedure
procedure golombSeq (n)
   seq[n] = {0}
   Initialize map: t
   for i = 1 to n
       seq[i - 1] = golomb(i, t)
   ans = seq
end procedure

Beispiel: C++-Implementierung

Im Programm unten werden die Ergebnisse früherer Berechnungen in einer Karte gespeichert, auf die bei der Berechnung von Artikeln zugegriffen wird.

#include <bits/stdc++.h>
using namespace std;

// Function to find golomb number
int golomb(int n, map<int, int> &t){

   // First term is 1
   if (n == 1){
      return 1;
   }
   
   // Checking if the term is previously computed
   if (t.find(n) != t.end()){
      return t[n];
   }
   int result = 1 + golomb(n - golomb(golomb(n - 1, t), t), t);
   
   // Saving the term to map
   t[n] = result;
   return result;
}

// Function to generate golomb sequence
vector<int> golombSeq(int n){
   vector<int> seq(n, 0);
   map<int, int> t;
   for (int i = 1; i <= n; i++){
      seq[i - 1] = golomb(i, t);
   }
   return seq;
}
int main(){
   int n = 15;
   vector<int> seq = golombSeq(n);
   cout << "Golomb sequence up to " <<n << " terms: ";
   for (int i = 0; i < n; i++){
      cout << seq[i] << " ";
   }
   return 0;
}

Ausgabe

Golomb sequence up to 15 terms: 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6

Zeitkomplexität – O(nlogn)

Raumkomplexität – O(n)

Methode 3: Dynamische Programmierung

Mit dynamischer Programmierung erstellen wir eine dp-Tabelle der Größe n+1 * 1. Zählen Sie dann mithilfe der oben verwendeten Eigenschaften, wobei die n-te Zahl 1 + golomb(n - golomb(golomb(n - 1))) ist, alle Zahlen in der Folge und speichern Sie sie in einem Vektor.

Pseudocode

procedure golombSeq (n)
   seq[n] = {0}
   seq[0] = 1
      Initialize the dp table of size n+1, 1
   for i = 2 to n
      dp[i] = dp[i - dp[dp[i - 1]]] + 1
   for i = 1 to n
      seq[i-1] = dp[i]
   ans = seq
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm verwenden wir eine dynamische Programmiermethode, um dieses Problem zu lösen.

#include <bits/stdc++.h>
using namespace std;
// Function to generate golomb sequence
vector<int> golombSeq(int n){
   vector<int> seq(n, 0);
   
   // First term is 1
   seq[0] = 1;
   vector<int> dp(n + 1, 1);
   for (int i = 2; i <= n; i++){
   
      // Satisfying the property that nth term is 1 + golomb(n - golomb(golomb(n - 1)))
      dp[i] = dp[i - dp[dp[i - 1]]] + 1;
   }
   for (int i = 1; i <= n; i++){
      seq[i - 1] = dp[i];
   }
   return seq;
}
int main(){
   int n = 15;
   vector<int> seq = golombSeq(n);
   cout << "Golomb sequence up to " <<n << " terms: ";
   for (int i = 0; i < n; i++){
      cout << seq[i] << " ";
   }
   return 0;
}

Ausgabe

Golomb sequence up to 15 terms: 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 

Fazit

Zusammenfassend lässt sich sagen, dass wir zum Finden der Columbus-Folge die Eigenschaften der n-ten Zahl der Columbus-Folge verwenden, um alle Zahlen in der Folge zu finden. Dabei verwenden wir verschiedene Methoden mit einer zeitlichen Komplexität von O(n^2) bis O(n). .

Das obige ist der detaillierte Inhalt vonGolomb-Sequenz. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!