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

Chia sẻ: Trần Việt Tân | Ngày: | Loại File: DOC | Số trang:23

Thêm vào BST

Báo xấu

331
lượt xem 97
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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. - Nếu n=2: có 3 xâu. - Từ n>2 trở đi thì số xâu nhị phân độ dài n chính bằng tổng của số xâu nhị phân độ dài n-1 và số xâu nhị phân độ dài n-2. c. Có ít nhất 2 bit 0 gần nhau: Số xâu cần tìm chính bằng số xâu tìm được ở câu a trừ đi số xâu được ở câu b. tìm 2.2. Thuật toán liệt kê các xâu nhị phân: Để giải quyết bài toán này,ta sẽ xây dựng các hàm và dùng thu ật toán quay lui để giải  Thuật toán cụ thể được mô tả như sau: • Khai báo biến toàn cục:mảng s[100],n,d=0; là kiểu nguyên • Cần tạo hàm print(tham số);Lke(tham số); SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc Trang 5  - void print(tham số): 1.Khai báo biến k kiểu nguyên; 2.Gán k=0 và lặp cho tới khi đủ cấu hình Cứ mỗi bước lặp thì in ra phần tử của mảng s Tăng biến đếm lên 1 đơn vị d++ - void Lke(tham số): 1.Khai báo biến j kiểu nguyên; 2.Gán j=0 và lặp cho tới khi j=1 -Cứ mỗi bước gán j vào cho mảng s -Nếu đủ cấu hình thì in mảng s -Khác thì quay lui lại hàm Lke(thamso+1) - Hàm main(): a) Khai báo i kiểu nguyên; b) Quét giá tr ị đ ộ dài xâu nh ị phân v ới n đã khai báo toàn cục, n>=1; c) Gọi hàm Lke(0); truy ền tham s ố i=0 cho l ần đ ầu tiên g ọi hàm; d) In ra số xâu nhị phân đếm được:printf(“%d”,d); 2.3. Liệt kê tổ hợp không lặp của xâu chữ cái: Ta dựa vào phương pháp sinh. Bao gồm các bước: Bước 1: Xây dựng cấu hình đầu tiên cho xâu theo thứ tự từ điển Xắp xếp lại xâu theo chiều giảm a[i]>=a[i+1] với i= 1, n − 1 . In ra cấu hình đầu tiên này và biến đếm số cách sắp xếp được khởi tạo giá trị bằng 1. Bước 2: Lặp cho tới khi đạt được cấu hình cuối có dạng a[i]a[i] .Vì dãy bên trái của phần tử thứ i là dãy tăng do đó j chính là vị trí của phần tử đầu tiên lớn hơn a[i] nếu j=1 i-1 .Sau khi hoán vị a[i] và a[j] cho nhau ta sắp xếp lại tất cả các phần tử bên trái i theo chiều giảm, in ra cấu hình mới của xâu và tăng biến đếm lên. SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc Trang 6  2.4. Giải phương trình: x1 + x2 + x3 + … + xn = k - Khai báo biến. - Khai báo thêm mảng a[i] để in ra các nghiệm của phương trình. - Nhập dữ liệu n và k. - Dùng bài toán chỉnh hợp lặp chập n của k+1 phần tử (0,1….,k): + Khai báo thêm biến “sum” + Nếu k=0 thì có nghiệm duy nhất x1 = x2 = … = xn = 0; + Ngược lại gán a[i]=0; Thay đổi a[i] để có a[i] kế tiếp theo bài toán chỉnh hợp lặp. Gán sum=a[i]; nếu (sum =k) in kết qủa a[i]; - Thuật toán chỉnh hợp lặp chập k của n phần tử (phương pháp liệt kê) Void Lke(int n,int k){ For(i=1;i
TH Toán Rời Rạc Trang 7  int DemXau1(int n){ return pow(2,n); } int DemXau2(int n){ if(n==1) return 2; if(n==2) return 3; else return DemXau2(n-1)+DemXau2(n-2); } int DemXau3(int n){ return DemXau1(n)-DemXau2(n); } - Câu 2: #include #include #include int n,s[50]; void Lke1(int n); void Lke2(int n); void Lke3(int n); void print(); void main(){ clrscr(); printf("Enter n="); scanf("%d",&n); printf("\n\nSo xau nhi phan bat ky do dai %d:\n ",n); Lke1(n); printf("\n\nSo xau nhi phan ko co 2 bit 0 ke nhau:\n"); Lke2(n); printf("\n\nSo xau nhi phan co it nhat 2 bit 0 ke nhau:\n"); Lke3(n); getch(); } //----------------------------------------------------- void Lke1(int n){ int dem=1; for(int i=0;i
TH Toán Rời Rạc Trang 8  s[i]=0; for(dem=2;dem
TH Toán Rời Rạc Trang 9  int n,kt=1; do{ kt=1; printf("\nEnter the string: "); gets(a); n=strlen(a) ; for(int i=0;i
TH Toán Rời Rạc Trang 10  - Câu 4: #include #include #include int s[50]; void Giaiptr(int n,int k); void print(int n); void main(){ clrscr(); int n,k; printf("Enter n="); scanf("%d",&n); printf("k="); scanf("%d",&k); Giaiptr(n,k); getch(); } void Giaiptr(int n,int k){ int i,j,sum=0,c,count=0; for(i=1;i
TH Toán Rời Rạc Trang 11  - Câu 2: - Câu 3: - Câu 4: SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc Trang 12  BÀI 2:BÀI TOÁN TỐI ƯU RỜI RẠC II. 1.Đề bài: 1. Viết chương trình nhập n là số chi tiết cần gia công và nhập thời gian gia công trên hai máy của từng chi tiết. Tính và in thời gian hoàn thành gia công nhanh nhất. 2. Viết chương trình nhập n là số thành phố và nhập ma trận khoảng cách Cnxn=(cij)nxn. Tìm hành trình ngắn nhất cho người du lịch. 2.Thuật toán: 2.1. Bài toán lập lịch: Mỗi một chi tiết trong số n chi tiết D1, D2,…, Dn cần phải được lần lượt gia công trên 2 máy A, B. Thời gian gia công chi tiết Di trên máy A là ai, trên máy B là bi (i=1..n). Lịch để gia công xong các chi tiết sớm nhất được trình bày theo thuật toán như sau: - Chia các chi tiết thành 2 nhóm: Nhóm N1 gồm các chi tiết Di thỏa mãn ai bi, tức là min(ai,bi) đạt được tại bi. Các chi tiết Di thỏa mãn ai = bi xếp vào nhóm nào cũng được. - Sắp xếp các chi tiết trong N1 theo chiều tăng của các ai và sắp xếp các chi tiết trong N2 theo chiều giảm của các bi. - Nối N2 vào N1. Dãy thu được (theo trái sang phải) sẽ là lịch gia công tối ưu. 2.2. Bài toán người du lịch: Khởi tạo cho tất cả những cạnh không nối được với nhau bao gồm cả cạnh c[i][i] đều được gán bằng ∞ và các cạnh không được nối với nhau. Tổng chi phí của một hành trình của người du lịch sẽ chứa đúng một phần tử của mỗi dòng và đúng một phần tử của một cột trong ma trận chi phí C. Do đó, nếu ta trừ mỗi phần tử của một dòng (hay cột) của ma trận C đi cùng một số α thì độ dài của tất cả các hành trình sẽ cùng giảm đi α SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc Trang 13  ,vì thế hành trình tối ưu cũng sẽ không thay đổi .Vì vậy nếu ta tiến hành trừ bớt các phần tử của hàng và cột đi một hằng số sao cho thu được ma trận gồm các phần tử không âm mà trong mỗi hàng và mỗi cột có ít nhất một số 0. Ta gọi tổng các hằng số trừ đi là “chi phí rút gọn” hay “cận”, quá trình trừ bớt được gọi là “quá trình rút gọn”, ma trận thu được gọi là “ma trận rút gọn”. Chi phí của ma trận C được tính bằng tổng chi phí rút gọn qua các bước biến đổi ma trận. Ví dụ ma trận gốc thì có cận = 0. Sau khi rút gọn ma trận C, ta được chi phí bằng α điều này có nghĩa là không thể tìm được 1 hành trình nào có chi phí tối ưu < α . Với mỗi cạnh (i,j) ta có 2 trường hợp : Trường hơp1: cạnh (i,j) là một cạnh của hành trình tối ưu hay còn được gọi là rẻ nhánh gần ( ta quy ước đường đi trên cạnh (i,j) là i-->j ) , như vậy tất cả “các đường đi từ i ra” và “các đường đi tới j” đều bị loại ra khỏi ma trận C bằng thủ tục hạ bậc ma trận .Vì đã có đường đi I --> j thì đường đi j --> i sẽ bị cấm .Cũng nhu vậy nếu việc nối cạnh (i,j) làm xuất hiện đường đi từ 2 đỉnh A đến B trong hành trình thì đường thẳng nối B đến A sẽ bị cấm. ví dụ :A--->i-->j-->B thì cạnh (B,A) sẽ bị cấm ,việc cấm cạnh (B,A) được gọi là cấm hành trình con . Phương án 2: cạnh (i,j) không thuộc hành trình tối ưu , vì vậy đường đi i-->j sẽ bị cấm ,đây là phương án rẻ nhánh xa . Chú thích: Việc cấm cạnh được thực hiện bằng cách gán cạnh cấm có chi phí bằng ∞. Trong chương trình ta ưu tiên chọn rẻ nhánh cận và nhánh xa chỉ thực hiện khi chi phí nhỏ nhất lớn hơn cận của ma trận, khi đó ta chọn cạnh (i,j) sao cho khi loại bỏ hàng i cột j ra khỏi ma trận rút gọn C thì ma trận hạ bậc mới được tạo thành có chi phí rút gọn lớn nhất .Ta có thể tìm được cận tiếp theo của ma trận hạ bậc bằng cách tìm phần tử nhỏ nhất trên hàng i khác phần tử c[i,j] và nhỏ nhất trên cột j khác phần tử c[i,j], khi đó tổng của 2 phần tử nhỏ nhất đó chính là cận mới của ma trận rút gọn C sau khi đã loại hàng i cột j ra khỏi ma trận . Quá trình trên được lặp cho tới khi ma trận trở thành ma trận vuông bậc 2. Theo quy ước ở trên thì bất cứ cạnh nào có c[i][j]= ∞ thì không tồn tại cạnh nối I --> j do vậy ở đây ta lần lượt nạp vào chu trình còn thiếu 2 cạnh còn lại được nối với nhau.Tại đây ta so sánh cận với chi phí min - Nếu lớn hơn thì bỏ qua. - Nếu nhỏ hơn thì cập nhật chi phí min mới, xoá bỏ hành trình cũ đã lưu và nạp hành trình mới. - Nếu bằng thì cập nhật trường hợp và lưu thêm hành trình mới. SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc Trang 14  3.Mã nguồn: - Câu 1: #include #include #define MAX 50 int x[2][MAX]; int n; void Print() { int i; printf("Thoi gian gia cong chi tiet: \n"); printf("A : "); for(i=0;i
TH Toán Rời Rạc Trang 15  ib++; } } //Sap xep moi nhom for(i=0;i
TH Toán Rời Rạc Trang 16  #include #include int c[20][20], a[20], xopt[20], chuaxet[20], n, fopt, cmin, can; void nhapdulieu() { int i, j; printf("Nhap so thanh pho: "); scanf("%d", &n); printf("nhap ma tran chi phi c[i][j]\n"); for (i = 1; i
TH Toán Rời Rạc Trang 17  //===============================// void init() { int i, j; cmin = 0; for (i = 1; i
TH Toán Rời Rạc Trang 18  BÀI 3: BÀI TOÁN TRÊN ĐỒ THỊ III. 1.Đề bài: Viết chương trình phát sinh ngẫu nhiên ma trận trọng số Anxn=(aij)nxn của đồ thị vô hướng liên thông G gồm n đỉnh (aij=aji ∀i,j=1..n). a) Kiểm tra đồ thị G có phải là đồ thị Euler hay không. b) Nhập hai đỉnh x,y và dùng thuật toán Dijkstra để tìm đường đi ngắn nhất từ x đến y. c) Dùng thuật toán Prim để tìm cây phủ nhỏ nhất của đồ thị G. 2.Thuật toán: - Tạo ma trận: sử dụng bộ ngẫu nhiên khởi tạo giá trị cho ma trận của đồ thị G. - Chuyển ma trận về dạng có a[i][i] và các cạnh không có đường đi bằng ∞ . - Kiểm tra đồ thị Euler: tất cả các đỉnh của đồ thị phải có bậc chẵn. - Thuật toán Dijkstra: + Đầu vào: đồ thị có hướng G=(V,E) với n đỉnh, x ∈ V là đỉnh xuất phát, y là đỉnh đích, a[u,v], u,v ∈ V là ma trận trọng số. + Đầu ra: khoảng cách từ x  y. + Truoc[v] ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ x v + Bước 1: Khởi tạo: d[v]=a[x,v]; Truoc[v]=x; d[x]=0; T=V\{x}, T là tập các đỉnh có nhãn tạm thời. + Bước 2: Lặp While T ≠ Φ : - Tìm đỉnh u thỏa mãn d[u] = min{d[z], z ∈ T}; SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc Trang 19  - T = T\{u} //Cố định nhãn của đỉnh u. - for v∈ T: //Gán nhãn lại cho các đỉnh trong T if(d[v] > d[u] +a[u,v]){ d[v] = d[u] +a[u,v]; Truoc[v] = u; } - Cây phủ Prim: Bước 1: Xuất phát từ đỉnh k bất kỳ (thông thường chọn đỉnh đầu tiên) chọn một cạnh có trọng số nhỏ nhất liền kề với đỉnh k (min{A[k] [j]}j=1..n) ta đánh dấu 2 đỉnh đi qua cạnh đó và số cạnh tìm được là 1. Chuyển sang bước 2. Bước 2: Tìm cạnh nhỏ nhất của đồ thị với điều kiện cạnh tìm được phải có 1 đỉnh chưa đánh dấu và 1 đỉnh đã đánh dấu (min{A[i] [j]}j=1..n, i=1..n sao cho i đánh đấu và j chưa đánh dấu) để tránh trường hợp tạo thành chu trình. Ta tăng số cạnh tìm được lên 1 và chuyển sang bước 3. Bước 3: Nếu số cạnh tìm được bằng n-1 kết thúc thuật toán, ngược lại quay về bước 2. Ta tổ chức mảng 1 chiều D để đánh dấu . Nếu D[i]=1 đỉnh i được đánh dấu và D[i]=0 nếu i chưa được đánh dấu. - Tìm min{A[1][j]}j=1..n. Sau đó gán D[1]=D[j]=1 (đánh dấu 2 đỉnh 1,j) và cho số cạnh tìm được bằng 1 (Dem=1). - Tìm min{A[i][j]}j=1..n, i=1..n với điều kiện D[i]=1 và D[j]=0. Sau đó gán D[j]=1 (đánh dấu đỉnh j vừa tìm được) và tăng số cạnh lên 1 (Dem++). - Nếu Dem = n-1 thì thuật toán kết thúc. 3.Mã nguồn: #include #include #define vc 32767 #include #include #include int i, j, n, x, y; int c[20][20], tr[20], s[20], chuaxet[20]; void khoitao(); void inra1(); void euler(); void xtoy(); void cayphu(); void taomang(); void ngaunhien(); SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc Trang 20  //====================// void main() { clrscr(); n = 0; taomang(); if (n != 0) { printf("\tMa tran sinh ra la:\n"); inra1(); khoitao(); euler(); printf("\tNhap vao dinh suat phat X="); scanf("%d", &x); printf("\tNhap vao dinh dich Y="); scanf("%d", &y); xtoy(); cayphu(); } getch(); } void taomang() { printf("\tnhap n="); scanf("%d", &n); randomize(); for (i = 1; i