Code 備忘錄►Math

STEP5::Problem 0129 : 驗算

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0129
這題是矩陣乘法，但是直接乘一定會爆掉(n^3)，所以要利用矩陣乘法的結合率(矩陣沒有交換率，但有結合率)，先randen一個1n的矩陣L，(AL)(BL)=(C*L)，這樣的情況有兩種:

1.不一樣，錯了就錯了
2.對了，不一定對(因為這樣算法會出現剛好一樣得狀況)

這就延伸出雖機的算法了，隨機演算法有 Las Vegas algorithm 和 Monte Carlo algorithm等等，其中 Las Vegas是一種猜測答案會對的演算法，而Monte Carlo則是利用機率來提高自己答案的正確性，以這題來說，因為錯了就錯了，但是對了有1/2的機會還是錯的，所以就多randen幾個L，做五次錯的機率就變成 1/2^5=1/32，基本上就AC了，而且出測資的人又不知道你的randen是多少ㄏ….。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdlib>
#include <iostream>
#include <cstdio>

using namespace std;

void pa(int[][1000],int[],int[]);
void mkl(int[]);
int in(void);

int n,a[1000][1000],b[1000][1000],c[1000][1000];
char t[1];
int main(int argc, char *argv[])
{
    
    srand(2);
    //scanf("%d\n",&n);
    n=in();
    
    //gets(t);
    for(int i=0;i<n;i++){
            for(int l=0;l<n;l++){
                    a[i][l]=in();//scanf("%d",&);
            }
    }
    
    for(int i=0;i<n;i++){
            for(int l=0;l<n;l++){
                    b[i][l]=in();//scanf("%d",&);
            }
    }
    //printf("%d %d",c[0][0],c[0][1]);
    
    //puts("YYY");
    for(int i=0;i<n;i++){
            for(int l=0;l<n;l++){
                    c[i][l]=in();//scanf("%d",&);
            }
    }
    
    for(int h=0;h<5;h++){        
            int l[1000]={0},lb[1000]={0},lab[1000]={0},lc[1000]={0};
            mkl(l);
            pa(b,l,lb);
            pa(a,lb,lab);
            pa(c,l,lc);
            
            for(int i=0;i<n;i++){
                   if(lab[i]!=lc[i]){
                           //printf("%d %d  ",lab[i],lc[i]);
                           printf("Bad\n");
                           //system("PAUSE");
                           return EXIT_SUCCESS;
                   }
            }
            
            
    }        
    printf("Good\n");
    //else{
            /*scanf("%d",&w);
            if(n>950&&w<100){
                   printf("Good\n");
            }else if(w>1000){
                   printf("Good\n");
            }else{
                   printf("Bad\n");
            }*/
            
    //}
    
    //system("PAUSE");
    return EXIT_SUCCESS;
}

void pa(int aa[][1000],int ll[],int lf[]){
       for(int i=0;i<n;i++){
              for(int l=0;l<n;l++){
                      lf[i]+=ll[l]*aa[i][l];
              }
              //printf("%d  ",lf[i]);
       }
}

void mkl(int _l[]){
       //_l[0]=1;
      //_l[1]=2;
       
       
       for(int i=0;i<n;i++){
               _l[i]=rand()%10;
       }
}

int in()   
{   
  char cha;   
  unsigned int x=0,flag=1;   
  while(cha=getchar())   
  if(cha!=' '&&cha!='\n')break;   
  if(cha!='-'){
       x=x*10+cha-'0';  
   }else{
         flag=-1; 
   }  
  while(cha=getchar())    
    {   
     if(cha==' '||cha=='\n') break;   
      x=x*10+cha-48;   
    }   
    return x*flag;   
}