/*
Name: 梅西迭代算法的實現
Copyright: 2003（C）
Author: 徐巖柏
Date: 31-10-03 16:09
Description: 該問題是線性移位寄存器的綜合問題提出的，給定一個N長的
二元序列，如何求出產生這一序列的級數最小的線性移位寄存
器，即最短的線性移位寄存器
*/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <fstream>
using namespace std;
int main(int argc, char *argv[])
{
typedef vector<bool> MyArray; file://定義自己的數據類
MyArray a; file://狀態數組 ，用來保存給定的m序列?
vector<int>l; file://線性移位寄存器的級數數組
MyArray temp;
vector<MyArray> f; file://為線性移位寄存器對應的多項式
int N =0;
ifstream infile("input.txt"); file://從文件中讀取數據
ofstream outfile("output.txt"); file://把結果寫入文件中。
if(!infile)
{
cout << "Aata file input.txt is not
ready! Please check it"<<endl;
exit (-1);
}
string strTemp;
infile>>strTemp; file://讀入N
// cout << strTemp <<endl;
N = atoi(strTemp.c_str());
infile>>strTemp; file://讀入序列
for( int i = 0 ;i<N; ++i)
{
a.push_back(strTemp[i]=='1'); file://把序列保存
}
file://cout << strTemp <<endl;
int n=0;
l.push_back(0);
temp.push_back(1); file://形成f0
f.push_back(temp); file://把f0加到f數組中。
do{
int dn =0;
for (int i = 0;i<=l[n];++i)
{
dn
+= f[n][i]*a[n-i]; file://計算dn
}
dn = dn % 2; file://取余
// cout <<"d"<<n<<"= "<<dn
<<endl;
int isum = 0;
for (int i =0;i<=n ;++i)
{
isum
+=l[i]; file://判定是不是所有的ln都等於0就是把所有的ln加起來看是不是零
}
if( dn == 0) file://如果dn ＝0
{
f.push_back(f[n]);
file://fn+1 = fn
l.push_back(l[n]);
file://ln+1 = ln
}
else if (!isum) file://所有的ln都是零
{
temp.clear();
for(int
i =0;i<n+2;++i)
{
temp.push_back(0);
}
temp[0]
= 1;
temp[n+1]
= 1;
f.push_back(temp);
l.push_back(n+1);
}
else file://lm<lm+1 = ...=ln
{
int m
=0;
for (int
i = n;i>=0; --i)
{
if(l[i]<l[n])
{
m= i; file://找到m
break;
}
}//end
for
temp.clear();//把臨時的目的數組清空
for (int
i =0;i<n-m;++i)
{
temp.push_back(0); file://fm乘x^n-m次方就是在多項式數組前面插入n-m個零
}
temp.insert(temp.end(),f[m].begin(),f[m].end());
file://構造fm*x^n-m
vector<bool>
ft; file://用來保存兩個多項式相加的結果
int len
= max(temp.size(),f[n].size()); file://取出多項式系數最大值
ft.insert(ft.begin(),len,0);
file://把目的數組填入len個零初始化
for (int
i = 0 ;i<temp.size(); ++i)
{
ft[i] = temp[i]; file://先把temp的值拷貝到ft目的數組中。
}
for (int
i = 0 ;i<f[n].size(); ++i) file://把兩個多項式加到一起
{
if(ft[i] != f[n][i]) file://如果多項式的對應系數不等，加後系數是1
ft[i] = 1;
else
ft[i] = 0; file://如果多項式的對應系數相等，加後系數是0
}
f.push_back(ft);
file://f[n+1] = ft
len =
max(l[n],n+1-l[n]);
l.push_back(len);//找L(n+1)=max(ln,n+1-ln)
}
/* cout <<"f(x)=1" ; file://如需要可以輸出中間結果
for (int i=1; i<f[n].size();++i)
file://常數項已經是1了，故忽略第一個
{
if (f[n][i])
cout<<"+X^"<<i;
}
cout <<endl;
getchar();
*/
if(n>=N-1) break;
++n;
}while(1);
if(outfile) file://輸出文件合法
{
outfile <<"ln="<<l.back()<<endl;
file://輸出ln
outfile <<"f(x)=1" ;
file://輸出結果多項式，並賦常數項為1
for (int i=1; i<f[N].size();++i)
file://常數項已經是1了，故忽略第一個
{
if (f[N][i])
outfile<<"+X^"<<i;
}
outfile<< endl;
cout <<"結果已經同時寫入到output.txt文件中了。"<<endl;
}
cout << "本算法的最終結果是："<<endl;
cout <<"ln="<<l.back()<<endl; file://輸出ln
cout <<"f(x)=1" ; file://輸出結果多項式，並賦常數項為1
for (int i=1; i<f[N].size();++i) file://常數項已經是1了，故忽略第一個
{
if (f[N][i])
cout<<"+X^"<<i;
}
cout<< endl<<endl<<endl;
cout << "請按任意健退出!" ;
getchar();
return 0;
}
