M序列

1. 信息安全

主要用在加密解密上面

2. 通信行業(yè)

CDMA通信的行業(yè)的信息

m序列是最長線性移位寄存器序列的簡稱，是一種偽隨機序列、偽噪聲(PN)碼或偽隨機碼?？梢灶A(yù)先確定并且可以重復(fù)實現(xiàn)的序列稱為確定序列;既不能預(yù)先確定又不能重復(fù)實現(xiàn)的序列稱隨機序列;不能預(yù)先確定但可以重復(fù)產(chǎn)生的序列稱偽隨機序列。

m序列是目前廣泛應(yīng)用的一種偽隨機序列，其在通信領(lǐng)域有著廣泛的應(yīng)用，如擴頻通信，衛(wèi)星通信的碼分多址，數(shù)字?jǐn)?shù)據(jù)中的加密、加擾、同步、誤碼率測量等領(lǐng)域。

在所有的偽隨機序列中，m序列是最重要、最基本的一種偽隨機序列。它容易產(chǎn)生，規(guī)律性強，有很好的自相關(guān)性和較好的互相關(guān)特性。在IS-95的反向信道中，選擇了m序列的PN碼作為地址碼，利用不同相位m序列幾乎正交的特性來為每個用戶的業(yè)務(wù)信道分配了一個相位。

對于一個n級反饋移位寄存器來說，最多可以有2^n 個狀態(tài)，對于一個線性反 饋移位寄存器來說，全"0"狀態(tài)不會轉(zhuǎn)入其他狀態(tài)，所以線性移位寄存器的序列的最長周期為 2^n-1。當(dāng)n級線性移位寄存器產(chǎn)生的序列{ai}的周期為T= 2^n-1時，稱{ai}為n級m序列。

當(dāng)反饋函數(shù)f(a1,a2,a3,…an)為非線性函數(shù)時，便構(gòu)成非線性移位寄存器，其輸出序列為非線性序列。輸出序列的周期最大可達 2^n ，并稱周期達到最大值的非線性移位寄存器序列為M序列。

最長上升子序列

Longest Increasing Subsequence

最長上升子序列:

有兩種基本方法:兩個時間復(fù)雜度分別為O(n^2)和O(nlogn)

對于給定數(shù)列a，元素個數(shù)為n，f[i]為以元素i結(jié)尾的最長子上升序列的最大長度。

最長上升子序列f滿足對任意1<=j<i<=n(a[j]<a[i])，有f[j]<f[i]。

容易得出O(n^2)的DP狀態(tài)轉(zhuǎn)移方程:

f[i]=max{f[j]}+1;(1<=j<i且a[j]<a[i])

我們不妨把f的初值設(shè)為0，并在末尾添加一個元素inf，并將n++

這樣經(jīng)過兩重循環(huán)，f[n]即為LIS長度

代碼如下:

又稱作CMI算法

時間復(fù)雜度為O(nlogn)

其操作如下:

開辟一個棧b，每次取棧頂元素s和讀到的元素a做比較，如果a>s，則置為棧頂;如果a<s，則二分查找棧中的比a大的第1個數(shù)，并替換。最終棧的大小即為最長遞增子序列為長度

考察b棧內(nèi)每個元素的含義,b[i] 表示所有長度為i的上升子序列中最小的最后一個數(shù).

·舉例:原序列為3，4，5，2，4，2

棧為3，4，5，此時讀到2，則用2替換3，得到棧中元素為2，4，5，再讀4，用4替換5，得到2，4，4，再讀2，得到最終棧為2，2，4,最終得到的解是:

長度為1的上升子序列中最小的最后一個數(shù)是2 (2)

長度為2的上升子序列中最小的最后一個數(shù)是2 (2,2)長度為3的上升子序列中最小的最后一個數(shù)是4 (3,4,4)

可知沒有長度為4的上升子序列,最長遞增子序列長度為3. (3,4,4)

CMI本質(zhì)是LIS問題的另一種動態(tài)規(guī)劃思路

注意:CMI只能求LIS的長度和最后一個數(shù),不能求LIS的序列!

代碼如下:

#include<iostream>

using namespace std;

int n;

int a[1001],b[1001];

int rear;

int solve(int t)

{ int l=1,r=rear;

while(l<=r)

{ int mid=(l+r)>>1;

if(b[mid]>=t)//若為非遞減序列，則為b[mid]>t

r=mid-1;

else

l=mid+1;

}

if(l>rear)

rear=l;

return l;

}

int main()

{ int i,j;

scanf("%d",&n);

rear=0;

for(i=1;i<=n;i++)

{

scanf("%d",&a[i]);

b[solve(a[i])]=a[i];

}

printf("%d\n",rear);

system("pause");

return 0;

}