Séquence de Golomb

Séquence colombienne - La séquence Columbus est une séquence non décroissante d'entiers où la valeur du nième élément est le nombre de fois que l'entier n apparaît dans la séquence.

Certains termes de la séquence de Colomb sont : 

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, …

Ici, nous pouvons voir que le 5ème élément est 3, et 5 apparaît également 3 fois dans la séquence.

L'élément 6 est 4, et 6 apparaît également 4 fois dans la séquence.

Propriétés de la séquence de Columbus - Le premier terme de la séquence est 1 et le nième terme est 1 + le nombre de termes de la séquence inférieur ou égal au n - nième terme.

Énoncé du problème

Étant donné un entier n. Trouvez les n premiers termes de la séquence de Columbus.

Exemple 1

Input: n = 4

Output: [1, 2, 2, 3]

Exemple 2

Input: n = 7

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

Méthode 1 : Utiliser la récursion

En utilisant les propriétés de la séquence de Columbus, le premier terme de la séquence est 1. Pour trouver le nième terme, on utilise la propriété suivante : Le nième terme est 1 + le nombre de termes inférieur ou égal au n - nième terme de la séquence.

En appliquant cette méthode dans une fonction récursive, si le nième élément est le plus petit entier positif qui apparaît au plus tôt n - golomb(golomb(n - 1)) fois dans la séquence, alors assurez-vous que cette propriété est satisfaite, où golomb ( ) consiste à trouver la fonction récursive du nième terme de la séquence de Columbus.

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

Exemple : implémentation C++

Dans le programme ci-dessous, nous utilisons la récursion pour trouver la séquence de Columbus.

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

Sortie

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

Complexité temporelle - O(n^2) car chaque élément est calculé en calculant de manière récursive l'élément précédent.

Complexité spatiale - O(n)

Méthode 2 : Récursion avec mémoïsation

Pour mémoriser le code récursif, nous créons une carte pour stocker les valeurs précédemment calculées de manière récursive dans le code ci-dessus. Ensuite, lors du calcul de chaque nombre, vérifiez d'abord si le nombre précédent a été calculé, si c'est le cas, prenez le résultat du calcul précédent, sinon effectuez le calcul.

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

Exemple : implémentation C++

Dans le programme ci-dessous, les résultats des calculs précédents sont stockés dans une carte accessible lors du calcul des éléments.

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

Sortie

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

Complexité temporelle - O(nlogn)

Complexité spatiale - O(n)

Méthode 3 : Programmation dynamique

En utilisant la programmation dynamique, nous créons une table dp de taille n+1 * 1. Ensuite, en utilisant les propriétés utilisées ci-dessus, où le nième nombre est 1 + golomb(n - golomb(golomb(n - 1))), comptez tous les nombres de la séquence et stockez-les dans un vecteur.

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

Exemple : implémentation C++

Dans le programme ci-dessous, nous utilisons la méthode de programmation dynamique pour résoudre ce problème.

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

Sortie

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

Conclusion

En résumé, pour trouver la séquence de Columbus, nous utilisons les propriétés du nième nombre de la séquence de Columbus pour trouver tous les nombres de la séquence, en utilisant diverses méthodes avec une complexité temporelle allant de O(n^2) à O(n) .

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!