关于一元多项式的， 保证能运行 #include"multinomial.cpp" int main() { polyNomial<double> pa,pb,add,sub,mul; pa.creatPoly(); cout<<pa<<endl; pb.creatPoly(); cout<<pb<<endl<<endl;

add.addPoly(pa,pb,add); cout<<add<<endl; add.countValue(); sub.subPoly(pa,pb,sub); cout<<sub<<endl; sub.countValue();

mul.mulPoly(pa,pb,mul); cout<<mul<<endl; mul.countValue(); system("pause"); return 0 ; } #include<iostream> using namespace std;

template<class T> class polyNomial; template<class T> class polyNode { friend class polyNomial<T>; public: polyNode(){} private: T quotiety; //项的系数 T quotiety_degree;//项的指数 polyNode<T> *next; };

template<class T> ostream& operator<<(ostream& outs,const polyNomial<T>& x);

template<class T> class polyNomial { public: polyNomial(){ first = new polyNode<T>; } //置空表 ~polyNomial(); polyNomial<T> *creatPoly(); //操作结果：输入m项的系数和指数，建立一元多项式p ,并调用sort() bool isEmpty(); //多项式存在返回false，否则返回true polyNomial<T> *order(); //前条件：已经存在多项式 //后条件：把多项式按指数高到低排序 polyNomial<T> *addPoly(polyNomial<T>& pa,polyNomial<T>& pb, polyNomial<T>& pc); //前条件：存在多项式pa，pb //后条件：完成多项式加法运算，pc ＝ pa＋pb, 并调用sort() polyNomial<T> *subPoly(polyNomial<T>& pa,polyNomial<T>& pb,polyNomial<T>& pc); //前条件：存在多项式pa，pb //后条件：完成多项式加法运算，pc ＝ pa－pb, 并调用sort() polyNomial<T> *mulPoly(polyNomial<T>& pa,polyNomial<T>& pb, polyNomial<T>& pc); //前条件：存在多项式pa，pb //后条件：完成多项式加法运算，pc ＝ pa*pb , 并调用sort() polyNomial<T> *sort(); //前条件：存在要整理的多项式 //按指数高到低排序，整理多项式，把系数是0的项删除 void countValue(); //前条件：存在要计算的多项式 //计算多项式的值 void output(ostream& outs) const ; //前条件：存在多项式 //后条件：输出多项式 ostream& operator<< <>(ostream& outs,const polyNomial<T>& x); //重载输出流 private: mutable T polyNumber; //项数 polyNode<T> *first; }; #include "multinomial.h" #include "math.h" //创建多项式函数 template<class T> polyNomial<T> *polyNomial<T>::creatPoly() { polyNode<T> *link,*s; link = first; cout<<"输入提示：先输入有多少项，然后输入谋项的系数后按回车，接着输入对应的指数再回车" <<"(2^3是代表2的3次方的意思)，未知数用y表示"<<endl; cout<<"输入多项式的项数"<<endl; cin>> polyNumber ; for(int i = 0; i < polyNumber ; i++) { cout<<"输入多项式的系数"<<endl; label1: s = new polyNode<T>; cin>>s->quotiety; if(s->quotiety == 0) { cout<<"系数不能为0！请重新输入该项"<<endl; goto label1; } cout<<"输入多项式的指数"<<endl; cin>>s->quotiety_degree; link->next = s; link = s; } link->next = NULL; sort(); return this; }

//析构函数 template<class T> polyNomial<T>::~polyNomial<T>() { polyNode<T>* link; while(first) { link = first->next; delete first; first = link; } }

//判断多项式是否为空 template<class T> bool polyNomial<T>::isEmpty() { if(first->next == NULL) return true; else return false; }

//排序 template<class T> polyNomial<T> *polyNomial<T>::order() { polyNode<T> *p = first->next; polyNode<T> *q = first->next; T _quotiety; T _quotiety_degree;

for( ; p ; p = p->next ) for( q = p->next ; q ; q = q->next ) if( (p->quotiety_degree)< (q->quotiety_degree)) { _quotiety = p->quotiety ; _quotiety_degree = p->quotiety_degree; p->quotiety = q->quotiety; p->quotiety_degree = q->quotiety_degree; q->quotiety = _quotiety; q->quotiety_degree = _quotiety_degree; } return this; }

//多项式相加函数 template<class T> polyNomial<T> *polyNomial<T>::addPoly(polyNomial<T>& pa,polyNomial<T>& pb,polyNomial<T>& pc) { //多项式的项已经以指数高到低的顺序排序了 polyNode<T> *p1 = pa.first->next; polyNode<T> *p2 = pb.first->next; polyNode<T> *link,*s; link = pc.first; // link 指向pc多项式（初始pc是空的）

while( p1 && p2 ) { if((p1->quotiety_degree)==(p2->quotiety_degree)) { //如果指数相同，则pa，pb的系数相加 s = new polyNode<T>; s->quotiety = p1->quotiety + p2->quotiety; s->quotiety_degree = p1->quotiety_degree;

link->next = s; link = s; p1 = p1->next ; p2 = p2->next ; }

else { //pa，pb的指数不同 s = new polyNode<T>; //把pa插入pc的最后1个节点 s->quotiety = p1->quotiety; s->quotiety_degree = p1->quotiety_degree; link->next = s; link =s; p1 = p1->next ; s = new polyNode<T>; //把pb插入pc的最后1个节点 s->quotiety = p2->quotiety; s->quotiety_degree = p2->quotiety_degree; link->next = s; link =s; p2 = p2->next ; } }

while (p1) //若pb的项数为空，则把pa继续插入pc的最后 { s = new polyNode<T>; s->quotiety = p1->quotiety; s->quotiety_degree = p1->quotiety_degree; link->next = s; link =s; p1 = p1->next ; }

while (p2 ) //若pa的项数为空，则把pb继续插入pc的最后 { s = new polyNode<T>; s->quotiety = p2->quotiety; s->quotiety_degree = p2->quotiety_degree; link->next = s; link =s; p2 = p2->next ; } link->next = NULL; sort(); return this; }

//多项式相减函数 template<class T> polyNomial<T> *polyNomial<T>::subPoly(polyNomial<T>& pa,polyNomial<T>& pb,polyNomial<T>& pc) { //多项式的项已经以指数低到高的顺序排序了 polyNode<T> *p1 = pa.first->next; polyNode<T> *p2 = pb.first->next; polyNode<T> *link,*s; link = pc.first; // link 指向pc多项式（初始pc是空的）

while( p1 && p2 ) { if((p1->quotiety_degree)==(p2->quotiety_degree)) { //如果指数相同，则pa，pb的系数相减 s = new polyNode<T>; s->quotiety = p1->quotiety - p2->quotiety; s->quotiety_degree = p1->quotiety_degree; link->next = s; link = s; p1 = p1->next ; p2 = p2->next ; }

else { //pa，pb的指数不同 s = new polyNode<T>; //把pa插入pc的最后1个节点 s->quotiety = p1->quotiety; s->quotiety_degree = p1->quotiety_degree; link->next = s; link =s; p1 = p1->next ;

s = new polyNode<T>; //把pb插入pc的最后1个节点 s->quotiety = p2->quotiety * -1; s->quotiety_degree = p2->quotiety_degree; link->next = s; link =s; p2 = p2->next ; } }

while (p1) //若pb的项数为空，则把pa继续插入pc的最后 { s = new polyNode<T>; s->quotiety = p1->quotiety; s->quotiety_degree = p1->quotiety_degree; link->next = s; link =s; p1 = p1->next ; }

while (p2 ) //若pa的项数为空，则把pb继续插入pc的最后 { s = new polyNode<T>; s->quotiety = p2->quotiety * -1; s->quotiety_degree = p2->quotiety_degree; link->next = s; link =s;

p2 = p2->next ; } link->next = NULL; sort(); return this; } //多项式相乘函数 template<class T> polyNomial<T> *polyNomial<T>::mulPoly(polyNomial<T>& pa,polyNomial<T>& pb, polyNomial<T>& pc) { polyNode<T> *p1 = pa.first->next; polyNode<T> *p2 = pb.first->next; polyNode<T> *link,*s; link = pc.first; // link 指向pc多项式(初始pc是空的) while(p1) { while(p2) //pa里的第1项和pb里的每一项，类推 { s = new polyNode<T>; s->quotiety = p1->quotiety * p2->quotiety; s->quotiety_degree =p1->quotiety_degree + p2->quotiety_degree; link->next = s; link = s; if(p2) p2 = p2->next;

} if(p1) p1 = p1->next; p2 = pb.first->next;

} link->next = NULL; sort(); return this ; } //整理新链表 template<class T> polyNomial<T> *polyNomial<T>::sort() { polyNode<T> *link; polyNode<T> *q; order(); //按指数从高到低排序 //整理链表：把相邻的元素比较，若指数相同的，则相加的结果放到比较的第2个项，并删除与之相连的项

link = first ; //link指向当前指针的前驱

q = link->next ; for( ; q!=NULL ; link = link->next , q = link->next) { if(q->next!=NULL) { if(q->quotiety_degree == q->next->quotiety_degree) {//若指数相同的，则把相加的结果放到比较的第2个项 q->next->quotiety += q->quotiety; //指数相同的系数相加，指数不变 if(q->next!=NULL) link->next = q->next; //删除与之相连的项 q = q->next ; } //删除系数为0的项 } if(q->quotiety == 0) { if(q->next == NULL) //判断删除的是不是最后1项 { link->next = NULL; break; } else { link->next = q->next; q = q->next ; } } } return this; } //计算机多项式的值 template<class T> void polyNomial<T>::countValue() { polyNode<T> *link = first->next; double sum = 0 ; double tem = 0,y ; cout<<"输入y的值用来求当前多项式的值:"<<endl; cin>>y; sort(); for( ; link ; link = link->next ) { if(link->quotiety_degree == 1) sum += link->quotiety * y ; else if(link->quotiety_degree == 0) sum += link->quotiety ; else { tem = pow(y,link->quotiety_degree) ; sum += link->quotiety * tem; tem = 0 ; } } cout<<"y="<<y<<"的当前多项式的值是: "<<sum<<endl; } //输出 template<class T> void polyNomial<T>::output(ostream& outs) const { polyNode<T> *current; polyNode<T> *p; outs<<"结果是：(建立2个多项式完后，将按顺序输出2个多项式+ - *后的多项式)"<<endl; current = first ; for( p = current->next ; p != NULL; current = current->next , p = current->next) //current指向当前节点的前驱, p指向当前节点 { if(p->quotiety == 0) //如果项系数是0的项，则删除 { if(p->next == NULL) current->next = NULL; else { current->next = p->next ; p = p->next ; } } if(p->quotiety > 0) //指数为0的项 { //系数为>0则打印+,指数为=1则打印y //指数为0的情况，则不打印 y if(p->quotiety_degree == 0) { if(p->quotiety>0) outs<<"+"<< p->quotiety; else if(p->quotiety < 0) outs<<p->quotiety; } else { if(p->quotiety!=1) //系数>0且系数 !=1 的情况 { if(p->quotiety_degree != 1) outs<<"+" << p->quotiety<<"y" <<"^"<<p->quotiety_degree; else outs<<"+" << p->quotiety<<"y"; } else //系数>0且系数 = 1 的情况 { if(p->quotiety_degree != 1) //系数等于1， 指数不等于1 outs<<"+"<<"y"<<"^"<<p->quotiety_degree; else //指数等于1的情况 outs<<"+"<<"y"; } } } else //系数<0的情况 { //系数为<0则打印+,指数为=1则打印y if(p->quotiety != -1) { if(p->quotiety_degree != 1) outs<< p->quotiety<<"y" <<"^"<<p->quotiety_degree; else outs<<p->quotiety<<"y"; } else //系数<0且系数 = -1 的情况 { if(p->quotiety_degree != 1) //系数等于1， 指数不等于1 outs<<"-"<<"y"<<"^"<<p->quotiety_degree; else //指数等于1的情况 outs<<"-"<<"y"; } }

} } //重载<< template<class T> ostream& operator<<(ostream& outs,const polyNomial<T>& x) { x.output(outs); return outs; }

/*汉诺塔的递归算法* #include<iostream.h>

void hanio(int n,char A,char B,char C)

{

if(n==1)

{

cout<<"将第"<<n<<"片金片从"<<A

<<"柱搬到"<<C<<"柱上"<<endl;

}

else

{

hanio(n-1,A,C,B);

cout<<"将第"<<n<<"片金片从"<<A

<<"柱搬到"<<C<<"柱上"<<endl;

hanio(n-1,B,A,C);

}

}

void main()

{

char A=''A'',B=''B'',C=''C'';

int n=3;

hanio(n,A,B,C);

}

*/

/****关于汉诺塔问题的另类解***** 汉诺塔问题归于中序遍历，采用递归算法或分治算法也许的最简单的求解方法。

递归是设计和描述算法的一种有力的工具。能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

如果原问题可分割成k个子问题（1<k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

当然，有时我们并不需要求解出问题的全解。如我们只想知道６４片金片要从A柱上移动到C柱上（B柱为桥），第一百亿步应该是哪片金片的第几次移动，且是从哪根柱上移动到哪根柱上呢？在计算机上是否能用递归算法或分治算法求解我不知道，但在只有一支笔一张纸的情况呢？我想用递归法或分治法是不现实的！那有没有方法求解呢，答案是肯定的。我通过递推法（利用问题本身所具有的一种递推关系求问题解的一种方法）找到了解决这个问题的数学表达式：

(2^i)*(2^j-1)=M；k=j%3； N； 条件：N金片数，第M步为已知。（金片1为最小，金片64最大）那么解就是：N片金片的第M步为金片i+1的第j次移动，当(i+1)%2=N%2时，k=0：从B柱上移动到A柱上；k=1：从A柱上移动到C柱上；k=2：从C柱上移动到B柱上；当(i+1)%2≠N%2时，k=0：从C柱上移动到A柱上；k=1：从A柱上移动到B柱上；k=2：从B柱上移动到C柱上；

如果此时想知道各柱上的金片是如何排列的却只有使用另一种方法了。那就是先用N位二进制数来表示M，余下的工作就是随手画出各柱上的金片的排列！再画出第M-1步各柱上的金片的排列，那么就可以不用计算而得到答案！这正是我为大家推荐的方法。

请仔细阅读程序中蓝色字体部分，我想信你也能随手画出答案！(提示：用N位二进制数来表示M，最高位代表最大的金片，最低位为最小。先从最高位开始，为1则最大的金片用N表示画在C柱上，否则在A柱上；次高位如果同上一位相同则画在同一柱上，否则画在B柱上；下一次高位如果同次高位同则画在同一柱上，否则画在A柱上；依此循环。并遵守在同一柱上相邻的两片金片编号不能同时为奇或偶。从低位往高位看，第一位为1的金片就是本次移动的金片，且在大多数情况下不用画出第M-1步各柱上的的排列就能知道该金片的如何移动的。例：4张金片第10步，10=（1010）₂ 显然A柱上有2，B柱上是3，C柱上有1和4。第一位为1在第2位上，因此是金片2，

1+（1010）₂>>2 =1+(0010)₂ =3,显然 4张金片第10步为金片2的第3次移动，且是从B柱移动到A柱。）

*********************************************/

/*********************************************

* 文件名称：hanio.cpp

* 摘 要：汉诺塔的终极经典的算法。

* 可以随手画出答案的方法。

* 本例没考虑程序本身的可读性和效率。

* 当前版本：1.0

* 作 者：赵智强

* 完成日期：2005年10月12日

* 电子邮箱：wwwindowsxp@163.com

* 腾讯 QQ : 191580647

* 测试环境：Turbo C++ 3.0

*********************************************/

#include<iostream.h>

void divtwo(int d[],int n)

{

int temp=0,cy=0;

int i;

for(i=n;i>=0;i--)

{

cy=d[i]%2;

d[i]=(d[i]+temp*10)/2;

temp=cy;

}

}//十进制数组除2

void multwo(int d[],int m,int n)

{

int temp=0,cy=0;

int i,j;

for(j=0;j<n;j++)

{

for(i=0;i<m;i++)

{

cy=(d[i]*2)/10;

d[i]=(d[i]*2)%10+temp;

temp=cy;

}

}

}//十进制数组=2^m

void decaddone(int d[],int n)

{

int i;

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

{

if(d[i]==9) d[i]=0;

else {d[i]+=1;break;}

}

}//十进制数组加1

void main()

{

int i,j,k, n;

int m=52;

char a[52]="1";

int b[52]={0};

int d[52]={1};

int e[52]={0};

cout<<"Input :disk(1~100) " //输入金片数：整型

<<"step(2^disk-1)"<<endl;//输入第M步：字符数组

cin>>n;

if(n>100){cout<<"disk err! (disk>100)"

<<endl; return;}

int c[100]={0};

int aa[100]={0};

int bb[100]={0};

int cc[100]={0};

for(i=0;i<m;i++)

{

cin>>a[i];

if(a[i]>0x39||a[i]<0x30)

{a[m-1]=i;break;}

}//输入第M步：字符数组以非数字结尾

for(i=0;i<a[m-1];i++)

b[i]=int(a[(a[m-1]-1-i)]-0x30);//转换成十进制整型数组，个位在b[0]

multwo(d,m,n);

cout<<endl;

cout<<"step max: ";

j=0;

for(i=m-1;i>=0;i--)

{

if(d[i]==0&&j==0) continue;

j=1;

cout<<d[i];

}

cout<<"-1"<<endl;

for(i=m-1;i>=0;i--)

{

if(b[i]<d[i]) break;

if(b[i]>d[i]||(b[i]==d[i]&&i==0))

{cout<<"step err! (step>=2^disk)"

<<endl; return;}

}//输入第M步是否<=2^disk-1

for(i=0;i<m;i++)

{

d[i]=b[i];e[i]=b[i];

}

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

{

if(b[0]%2==1) { c[i]=1;b[0]-=1;}

else c[i]=0;

for(j=0;j<m;j++) if(b[j]!=0) break;

if(j==m) break;

divtwo(b,1+n/2);

}

cout<<" ";

for(i=n-1;i>=0;i--)

{

cout<<c[i]<<" ";

}//step的n位二进制数组表示

cout<<endl;

j=0;

int aa1=0,bb1=0,cc1=0,dd1=0;

if(c[n-1]==0) { aa[aa1]=n;aa1++;dd1=1;}

else { cc[cc1]=n;j++;cc1++;dd1=3;}

for(i=n-2;i>=0;i--)

{

if(c[i+1]==c[i])

{

switch(dd1)

{

case 1: { aa[aa1]=i+1;aa1++;

dd1=1;continue;break;}

case 2: { bb[bb1]=i+1;bb1++;

dd1=2;continue;break;}

case 3: { cc[cc1]=i+1;cc1++;

dd1=3;continue;break;}

}

}

else

{

j++;

switch(dd1)

{

case 1: if(j%2==i%2) {cc[cc1]=i+1;

cc1++;dd1=3;continue;break;}

else { bb[bb1]=i+1;bb1++;

dd1=2;continue;break;}

case 2: if(j%2==i%2){aa[aa1]=i+1;

aa1++;dd1=1;continue;break;}

else {cc[cc1]=i+1;cc1++;

dd1=3;continue;break;}

case 3: if(j%2==i%2) {bb[bb1]=i+1;

bb1++;dd1=2;continue;break;}

else { aa[aa1]=i+1;aa1++;

dd1=1;continue;break;}

}

}

}// 根据step的n位二进制数组表示，解出A、B、// C柱上各金片的相对排列。

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

{

if(d[0]%2==1)

{

divtwo(d,1+n/2);

decaddone(d,m);

cout<<"disk: "<<n<<" "<<"step: ";

k=0;

for(j=m-1;j>=0;j--)

{

if(e[j]==0&&k==0) continue;

k=1;

cout<<e[j];

}

cout<<endl;

cout<<"No. "<<i+1<<" "

<<"times: ";

k=0;

for(j=m-1;j>=0;j--)

{

if(d[j]==0&&k==0) continue;

k=1;

cout<<d[j];

}

if(d[0]==0&&k==0) cout<<d[0];

cout<<" ";

k=0;

for(j=0;j<m;j++)

{

k+=d[j];

}

if(n%2==(i+1)%2)

{

switch(k%3)

{

case 0: cout<<"B------>A"

<<endl; break;

case 1: cout<<"A------>C"

<<endl; break;

case 2: cout<<"C------>B"

<<endl; break;

}

}

else

{

switch(k%3)

{

case 0: cout<<"C------>A"

<<endl; break;

case 1: cout<<"A------>B"

<<endl; break;

case 2: cout<<"B------>C"

<<endl; break;

}

}

break;

}

else divtwo(d,1+n/2);

}//根据上文提到的数学表达式(2^i)*(2^j-1)=M计算

cout<<"A ";

for(i=n-1;i>=0;i--)

{

if(n%2==1&&c[n-1]==1)

cout<<bb[i]<<" ";

else cout<<aa[i]<<" ";

}

cout<<endl;

cout<<"B ";

for(i=n-1;i>=0;i--)

{

if(n%2==1)

if(c[n-1]==1) cout<<aa[i]<<" ";

else cout<<cc[i]<<" ";

else cout<<bb[i]<<" ";

}

cout<<endl;

cout<<"C ";

for(i=n-1;i>=0;i--)

{

if(n%2==1&&c[n-1]==0)cout<<bb[i]<<" ";

else cout<<cc[i]<<" ";

}

cout<<endl;

//求解出A、B、C柱上各金片的最终排列。

}

/*****************非递归算法******************

* 本例输入：disk为金片数（1～100）。

* step为移动的第xxxx步。

* xxxx应小于2^disk。

* 本例输出：第xxxx步为第xx金片第xxxx次移动。

* 且是从x柱移动到x柱。

* 注： A源柱，B桥柱，C目的柱。

* 另注： 例共1张金片，其移动步骤可能是：第

* 1步从A—>B,第2步从B-->C。但这不是我们

* 要的答案！正确方法是：第1步从A—>C。

*****************程序运进结果*****************

输入：4 10p（非数字结尾）

输出：step max: 16-1

1 0 1 0(10的4位二进制表示)

disk：4 step：10

No. 2 times：3 B--àA

A 0 0 0 2

B 0 0 0 3

C 0 0 1 4

解析：共4张金片的第10步为：

第2张金片第3次移动，且是从B柱上移动到A柱上。

*********************************************/

厉害

大家都那么出力，我也灌一下，原创的1维的LCS（最长公共子序列）
#include<iostream>
#include<vector>
using namespace std;
int main(){
for(string s1,s2; cin>>s1>>s2; ){
int temp,temp1,l1=s1.length(),l2=s2.length(),mx=0;
vector<int> sign(l2,0);
for(int i=0; i<l1; i++){
temp=temp1=0;
for(int j=0; j<l2; j++){
if(sign[j]>temp1) temp1=sign[j];
if(s1[i]==s2[j]){
sign[j]=temp+1;
if(sign[j]>mx) mx=sign[j];
}
if(temp1>temp) temp=temp1;
}
}
cout<<mx<<endl;
}
}