[Download] Quy Hoạch Động trạng thái – Tải File Word, PDF Miễn Phí

  • Loading …
    Loading …
    Loading …

Thông tin tài liệu

Ngày đăng: 23/11/2014, 05:00

Download

Quy hoạch động là một phương pháp thường được sử dụng để giải các bài toántrong tin học. Trong một số bài toán giải bằng phương pháp này khi xét tại mỗibước thường có nhiều khả năng lựa chọn ta gọi là các trạng thái. Chẳng hạn đểtìm lời giải cho bài toán ta đi lần lượt từ bước 1 đến bước thứ K, tại bước thứ icó nhiều lựa chọn (trạng thái) khác nhau, để tìm hướng đi đúng cho bước thứ ilại dựa vào các trạng thái của bước thứ i1 và có thể xác định bằng một côngthức cụ thể nếu tập các trạng thái là hữu hạn. Khi gặp các bài toán loại này tathường giải bằng phương pháp quy hoạch động trạng thái.Trong quá trình giảng dạy các lớp chuyên tin học và ôn luyện học sinh giỏiquốc gia, tôi nhận thấy tài liệu viết về vấn đề này rất hạn chế. Để hiểu hơn vềphương pháp này chúng ta cùng tìm hiểu một bài toán cụ thể.Cho một bảng hình chữ nhật kích thước 4×n ô vuông. Các dòng được đánh sốtừ 1 đến 4, từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải.Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên mỗi ô (i,j) có ghimột số nguyên aij , i =1, 2, 3, 4; j =1, 2, …, n. Một cách chọn ô là việc xác địnhmột tập con khác rỗng S của tập tất cả các ô của bảng sao cho không có hai ônào trong S có chung cạnh. Các ô trong tập S được gọi là ô được chọn, tổng cácsố trong các ô được chọn được gọi là trọng lượng của cách chọn.Chuyến du lịch (TRIP)Trong kì nghỉ hè năm nay sherry được bố thưởng cho 1 tour du lịch quanh Nđất nước tươi đẹp với nhiều thắng cảnh nổi tiếng (vì sherry rất ngoan ). Tấtnhiên sherry sẽ đi bằng máy bay.Giá vé máy bay từ đất nước i đến đất nước j là Cij(dĩ nhiên Cijcó thể khác Cji).Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng sherry cũng muốn tìmcho mình 1 hành trình với chi phí rẻ nhất có thể để dành tiền mua quà về tặngmọi người ( Các chuyến bay của sherry đều được đảm bảo an toàn tuyệt đối ).Bạn hãy giúp sherry tìm 1 hành trình đi qua tất cả các nước, mỗi nước đúng 1lần sao cho chi phí là bé nhất nhé.Cô gái chăn bò (COWGIRL)Trên một thảo nguyên nhỏ bé có 1 gia đình gồm 3 anh em: 2 người anh trai làNvutri và Andorea còn người em gái là Lola. Cuộc sống gia đình khá giảnhưng gia đình có truyền thống chăn nuôi và muốn để các con tự lập nên chamẹ 3 người quyết định để các con hằng ngày sẽ đi chăn 1 số bò nào đó (tùy ý 3người con).Thảo nguyên là 1 cánh đồng chia làm MN ô vuông, mỗi con bò chỉ đứngtrong 1 ô và mỗi ô chỉ chứa 1 con bò.Chỉ có 1 quy tắc duy nhất là không baogiờ được để 4 con bò tạo thành 1 hình vuông 22 hoặc để trống 1 khu đất 22.Hai người anh mải chơi nên đã hối lộ kem để Lola chăn bò 1 mình. Lolamuốn biết tất cả có bao nhiêu cách xếp bò thỏa mãn quy tắc trên để đề phòngmọi trường hợp. Vì con số này rất lớn nên hãy giúp Lola tính toán con số nàyĐàn bò hỗn loạn (MIXUP)Mỗi trong N cô bò (4

– Xem thêm –

Bạn đang xem: [Download] Quy Hoạch Động trạng thái – Tải File Word, PDF Miễn Phí

Xem thêm: Quy Hoạch Động trạng thái, Quy Hoạch Động trạng thái

Hy vọng thông qua bài viết Quy Hoạch Động trạng thái . Bạn sẽ tìm được cho mình những tài liệu học tập bổ ích nhất.

[Download] Quy Hoạch Động trạng thái – Tải File Word, PDF Miễn Phí

  • Loading …
    Loading …
    Loading …

Thông tin tài liệu

Ngày đăng: 23/11/2014, 05:00

Download

Quy hoạch động là một phương pháp thường được sử dụng để giải các bài toántrong tin học. Trong một số bài toán giải bằng phương pháp này khi xét tại mỗibước thường có nhiều khả năng lựa chọn ta gọi là các trạng thái. Chẳng hạn đểtìm lời giải cho bài toán ta đi lần lượt từ bước 1 đến bước thứ K, tại bước thứ icó nhiều lựa chọn (trạng thái) khác nhau, để tìm hướng đi đúng cho bước thứ ilại dựa vào các trạng thái của bước thứ i1 và có thể xác định bằng một côngthức cụ thể nếu tập các trạng thái là hữu hạn. Khi gặp các bài toán loại này tathường giải bằng phương pháp quy hoạch động trạng thái.Trong quá trình giảng dạy các lớp chuyên tin học và ôn luyện học sinh giỏiquốc gia, tôi nhận thấy tài liệu viết về vấn đề này rất hạn chế. Để hiểu hơn vềphương pháp này chúng ta cùng tìm hiểu một bài toán cụ thể.Cho một bảng hình chữ nhật kích thước 4×n ô vuông. Các dòng được đánh sốtừ 1 đến 4, từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải.Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên mỗi ô (i,j) có ghimột số nguyên aij , i =1, 2, 3, 4; j =1, 2, …, n. Một cách chọn ô là việc xác địnhmột tập con khác rỗng S của tập tất cả các ô của bảng sao cho không có hai ônào trong S có chung cạnh. Các ô trong tập S được gọi là ô được chọn, tổng cácsố trong các ô được chọn được gọi là trọng lượng của cách chọn.Chuyến du lịch (TRIP)Trong kì nghỉ hè năm nay sherry được bố thưởng cho 1 tour du lịch quanh Nđất nước tươi đẹp với nhiều thắng cảnh nổi tiếng (vì sherry rất ngoan ). Tấtnhiên sherry sẽ đi bằng máy bay.Giá vé máy bay từ đất nước i đến đất nước j là Cij(dĩ nhiên Cijcó thể khác Cji).Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng sherry cũng muốn tìmcho mình 1 hành trình với chi phí rẻ nhất có thể để dành tiền mua quà về tặngmọi người ( Các chuyến bay của sherry đều được đảm bảo an toàn tuyệt đối ).Bạn hãy giúp sherry tìm 1 hành trình đi qua tất cả các nước, mỗi nước đúng 1lần sao cho chi phí là bé nhất nhé.Cô gái chăn bò (COWGIRL)Trên một thảo nguyên nhỏ bé có 1 gia đình gồm 3 anh em: 2 người anh trai làNvutri và Andorea còn người em gái là Lola. Cuộc sống gia đình khá giảnhưng gia đình có truyền thống chăn nuôi và muốn để các con tự lập nên chamẹ 3 người quyết định để các con hằng ngày sẽ đi chăn 1 số bò nào đó (tùy ý 3người con).Thảo nguyên là 1 cánh đồng chia làm MN ô vuông, mỗi con bò chỉ đứngtrong 1 ô và mỗi ô chỉ chứa 1 con bò.Chỉ có 1 quy tắc duy nhất là không baogiờ được để 4 con bò tạo thành 1 hình vuông 22 hoặc để trống 1 khu đất 22.Hai người anh mải chơi nên đã hối lộ kem để Lola chăn bò 1 mình. Lolamuốn biết tất cả có bao nhiêu cách xếp bò thỏa mãn quy tắc trên để đề phòngmọi trường hợp. Vì con số này rất lớn nên hãy giúp Lola tính toán con số nàyĐàn bò hỗn loạn (MIXUP)Mỗi trong N cô bò (4

– Xem thêm –

Bạn đang xem: [Download] Quy Hoạch Động trạng thái – Tải File Word, PDF Miễn Phí

Xem thêm: Quy Hoạch Động trạng thái, Quy Hoạch Động trạng thái

Hy vọng thông qua bài viết Quy Hoạch Động trạng thái . Bạn sẽ tìm được cho mình những tài liệu học tập bổ ích nhất.