Kế hoạch bài dạy Tin học 11 - Bài: Thuật toán quay lùi

Nội dung text: Kế hoạch bài dạy Tin học 11 - Bài: Thuật toán quay lùi

1. PHẦN I. PHUƠNG PHÁP QUAY LUI * Ý tưởng: Giả thiết một cấu hình cần tìm được mô tả bởi một bộ phận gồm n thành phần a1, a2,...an. Giả sử tìm được i-1 thành phần a1, a2, ai-1, ta tìm thành phần thứ i bằng cách duyệt tất cả các khả năng có thể của a i. Với mỗi khả năng j kiểm tra xem nó có chấp nhận được không. Xảy ra hai trường hợp: - Chấp nhận được thì xác định a i theo j và kiểm tra xem i = n chưa, nếu i = n thì ta ghi nhận một cấu hình, còn nếu i < n ta tiến hành xác định ai+1. - Nếu thử tất cả các khả năng mà không có khả năng nào chấp nhận được thì quay lại bước trước xác định lại ai-1. Nội dung của thuật toán này rất phù hợp với việc gọi đệ quy. Ta có thủ tục đệ quy sau đây: * Thuật Toán: void Try (int i) { int j; for (j=1; j<=n; j++) if (chấp nhận j) { xác nhận ai theo j if (i==n) ; else try(i+1); } } * Chú ý: Trong thuật toán quay lui ta thường thực hiện các bước sau: - Xác định các khả năng có thể đề cử cho j; - Kiểm tra xem với mỗi phương án đó có chấp nhận được không? - Có cần đánh dấu phương án đã chọn hay không? - Kiểm tra xem đã được một cấu hình chưa (i=n) để ghi nhân một cấu hình, nếu không tiếp tục xác định thành phần kế tiếp. - - Nếu không còn khả năng nào để đề cử cho thành phần thứ i+1 thì lùi lại. Có hay không bỏ đánh dấu phương án đã chọn khi lùi lại. * Ứng dụng thuật toán quay lui giải một số bài toán cơ bản: Bài 1: Hãy viết chương trình liệt kê tất cả các dãy nhị phân có độ dài n. Bài 2: Hãy viết chương trình liệt kê các hoán vị của {1,2,...,n} Bài 3: Hãy viết chương trình liệt kê các tổ hợp chập m của {1,2,...,n} Bài 4: Liệt kê tất cả các cách sắp xếp những con hậu trên bàn cờ NxN sao cho chúng không ăn được nhau. Bài 5: Hãy viết chương trình liệt kê tất cả các chu trình Haminton của đơn đồ thị vô hướng. (Chu trình bắt đầu từ đỉnh v nào đó qua tất cả các đỉnh còn lại, mỗi đỉnh đúng một lần rồi quay trở về đỉnh v được gọi là chu trình Hamilton). (*Bài 1: Hãy viết chương trình liệt kê tất cả các dãy nhị phân có độ dài n*) Giải: Biểu diễn dãy nhị phân dưới dạng b 1,b2,...,bn trong đó bi {0,1}. Thủ tục đệ quy Try(i) xác định bi, trong đó các giá trị đề cử là 0 và 1. Các giá trị này mặc nhiên được chấp nhận mà không phải thỏa mãn điều kiện gì (vì vậy bài toán không cần biến trạng thái). Thủ tục Init nhập giá trị n và khởi gán biến đếm Count. Thủ tục result đưa ra dãy tìm được. Sau đây là chương trình: #include using namespace std; int n,count; int b[10];
2. /* KHOI TAO */ void init() { cout<<"Nhap N="; cin>>n; count=0; } /* IN KET QUA */ void result() { count++; cout<<count<<": "; for (int i=1;i<=n;i++) cout<<b[i]<<" "; cout<<endl; } /* QUAY LUI – LIET KE DAY NHI PHAN */ void nhiphan(int i) { for (int j=0;j<=1;j++) { b[i]=j; if (i==n) result(); else nhiphan(i+1); } } /* CHUONG TRINH CHINH */ main() { init(); nhiphan(1); getchar(); } (*Bài 2: Hãy viết chương trình liệt kê các hoán vị của {1,2,...,n}*) Giải: Biểu diễn hoán vị dưới dạng p 1,p2,...,pn, trong đó pi nhận các giá trị từ 1 đến n và p i pj với i j. Các giá trị từ 1 đến n lần lượt được đề cử cho pi, trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì vậy cần được ghi nhớ đối với mỗi giá trị j xem nó đã được dùng hay chưa. Điều này được thực hiện nhờ một dãy biến logic b j, trong đó bj bằng True nếu j chưa được dùng. Các biến này cần được gán giá trị True trong thủ tục Init. Sau khi gán j cho pi cần ghi nhận False cho bj và phải gán lại giá trị True sau khi thực hiện xong Result. Sau đây là chương trình: #include using namespace std; int n,count; int p[20]; bool b[20]; /* KHOI TAO */ void init() {
3. int i; printf("Nhap n="); scanf("%d",&n); for (i=1;i<=n;i++) b[i]=true; count=0; } /* IN KET QUA */ void result() { int i; count=count+1; cout<<count<<": "; for (i=1;i<=n;i++) cout<<p[i]; cout<<"\n"; } /* QUAY LUI – LIET KE HOAN VI */ void hoanvi(int i) { int j; for (j=1;j<=n;j++) if (b[j]==1) { p[i]=j; b[j]=false; if (i==n) result(); else hoanvi(i+1); b[j]=1; } } /* CHUONG TRINH CHINH */ main() { init(); hoanvi(1); } (* Bài 3: Hãy viết chương trình liệt kê các tổ hợp chập m của {1,2,...,n}*) Giải: Biểu diễn tổ hợp dưới dạng c1c2...cm, trong đó: 1 c1 c2 ... cm n 5! Ví dụ: Tổ hợp chập 3 của 5 (C 3 10 ) gồm: 5 3!(5 3)! 123; 124; 125; 134; 135; 145; 234; 235; 245; 345 Từ đó suy ra các giá trị đề cử cho c i là từ ci-1+1 đến n. Để điều này đúng cho cả trường hợp i=1, cần thêm vào c0 với c0=0. Các giá trị đề cử này mặc nhiên được chấp nhận. Các thủ tục Init, result được xây dựng giống như bài toán trước. Sau đây là chương trình: #include #include using namespace std; int i,j,n,m;
4. int a[10]; /* KHOI TAO */ void result() { for (i=1;i<=m;i++) { cout << a[i]<<" "; } cout <<endl; } /* QUAY LUI – LIET KE TO HOP*/ void lietke(int i) { int j; for (j=a[i-1]+1;j<=n;j++) { a[i]=j; if (i==m) result(); else lietke(i+1); } } /* CHUONG TRINH CHINH */ main() { cout <<"nhap n, m:"; cin >> n >> m; cout <<n<<" "<<endl; lietke(1); return 0; } (* Bài 4: Liệt kê tất cả các cách sắp xếp những con hậu trên bàn cờ NxN sao cho chúng không ăn được nhau *) Giải: Ta xếp n con hậu trên n dòng, theo nguyên lý nhân ta có nn cách sắp xếp thoả mãn điều kiện đầu bải. Để làm điều đó ta dùng thủ tục đệ quy mô tả ở trên để giải. Ta đánh ghi số cột và dòng của bàn cờ từ 1 đến n, mỗi cách sắp xếp ứng với 1 bộ gồm x1,x2,.....,xn với xi = j (j=1,2,...,n) có nghĩa là con hậu thứ i đặt vào cột j. Giả sử ta chọn được i-1 con hậu bằng cách duyệt tất cả các khả năng của nó. Các giá trị đề cử cho x i là từ 1 đến n. Quan trọng nhất là ta tìm điều kiện chấp nhận j, một con hậu đứng ở một ô trong bàn cờ nó có nhiều nhất bốn hướng đi (đường dọc, đường ngang và hai đường chéo). Vậy điều kiện chấp nhận j nếu ô (i,j) không nằm trên đường đi của tất cả i-1 con hậu đã xếp. Bởi vì n con hậu xếp ở n hàng nên đường đi ngang của chúng là không chiếu nhau, do đó khi chọn con hậu thư i chỉ cần kiểm tra xem trên 2 đường chéo và đường dọc của chúng có chiếu vào những con hậu đã xếp không? Để kiểm tra điều này mỗi đường ta dùng một biến trạng thái. * Đường dọc kiểm soát bằng biến a[j], j={1,2,...,n}. * Một đường chéo kiểm soát bằng biến b[i+j],i+j={2,....,2n}. * Còn đường chéo kia kiểm soát bằng biến c[i-j],i-j={1-n,....,n-1}. VD: Ví dụ bàn cờ 4x4 thì hai đường chéo được kiểm soát là:
5. Đường chéo i+j, với i+j={2,....,2n}. j 1 2 3 4 i 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 Đường chéo i-j, với i-j={1-n,....,n-1}. j 1 2 3 4 i 1 0 -1 -2 -3 2 1 0 -1 -2 3 2 1 0 -1 4 3 2 1 0 Các biến trạng thái này khởi gán giá trị True trong thủ tục Init. Như vậy con hậu thứ i được chấp nhận xếp vào cột j nếu nó thoả mãn cả ba biến a[j], b[i+j], c[i-j] đều có giá trị True. Các biến này gán giá trị False khi xếp xong con hậu thứ i và trả lại giá trị True sau khi gọi Result. Ta có chương trình C++ sau: #include using namespace std; int n; int a[10],b[20],c[20],x[10]; /* KHOI TAO */ void init() { int i; cout<<"cho biet do rong ban co la:"; cin >> n; for (i=1;i<=n;i++) a[i]=1; for (i=2;i<=2*n;i++) b[i]=1; for (i=1;i<=2*n-1;i++) c[i]=1; } /* IN KET QUA */ void result() { for (int i=1;i<=n; i++) cout <<x[i]<<" "; cout <<endl; } /* QUAY LUI – TIM CACH XEP HAU */ void xephau(int i) { for (int j=1;j<=n;j++) {if ((a[j]) && (b[i+j]) && (c[i-j+n])) {
6. x[i]=j; a[j]=0; b[i+j]=0; c[i-j+n]=0; if (i==n) result(); else xephau(i+1); a[j]=1; b[i+j]=1; c[i-j+n]=1; } } } /* CHUONG TRINH CHINH */ main() { init(); xephau(1); } (*Bài 5: Hãy viết chương trình liệt kê tất cả các chu trình HaminTon của đơn đồ thị vô hướng *) Hainput.txt (ma trận kề) 2 5 7 1 2 2 3 3 4 4 5 1 5 3 4 1 5 2 3 5 Giải: #include #include 4 using namespace std; int chuaxet[20]; int a[20][20]; int x[20]; int n,m,u,v; ifstream f1; ofstream f2; /* IN KET QUA */ void result() { int i; f2<<"CO CHU TRINH HAMINTON: "; for (i=1;i<=n;i++) f2<<x[i]<<"<--"; f2<<x[1]<<endl; } /* QUAY LUI – TIM CHU TRINH HAMINTON*/
7. void try1(int i) { int j; for (j=1; j<=n; j++) if (chuaxet[j]&&(a[x[i-1]][j])) { x[i]=j; if (i<n) { chuaxet[j]=0; try1(i+1); chuaxet[j]=1; } else if (a[j][x[1]]) result(); } } /* CHUONG TRINH CHINH */ main() { int u,v; f1.open("Hainput.INP",ios::in); f2.open("Haoutput.OUT",ios::out); f1 >>n >> m; for (int i=1;i<=n;i++) { for (int j=1; j<=n; j++) a[i][j]=0; } for (int i=1; i<=n;i++) chuaxet[i]=1; cout <<n <<" "<< m<<endl; for (int i=1; i<=m; i++) { f1 >> u >> v; cout<<u<<" "<<v<<endl; a[u][v]=1; a[v][u]=1; } x[1]=1; chuaxet[1]=0; try1(2); f1.close(); f2.close(); } Kết quả ghi vào file: Haoutput.txt 1 2 3 5 4 1 1 2 5 3 4 1 1 4 3 5 2 1 1 4 5 3 2 1* Ứng dụng thuật toán quay lui (có đánh giá cận) giải bài toán: a. Đặt vấn đề: • Bài Toán thực tế: Bài Toán người giao hàng.
8. • Một người cần phải giao hàng tại N thành phố T1, T2, , Tn. • Cij: chi phí đi từ thành phố Ti đến thành phố Tj (i,j = 1, 2, , N). • Yêu cầu: xác định hành trình thỏa mãn đi qua tất cả các thành phố, mỗi thành phố qua đúng 1 lần, rồi quay trở lại thành phố xuất phát. Chi phí nhỏ nhất. b. Ý tưởng: • Giữ lại 1 phương án mẫu. • Tính chi phí của các phương án khác ngay trong quá trình xây dựng. Nếu tốt hơn: Cập nhật lại phương án mẫu và đi tiếp. Không tốt hơn: Quay lại bước trên xét phương án khác. c. Thuật giải: - Khái niệm bài Toán tối ưu: Hãy lựa chọn trong số các cấu hình tổ hợp chấp nhân được, cấu hình có giá trị tốt nhất. - Kỹ thuật nhánh cận thêm vào cho thuật toán quay lui khả năng đánh giá theo từng bước, nếu tại bước thứ i, giá trị thử gán cho x i không có hi vọng tìm thấy cấu hình tốt hơn cấu hình CẤU_HÌNH_TỐT_NHẤT thì thử giá trị khác ngay mà không cần phải gọi đệ quy tìm tiếp hay ghi nhận kết quả làm gì. Nghiệm của bài toán sẽ được làm tốt dần, bởi khi tìm ra một cấu hình mới (tốt hơn CẤU_HÌNH_TỐT_NHẤT), ta không in kết quả ngay mà sẽ cập nhật CẤU_HÌNH_TỐT_NHẤT bằng cấu hình mới vừa tìm được. • Bài toán tối ưu: Tìm min{f(x): x D} • Nghiệm bài toán có dạng x=( x1,x2, ,xn ). Bước 1: Xuất phát từ x1, xây dựng một phương án mẫu f* Bước i: Đã xây dựng được nghiệm thành phần (x1, x2, , xi-1) Đánh giá cận: tìm g xác định trên xi: g(x1, ,xi) < Min {f(a): a=(a1, ,an) thuộc x, xi=ai, i=1, ,n} Giả sử x* là lời giải tốt nhất tại thời điểm đó, f* là giá trị tốt nhất f*=f(x*) Nếu g>f* có thể bỏ đi không cần phát triển lời giải bộ phận (x1, x2, , xi) Ngược lại: tiến hành bước i+1 để xác định xi+1. d. Cài đặt: Try(i) For ( j=1->n ) If ( chấp nhận được j) {Xác định xi theo j; Ghi nhận trạng thái mới} If ( i=n ) Cập nhật lời giải tối ưu Else { Xác định cận g(x1, ,xi); If ( g(x1, , xi) < f* ) Try(i+1)}}} e. Đánh giá: Ưu điểm: Giảm được chi phí: Do loại bỏ được những bước đi không cần thiết (nhờ đánh giá cận). Nhược điểm:Việc xây dựng hàm g phụ thuộc vào từng bài toán tối ưu tổ hợp cụ thể. Hàm g phải đảm bảo điều kiện: • Việc tính giá trị của g phải đơn giản hơn việc giải bài toán tổ hợp tìm min= min{f (a): a=(a1 , ,an) thuộc x, xi =ai , i=1, ,n} • Giá trị của g(a1, a2 , , ak) phải sát với các giá trị của min. f. Ví dụ minh họa: Bài 1: Bài toán cái túi Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b. Có n đồ vât có thể mang theo (số lượng mỗi loại là không hạn chế). Đồ vật thứ j có trọng lượng a j và giá trị sử dụng cj (j=1,2,...,n). Hỏi nhà thám hiểm cần đem theo những loại đồ vật nào, số lượng mỗi loại là bao nhiêu để cho tổng giá trị sử dụng của các đồ vật đem theo là lớn nhất? Mô hình toán học của bài toán có dạng sau: Tìm
9. n n f max{ f (x) cj.xj : aj.xj b, xj Z , j 1,2,...,n}. j 1 j 1 Trong đó: xj là số lần lấy đồ vật j. cj là giá trị đồ vật j. aj là trọng lượng đồ vật j. Dưới đây là chương trình C++ giải bài toán cái túi theo thuật toán quay lui có đánh giá cận với các biến sử dụng trong chương trình là: (* Cost: Tổng giá trị các đồ vật chứa trong túi tại thời điểm đang xét *) (* Fopt: Giá trị kỷ lục đến tại thời điểm đang xét *) (* Xopt: Mảng chứa số lần lấy các đồ vật đã bỏ vào túi *) (* Weight: Trọng lượng của cái túi tại thời điểm đang xét *) (* c[i]: Giá trị đồ vật thứ i *) (* a[i]: Trọng lượng đồ vật thứ i *) (* n: Số lượng đồ vật đã cho *) (* w: Trọng lượng toàn bộ cái túi có thể chứa *) (* ind(i): Ghi nhận vị trí ban đầu của đồ vật i *) (* x[i]: Số lần lấy đồ vật thứ i *) Chương trình: #include #include #include #include using namespace std; int n; float a[20],c[20]; int x[20],xopt[20],ind[20]; float w,fopt,cost,weight; void khoitao() { int i,j,tg; float t; fopt=0; weight=0; for (i=1; i<=n;i++) ind[i]=i; for (i=1;i<=n-1;i++) for (j=i+1;j<=n;j++) if ((c[i]/a[i])<(c[j]/a[j])) { t=c[i];c[i]=c[j];c[j]=t; t=a[i];a[i]=a[j];a[j]=t; tg=ind[i];ind[i]=ind[j];ind[j]=tg; } }void docfile() { ifstream f; f.open("D:\\caitui.txt",ios::in); f>>n>>w; cout<<n<<" "<<w<<endl; for (int i=1;i<=n;i++) {
10. f>>a[i]; cout<<a[i]<<" "; } cout<<endl; for (int i=1;i<=n;i++) { f>>c[i]; cout<<c[i]<<" " ; } cout<<endl; f.close(); //cout<<trunc((w-weight)/a[1])<<endl; } void ghinhankyluc() { if (cost>fopt) { for (int i=1;i<=n;i++) xopt[i]=x[i]; fopt=cost; } } void caitui(int i) { int j,t; t=trunc((w-weight)/a[i]); for (j=t;j>=0;j--) { x[i]=j; weight=weight+a[i]*x[i]; cost=cost+c[i]*x[i]; if (i==n) ghinhankyluc(); else if ((cost+c[i+1]*(w-weight)/a[i+1])>fopt) caitui(i+1); weight=weight-a[i]*x[i]; cost=cost-c[i]*x[i]; } } void inketqua() { int i,j; cout<<"*********KET QUA TINH TOAN*************"<<endl; cout<<"Tong gia tri do vat:"<<fopt<<endl; cout<<"Phuong an lay do:"<<endl; for (i=1;i<=n;i++) cout<<"So luong do vat "<<ind[i]<<" la: "<<xopt[i]<<" lan"<<endl; } main() {
11. system("cls"); docfile(); khoitao(); caitui(1); inketqua(); } Giả sử ta có File dữ liệu là Caitui.txt trong ổ G có nội dung: 4 20 3 4 5 6 5 4 7 3 Bấm F11, Thì sau khi chay xong chương trình ta có kết quả: 4 20 3 4 5 6 5 4 7 3 *********KET QUA TINH TOAN************* Tong gia tri do vat : 32 Phuong an lay do: So luong do vat 1 la: 5 lan So luong do vat 3 la: 1 lan So luong do vat 2 la: 0 lan So luong do vat 4 la: 0 lan -------------------------------- Bài 2: Bài Toán người du lịch Một người du lịch muốn đi tham quan n thành phố T 1, T2,..., Tn. Xuất phát từ một thành phố nào đó người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đúng một lần, rồi quay lại thành phố xuất phát. Cij là chi phí đi từ thành phố Ti đến thành phố Tj (i,j=1,2,...,n), hãy tìm một hành trình (một cách đi thỏa mãn điều kiện đặt ra) với tổng chi phí nhỏ nhất. (Giữa hai thành phố bất kỳ luôn có đường đi) Cố định thành phố xuất phát là T1, bài toán người du lịch dẫn về bài toán: f (x2 , x3 ,..., xn ) c[1, x2 ] c[x2 , x3 ] ... c[xn 1, xn ] c[xn , x1] Min Với điều kiện (x2,x3,...,xn) là hoán vị của các số 2,3,...,n. Ký hiệu cmin min{c[i, j];i, j 1,2,...,n;i j} là chí phí nhỏ nhất đi lại giữa các thành phố. Giả sử ta đang có phương án bộ phận (u 1,u2,...,uk). Phương án này tương ứng với thành phần bộ phận đi qua k thành phố: T1 T (u2 ) ... T (uk 1) T (uk ) Vì vậy chi phí phải trả cho hành trình bộ phận này là:  c[1,u2 ] c[u2 ,u3 ] ... c[uk 1,uk ] Để phát triển hành trình bộ phận này thành hành trình đầy đủ, ta phải đi qua n-k thành phố còn lại rồi quay về thành phố T1, tức là còn đi qua n-k+1 đoạn đường nữa. Do chi phí phải trả cho việc đi qua mỗi một trong số n-k+1 đoạn đường còn lại đều không nhỏ hơn cmin nên cận dưới cho phương án bộ phận (u1,u2,...,uk) có thể được tính theo công thức: g u1,u2 ,...,uk  (n k 1).cmin . Dưới đây là chương trình C++ giải bài toán người du lịch theo thuật toán quay lui có đánh giá cận: #include #include using namespace std;
12. int a[100],xopt[100],c[100][100]; bool chuaden[100]; int n,fopt,cmin,can; void docfile() { int i,j; ifstream f; f.open("D:\\dulich.txt"); f>>n; for (i=1;i<=n;i++) { for (j=1;j >c[i][j]; } f.close(); cmin=INT_MAX; for (i=1;i<=n;i++) for (j=1;j c[i][j])) cmin=c[i][j]; } void capnhatkq() { int sum; sum=can+c[a[n]][a[1]]; if (sum<fopt) { for (int i=1; i<=n;i++) xopt[i]=a[i]; fopt=sum; } } void inketqua() { int i,j; cout<<"Hanh trinh toi uu co chi phi"<<fopt<<endl; for (i=1;i "; cout<<xopt[1]; } void dulich(int i) { int j; for (j=2;j<=n;j++) if (chuaden[j]) { a[i]=j; chuaden[j]=false; can=can+c[a[i-1]][a[i]]; if (i==n) capnhatkq(); else if(can+((n-i+1)*cmin)<fopt) dulich(i+1); chuaden[j]=true; can=can-c[a[i-1]][a[i]]; }
13. } void khoitao() { for (int i=1;i<=n;i++) chuaden[i]=true; fopt=INT_MAX; can=0; a[1]=1; } main() { docfile(); khoitao(); dulich(2); inketqua(); } Giả sử ta có File dữ liệu là Dulich.txt trong ổ G có nội dung: 5 0 3 14 18 15 3 0 4 22 20 17 9 0 16 4 6 2 7 0 12 9 15 11 5 0 Thì sau khi chay xong chương trình ta có kết quả: Hanh trinh toi uu co chi phi: 22 1 2 3 5 4 1 Bài 3: Xâu nhị phân (Thi chọn HSG tỉnh dự thi quốc gia năm 2014-2015) Xâu nhị phân là xâu chỉ chứa các số 0 và 1. Độ dài xâu là số lượng các số 0 và 1 trong xâu. Yêu cầu: Cho biết số n chỉ độ dài của xâu. Hãy đếm số xâu nhị phân có độ dài n và chỉ chứa tối đa 2 số 0 liên tiếp. Dữ liệu vào: Cho từ tệp văn bản XAUBIT.INP - Dòng đầu tiên ghi số lượng Test k (1 k 12); - k dòng tiếp theo mỗi dòng ghi số n (n là độ dài của xâu; 1 n 103). Dữ liệu ra: Ghi ra tệp văn bản XAUBIT.OUT số xâu nhị phân thỏa mã yêu cầu, mỗi Test trên một dòng. Ví dụ: XAUBIT.INP XAUBIT.OUT Giải thích 2 Với n=4 có các xâu sau: 3 7 0010 0011 0100 0101 0110 0111 4 13 1001 1010 1011 1100 1101 1110 1111 Giải: Biểu diễn dãy nhị phân dưới dạng b 1,b2,...,bn trong đó bi {0,1}. Thủ tục đệ quy Try(i) xác định bi, trong đó các giá trị đề cử là 0 và 1. Các giá trị này mặc nhiên được chấp nhận mà không phải thỏa mãn điều kiện gì (vì vậy bài toán không cần biến trạng thái), ngoại trừ trường hợp 2 phần tử trước nó là 2 bít 0 liên tiếp thì bít kế tiếp phải là bít 1. Thủ tục Khoitao khởi gán biến đếm sl=0,và x[-1]:=1; x[0]:=1; thủ tục Docfile đọc dữ liệu từ tệp ra các biến, thủ tục Ghifile ghi giá trị biến sl tương ứng với các giá trị n vào tệp. Sau đây là chương trình C++ giải bài toán trên: #include
14. #include using namespace std; int x[100],d[100]; int k,n; long int sl; void docfile() { ifstream f1; f1.open("D:\\Xaubit.int"); f1>>k; for (int i=1;i >d[i]; f1.close(); cout<<k<<endl; for (int i=1;i<=k;i++) cout<<d[i]<<endl; x[1]=0; } void xaubit(int i) { int t; if (i<3) t=0; else if((x[i-2]==0) && (x[i-1]==0)) t=1; else t=0; for (int j=t;j<=1;j++) { x[i]=j; if (i==n) sl++; else xaubit(i+1); } } void ghifile() { ofstream f2; f2.open("d:\\xaubit.out"); for (int i=1; i<=k;i++) { sl=0; n=d[i]; xaubit(1); f2<<sl<<endl; } f2.close(); } main() { docfile(); ghifile(); } Kết quả chạy chương trình: XAUBIT.INP XAUBIT.OUT 7 1 2 2 4
15. 3 7 4 13 8 149 10 504 20 223317 30 98950096 Bài 4: Bác sỹ Một Bác sỹ đi lấy mẫu xét nghiệm Covid muốn đi lấy mẫu các hộ gia đình trong khu phố X gồm có n hộ H1, H2,..., Hn. Xuất phát từ một hộ nào đó Bác sỹ muốn đi lấy mẫu tất cả các hộ còn lại, mỗi hộ đến đúng một lần và quay lại hộ xuất phát (để lấy xe và tư trang cá nhân). Cij là đoạn đường đi từ hộ Hi đến hộ Hj (i,j=1,2,...,n), hãy tìm một hành trình (một cách đi thỏa mãn điều kiện đặt ra) với tổng đoạn đường nhỏ nhất. (Giữa hai hộ bất kỳ luôn có đường đi). Dữ liệu: Vào từ file BACSY.INP Dòng 1 chứa số nguyên dương N ≤ 100 N dòng còn lại mỗi dòng chứa N số nguyên dương a1, a2, , an là khoảng cách đi lại giữa các hộ; Kết quả: Ghi ra file BACSY.OUT - Dòng 1: Một số nguyên là tổng đoạn đường ngắn nhất khi đi qua hết n hộ và trở về hộ xuất phát. - Dòng 2: Hành trình mà bác sỹ đã đi qua. Ví dụ: BACSY.INP BACSY.OUT 5 45 0 9 8 14 14 1-->5-->3-->4-->2-->1 9 0 22 10 15 8 22 0 8 4 (Hoặc 1-->2-->4-->3-->5-->1) 14 10 8 0 19 14 15 4 19 0 Chương trình C++: #include #include using namespace std; int n,khoang_cach,khoang_cach_min; int x[50],a[50][50],xmin[50]; bool chua_den[50]; void doc_file() { fstream f1; f1.open("BACSY.INP",ios::in); f1>>n; for (int i=1;i<=n;i++) for (int j=1;j >a[i][j]; } void khoi_tao() { for (int i=1;i<=n;i++) chua_den[i]=true; khoang_cach=0; khoang_cach_min=INT_MAX; x[1]=1; } void cap_nhat_kq() {
16. int sum=khoang_cach+a[x[n]][1]; if (sum<khoang_cach_min) { khoang_cach_min=sum; for (int i=1;i<=n;i++) xmin[i]=x[i]; } } /* THỦ TỤC ĐỆ QUY QUAY LUI TÌM PHƯƠNG ÁN ĐI TỐI ƯU */ void di_xet_nghiem(int i) { for (int j=2;j<=n;j++) if (chua_den[j]) { x[i]=j; chua_den[j]=false; khoang_cach=khoang_cach+a[x[i-1]][x[i]]; if (i==n) cap_nhat_kq(); else di_xet_nghiem(i+1); chua_den[j]=true; khoang_cach=khoang_cach-a[x[i-1]][x[i]]; } } void ghi_file() { fstream f2; f2.open("BACSY.OUP",ios::out); f2<<khoang_cach_min<<endl; for (int i=1;i "; f2<<x[1]; } main() { doc_file(); khoi_tao(); di_xet_nghiem(2); ghi_file(); } Bài 5: Việc làm bán thời gian An là sinh viên năm thứ 2 khoa Kế toán trường đại học Kinh tế, vì hoàn cảnh gia đình khó khăn nên An thường xuyên tìm công việc bán thời gian để có thêm thu nhập phục vụ cho việc sinh hoạt và học tập của mình. Vào một buổi sáng nhật An được các anh chị khóa trước giới thiệu cho n công việc làm thêm, các công việc này được đánh số từ 1 đến n. Mỗi công việc đều có thời điểm bắt đầu, thời gian hoàn thành và kèm theo tiền thù lao của mỗi công việc. Biết rằng công việc thứ i bắt đầu thời điểm ti, thời gian hoàn thành ci và tiền thù lao mi, tại một thời điểm An chỉ làm một việc (thời điểm hai việc phải không giao nhau). Vì làm bán thời gian nên An phải lựa chọn những công việc phù hợp với khả năng và làm sao nhận được tiền thù lao là lớn nhất. Yêu cầu: Em hãy lập trình giúp an lựa chọn các công việc để nhận được số tiền thù lao là lớn nhất. Dữ liệu vào: Vào từ file văn bản PARTTIMEJOB.INP - Dòng đầu tiên ghi số nguyên dương n (số lượng công việc làm thêm, 0<n 103) - N dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương lần lượt là ti, ci, mi (0< ti, ci, mi 106)
17. Kết quả: Ghi ra file PARTTIMEJOB.OUT - Dòng đầu tiên ghi ra 2 số nguyên dương lần lượt là số lượng công việc được chọn và tổng tiền thù lao An nhận được; - Dòng tiếp theo thứ tự công việc được chọn (các số trên cùng một dòng và cách nhau một dấu cách) Ví dụ: PARTTIMEJOB.INP PARTTIMEJOB.OUT 4 2 550 120 50 300 1 3 100 250 500 230 125 250 200 100 200 HƯỚNG DẪN GIẢI BẰNG PHƯƠNG PHÁP QUAY LUI: - Các khả năng có thể đề cử cho j: 1..n (Các công việc); - Điều kiện chấp nhận j: Nếu thời gian bắt đầu sau thời gian kết thúc của công việc trước và công việc đó chưa được chọn; - Đánh dấu đã chọn để tránh chọn lại; - Nếu i=n ghi nhân một cấu hình, nếu không tiếp tục xác định thành phần kế tiếp. - Bỏ đánh dấu đã chọn khi lùi lại. Chương trình C++, giải băng phương pháp quay lui: #include #include using namespace std; fstream f1,f2; int n,sl,sluong,sum,sum_max; int t[100],c[100],m[100],time_kt[100],x[100],x_max[100],lay[100]; bool chuachon[100]; /* DOC FILE */ void doc() { f1.open("PARTTIMEJOB.INP",ios::in); f1 >> n; for (int i=1;i<=n;i++) { f1>>t[i]>>c[i]>>m[i]; time_kt[i]=(t[i]+c[i]); } } /* KHOI TAO */ void khoitao() { for (int i=1;i<=n;i++) chuachon[i]=true; time_kt[0]=0; sum=0; sum_max=0; sluong=0; x[0]=0; } //CAP NHAT void capnhat() {
18. if (sum>sum_max) { sl=sluong; sum_max=sum; for (int i=1;i<=n;i++) x_max[i]=x[i]; } } /* QUAY LUI */ void quaylui(int i) { int k; if ((chuachon[i])&&(t[i] >=time_kt[sluong])) k=1; else k=0; for (int j=k;j>=0;j--) { x[i]=j; chuachon[i]=j; sum=sum+m[i]*j; sluong=sluong+1*j; if (i==n) capnhat(); else quaylui(i+1); chuachon[i]=j; sum=sum-m[i]*j; sluong=sluong-1*j; } } /* GHI VAO FILE PARTTIMEJOB.OUT */ void ghi() { f2.open("PARTTIMEJOB.OUT",ios::out); f2<<sl<<" "<<sum_max<<endl; for (int i=1;i<=n;i++) if (x_max[i]!=0) f2<<i<<" "; } /* CHUONG TRINH CHINH*/ main() { doc(); khoitao(); quaylui(1); ghi(); }
19. Phần II. Phuơng pháp quy hoạch động: * Ý tưởng của thuật Toán: Cơ sở của phương pháp dựa trên nguyên lý tối ưu của Bellman: Nếu một dãy các lựa chọn là tối ưu thì mọi dãy con của nó cũng là tối ưu. Vì vậy khi áp dụng nguyên lý, ta cần phân rã bài toán thành các bài toán con có nội dung tương tự nhưng kích thước nhỏ hơn. Sau đó phân tích kết quả các bái toán con này để tổng hợp chúng tìm ra kết quả cho bài toán có kích thuớc lớn hơn. * Thuật Toán: Bước 1. Lập hệ thức: Lập hệ thức biểu diễn tuơng quan quyết định bước đang xử lí với các bước đã xử lí trước đó. Khi đã có hệ thức tương quan chúng ta có thể xây dựng ngay thuật giải, tuy nhiên các hệ thức này thường là các biểu thức đệ quy, do đó dễ gây ra hiện tượng tràn miền nhớ khi ta tổ chức chương trình trực tiếp bằng đệ quy. Bước 2. Tổ chức dữ liệu và chương trình: Tổ chức dữ liệu tính toán dần theo từng bước. Nên tìm cách khử đệ quy. Trong các bài toán quy hoạch động thuộc chuơng trình phổ thông thường đòi hỏi một vài mảng hai chiều. Bước 3. Làm tốt: Làm tốt thuật toán bằng cách thu gọn hệ thức quy hoạch động và giảm kích thước miền nhớ.* Ứng dụng thuật toán giải các bài toán: Bài 1: Chia thuởng Cần chia hết m phần thưởng cho n học sinh sắp xếp theo thứ tự từ giỏi trở xuống sao cho mỗi bạn không nhận ít thưởng hơn bạn đứng sau mình. 1 ≤ m, n ≤ 70 Thí dụ: Với số phần thuởng m=7 và số học sinh n=4 sẽ có 11 cách chia 7 phần thuởng cho 4 học sinh theo yêu cầu của đầu bài. Đó là: Phuơng án     1 7 0 0 0 2 6 1 0 0 3 5 2 0 0 4 5 1 1 0 5 4 3 0 0 6 4 2 1 0 7 3 3 1 0 8 3 2 2 0 9 4 1 1 1 10 3 2 1 1 11 2 2 2 1 Bài giải: 1. Lập hệ thức Gọi Chia(i,j) là số cách chia i phần thưởng cho j học sinh, ta thấy: - Nếu không có học sinh nào (j=0) thì không có cách chia nào (Chia=0). - Nếu không có phần thưởng nào (i=0) thì chỉ có một cách chia (Chia=1, mỗi học sinh được không phần thưởng). Ta cũng quy ước Chia(0,0)=1. - Nếu số phần thưởng ít hơn số học sinh (i < j) thì trong mọi phương án chia, từ học sinh thứ i+1 trở đi sẽ không được nhận phần thưởng nào: Chia(i,j)=Chia(i,i) nếu i<j - Nếu số phần thưởng nhiều hơn hoặc bằng số học sinh (i j ). Ta tách các phương án chia thành hai nhóm không giao nhau dựa trên số phần thưởng mà học sinh đứng cuối bảng thành tích, học sinh thứ j, được nhận:
20. + Nhóm thứ nhất gồm phương án trong đó học sinh thứ j không được nhận thưởng, tức là i phần thưởng chỉ chia chi j-1 học sinh và do đó số cách chia là: Chia(i,j-1). + Nhóm thứ hai gồm các phương án trong đó học sinh thứ j cũng được nhận thưởng. Khi đó, do học sinh đứng cuối bảng thành tích được nhận thưởng thì mọi học sinh khác đều có thưởng. Số cách chia i phần thưởng cho j học sinh mà học sinh thứ j cũng có thưởng chính bằng số cách chia i-j phần thưởng cho j học sinh. Vậy số cách chia trong trường hợp này là Chia(i-j, j). Ví dụ: Lấy 7 phần thưởng chia cho 4 học sinh mà học sinh ở cuối bảng xếp hạng cũng được nhận thưởng, ta có 3 cách chia sau: Phuơng án     1 4 1 1 1 2 3 2 1 1 3 2 2 2 1 Lấy 7-4=3 phần thưởng chia cho 4 học sinh, ta cũng có 3 cách chia sau: Phuơng án     1 3 0 0 0 2 2 1 0 0 3 1 1 1 0 Vậy tổng số cách chia cho trường hợp i j sẽ là tổng số phần tử của hai nhóm, ta có: Chia(i,j)=Chia(i,j-1) + Chia(i-j,j).Tổng hợp lại ta có: Điều kiện (i: số phần thưởng Chia(i,j) j: là số học sinh) j=0 Chia(i,j)=0 i = 0 and j 0 Chia(i,j)=1 i < j Chia(i,j)=Chia(i,i) i j Chia(i,j)=Chia(i,j-1) + Chia(i – j,j) 2. Tổ chức dữ liệu và chương trình: Ta có phương án đầu tiên của giải thuật Chia (đệ quy) như sau: long int chia(int i,int j) { int kq; if (j==0) kq=0; else if (i==0) kq=1; else if (i<j) kq=chia(i,i); else kq=chia(i,j-1)+chia(i-j,j); return kq; } Phương án này chạy chậm vì phát sinh ra quá nhiều lần gọi hàm trùng lặp. Làm tốt lần 1: Cải tiến đầu tiên là tránh những lần gọi lặp như vậy. Muốn thế chúng ta tính sẵn các giá trị của hàm theo các giá trị của đầu vào khác nhau và điền vào một mảng hai chiều cc. Mảng cc được mô tả như sau: Var cc:array[0..70,0..70] of longint; Ta quy ước cc[i,j] chứa số cách chia i phần thưởng cho j học sinh. Theo phân tích của phương án 1, ta có: • cc[0,0]=1; c[i,0]=0, với i:=1..m. • cc[i,j]=cc[i,i], nếu i<j • cc[i,j]=cc[i,j-1]+cc[i-j,j], nếu i j.