哥倫布序列 - 哥倫布序列是一個非遞減的整數序列，其中第 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 - n 項的項數。
給定一個整數n。求出哥倫布序列中的前 n 項。
Input: n = 4
Output: [1, 2, 2, 3]
Input: n = 7
Output: [1, 2, 2, 3, 3, 4, 4]
利用哥倫布數列的性質，序列的第一項是 1。為了找到第 n 項，我們使用以下性質：第 n 項是 1 序列中小於或等於的項數到第 n - n 項。
在遞歸函數中應用此方法，如果第n 項是序列中出現時間不早於n - golomb(golomb(n - 1)) 次的最小正整數，則確保滿足該屬性，其中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
在下面的程式中，我們使用遞歸來求哥倫布序列。
#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)
為了記住遞歸程式碼，我們建立一個映射來儲存先前在上述程式碼中遞歸計算的值。然後計算每個數時，先檢查前一個數是否計算過，如果是則取前一個計算結果，否則進行計算。
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
在下面的程式中，先前的計算結果儲存在一個映射中，在計算項目時可以存取該映射。
#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)
使用動態規劃，我們建立一個大小為 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
在下面的程式中，我們使用動態規劃方法來解決這個問題。
#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
總之，為了找出哥倫布序列，我們使用哥倫布序列的第n 個數字的屬性來找出序列中的所有數字，並使用時間複雜度從O(n^2) 到O(n) 的各種方法。
以上是Golomb序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！
