資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究Moser-de Bruijn 序列
題目要求列印 Moser-de Bruijn 序列的前 N 項，其中 N 將作為使用者輸入。
Moser-de Bruijn 序列是一個由整數構成的序列，這些整數不過是 4 的不同次冪的和，例如 1、4、16、64 等等。
該序列的前幾項包括 0、1、4、5、16、17、20、21、64……
該序列總是以零開頭，然後是 4 的不同次冪的和，例如 4⁰，即 1；4¹，即 4；然後是 4⁰ 和 4¹ 的和，即 5，依此類推。
在這個問題中，我們將得到任意正整數 N，我們的任務是列印 Moser-de Bruijn 序列直到 N 項。
讓我們透過以下示例瞭解這個問題。
輸入
N=6
輸出
0 1 4 5 16 17
解釋 - 給定的輸入是 6，這意味著我們需要列印 Moser-de Bruijn 序列的前 6 項，這就是我們所需的輸出。
輸入
N=12
輸出
0 1 4 5 16 17 20 21 64 65 68 69
解釋 - Moser-de Bruijn 序列的前 12 項是我們所需的輸出。我們可以透過將 4 的不同次冪相加來計算序列的第 N 項。
讓我們瞭解根據輸入中 N 的值列印 Moser-de Bruijn 序列前 N 項的演算法。
演算法
透過觀察 Moser-de Bruijn 序列中的數字，我們可以看到序列中的數字遵循它們之間的數學關係。
序列中的前幾個數字是 0、1、4、5、16、17、20、21、64、65、68、69、80、81、84……
序列中的數字只包含 4 的不同次冪和 4 的不同次冪的和。
如果我們從 0 開始考慮序列中數字的位置，我們可以觀察到 M(0)=0 且 M(1)=1。
並且每個第 N 項（其中 N 為偶數）可以由下式給出：
$$\mathrm{M(N)=4*M(N/2)}$$
類似地，每個第 N 項（其中 N 為奇數）可以由下式給出：
$$\mathrm{M(N)=4*M(N/2)+1}$$
讓我們嘗試使用上述關係找出 Moser-de Bruijn 序列的幾項。
$$\mathrm{M(0)=0\:\:\:M(1)=1}$$
M(2) 將等於 4*M(N/2)，因為在這種情況下 N 是偶數。所以 M(2)=4*1=4。
M(3) 將等於 4*M(N/2)+1，因為在這種情況下 N 是奇數。所以 M(3)=5。
同樣地，
$$\mathrm{M(4)=4*M(4/2)=4*4=16}$$
$$\mathrm{M(5)=4*M(5/2)+1=4*4+1=17}$$
我們可以使用此關係計算直到 N 的序列的所有項。我們將使用序列中數字之間的上述關係來列印 Moser-de Bruijn 序列的前 N 項。
方法 1（使用遞迴）
我們將使用遞迴來根據演算法中討論的公式查詢序列的第 i 項。為了實現遞迴以列印 Moser-de Bruijn 序列的前 N 項，需要遵循以下步驟：
為了找到序列的第 i 個數，我們將建立一個遞迴函式。
在函式中，如果 i=0，我們將返回 0；如果 i=1，我們將返回 1。對於 i 的所有其他值，我們將檢查 i 是偶數還是奇數。如果 i 是偶數，則返回 4*rec(i/2)；如果 i 是奇數，則返回 4*rec(i/2)+1。
為了解決所包含的子問題，我們可以透過使用遞迴計算第 i/2 項的值來獲得第 i 項的值。
在 for 迴圈中從 i=0 迭代到 i>N，以列印 Moser-de Bruijn 序列的前 N 項。
對於每次迭代，我們將呼叫遞迴函式以獲取序列中第 i 項的值並繼續列印它們。
示例
//C++ code to print the N terms of Moser-de Bruijn Sequence
#include <bits/stdc++.h>
using namespace std;
//recursive function to get the Nth term of the sequence
int rec(int N){
if(N==0){ //as M(0)=0
return 0;
}
else if(N==1){ //as M(1)=1
return 1;
}
else if(N&1){ //for the case when N is odd
return 4*rec(N/2)+1;
}
else{ //for the case when N is even
return 4*rec(N/2);
}
}
//to print the first N terms of the sequence
void print_sequence(int N){
//for printing each term upto N using the rec() function
for(int i=0;i<N;i++){
cout<<rec(i)<<" ";
}
}
int main()
{
int N; //for input value
N=22;
print_sequence(N); //calling the function
return 0;
}
輸出
0 1 4 5 16 17 20 21 64 65 68 69 80 81 84 85 256 257 260 261 272 273
方法 2（動態規劃）
眾所周知，動態規劃是對使用遞迴解決的問題的最佳化解決方案。因此，為了最佳化上述方法，我們將使用動態規劃的概念來列印 Moser-de Bruijn 序列的前 N 項。
在這裡，我們將把第 i 項的值儲存在一個大小為 N 的陣列中，這樣我們就無需為序列中的第 i 個數重複計算重複子問題的值。
下面介紹在方法中實現動態規劃以列印 Moser-de Bruijn 序列前 N 項的步驟：
我們將建立一個大小為 N 的向量來儲存序列的前 N 項。
為了將數字儲存在陣列中，我們將建立一個函式，在該函式中我們將使用演算法部分中討論的公式查詢序列的第 i 個數。
一旦向量被更新到序列的 N 項，我們將透過在 for 迴圈中從 i=0 迭代到 i
示例
//C++ code to print the first N terms of Moser-de Bruijn Sequence
#include <bits/stdc++.h>
using namespace std;
//function to update the vector using dp
void calculate_numbers(vector<int>& dp, int N){
dp[0]=0; //as M(0)=0
dp[1]=1; //M(1)=1
for(int i=2;i<N;i++){
if((i&1) == 0){ //if i is even
dp[i]=4*dp[i/2];
}
else{ //if i is odd
dp[i]=4*dp[i/2]+1;
}
}
}
//function to print the first N terms of the Moser-de Bruijn sequence
void print_sequence(vector<int>& dp, int N){
for(int i=0;i<N;i++){
cout<<dp[i]<<" ";
}
}
int main()
{
int N; //for taking input
N=35;
vector<int> dp(N,0); //to store first N terms of the sequence
//calling the function to update the array up to N
calculate_numbers(dp,N);
//to print the sequence
print_sequence(dp,N);
return 0;
}
輸出
0 1 4 5 16 17 20 21 64 65 68 69 80 81 84 85 256 257 260 261 272 273 276 277 320 321 324 325 336 337 340 341 1024 1025 1028
時間複雜度：O(N) 因為我們用 for 迴圈迭代 N 次來更新序列的 N 項。
空間複雜度：O(N) 因為我們使用了大小為 N 的向量來儲存序列的數字。
結論
本文討論了 Moser-de Bruijn 序列的概念。我們討論了使用數字之間數學關係查詢序列中任何第 N 項的演算法，我們在 C++ 中使用遞迴和動態規劃這兩種方法來實現我們的方法，以便更好地讓您理解。
我希望您覺得這篇文章有助於澄清您關於該主題的所有概念。
瀏覽量：164
