南郵 OJ 1340 逆矩陣問題

逆矩陣問題

時間限制(普通/Java) :  1000 MS/ 3000 MS          運作記憶體限制 : 65536 KByte

總送出 : 51            測試通過 : 24 

比賽描述

給定2 個n×n矩陣a 和b，試設計一個判定a 和b 是否互逆的蒙特卡羅算法，算法的計算時間應為O(n2)。設計一個蒙特卡羅算法，對于給定的矩陣a和b，判定其是否互逆。

輸入

輸入的第一行有1個正整數n，表示矩陣a和b 為n×n矩陣。接下來的2n行，每行有n個實數，分别表示矩陣a和b 中的元素。

輸出

矩陣a 和b 互逆則輸出YES，否則輸出NO。

樣例輸入

3

1 2 3

2 2 3

3 3 3

-1 1 0

1 -2 1

0 1 -0.666667

樣例輸出

YES

提示

題目來源

算法設計與實驗題解

#include<iostream>
#define MAX_N 100
#define LIMIT (1e-3)
double a[MAX_N][MAX_N];
double b[MAX_N][MAX_N];

bool equal(double a, double b){
	a -= b;
	if( a<LIMIT && a>-LIMIT){
		return 1;
	}else{
		return 0;
	}
}

int main(){
	freopen("test.txt","r",stdin);
	int n,i,j,k;
	double temp;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			scanf("%lf",&a[i][j]);
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			scanf("%lf",&b[i][j]);
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			temp = 0;
			for(k=0;k<n;k++){
				temp += a[i][k]*b[k][j];
			}
			if(i==j && !equal(temp,1) ||
				i!=j && !equal(temp,0)){
				printf("NO\n");
				return 0;
			}
		}
	}
	printf("YES\n");
}