Mô phỏng bài toán bằng thuật toán minmiax
Sau đó ta bấm để bắt đầu tiềm min max, giá trị trong dãy được chọn ngẫu nhiên trong khoảng -100 đến 100.
Ví dụ ta nhập số phần tử là 5 thì giao diện xuất hiện
14 trang |
Chia sẻ: tienthan23 | Lượt xem: 3941 | 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 thực hiện:
Đinh Hữu Luận
Đỗ Hoàng Cương
Đoàn Anh Khoa
Nguyễn Mai Chí Trung
TP.Hồ Chí Minh 2015
MỞ ĐẦU
------- -------
Trong mọi thời đại, việc tìm ra lời giải tối ưu cho một bài toán nào đó là một vấn đề rất khó để thực hiện. Đã có rất nhiều nghiên cứu để tìm ra các phương pháp hữu hiệu giải quyết các 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 hiện lời giải cho từng bài toán nhỏ này và từ đó 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 tế 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 có thể tìm ra lời giải dễ dàng bằng cách sử dụng phương pháp chia để trị
Hiểu rõ và cài đặt được các thuật toán, cũng như tìm ra lời giải 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 yêu cầu không thể thiếu đối với sinh viên nghành Tin học. Tuy nhiên, trong giới hạn của đề tài, chúng em không thể trình bày tất cả các thuật toán có liên quan đến đồ thị mà ở đây húng em chỉ trình bày “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 giải quyết
Phần 2:Cở sở lý thuyết
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 tham khảo
PHẦN 1
MỤC TIÊU VÀ HƯỚNG GIẢI QUYẾT
1. Mục tiêu:
Nắm vững các khái niệm của phương pháp chia để trị, các bước giải một bài toán dùng phương 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 giá được bài toán: ý tưởng, giải thuật, minh họa và đánh giá độ 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 giải quyết:
Về lý thuyết: tìm hiểu các khái niệm phương pháp chia để trị, giải thuật được yêu cầu trong đề tài.
Về chương trình: Sử dụng ngôn ngữ Visual Basic .Net ( Visual Basic 2008) để viết chương trình.
PHẦN 2
CƠ SỞ LÝ THUYẾT
Giới thiệu phương pháp chia để trị
Chia để trị là một trong những phương pháp thiết kế giải thuật cơ bản bao gồm các thao tác:
Chia: chia bài toán cần giải thành một loạt các bài toán con độc lập
Trị: đòi hỏi việc giải quyết các bài toán con thu được
Tổng hợp:thực hiện việc xây dựng lời giải của bài toán đặt ra từ các lời giải 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 các bài toán con S1, S2, S3..
Trị (conquer) : giải các bài toán con một cách đẹ quy
Tổng hợp (Combie) : tổng hợp lời giải các bài toán S1, S2, S3.. thành lời giải của bài toán S
Để phân tích độ phức tạp của thuật toán có thể sử dụng công thức đệ quy
Vấn đề đặt ra là cần giải các bài toán con độc lập bằng cách nào ? đó là vấn đề trung tâm 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[1r] của mảng a[1n].
Ý 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 kết quả lại
Nếu đoạn chia chỉ có 1 phần tử thì Min = Max và bằng phần tử đó.
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 hiện. Khi đó ta có:
T(n / 2) + T(n / 2) + 2;n > 2
T(n) = 1;n = 2
0;n = 1
Với n = 2k , thì
T(n) = 2 + 2T(n/2) = 2 + 22 + 22T(n/22) = .= 2k-1T(2) + ∑i=1k-12i
= ∑ki=1 2i – 2k-1 = 2k+1 – 2k-1 – 2 = (3n/2) – 2.
Vậy T(n) € O (n).
Cài đặt
Void MinMax(int a[.], int l, int r, int &Min, int &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 chắn 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ị phần tử 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 phần mềm:
Phần mềm được thiết kế trên giao diện Microsoft Visual bằng ngôn ngữ C#.
Sau đây chi tiết 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 để bắt đầu tiềm min max, giá trị trong dãy được chọn ngẫu nhiên trong khoảng -100 đến 100.
Ví dụ ta nhập số phần tử là 5 thì giao diện xuất hiện
Các số được chọn ngẫu nhiên
Hoặc có thể thấy các 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 hiện nhập lại giá trị mảng ta nhấn vào nút để trở lại giao diện ban đầu và có thể nhập lại số phần tử mảng.
Để thoát giao diện ta có thể bấm vào hoặc
Có thể bấm vào để biết thông tin chi tiết.
Các công nghệ sử dụng:
Sử dụng phần mềm Microsoft Visual 2010 (MV) để tạo giao diện.
Trong MV ta thiết kế trên Windown Form sử dụng ngôn ngữ 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