代码之家 › 专栏 › 技术社区 › Killroy

使用自定义运算符的高斯消元

math algorithm javascript

Killroy · 技术社区 · 15 年前

当运算符是自定义运算符而不是标准算术运算符时,实现高斯消元的好方法是什么?

操作员如下:

添加:

0 + 0 = 0
0 + 1 = 1
1 + 1 = 0

减法:

0 - 0 = 0
0 - 1 = 1
1 - 1 = 0

乘法:

0 * 0 = 0
0 * 1 = 0
1 * 1 = 1

师:

0 / 0 = illegal
0 / 1 = 0
1 / 1 = 1

下面是一组作为增广矩阵的公式示例,其中最右边的列是rhs:

1, 1, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 1, 1, 0, 0, 1, 0, 0, 0, 1
1, 0, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 0, 1
0, 0, 0, 1, 0, 0, 1, 0, 0, 1
0, 0, 0, 1, 1, 0, 1, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 1, 1

此集合的解决方案是:

x1 = 1
x2 = 0
x3 = 0
x4 = 0
x5 = 1
x6 = 1
x7 = 1
x8 = 1
x9 = 0

高斯消去法对我来说是失败的,因为我在这套装置上尝试过。

方程式有9、16、25或36项。如果算法可以很容易地扩展到更大的正方形,达到100,那就太好了。我正在寻找一种算法,最好是伪代码或JavaScript。

2 回复 | 直到 15 年前

RaYell 15 年前

在伪码中可以找到高斯消元算法 here .

不管你是用“正常”数字还是Z _二环,算法保持不变。

您可以做的是实现一个结构来保存您正在操作的值,并重载所有必要的运算符。然后,您需要做的就是将伪代码重写为您想要使用的语言。

不幸的是,由于您提到了javascript,您不能重写该语言中的运算符,因此这将变得更加复杂。我想您可以定义执行操作员作业的函数,并使用它们代替标准操作员。

function add(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return (v1 + v2) % 2;
}

function subtract(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return Math.abs((v1 - v2) % 2);
}

function multiply(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return v1 * v2;
}

function divide(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    } else if (v2 == 0) {
        alert('Divider cannot be zero');
        return;
    }

    return v1 / v2;
}

balpha 15 年前

您所描述的并不是真正的自定义运算符。相反,它是Z _二使用标准的加法和乘法模2。

这是一个 field ;所以您没有任何“分数”问题。

高斯消元算法不局限于实数域,也适用于Z域。 _二 .