C++ 高尔朋数列

高尔朋数列 - 高尔朋数列是一个非递减的整数序列，其中第n个项的值是整数n在序列中出现的次数。

高尔朋数列的一些项为：

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

正如我们所看到的，第5个项是3，数字5在序列中也出现了3次。

第6个项是4，数字6在序列中也出现了4次。

高尔朋数列的性质 - 序列的第一个项是1，第n个项是1加上前n-1个项中小于等于n的项的数量。

问题陈述

给定一个整数n，找出高尔朋数列的前n个项。

示例1

Input: n = 4

Output: [1, 2, 2, 3]

示例2

Input: n = 7

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

递归方法

使用Golomb序列的性质，序列的第一项是1。对于找到第n项，我们使用这样的性质：第n项是序列中小于等于n – n项的项数再加上1。

将此方法应用于递归函数中，如果第n项是最小的正整数，并且在序列中出现的次数不超过n – golomb(golomb(n – 1))次，则可以确保满足该性质。其中golomb()是用于找到golomb序列第n项的递归函数。

伪代码

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

示例：C++实现

在下面的程序中，我们使用递归来查找Golomb数列。

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

输出

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

时间复杂度 – O(n^2)，因为每个项都通过递归计算前面的项。

空间复杂度 – O(n)

方法2：递归与记忆化

为了记忆化递归代码，我们创建一个映射来存储在上述代码中递归计算的先前计算值。然后，对于计算每个数字，首先检查前一个数字是否计算过，如果已经计算过，则使用先前计算得到的结果，否则重新计算。

伪代码

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

示例：C++实现

在以下程序中，先前的计算结果存储在一个地图中，在计算术语时访问该地图。

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

输出

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

时间复杂度 − O(nlogn)

空间复杂度 − O(n)

方法3：动态规划

使用动态规划，我们创建一个大小为 n+1 * 1 的dp表。然后使用上面使用的性质，即第n个数字为 1 + golomb(n – golomb(golomb(n – 1)))，计算序列中的所有数字并将其存储在向量中。

伪代码

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

示例：C++实现

在下面的程序中，我们使用动态规划方法来解决这个问题。

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

输出

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

结论

总之，为了找到Golomb序列，我们利用了Golomb序列的第n个数的性质，采用时间复杂度从O(n^2)到O(n)的各种方法找到了序列中的所有数字。