C++ 莫泽-德布鲁因序列

问题陈述包括打印出莫泽-德布鲁因序列的前N项，其中N将在用户输入中给出。

莫泽-德布鲁因序列是一个由整数组成的序列，这些整数恰好是4的不同幂次的和，例如1、4、16、64等等。

序列的前几个数字包括0、1、4、5、16、17、20、21、64……

序列总是以零开始，然后是4的不同幂次的和，例如 $\mathrm{4^{0}}$ 即 $\mathrm{4^{1}:即4}$ ，然后是 $\mathrm{4^{0}:and:4^{1}:i.e:5}$ 等等。

在这个问题中，我们将给定任何正整数N，我们的任务是打印出莫泽-德布鲁因序列的前N项。

让我们通过下面给出的示例来理解这个问题。

输入

N=6

输出

0  1  4  5  16  17

解释 − 给定的输入是6，这意味着我们需要打印莫泽-德布鲁因序列的前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的不同幂和这些幂的和。

如果我们将序列中的数字的位置从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（动态规划）

众所周知，动态规划是用递归解决问题的优化解决方案。因此，为了优化上述方法，我们将使用动态规划的概念来打印莫泽-德布鲁因序列的前N个项。

在这里，我们将在一个N大小的数组中存储第i个项的值，以便我们不需要计算序列中第i个数字的重复子问题的值。

实现动态规划的步骤以打印莫泽-德布鲁因序列的前N项如下：

我们将建立一个大小为N的向量来存储序列的前N个项。
为了将数字存储在数组中，我们将创建一个函数，在该函数中，我们将使用算法部分讨论过的公式找到序列的第i个数字。
一旦向量被更新到序列的N项，我们将通过在for循环中从i=0到i<N迭代打印向量中存储的数字，这将是莫泽-德布鲁因序列的前N个项。

例子

//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) 因为我们在循环中迭代N次，更新数列的N个数。

空间复杂度：O(N) 因为我们使用了大小为N的向量来存储数列中的数字。