今年网络安全的一个小作业，简单用C++实现了下 有些粗糙 先放这儿吧 ^_^
算法描述 考完试再附上
1
/**//*
2
* 文件名称：myecu.cpp
3* 摘 要：Extend Euclid Algorithm
4* 作者：ld
5* 完成日期：25th June,2010
6
*/
7
8#include "stdafx.h"
9#include <iostream>
10#include <vector>
11#include <algorithm>
12#include <fstream>
13#include <math.h>
14
15using namespace std;
16
17typedef struct polyNode//多项式节点项
18
{
19 int coef;
20 int power;
21}polyNode;
22
23void CreatePoly(vector<polyNode>&poly);//构造多项式
24void SortPolyByPower(vector<polyNode>&poly);//对多项式排序，按照降幂
25vector<polyNode> PolyAdd(vector<polyNode>p1,vector<polyNode>p2);//多项式加法
26vector<polyNode> PolySub(vector<polyNode>p1,vector<polyNode>p2);//多项式减法
27vector<polyNode> PolyMultiply(vector<polyNode>p1,vector<polyNode>p2);//多项式乘法
28vector<polyNode> PolyDiv(vector<polyNode>&p1,vector<polyNode>p2);//多项式除法
29vector<polyNode> Eculid(vector<polyNode>&p1,vector<polyNode>&p2);//扩展欧几里得算法
30
31
32void SortPolyByPower(vector<polyNode>&poly)//OK
33{
34 vector<polyNode>::iterator iter,tmpIter;
35 iter = poly.begin();
36 for (; iter != poly.end(); iter++)//按照幂数高低排序
37
{
38 tmpIter = iter + 1;
39 int maxPower = (*iter).power;
40 for (; tmpIter != poly.end(); tmpIter++)
41 {
42 if ((*tmpIter).power > (*iter).power)
43 {
44 iter_swap(iter,tmpIter);
45
}
46 }
47 }
48
49}
50
51void CreatePoly(vector<polyNode>&poly)//OK
52{
53 static int itemCount = 0;
54 cout<<"Please input the itemCount of the poly:"<<endl;
55 cin>>itemCount;
56 for (int t = 0; t < itemCount; t++)
57 {
58 static polyNode tmpItem;
59 cout<<"Please input the coef and power:"<<endl;
60 cin>>tmpItem.coef>>tmpItem.power;
61 poly.push_back(tmpItem);
62
63 }
64 SortPolyByPower(poly);
65 cout<<"原始多项式为："<<endl;
66 vector<polyNode>::iterator iter;
67 for ( iter = poly.begin();iter!= poly.end();iter++)
68 {
69 cout<<"X^"<<(*iter).power<<"+";
70 }
71 cout<<endl;
72}
73
74vector<polyNode> PolyAdd(vector<polyNode>p1,vector<polyNode>p2)//OK
75{
76 vector<polyNode> tmpPolyAdd;
77 vector<polyNode>::iterator iter1,iter2;
78 iter1 = p1.begin();
79 iter2 = p2.begin();
80 if (p1.size() == 0)
81 {
82 tmpPolyAdd.clear();
83 tmpPolyAdd = p2;
84 return tmpPolyAdd;
85 }
86 else if(p2.size() == 0)
87 {
88 tmpPolyAdd.clear();
89 tmpPolyAdd = p1;
90 return tmpPolyAdd;
91 }
92 else
93 {
94 tmpPolyAdd.clear();
95 for (; iter1 != p1.end() && iter2 != p2.end();)
96 {
97 if ((*iter1).power > (*iter2).power)
98 {
99 tmpPolyAdd.push_back(*iter1);
100 iter1++;
101 }
102 else if ((*iter1).power == (*iter2).power)
103 {
104 polyNode tmp;
105 tmp.coef = ((*iter1).coef + (*iter2).coef)%2;
106 tmp.power = (*iter1).power;
107 if (tmp.coef != 0)
108 {
109 tmpPolyAdd.push_back(tmp);
110 }
111 else;
112 iter1++;
113 iter2++;
114 }
115 else if ((*iter1).power < (*iter2).power)
116 {
117 tmpPolyAdd.push_back(*iter2);
118 iter2++;
119 }
120 }
121 if (iter2 != p2.end())
122 {
123 for (;iter2 != p2.end();iter2++)
124 {
125 tmpPolyAdd.push_back(*iter2);
126 }
127 SortPolyByPower(tmpPolyAdd);
128 return tmpPolyAdd;
129 }
130 else if(iter1 != p1.end())
131 {
132 for (;iter1 != p1.end();iter1++)
133 {
134 tmpPolyAdd.push_back(*iter1);
135 }
136 SortPolyByPower(tmpPolyAdd);
137 return tmpPolyAdd;
138 }
139 else
140 {
141 SortPolyByPower(tmpPolyAdd);
142 return tmpPolyAdd;
143 }
144
145 }
146}
147
148vector<polyNode> PolySub(vector<polyNode>p1,vector<polyNode>p2)//OK
149{
150 vector<polyNode> tmpPolySub;
151 vector<polyNode>::iterator iter1,iter2;
152 iter1 = p1.begin();
153 iter2 = p2.begin();
154 for (; iter1 != p1.end() && iter2 != p2.end();)
155 {
156 if ((*iter1).power > (*iter2).power)
157 {
158 tmpPolySub.push_back(*iter1);
159 iter1++;
160 }
161 else if ((*iter1).power == (*iter2).power)
162 {
163 polyNode tmp;
164 tmp.coef = ((*iter1).coef - (*iter2).coef)%2;
165 tmp.power = (*iter1).power;
166 if (tmp.coef != 0)
167 {
168 tmpPolySub.push_back(tmp);
169 }
170 else;
171
172 iter1++;
173 iter2++;
174 }
175 else if ((*iter1).power < (*iter2).power)
176 {
177 tmpPolySub.push_back(*iter2);
178 iter2++;
179 }
180 }
181 if (iter2 == p2.end())
182 {
183 for (;iter1 != p1.end();iter1++)
184 {
185 tmpPolySub.push_back(*iter1);
186 }
187 }
188 else if(iter1 == p1.end())
189 {
190 for (;iter2 != p2.end();iter2++)
191 {
192 tmpPolySub.push_back(*iter2);
193 }
194 }
195 SortPolyByPower(tmpPolySub);
196 return tmpPolySub;
197}
198
199vector<polyNode> PolyMultiply( vector<polyNode>p1, vector<polyNode>p2)//OK
200{
201 vector<polyNode> tmpPolyMul;
202 tmpPolyMul.clear();
203 vector<polyNode> itemPoly;
204 polyNode tmp;
205
206 vector<polyNode>::iterator iter1,iter2;
207 iter1 = p1.begin();
208 iter2 = p2.begin();
209 for (; iter2 != p2.end(); iter2++)
210 {
211 for (;iter1 != p1.end(); iter1++)
212 {
213 tmp.coef = (*iter1).coef * (*iter2).coef;
214 tmp.power = (*iter1).power + (*iter2).power;
215 itemPoly.push_back(tmp);
216 }
217 SortPolyByPower(itemPoly);
218 iter1 = p1.begin();
219 tmpPolyMul = PolyAdd(tmpPolyMul,itemPoly);
220 itemPoly.clear();
221 }
222 SortPolyByPower(tmpPolyMul);
223 return tmpPolyMul;
224
225}
226
227vector<polyNode> PolyDiv(vector<polyNode>&p1, vector<polyNode>p2)//OK
228{
229 polyNode tmpItem;
230 vector<polyNode> tmpP1 = p1;
231 vector<polyNode> tmpP2 = p2;
232 static vector<polyNode> result;
233 static vector<polyNode> ret;
234 vector<polyNode> tmpMultiply;
235 vector<polyNode> tmpResult;
236 static vector<polyNode> rPoly;
237
238 vector<polyNode>::iterator iter1;
239 vector<polyNode>::iterator iter2;
240 iter1 = tmpP1.begin();
241 iter2 = tmpP2.begin();
242 while ((*iter1).power >= (*iter2).power)
243 {
244 for (;iter2!=tmpP2.end();iter2++)
245 {
246 tmpItem.coef = abs((*iter1).coef / (*iter2).coef);
247 tmpItem.power = (*iter1).power - (*iter2).power;
248 tmpResult.push_back(tmpItem);
249 result.push_back(tmpItem);
250
251 tmpMultiply = PolyMultiply(p2,tmpResult);
252 vector<polyNode>::iterator tmpIter;
253 tmpIter = tmpMultiply.begin();
254 tmpResult.clear();
255 rPoly= PolySub(tmpP1,tmpMultiply);
256
257 p1 = rPoly;
258 rPoly.clear();
259 return PolyDiv(p1,p2);
260 }
261 }
262 SortPolyByPower(result);
263 ret = result;
264 result.clear();
265 return ret;
266}
267
268vector<polyNode> Eculid(vector<polyNode>&mx,vector<polyNode>&bx)//OK
269{
270 vector<polyNode> a1x;
271 vector<polyNode> a2x;
272 vector<polyNode> a3x;
273 vector<polyNode> a3xcp;
274
275 vector<polyNode> b1x;
276 vector<polyNode> b2x;
277 vector<polyNode> b3x;
278
279 vector<polyNode> t1x;
280 vector<polyNode> t2x;
281 vector<polyNode> t3x;
282
283 vector<polyNode> qx;
284 vector<polyNode> gcd;
285 vector<polyNode> inverse;
286 vector<polyNode>::iterator iter;
287
288 static polyNode tmpItem;
289 tmpItem.coef = 1;
290 tmpItem.power = 0;
291 a1x.push_back(tmpItem);
292 a3x.clear();
293 a3x = mx;
294
295 b1x.clear();
296 tmpItem.coef = 1;
297 tmpItem.power = 0;
298 b2x.push_back(tmpItem);
299 b3x = bx;
300 do
301 {
302 iter = b3x.begin();
303 if (b3x.empty())
304 {
305 cout<<"No inverse!!!"<<endl;
306 exit(0);
307 }
308 else if (b3x.size() == 1 && ((*iter).coef == 1 && (*iter).power == 0))
309 {
310 inverse = b2x;
311 return inverse;
312 }
313 a3xcp = a3x;
314 qx = PolyDiv(a3x,b3x);
315 a3x = a3xcp;
316
317 t1x = PolySub(a1x,PolyMultiply(qx,b1x));
318 t2x = PolySub(a2x,PolyMultiply(qx,b2x));
319 t3x = PolySub(a3x,PolyMultiply(qx,b3x));
320
321 a1x = b1x;
322 a2x = b2x;
323 a3x = b3x;
324
325 b1x = t1x;
326 b2x = t2x;
327 b3x = t3x;
328 } while (1);
329
330}
331
332
333int main()
334{
335 vector<polyNode> polynomial1;
336 vector<polyNode> polynomial2;
337 vector<polyNode> inverse;
338 vector<polyNode> ::iterator iter;
339 vector<polyNode> r;
340 CreatePoly(polynomial1);
341 CreatePoly(polynomial2);
342 inverse = Eculid(polynomial1,polynomial2);
343 SortPolyByPower(inverse);
344 iter = inverse.begin();
345 cout<<"求得的逆为："<<endl;
346 for (;iter!=inverse.end();iter++)
347 {
348 cout<<"X^"<<(*iter).power<<"+"<<endl;
349 }
350 getchar();
351
352}
posted on 2010-07-07 00:23
yibani 阅读(3316)
评论(0) 编辑 收藏 引用