分享
 
 
 

梅西迭代算法的实现

王朝vc·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

/*

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;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有