首页 > 代码库 > [ACM] POJ 3318 Matrix Multiplication (随机化算法）
[ACM] POJ 3318 Matrix Multiplication (随机化算法）
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 16118 | Accepted: 3485 |
Description
You are given three n × n matrices A, B and C. Does the equation A × B = C hold true?
Input
The first line of input contains a positive integer n (n ≤ 500) followed by the the three matrices A, B and C respectively. Each matrix‘s description is a block of n × n integers.
It guarantees that the elements of A and B are less than 100 in absolute value and elements of C are less than 10,000,000 in absolute value.
Output
Output "YES" if the equation holds true, otherwise "NO".
Sample Input
2 1 0 2 3 5 1 0 8 5 1 10 26
Sample Output
YES
Hint
Source
题意为给定N*N的矩阵 A,B,C ， 如果A*B=C，输出YES，否则输出NO。
第一次接触随机化算法，真的很奇妙。利用计算机随机给出符合题意的值，再根据题意关系计算是否出现矛盾，如果出现，则不成功。比如本题，就随机给出一个行数row，一个列数col， 那么必须有
for(int i=1;i<=n;i++)
temp+=A[row][i]*B[i][col]; temp==C[row][col] ;
如果 出现不相等，那么肯定是不符合A*B=C的。但是这里随机的次数是个问题，开大了怕超时，开小了怕得不出正确答案，所以尽量比所有可能情况多一点。这种弊端会在下面第二种方法中解决。
百度百科说的很好：
随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。随机化算法基于随机方法，依赖于概率大小。
在我们的生活中，人们经常会去掷色子来看结果，投硬币来决定行动，这就牵涉到一个问题：随机。
这种算法看上去是凭着运气做事，其实，随机化算法是有一定的理论基础的，我们可以想象，在[1,10000]这个闭区间里，随机1000次，随机到2这个数的几率是多大(约为0.1)，何况1000次的随机在计算机程序中仅仅是一眨眼的功夫。可以看出，随机化算法有着广阔的前景。只是由于随机化算法比较难于掌控，所以并不是很多人都接触过他，但肯定有很多人都听说过。
例一
例二
第一种方法代码：
#include <iostream>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int maxn=510;
int A[maxn][maxn];
int B[maxn][maxn];
int C[maxn][maxn];
int n;
void input(int c[maxn][maxn])
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&c[i][j]);
}
bool ok()
{
int row,col;//随机行数，列数
for(int k=1;k<=30000;k++)
{
row=rand()%n+1;
col=rand()%n+1;
int temp=0;
for(int i=1;i<=n;i++)
temp+=A[row][i]*B[i][col];
if(temp!=C[row][col])
return false;
}
return true;
}
int main()
{
scanf("%d",&n);
srand(time(NULL));
input(A);
input(B);
input(C);
if(ok())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}第二种方法：
左乘一个一行N列的向量 r[], 那么 肯定有 r*A*B=r*C
代码：
#include <iostream>
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int maxn=510;
int A[maxn][maxn];
int B[maxn][maxn];
int C[maxn][maxn];
int r[maxn];
int rA[maxn];
int rAB[maxn];
int rC[maxn];
int n;
void input(int c[maxn][maxn])
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&c[i][j]);
}
bool ok()
{
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
{
rA[j]+=r[i]*A[i][j];
rC[j]+=r[i]*C[i][j];
}
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
rAB[j]+=rA[i]*B[i][j];
for(int i=1;i<=n;i++)
if(rAB[i]!=rC[i])
return false;
return true;
}
int main()
{
scanf("%d",&n);
srand(time(NULL));
input(A);
input(B);
input(C);
memset(rA,0,sizeof(rA));
memset(rAB,0,sizeof(rAB));
memset(rC,0,sizeof(rC));
for(int i=1;i<=n;i++)
r[i]=rand()%99+1;
if(ok())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}