Urutan Golomb

Jujukan Kolombia - Jujukan Columbus ialah jujukan integer tidak menurun dengan nilai item ke-n ialah bilangan kali integer n muncul dalam jujukan.

Beberapa istilah jujukan Columbus ialah,

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

Di sini, kita dapat melihat bahawa item ke-5 ialah 3, dan 5 juga muncul 3 kali dalam urutan.

Item 6 ialah 4, dan 6 juga muncul 4 kali dalam urutan.

Sifat Jujukan Columbus - Sebutan pertama jujukan ialah 1 dan sebutan ke-n ialah 1 + bilangan sebutan dalam jujukan kurang daripada atau sama dengan sebutan ke-n.

Pernyataan Masalah

Diberi integer n. Cari n sebutan pertama dalam jujukan Columbus.

Contoh 1

Input: n = 4

Output: [1, 2, 2, 3]

Contoh 2

Input: n = 7

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

Kaedah 1: Gunakan rekursi

Menggunakan sifat jujukan Columbus, sebutan pertama jujukan ialah 1. Untuk mencari sebutan ke-n, kita menggunakan sifat berikut: Sebutan ke-n ialah 1 + bilangan sebutan kurang daripada atau sama dengan sebutan ke-n dalam jujukan.

Menggunakan kaedah ini dalam fungsi rekursif, jika item ke-n ialah integer positif terkecil yang muncul tidak lebih awal daripada n - golomb(golomb(n - 1)) kali dalam jujukan, maka pastikan sifat ini berpuas hati, di mana golomb ( ) adalah untuk mencari fungsi rekursif bagi sebutan ke-n bagi jujukan Columbus.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program di bawah, kami menggunakan rekursi untuk mencari jujukan 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;
} 

Output

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

Kerumitan masa - O(n^2) kerana setiap item dikira dengan mengira item sebelumnya secara rekursif.

Kerumitan ruang - O(n)

Kaedah 2: Rekursi dengan menghafal

Untuk mengingati kod rekursif, kami mencipta peta untuk menyimpan nilai yang dikira secara rekursif sebelum ini dalam kod di atas. Kemudian apabila mengira setiap nombor, semak dahulu sama ada nombor sebelumnya telah dikira. Jika ya, ambil keputusan pengiraan sebelumnya, jika tidak lakukan pengiraan.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program di bawah, hasil pengiraan sebelumnya disimpan dalam peta yang boleh diakses semasa mengira item.

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

Output

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

Kerumitan masa - O(nlogn)

Kerumitan ruang - O(n)

Kaedah 3: Pengaturcaraan Dinamik

Menggunakan pengaturcaraan dinamik, kami mencipta jadual dp bersaiz n+1 * 1. Kemudian menggunakan sifat yang digunakan di atas, di mana nombor ke-n ialah 1 + golomb(n - golomb(golomb(n - 1))), kira semua nombor dalam jujukan dan simpannya dalam vektor.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program di bawah, kami menggunakan kaedah pengaturcaraan dinamik untuk menyelesaikan masalah ini.

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

Output

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

Kesimpulan

Ringkasnya, untuk mencari jujukan Columbus, kami menggunakan sifat nombor ke-n bagi jujukan Columbus untuk mencari semua nombor dalam jujukan, menggunakan pelbagai kaedah dengan kerumitan masa antara O(n^2) hingga O(n) .

Atas ialah kandungan terperinci Urutan Golomb. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!