Cấu trúc dữ liệu và giải thuật (phần 23)

Tiếp tục với chuỗi bài về xác suât thống kê trong lập trình đây là phần cuối cùng trong chuỗi bài giảng về cấu trúc dữ liệu và giải thuật, bạn sẽ hiện thực một số đoạn code vê các thuật toán về toán trong lập trình
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật (phần 23) Monte Carlo Algorithms Monte- Có 2 cách tăng chính xác cho k t qu c a thu t toán Monte Carlo:1.Tăng th i gian ch y c a thu t toán2.G i thu t toán nhi u l nVí 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 Monte1. Majority Element: (Ph n t chi m a s ) - M c ích c a bài toán là tìm s chi m a s trong 1 dãy s ó là s chi m hơn 50% trong dãy s . Gi i quy t bài toán thông thư ng O (n2) vì - ph i so sánh t ng c p s 1 Monte Carlo Algorithms Monteint Timsochiemdaso (int a[], int n){ int count =0; while (count Monte Carlo Algorithms Monte i v i gi i thu t Monte Carlo:- + L y ng u nhiên 1 s n m trong kho ng (1,n) + Ki m tra xem v trí c a s ng u nhiên ó có ph i là s Majority không + K t qu c a thu t toán tr v True ho c False + N u True ã tìm ra ư c s Majority + N u False Phép ch n không chính xác Th v i l n ti p theo + Gi i thu t ch úng kho ng 50% trong 1 s trư ng h p. Vì v y n u g i hàm 5 l n thì k t qu chính xác tăng lên là 97% O(5N)=O(N) Monte Carlo Algorithms Montebool Majority (int a[], int n){ choice = uniform (1,n); // Hàm l y 1 s ng u nhiên t 1 n int count =0; for (int i=1;in/2);} Monte Carlo Algorithms Monte2. Monte Carlo Prime Testing: - Ki m tra s N có ph i là s nguyên t hay không b ng cách s d ng thu t toán Monte Carlo. - Ch n 1 s A ng u nhiên t 2 sqrt(N) - N u N chia h t cho a N không ph i là s nguyên t - N u N không chia h t cho a Chưa ch c kh ng nh N là s nguyên t - Xác su t cho k t qu úng c a bài toán ch 1,2% Las Vegas Algorithms LasGi i thi u:- Gi i thu t Las Vegas không bao gi tr v 1 k t qu sai. Tuy nhiên, th nh tho ng không tr v k t qu .- S l n ch y thu t toán càng nhi u thì xác su t thành công càng cao- Ý tư ng cơ b n c a gi i thu t Las Vegas: Ch n ng u nhiên 1 quy t nh, và ki m tra xem quy t nh ó có d n n 1 k t qu thành công hay không- Gi i thu t s l p l i cho n khi có ư c 1 k t qu thành công Las Vegas Algorithms LasVí d :- Success (x) – Là s l n cho k t qu thành công.- Failure(x) – Là s l n cho k t qu sai.- P(x) – Xác su t gi i thu t cho ra k t qu thành công S l n ch y gi i thu t Time(x)Time(x) = p(x) *S(x) + (1-p(x))*(F(x) + Time(x))Time(x) = S(x) + (1-p(x))/p(x)*F(x) Las Vegas Algorithms Las ng d ng: Bài toán 8 quân h u1. Gi i b ng qui quay lui2. Las Vegas Algorithm:- t quân h u 1 t i v trí b t kì hàng u tiên.- Ti p theo t quân h u 2 v trí b t kì hàng 2 sao cho chúng không ăn nhau v i quân h u 1.- Ti p t c cho n quân h u 8- K t qu c a gi i thu t có th là True ho c False. Las Vegas s gi i ti p cho n khi t k t qu True Las Vegas Algorithms LasGi i thu t:bool LasVegasQueeen ( result) // ưa ra v trí c t cho m i dòng{ row = 1; do{ spot =0; for (int i=1;i0) result[row] = try; }while ((spot = 0) or (row =9))