数据结构
网络
关系数据库管理系统 (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
