首页 > 代码库 > POJ 3318：Matrix Multiplication（随机算法）
POJ 3318：Matrix Multiplication（随机算法）
http://poj.org/problem?id=3318
题意：问A和B两个矩阵相乘能否等于C。
思路：题目明确说出（n^3）的算法不能过，但是通过各种常数优化还是能过的。
这里的随机算法指的是随机枚举矩阵C的一个位置，然后通过A*B计算是否能够得到矩阵C相应位置的数，如果不等，就直接退出了，如果跑过一定的数量后能够相等，那么就可以判断这个矩阵C等于A*B的。第一次见这样的题目。。。有点新奇。
暴力算法：
1 #include <cstdio> 2 using namespace std; 3 int a[505][505], b[505][505], c[505][505]; 4 5 int read() { 6 int num = 0, f = 0; 7 char c; 8 while((c = getchar()) == ‘ ‘ || c == ‘\n‘) ; 9 if(c == ‘-‘) f = 1;10 else num = c - ‘0‘;11 while((c = getchar()) >= ‘0‘ && c <= ‘9‘) num = num * 10 + c - ‘0‘;12 if(f) return -num;13 else return num;14 }15 16 void solve(int n) {17 for(int i = 1; i <= n; i++) {18 for(int j = 1; j <= n; j++) {19 int num = 0;20 for(int k = 1; k <= n; k++)21 num += a[i][k] * b[k][j];22 if(num != c[i][j]) { puts("NO"); return ; }23 }24 }25 puts("YES");26 }27 28 int main() {29 int n;30 while(~scanf("%d", &n)) {31 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = read();32 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) b[i][j] = read();33 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) c[i][j] = read();34 solve(n);35 }36 return 0;37 }
随机算法（试了好多次才对）：
1 #include <cstdio> 2 #include <ctime> 3 #include <cstdlib> 4 using namespace std; 5 int a[505][505], b[505][505], c[505][505]; 6 7 int main() { 8 srand((unsigned)time(NULL)); 9 int n;10 while(~scanf("%d", &n)) {11 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%d", &a[i][j]);12 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%d", &b[i][j]);13 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%d", &c[i][j]);14 bool f = 0;15 for(int t = 0; t < 60000; t++) {16 int row = rand() % n + 1;17 int col = rand() % n + 1;18 int num = 0;19 for(int i = 1; i <= n; i++)20 num = num + a[row][i] * b[i][col];21 if(num != c[row][col]) { f = 1; break; }22 }23 if(!f) puts("YES");24 else puts("NO");25 }26 return 0;27 }
POJ 3318：Matrix Multiplication（随机算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。