Mô phỏng bài toán bằng thuật toán minmiax – Luận văn, đồ án, đề tài tốt nghiệp

14 trang |

Chia sẻ: tienthan23

| Lượt xem : 3458

| Lượt tải: 0

Bạn đang xem nội dung tài liệu Mô phỏng bài toán bằng thuật toán minmiax, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

TRƯỜNG ĐẠI HỌC TRẦN ĐẠI NGHĨA KHOA CÔNG NGHỆ THÔNG TIN MÔ PHỎNG BÀI TOÁN BẰNG THUẬT TOÁN MINMIAX Giáo viên hướng dẫn : Tiến sĩ – Phùng Thế Bảo Người triển khai : Đinh Hữu Luận Đỗ Hoàng Cương Đoàn Anh Khoa Nguyễn Mai Chí Trung TP.Hồ Chí Minh năm ngoái MỞ ĐẦU ——- ——- Trong mọi thời đại, việc tìm ra giải thuật tối ưu cho một bài toán nào đó là một yếu tố rất khó để triển khai. Đã có rất nhiều điều tra và nghiên cứu để tìm ra những chiêu thức hữu hiệu xử lý những bài toán tối ưu này. Có lẽ thuật toán được sử dụng nhiều nhất, quan trọng nhất là kỹ thuật “ chia để trị ”. Kỷ thuật này sẽ chia bài toán thành N bài toán nhỏ hơn, thực thi giải thuật cho từng bài toán nhỏ này và từ đó thiết kế xây dựng thuật toán cho bài toán tổng hợp. Một trong những bài toán trong thực tiễn ta thường gặp là : Sắp xếp trộn hoặc tìm giá trị Min Max và những bài toán trên hoàn toàn có thể tìm ra giải thuật thuận tiện bằng cách sử dụng giải pháp chia để trị Hiểu rõ và thiết lập được những thuật toán, cũng như tìm ra giải thuật tối ưu cho một bài toán nào đó dựa trên những tài liệu đã học là một nhu yếu không hề thiếu so với sinh viên ngành Tin học. Tuy nhiên, trong số lượng giới hạn của đề tài, chúng em không hề trình diễn toàn bộ những thuật toán có tương quan đến đồ thị mà ở đây húng em chỉ trình diễn “ bài toán Min Max ”. Đây cũng là nội dung chính của đề tài chúng em đã chọn. MỤC LỤC Phần 1 : Mục tiêu và hướng xử lý Phần 2 : Cở sở kim chỉ nan Bài toán Ý tưởng Giải thuật Minh họa Đánh giá độ phức tạp Phần 3 : Mô phỏng chương trình Giới thiệu về chương trình Mô tả bằng lời Mô tả bằng sơ đồ khối Kết quả Phần 4 : Tài liệu tìm hiểu thêm PHẦN 1 MỤC TIÊU VÀ HƯỚNG GIẢI QUYẾT 1. Mục tiêu : Nắm vững những khái niệm của chiêu thức chia để trị, những bước giải một bài toán dùng giải pháp chia để trị Nắm vững thuật toán “ bài toán MinMax ”. 2. Yêu cầu cần đạt : Thiết kế nhìn nhận được bài toán : sáng tạo độc đáo, giải thuật, minh họa và nhìn nhận độ phức tạp của giải thuật. Mô phỏng : mô phỏng bằng lời và bằng sơ đồ khối “ bài toán MinMax ” 3. Hướng xử lý : Về kim chỉ nan : khám phá những khái niệm chiêu thức chia để trị, giải thuật được nhu yếu trong đề tài. Về chương trình : Sử dụng ngôn từ Visual Basic. Net ( Visual Basic 2008 ) để viết chương trình. PHẦN 2 CƠ SỞ LÝ THUYẾT Giới thiệu chiêu thức chia để trị Chia để trị là một trong những chiêu thức phong cách thiết kế giải thuật cơ bản gồm có những thao tác : Chia : chia bài toán cần giải thành một loạt những bài toán con độc lập Trị : yên cầu việc xử lý những bài toán con thu được Tổng hợp : triển khai việc thiết kế xây dựng giải thuật của bài toán đặt ra từ những giải thuật của bài toán con. SƠ ĐỒ CHUNG Sơ đồ chung của thuật toán chia để trị ( Divide and Conquer ) gồm 3 thành phần Chia ( Divide ) : chia bài toán cần giải S ra thành những bài toán con S1, S2, S3 .. Trị ( conquer ) : giải những bài toán con một cách đẹ quy Tổng hợp ( Combie ) : tổng hợp giải thuật những bài toán S1, S2, S3 .. thành giải thuật của bài toán S Để nghiên cứu và phân tích độ phức tạp của thuật toán hoàn toàn có thể sử dụng công thức đệ quy Vấn đề đặt ra là cần giải những bài toán con độc lập bằng cách nào ? đó là yếu tố TT của bài toán. Bài toán MinMax Phát biểu bài toán Tìm giá trị Min, Max trong đoạn a [ 1 r ] của mảng a [ 1 n ]. Ý tưởng Tại mỗi bước, chia đôi đoạn cần tìm rồi tìm Min, Max của từng đoạn, sau đó tổng hợp hiệu quả lại Nếu đoạn chia chỉ có 1 thành phần thì Min = Max và bằng thành phần đó. Minh họa : I 1 2 3 4 5 6 7 8 A [ i ] 10 1 5 0 9 3 15 19 Tìm giá trị Min, Max trong đoạn a [ 2.7 ] của mảng a [ 1 .. 7 ] Ký hiệu : MinMax ( a, 1, r, Min, Max ) cho Min và Max trong đoạn a [ 1. r ] MinMax ( a, 2,7, Min, Max ) cho Min = 0 và Max = 15 trong đoạn a [ 2 .. 7 ] Thuật toán Input : a [ l .. r ], ( l ≤ r ) Output : Min = Min ( a [ l ], .., a [ r ] ), Max = Max ( a [ l ], .., a [ r ] ). MinMax ( a, l, r, Min, Max ) if ( l = = r ) { Min = a [ l ] ; Max = a [ l ] ; } Else { MinMax ( a, l, ( l + r ) / 2, Min1, Max1 ) ; MinMax ( a, ( l + r ) / 2 + 1, r, Min2, Max2 ) ; If ( Min1 < Min2 ) Min = Min1 ; Else Min = Min2 ; If ( Max1 > Max2 ) Max = Max1 ; Else Max = Max2 ; } Độ phức tạp thuật toán Gọi t ( n ) là số phép toán so sánh cần thực thi. Khi đó ta có : T ( n / 2 ) + T ( n / 2 ) + 2 ; n > 2 T ( n ) = 1 ; n = 2 0 ; n = 1 Với n = 2 k, thì T ( n ) = 2 + 2T ( n / 2 ) = 2 + 22 + 22T ( n / 22 ) =. = 2 k – 1T ( 2 ) + ∑ i = 1 k – 12 i = ∑ ki = 1 2 i – 2 k – 1 = 2 k + 1 – 2 k – 1 – 2 = ( 3 n / 2 ) – 2. Vậy T ( n ) € O ( n ). Cài đặt Void MinMax ( int a [. ], int l, int r, int và Min, int và Max ) { Int Min1, Min2, Max1, Max2 ; If ( l = = r ) { Min = a [ l ] ; Max = a [ l ] ; } Else { MinMax ( a, l, ( l + r ) / 2, Min1, Max1 ) ; MinMax ( a, ( l + r ) / 2 + 1, r, Min2, Max2 ) ; If ( Min1 < Min2 ) Min = Min1 ; Else Min = Min2 ; If ( Max1 > Max2 ) Max = Max1 ; Else Max = Max2 ; } } PHẦN 3 MÔ PHỎNG CHƯƠNG TRÌNH Giới thiệu về chương trình using System ; using System. Collections. Generic ; using System. ComponentModel ; using System. Data ; using System. Drawing ; using System. Linq ; using System. Text ; using System. Threading. Tasks ; using System. Windows. Forms ; namespace Chia_De_Tri___Min_Max { public partial class frmMain : Form { int [ ] manglamviec = null ; int min, max, x, y, n ; Button btnCreate = new Button ( ) ; public frmMain ( ) { InitializeComponent ( ) ; } void tim ( int [ ] manglamviec, int x, int y, ref int min, ref int max ) { int min1 = 0, min2 = 0, max1 = 100, max2 = 100 ; if ( x = = y ) { min = manglamviec [ x ] ; max = manglamviec [ x ] ; if ( btnCreate. Text = = min. ToString ( ) | | btnCreate. Text = = max. ToString ( ) ) { } } else { tim ( manglamviec, ( x + y ) / 2 + 1, y, ref min1, ref max1 ) ; tim ( manglamviec, x, ( x + y ) / 2, ref min2, ref max2 ) ; if ( min1 < min2 ) min = min1 ; else min = min2 ; if ( max1 < max2 ) max = max2 ; else max = max1 ; } } private void btnExit_Click_1 ( object sender, EventArgs e ) { DialogResult thongbao ; thongbao = MessageBox. Show ( " Bạn có chắc như đinh muốn thoát khỏi chương trình ? ", " Message ", MessageBoxButtons. YesNo, MessageBoxIcon. Question ) ; if ( thongbao = = DialogResult. Yes ) this. Close ( ) ; } private void btnReset_Click ( object sender, EventArgs e ) { txtPhanTu. Text = " " ; txtMax. Text = " " ; txtMin. Text = " " ; txtXuatmang. Text = " " ; txtPhanTu. Focus ( ) ; xoa ( ) ; } private void btnStart_Click ( object sender, EventArgs e ) { if ( txtMin. Text ! = " ". ToString ( ) ) { MessageBox. Show ( " Vui lòng Restart trước khi chạy lại chương trình ! ", " Thông báo " ) ; txtPhanTu. Focus ( ) ; } else { int dem = 0 ; try { n = int. Parse ( txtPhanTu. Text ) ; } catch { MessageBox. Show ( " Nhập giá trị thành phần mảng kiểu integer. ", " Thông báo ", MessageBoxButtons. OK, MessageBoxIcon. Information ) ; dem + + ; txtPhanTu. Focus ( ) ; } if ( dem = = 0 ) { int [ ] mangso = new int [ n ] ; / / khoi tao gia tri cho mang Random bien = new Random ( ) ; for ( int i = 0 ; i < n ; i + + ) { mangso [ i ] = bien. Next ( - 100, 100 ) ; } / / / duyet mang de xuat ra man hinh manglamviec = mangso ; txtXuatmang. Text = " " ; int dodai = mangso. Length ; for ( int i = 0 ; i < dodai ; i + + ) { txtXuatmang. Text + = mangso [ i ]. ToString ( ) + " " ; } x = 0 ; y = manglamviec. Length ; min = manglamviec [ 0 ] ; max = manglamviec [ y - 1 ] ; tim ( manglamviec, x, y - 1, ref min, ref max ) ; txtMax. Text = max. ToString ( ) ; txtMin. Text = min. ToString ( ) ; khoiTao ( ) ; if ( btnCreate. Text = = min. ToString ( ) | | btnCreate. Text = = max. ToString ( ) ) { btnCreate. Location = new Point ( 100, 50 ) ; } } } } private void txtPhanTu_KeyPress ( object sender, KeyPressEventArgs e ) { if ( ! char. IsDigit ( e. KeyChar ) ) e. Handled = true ; } public void khoiTao ( ) { int left = 30 ; int top = 240 ; int sizes = 9 * ( 420 / n ) / 10 ; int sizess = ( 420 / n ) ; for ( int i = 0 ; i < n ; i + + ) { Button btnCreate = new Button ( ) ; btnCreate. Text = manglamviec [ i ]. ToString ( ) ; btnCreate. ForeColor = Color. White ; btnCreate. BackColor = Color. Black ; btnCreate. Font = new Font ( btnCreate. Font, FontStyle. Bold ) ; btnCreate. Font = new Font ( " Time New Roman ", 12 ) ; btnCreate. Size = new Size ( sizes, 50 ) ; if ( btnCreate. Text = = txtMax. ToString ( ) | | btnCreate. Text = = txtMin. ToString ( ) ) { btnCreate. Location = new Point ( left, top + 300 ) ; } else { btnCreate. Location = new Point ( left, top ) ; } this. Controls. Add ( btnCreate ) ; left = left + sizess ; } } public void xoa ( ) { Application. Restart ( ) ; } private void btnAbout_Click ( object sender, EventArgs e ) { frmAbout frm = new frmAbout ( ) ; frm. Show ( ) ; } private void frmMain_Load ( object sender, EventArgs e ) { } } } Mô phỏng bằng lời Nội dung ứng dụng : Phần mềm được phong cách thiết kế trên giao diện Microsoft Visual bằng ngôn từ C #. Sau đây cụ thể về giao diện khi khởi động : Bắt đầu chương trình ta nhập N phần hay chiều dài của mảng như hình dưới : Sau đó ta bấm để khởi đầu tiềm min max, giá trị trong dãy được chọn ngẫu nhiên trong khoảng chừng - 100 đến 100. Ví dụ ta nhập số thành phần là 5 thì giao diện Open Các số được chọn ngẫu nhiên Hoặc hoàn toàn có thể thấy những giá trị ngẫu nhiên bên trên góc phải giao diện Kết quả tìm được giá trị Min Max sẽ xuất hiên Để thực thi nhập lại giá trị mảng ta nhấn vào nút để trở lại giao diện bắt đầu và hoàn toàn có thể nhập lại số thành phần mảng. Để thoát giao diện ta hoàn toàn có thể bấm vào hoặc Có thể bấm vào để biết thông tin cụ thể. Các công nghệ tiên tiến sử dụng : Sử dụng ứng dụng Microsoft Visual 2010 ( MV ) để tạo giao diện. Trong MV ta phong cách thiết kế trên Windown Form sử dụng ngôn từ C # để viết chương trình. Sau đây là sơ đồ khối : Nhập N, a [ l .. r ], ( l ≤ r ) END Min1, Min2, Max1, Max2 Min = a [ l ] Max = a [ l ] if ( l = = r ) MinMax ( a, l, ( l + r ) / 2, Min1, Max1 ) ; MinMax ( a, ( l + r ) / 2 + 1, r, Min2, Max2 ) Min = Min2 If ( Min1 < Min2 ) Min = Min1 Max = Max2 If ( Max1 > Max2 ) Max = Max1 Min = Min ( a [ l ], .., a [ r ] ) Max = Max ( a [ l ], .., a [ r ] ). MinMax ( a, l, r, Min, Max ) Begin Sai Sai Sai Đúng Đúng Đúng
Các file đính kèm theo tài liệu này :

• giai_thuat_8799.docx

Source: https://vh2.com.vn
Category : Tin Học