poj3318(随机化算法)

本文主要是介绍poj3318(随机化算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：点击打开链接

题意：给出三个n*n的矩阵A,B,C，问是否存在A*B=C(n<=500)

代码：

#include <math.h>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int r[505],rA[505],rAB[505],rC[505];
int A[505][505],B[505][505],C[505][505];
int main(){                                     //因为矩阵乘法是O(n^3)，但是int n,i,j,sign;                             //当其中一个矩阵只有一维时，复杂度则while(scanf("%d",&n)!=EOF){                 //为O(n*n)所以当A*B=C时，H*(A*B)=H*Cfor(i=1;i<=n;i++)                       //所以我们可以构造一个只有一维的矩阵Hfor(j=1;j<=n;j++)                       //但是当A*B!=C时，也可能有许多H满足条scanf("%d",&A[i][j]);                   //件为了避免这种情况发生，因此采用随机for(i=1;i<=n;i++)                       //化算法随机产生H矩阵for(j=1;j<=n;j++)scanf("%d",&B[i][j]);for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&C[i][j]);for(i=1;i<=n;i++)                       //随机化是有理论依据的，只不过太菜不会证明而已.....r[i]=rand()%100+1;memset(rA,0,sizeof(rA));memset(rAB,0,sizeof(rAB));memset(rC,0,sizeof(rC));for(i=1;i<=n;i++){for(j=1;j<=n;j++)rA[i]+=r[j]*A[j][i];}for(i=1;i<=n;i++){for(j=1;j<=n;j++)rAB[i]+=rA[j]*B[j][i];}for(i=1;i<=n;i++){for(j=1;j<=n;j++)rC[i]+=r[j]*C[j][i];}sign=0;for(i=1;i<=n;i++)if(rAB[i]!=rC[i]){sign=1;break;}if(sign)puts("NO");elseputs("YES");cout<<endl;}return 0;
}

这篇关于poj3318(随机化算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---