Thuật toán Freivald xác định xem hai ma trận có bằng nhau hay không cho giá trị k được chọn với xác suất thất bại nhỏ hơn 2^-k trong thời gian O(kn^2). Thuật toán này được dùng để kiểm tra phép nhân ma trận.
Thuật toán
Bắt đầu
Nhập matrix1(n*n), matrix2(n*n), matrix3(n*n).
// Cần kiểm tra: matrix1 × matrix2 = matrix3.
1) Chọn vector a[n][1] ngẫu nhiên, đồng đều, các thành phần là 0 hoặc 1.
2) Tính matrix2 * a, matrix3 * a, rồi matrix1 * (matrix2 * a)
để đánh giá biểu thức matrix1 * (matrix2 * a) - matrix3 * a.
3) Kiểm tra xem matrix1 * (matrix2 * a) - matrix3 * a có bằng 0 hay không.
4) Nếu bằng 0, nhân ma trận đúng, ngược lại sai.
Kết thúc.
Ví dụ mã nguồn
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main(int argc, char **argv) {
cout << "Nhập kích thước ma trận: ";
int n;
cin >> n;
cout << "Nhập ma trận thứ nhất: ";
double matrix1[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix1[i][j];
}
}
cout << "Nhập ma trận thứ hai: ";
double matrix2[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix2[i][j];
}
}
cout << "Nhập ma trận kết quả: ";
double matrix3[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix3[i][j];
}
}
double a[n][1];
for (int i = 0; i < n; i++) {
a[i][1] = rand() % 2;
}
double matrix2a[n][1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 1; j++) {
for (int k = 0; k < n; k++) {
matrix2a[i][j] = matrix2a[i][j] + matrix2[i][k] * a[k][j];
}
}
}
double matrix3a[n][1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 1; j++) {
for (int k = 0; k < n; k++) {
matrix3a[i][j] = matrix3a[i][j] + matrix3[i][k] * a[k][j];
}
}
}
double matrix12a[n][1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 1; j++) {
for (int k = 0; k < n; k++) {
matrix12a[i][j] = matrix12a[i][j] + matrix1[i][k] * matrix2a[k][j];
}
}
}
for (int i = 0; i < n; i++) {
matrix12a[i][0] -= matrix3a[i][0];
}
bool flag = true;
for (int i = 0; i < n; i++) {
if (matrix12a[i][0] == 0)
continue;
else
flag = false;
}
if (flag == true)
cout << "Đây là ma trận kết quả";
else
cout << "Đây KHÔNG phải ma trận kết quả";
return 0;
}
Kết quả 1
Nhập kích thước ma trận: 2 Nhập ma trận thứ nhất: 1 2 3 4 Nhập ma trận thứ hai: 2 0 1 2 Nhập ma trận kết quả: 4 4 10 8 Đây là ma trận kết quả
Kết quả 2
Nhập kích thước ma trận: 2 Nhập ma trận thứ nhất: 1 2 3 4 Nhập ma trận thứ hai: 2 0 1 2 Nhập ma trận kết quả: 4 5 5 5 Đây KHÔNG phải ma trận kết quả