《向量分类问题的最优算法》由会员分享，可在线阅读，更多相关《向量分类问题的最优算法（9页珍藏版）》请在金锄头文库上搜索。
1、1 向量分类问题的最优算法向量分类问题的最优算法 Xiaodong Wang () Department of Computer Science Fuzhou University P.R.China March , 2006 ?问题描述：问题描述： 给定m个n维向量maaa,21，向量分类问题要求将相同的向量划分为同一类。试用抽象数据类型表设计解向量分类问题的有效算法。 ?编程任务：编程任务： 给定m个n维向量，编程计算这m个n维向量可分为多少个类。 ?数据输入：数据输入： 由文件input.txt给出输入数据。第1行有2个正整数m和n，分别表示给定的向量个数和每个向量的维数。接下来的m行中
2、，每行有n个整数，表示相应的n维向量。 ?结果输出结果输出: 将计算出的向量的等价类数输出到文件output.txt。 输入文件示例输入文件示例 输出文件示例输出文件示例 input.txt output.txt 6 4 3 5 7 9 4 3 7 5 3 5 7 9 2 1 4 6 3 5 7 9 2 1 4 6 3 2 分析与解答：分析与解答： 1 1 算法设计思想算法设计思想 （1）将向量存入数组vect。首先将所有向量在数组vect中的下标插入一个表中。 （2）依次考察向量各维的值，将具有相同值的向量归为一类并存入新表中，而将值不同的向量分离到另一表中。 （3）递归地对当前各表用下一维
3、向量值进行分类，直至第 n 维。 （4）计算结束后，当前各表中的向量属于同一类。 2 2 算法描述算法描述 int m,n,cnt,*vect; LIST *classout; int main() readin(); compute(); out(); return 0; readin 读入数据并初始化。 void readin() cinmn; classout = new LIST *m; Make2DArray(vect,m,n); for(int i=0;ivectij; cnt=0; compute 执行步骤（1），并调用 classify 完成分类工作。 void compute
4、() LIST *Lst=new LIST; for(int i=0;iINSERT(0,i); classify(Lst, 0); 3 split完成步骤（2）。 LIST *split(LIST * LIST *L=new LIST; LIST *L0=new LIST; Lst- DELETE(1,row); value = vectrowcolumn; L0- INSERT(0,row); while(!Lst- EMPTY() Lst- DELETE(1, row); if (vectrowcolumn != value) L- INSERT(0,row); else L0- INS
5、ERT(0,row); Lst=L0; return L; classify完成步骤（3）。 void classify(LIST *Lst, int column) LIST *L; if (column=n) classoutcnt+ = Lst; else L = split(Lst,column); classify(Lst,column+1); if (!L- EMPTY() classify(L,column); 最后，由out输出计算结果。 void out() cout *classout; int main() readin(); compute(); out(); retu
6、rn 0; readin 读入数据并初始化。 void readin() cinmn; classout = new STACK *m; Make2DArray(vect,m,n); for(int i=0;ivectij; cnt=0; compute 执行步骤（1），并调用 classify 完成分类工作。 void compute() STACK *Stk=new STACK(m+1); for(int i=0;iPUSH(i); classify(Stk, 0); 5 split完成步骤（2）。 STACK *split(STACK * STACK *S=new STACK(m); S
7、TACK *S0=new STACK(m); Stk- POP(row); value = vectrowcolumn; S0- PUSH(row); while(!Stk- EMPTY() Stk- POP(row); if (vectrowcolumn != value) S- PUSH(row); else S0- PUSH(row); Stk=S0; return S; classify完成步骤（3）。 void classify(STACK *Stk, int column) STACK *S; if (column=n) classoutcnt+ = Stk; else S = s
8、plit(Stk,column); classify(Stk,column+1); if (!S- EMPTY() classify(S,column); 最后，由out输出计算结果。 void out() coutEMPTY() classouti- POP(row);cout *classout; int main() readin(); compute(); out(); return 0; readin 读入数据并初始化。 void readin() cinmn; classout = new QUEUE *m; Make2DArray(vect,m,n); for(int i=0;i
9、vectij; cnt=0; compute 执行步骤（1），并调用 classify 完成分类工作。 void compute() QUEUE *Que=new QUEUE(m+1); for(int i=0;iENQUEUE(i); classify(Que,0); split完成步骤（2）。 QUEUE *split(QUEUE * QUEUE *Q=new QUEUE(m); QUEUE *Q0=new QUEUE(m); Que- DEQUEUE(row); value = vectrowcolumn; Q0- ENQUEUE(row); while(!Que- EMPTY() Qu
10、e- DEQUEUE(row); 7 if (vectrowcolumn != value) Q- ENQUEUE(row); else Q0- ENQUEUE(row); Que=Q0; return Q; classify完成步骤（3）。 void classify(QUEUE *Que, int column) QUEUE *Q; if (column=n) classoutcnt+ = Que; else Q = split(Que,column); classify(Que,column+1); if (!Q- EMPTY() classify(Q,column); 最后，由out输
11、出计算结果。 void out() coutEMPTY() classouti- DEQUEUE(row);coutmn; ind=new intm; for(int i=0;ivectij; classind00=0;classind01=m- 1; cnt=0; 其中，数组ind的功能相当于第一个算法中的表Lst。数组classind用于记录当前向量分类在ind中的位置。 Group 实现用向量 column 列的值进行 1 次分类。 int group(int s, int t,int column) int value = vectinds+column; while(s=s) int
12、 s0=s; if(c=1)classindi1=s- 1; s=group(s,t,column);c+; if(c1)classindcnt+cc+c- 10=s0;classindcnt+cc+c- 11=s- 1; cc+=c- 1; return cc; 9 classify完成用n列向量值进行的分类。 void classify() for(int i=0;in;i+)cnt+=divide(cnt,i); 最后，由out输出计算结果。 void out() coutcnt+1endl; Delete2DArray(vect,m); Delete2DArray(classind,m); 上述算法所需的空间显然为)(mnO。 在最坏情况下，每次每个向量最多做n次比较。总共做了n次分类，因此算法所做的比较次数不超过2mn。另外，注意到算法中数组元素的swap运算只需要) 1 (O时间，在最坏情况下，算法所需的计算时间为)(2mnO。
