BẢN BÁO CÁO THỰC HÀNH TOÁN RỜI RẠC

Ngày nay, Công nghệ thông tin là một trong những ngành đang phát triển rất mạnh mẽ và có ảnh hưởng sâu rộng đến mọi mặt đời sống. Nó là nền tảng của nền kinh tế tri thức, là thước đo trình độ phát triển của một quốc gia.Vì vậy, việc đào tạo đội ngũ kỹ sư công nghệ thông tin có chất lượng đòi hỏi phải được chú trọng và đầu tư đúng mức.
Nội dung trích xuất từ tài liệu:
BẢN BÁO CÁO THỰC HÀNH TOÁN RỜI RẠC TH Toán Rời Rạc Trang 1  TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG KHOA CÔNG NGHỆ THÔNG TIN  BẢN BÁO CÁO THỰC HÀNH TOÁN RỜI RẠC Giáo viên hướng dẫn: Thầy Nguyễn Văn Nguyên Nhóm : Lớp : 07T1 Sinh viên thực hiện : Nguyễn Thị Quỳnh Mai SV: Nguyễn Thị Quỳnh Mai Lớp 07T1 TH Toán Rời Rạc Trang 2  Đà Nẵng – Tháng 8/2010 LỜI NÓI ĐẦU Ngày nay, Công nghệ thông tin là một trong những ngành đang phát triển rất mạnh mẽ và có ảnh hưởng sâu rộng đến mọi mặt đời sống. Nó là nền tảng của nền kinh tế tri thức, là thước đo trình độ phát triển của một quốc gia.Vì vậy, việc đào tạo đội ngũ kỹ sư công nghệ thông tin có chất lượng đòi hỏi phải được chú trọng và đầu tư đúng mức. Đại học là môi trường cơ bản cung cấp kiến thức chuyên môn, giúp sinh viên hình thành và phát triển những kĩ năng cần thiết cho công việc. Vì vậy, học đi đôi với hành luôn là phương châm đào tạo hàng đầu trong các trường đại học hiện nay. Cùng với học phần lý thuyết, học phần Thực Hành Toán Rời Rạc giúp nâng cao khả năng tư duy của sinh viên. Trên cơ sở đề bài thực hành được nhận, sinh viên phải biết cách phân tích và cài đặt để giải quyết các bài toán liệt kê, lập lịch, … nhằm giải quyết những bài toán có tính ứng dụng thực tế cao. Em xin chân thành cảm ơn giáo viên hướng dẫn – thầy Nguyễn Văn Nguyên đã giúp đỡ và chỉ dẫn em hoàn thành bài báo cáo này. Đà Nẵng, ngày 9 tháng 7 năm 2010 SV: Nguyễn Thị Quỳnh Mai Lớp 07T1 TH Toán Rời Rạc Trang 3  MỤC LỤC I. BÀI 1: BÀI TOÁN ĐẾM – BÀI TOÁN LIỆT KÊ......................................4 1.Đề bài:......................................................................................................4 2.Thuật toán:...............................................................................................4 3.Mã nguồn:................................................................................................6 4.Demo: ....................................................................................................10 II. BÀI 2:BÀI TOÁN TỐI ƯU RỜI RẠC................................................... 12 1.Đề bài:....................................................................................................12 2.Thuật toán:.............................................................................................12 3.Mã nguồn:..............................................................................................14 4.Demo:.....................................................................................................17 III.BÀI 3: BÀI TOÁN TRÊN ĐỒ THỊ.........................................................18 1.Đề bài:....................................................................................................18 2.Thuật toán:.............................................................................................18 3.Mã nguồn:..............................................................................................19 4.Demo: .................................................................................................22 SV: Nguyễn Thị Quỳnh Mai Lớp 07T1 TH Toán Rời Rạc Trang 4  BÀI 1: BÀI TOÁN ĐẾM – BÀI TOÁN LIỆT KÊ I. 1.Đề bài: 1. Đếm số xâu nhị phân độ dài n: a) Bất kỳ. b) Không có hai bit 0 kề nhau. c) Có ít nhất hai bit 0 kề nhau. 2. Viết chương trình liệt kê tất cả các xâu nhị phân độ dài n như yêu cầu của bài toán 1. Liệt kê có số thứ tự để kiểm tra kết quả đã đếm được. Thử nhập với nhiều giá trị khác nhau của n. Lưu ý các trường hợp n=1 và n=2. 3. Viết chương trình nhập một xâu chữ gồm n chữ cái hoa (A..Z)-trong đó có một số chữ cái lặp. Liệt kê tất cả các cách sắp xếp n chữ cái này. Có đếm tổng số cách sắp xếp. 4. Xét phương trình nguyên: x1+x2+..+xn=k với xi≥0 ∀i=1..k. Viết chương trình nhập n,k và in ra tất cả các nghiệm của phương trình.Có đếm tổng số nghiệm. 2.Thuật toán: 2.1. Đếm số xâu nhị phân độ dài n: a. Bất kỳ: Số xâu nhị phân độ dài n chính là 2n. b. Không có hai bit 0 kề nhau: - Nếu n=1: có 2 xâu. ...