目录
题目：多项式广义的欧几里得除法
1 数学基础
2 算法描述
3 算法实现
4 运行结果
5 具体代码
题目：多项式广义的欧几里得除法
1 数学基础
多项式广义Euclid除法：
设f（x），g（x）是域K上的多项式，deg g≥1。反复运用多项式Euclid除法，我们有
f(x) = q0g(x) + r0(x) , 0≤deg r0<deg g(x)
g(x) = q1r0(x) + r1(x) , 0≤deg r1<deg r0
r0(x) = q2r1(x) + r2(x) , 0≤deg r2<deg r1
r1(x) = q3r2(x) + r3(x) , 0≤deg r3<deg r2
……
rk-4(x) = qk-2rk-3(x) + rk-2(x) , 0≤deg rk-2<deg rk-3
rk-3(x) = qk-1rk-2(x) + rk-1(x) , 0≤deg rk-1<deg rk-2
rk-2(x) = qkrk-1(x) + rk(x) , rk(x)=0
经过有限个步骤，必然存在k使得rk(x)=0
2 算法描述
我实现的是F2域上面的多项式欧几里得除法
模2除法需要用到模2加减法,关于模2加减法,其实就是异或操作,规则如下:
//不需要考虑进位和借位
0 ± 0 = 0
1 ± 1 = 0
0 ± 1 = 1
1 ± 0 = 1
例: 1101 ± 1001 = 0100
计算如下:
1 1 0 1
± 1 0 0 1
-----------
0 1 0 0
简记:同为0,异为1
模2除法:
规则:假设被除数X,和除数P,余数R
1. 被除数X除以P(对X和P做模2加减法),被除数首位为1时,商1,为0时商0
2. 所得余数去除首位(左移一位):
- R第一位为0,将其作为新的被除数,除以0,此时其首位为0,商即为0
- R第一位为1,将其作为新的被除数,除以P,此时其首位为1,商即为1
3. 重复第2步直到R位数少于P位数
例:对除数1101做模2除法:
先说结果: 商1011余111
整体运算
1 0 1 1 //商
---------------
1 1 1 1 0 0 0 //被除数,注意首位为1
1 1 0 1 //被除数首位为1,除以除数
---------------
0 1 0 0 0 0 //余数去除首位,作为新的被除数
0 0 0 0 //被除数首位为0,除以0
---------------
1 0 0 0 0 //余数去除首位,作为新的被除数
1 1 0 1 //被除数首位为1,除以除数
---------------
1 0 1 0 //余数去除首位,作为新的被除数
1 1 0 1 //被除数首位为1,除以除数
---------------
0 1 1 1 //余数,此时java 数学基础余数位数少于除数,不能继续除了(忽略首位0)
3 算法实现
f(x),g(x)多项式采用二进制码输入，如x+1用11表示，程序用全局静态变量static Vector<Integer> ax和static Vector<Integer> bx存储，a(x),b(x)是函数Euclidean 的两个参数,函数进行a(x)/b(x)操作，操作完成之后a（x）存储余数，b（x）值不变，于是再将b(x),a(x)带入Euclidean函数重复操作，直到余数即a(x)运算之后存储的内容为0.运算结束。
流程图如下：
Invert（）函数是将vector存储的二进制码转化为多项式输出
从开始到结束遍历，分四种情况：
1、当前位是1 且不是最后两位（x，1），输出 x的几次方形式
if((i!=0)&(i!=1))
System.out.print("x^"+i);
2、当前位是1 且是最后一位输出1
if(i==0)
System.out.print("1");
3、当前位是1 且是倒数第二位输出 x
if(i==1)
System.out.print("x");
4、输出加号规则最后一位不输出+，当前的后面存在是1 输出+
if(i==0) continue;
else if(a.get(asize-i)==0) continue;
System.out.print("+");
Euclidean()函数用一个变量Vector<Integer> cx存储除得到的商，ax则在运算过程中不断变化。模2除法与长除法类似，但有个特点：不借位。说白了就是按位异或，相同为0，不同为1。
1、除数与被除数最高几位（与除数位数相同）做异或，商1。（除数首位必须为1） 用cx存储，ax每轮运算后去除首位数字，而且每轮循环对ax进行去0处理 否则ax=00001 会影响下一步运算
如果ax=00000，又会数组越界
2、余数先去掉首位，若此时余数最高位为1，商1，并对以它为除数继续模2除。
若最高位为0，则商0，重复步骤2。
3、直到余数位数小于除数位数时，运算结束。
for(int i=0;i<al-bl+1;i++) {
cx.add(i, ax.get(0));
int ax0 = ax.get(0);
for(int j=0;j<bl;j++) {
if(ax0==1)
ax.set(j, (ax.get(j)+bx.get(j))%2);
}
ax.remove(0);
}
int ax_length=ax.size();
for(int i=0;i<ax_length-1;i++) {
if(ax.get(0)==0) ax.remove(0);//去0处理
}
主函数main中，不停进行Euclidean函数操作，只要rx不为0.每轮循环结束时借助中间变量rx交换ax与bx，以便开启下一轮循环。
步骤： rx 清空; a赋值给r;
ax 清空; b赋值给a;
bx 清空; r赋值给b;
while(true) {
Euclidean(ax,bx);
//循环结束条件
int flag=0;
for(int i=0;i<ax.size();i++) {
if(ax.get(i)==1) flag=1;
}
if(flag==0) break;
rx.clear();
for(int i=0;i<ax.size();i++) rx.add(i, ax.get(i));
ax.clear();
for(int i=0;i<bx.size();i++) ax.add(i, bx.get(i));
bx.clear();
for(int i=0;i<rx.size();i++) bx.add(i, rx.get(i));
}
4 运行结果
为方便区分，输出中用括号分开两多项式
5 具体代码
2020.7.3回顾：
大二时候信安数学基础学的差，以为只可以实现F2域上的多项式除法，真傻（感谢老师当时接受那么菜那么傻的我）
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/1109.html