Monte Carlo Algorithms
Monte Carlo Algorithms
- Có 2 cách  chính xác cho kt quca
thut toán Monte Carlo:
1.Tng thi gian chy ca thut toán
2.Gi thut toán nhiu ln
Ví d:
Monte3 (x)
{ One = Monte (x);
Two = Monte (x);
Three = Monte (x);
if (One = Two) or (One = Three)
return One;
else return Two;
}
Monte Carlo Algorithms
Monte Carlo Algorithms
1. Majority Element: (Phn t?chim a s)
- M$c ích ca bài toán là tìm schim a strong
1 dãy só là schim h,n 50% trong dãy s.
- Gii quyt bài toán thông thưng O (n
2
) vì
phi so sánh tng c/p s1
Monte Carlo Algorithms
Monte Carlo Algorithms
int Timsochiemdaso (int a[], int n)
{ int count =0;
while (count <n/2)
{ for (int k=0;k<n;k++)
{ int choice = a[k];
for (int i=1;i<n;i++)
if (a[i] = choice) count++;
return choice;
}
}
Monte Carlo Algorithms
Monte Carlo Algorithms
-i vi gii thut Monte Carlo:
+ Ly ngHu nhiên 1 sn3m trong khong (1,n)
+ Kim tra xem v trí ca sngHu nhiên ó có
phi là sMajority không
+ Kt quca thut toán trvTrue ho/c False
+ Nu True 5Oìm ra ưc sMajority
+ Nu False Phép chn không chính xác
Th?v"i ln tip theo
+ Gii thut chúng khong 50% trong 1 s
trưng hp. Vì vy nu gi hàm 5 ln thì kt
quchính xác tng lên là 97% O(5N)=O(N)
Monte Carlo Algorithms
Monte Carlo Algorithms
bool Majority (int a[], int n)
{ choice = uniform (1,n); // Hàm ly 1 sngHu
nhiên t1n
int count =0;
for (int i=1;i<n;i++)
if (a[i] = a[choice])count++;
return (count >n/2);
}