Cấu trúc dữ liệu và giải thuật - Buổi3: Cấu trú cdữ liệu và thuật giải

Buổi 3: Cấu trúc dữ liệu và thuật giải Giáo viên: Tạ Thúc Nhu Khoa CNTT trường ĐH Lạc Hồng Một số vấn đề cơ sở của Tin học Mã hóa2 ĐỆ QUI RECURVE Mã hóa3 Khái niệm Đệ Qui Một đối tượng được gọi là đệ qui nếu nó hoặc 1 phần của nó được định nghiã thông qua khái niệm về chính nó. Ví dụ: Định nghiã phép toán giai thừa, ký hiệu: N! • (a) Nếu N = 0, thì N! = 1 • (b) nếu N > 0 thì N! = N*(N-1)! Ví dụ: Định nghiã UCLN của 2 số x và y, ký hiệu: UCLN(x, y) • (a)UCLN(x,y) = x nếu y = 0 • (b)UCLN(x,y) = UCLN(y, phần dư của x/y) nếu y0 Mã hóa4 Chương trình đệ qui • Một chương trình là đệ qui nếu trong chương trình có lời gọi đến chính nó. Ví dụ: Định nghĩa hàm tính N! theo đệ qui. int GiaiThua(int N) { if (N == 0) return 1; return N * GiaiThua(N - 1); } Mã hóa5 Một định nghiã đệ qui phải có 2 thành phần: • Thành phần dừng: Không chứa khái niệm đang định nghiã Ví dụ: N! = 1 • Thành phần đệ qui: có chứa khái niệm đang định nghiã Mã hóa6 Ví dụ: Tính UCLN(x,y) theo thuật toán Euclide • (a)UCLN(x,y) = x nếu y = 0 • (b)UCLN(x,y) = UCLN(y, phần dư của x/y) nếu y0 int UCLN(int x, int y) { if (y == 0) return x; return UCLN(y, x % y); } Mã hóa7 THUẬT GIẢI QUAY LUI BACK TRACKING Mã hóa8 Tổng quan thuật giải Quay lui (Back Tracking) • Dùng giải bài toán liệt kê các cấu hình • Mỗi cấu hình được xác định bằng cách xây dựng tuần tự từng thành phần trong cấu hình. • Mỗi thành phần được xác định bằng cách chọn lựa dữ liệu trong tập khả năng được đề xuất. XnX3X2X1 KmK2K1Tập khả năng Cấu hình một lời giải Mã hóa9 Mô hình thuật giải quay lui: Xác định phần tử Xi bằng đệ quy void Try( int i ) { If (Xi là phần tử cuối cùng trong cấu hình) ; else for ( mọi Kj thuộc tập khả năng đề cử cho Xi) [ if ( Chấp nhận Kj ) ] { Thử chọn Kj cho Xi; Try( i+1); //Gọi đệ quy để xác định phần tử Xi+1 Bỏ ghi nhận Kj đã chọn cho Xi để chọn khả năng khác; } } Mã hóa10 Hai điểm mấu chốt quyết định độ phức tạp của bài toán là: 1. Xác định tập khả năng đề cử: Phụ thuộc vào việc phân tích nhu cầu dữ liệu của từng thành phần trong cấu hình 2. Kiểm tra khả năng đề cử phải phù hợp với thành phần cần xác định. Mã hóa11 Bài toán: Liệt kê các dãy nhị phân có độ dài n Phân tích: • Biểu diến cấu hình dãy nhị phân dưới dạng: X[1..n] • Tập khả năng đề cử cho mỗi phần tử Xi là {0, 1} • Thuật giải xác định phần tử Xi của dãy nhị phân như sau: void Try(int i) { if ( i > n ) ; else for (int j =0; j<= 1; j++) { X[ i ] = j; Try( i + 1 ); } } Mã hóa12 Mã đi tuần: chỉ ra hành trình của quân Mã xuất phát từ một ô trên bàn cờ đi qua tất cả các ô còn lại của bàn cờ, mỗi ô đúng 1 lần. Phân tích: • Cấu hình lời giải là BC[1..n][1..n] chứa số thứ tự hành trình của quân Mã. • Tập khả năng chứa các giá trị dùng tính tọa độ các ô kế tiếp dx[1..8] = {-2,-1, 1, 2, 2, 1, -1, -2} dy[1..8] = { 1, 2, 2, 1, -1, -2, -2, -1} • Điều kiện chọn khả năng cho bước đi thứ i là Ô được chọn phải : – Thuộc bàn cờ – Và chưa đi qua 1 2 (x, y) (u, v) Mã hóa13 Thuật giải xác định bước đi thứ i của quân Mã void Try(int i) { int j,u,v; if (i > n*n) ; else for ( j =1; j <= 8 ; j++) { u =x+dx[j]; v = y+dy[j]; if (u >= 1 && u = 1 && v<=n && BC[u,v] = 0) { x = u; y = v; BC[u,v] = i; Try(i+1); x = u-dx[j]; y = v-dy[j]; BC[u,v] = 0; } } } Mã hóa14 Bài toán: Liệt kê các hoán vị của dãy số {1, 2, .., n} • Biểu diễn cấu hình một hoán vị: X[1..n] • Tập khả năng đề cử: { 1, 2, .., n } • Nhưng do Xi Xj với i j. Nên phải kiểm tra giá trị đề cử cho Xi phải khác với các giá trị đã chọn cho các thành phần trước đó. Hướng giải quyết chung là tổ chức các biến trạng thái lưu trữ thông tin phục vụ cho việc kiểm tra: Dùng mảng F[1..n] để ghi nhớ tình trạng sử dụng của từng khả năng trong tập S={1, 2, .., n}, với qui ước: F[ j ] = 0 nếu j chưa sử dụng F[ j ] = 1 nếu j đã sử dụng Mã hóa15 Thuật giải xác định phần tử Xi của một hoán vị void Try(int i) { if ( i > n ) ; else for (int j = 1; j<= n; j++) if (F[j] = 0) { X[i] = j; F[j] = 1; Try( i + 1 ); F[j] = 0; } } Mã hóa16 Ví dụ: Liệt kê các tập con k phần tử của tập S = {1, 2, .., n}. Trong đó (k <= n) • Biểu diễn cấu hình một tập con K phần tử: X[1..K] • Tập khả năng đề cử: { 1, 2, .., n } • Nhưng do Xi Xj với i j. Nên các giá trị đề cử cho Xi phải khác với các giá trị đề cử cho các thành phần trước đó Hướng giải quyết: Dùng mảng F[1..N] để ghi nhớ tình trạng sử dụng của từng khả năng trong tập S={1, 2, .., N}, với qui ước: F[ j ] = 0 nếu j chưa sử dụng F[ j ] = 1 nếu j đã sử dụng Mã hóa17 Thuật giải xác định phần tử Xi của một tập con void Try(int i) { if ( i > K ) ; else for (int j = 1; j<= N; j++) if (F[j] = 0) { X[i] = j; F[j] = 1; Try( i + 1 ); F[j] = 0; } } Mã hóa18 Một cách giải khác của bài toán tập con Đưa ra điều kiện cho mỗi tập con là : 1 <= X[1] < X[2] < .. < X[ i ] < .. < X[K-1] < X[K] <= N • Nhận xét: X[K] <= N X[K-1] <= X[K] - 1 <= N - 1 X[ i ] = X[K-(K-i)] <= N - (K - i) • Do đó, ta có thể giới hạn giá trị đề cử cho thành phần X[i] trong khoảng từ : X[i-1]+1 đến (N – K + i) • Để điều này cũng đúng cho cả trường hợp i = 1, ta thêm vào X[0] = 0. Mã hóa19 Thuật giải xác định phần tử Xi của một tập con void Try(int i) { if ( i > K ) ; else for (int j = X[i-1]+1; j<= N-K+i; j++) { X[i] = j; Try( i + 1 ); } } Mã hóa20 KỸ THUẬT NHÁNH CẬN Mã hóa21 Công dụng • Dùng giải quyết bài toán tìm cấu hình tốt nhất trong các cấu hình liệt kê bằng thuật toán quay lui. • Giảm thời gian thực hiện của thuật toán quay lui. Kỹ thuật nhánh cận thêm vào cho thuật toán quay lui khả năng đánh giá cấu hình ở từng bước. Nếu tại bước thứ i đánh giá được cấu hình không tối ưu thì quay lui ngay không cần phải gọi đệ quy tìm tiếp các thành phần khác của cấu hình. Mã hóa22 Mô hình đánh giá nhánh cận trong thuật toán quay lui: // Khởi tạo cấu hình BESTCONFIG xấu nhất void Init() { } //Mô hình thuật toán quay lui xác định X[i] có đánh giá nhánh cận void Try( int i ) { If (Xi là phần tử cuối cùng trong cấu hình) ; else for ( mọi Kj thuộc tập khả năng đề cử cho Xi) [ if ( Chấp nhận Kj ) ] { Thử chọn Kj cho Xi; if (còn hy vọng tìm ra cấu hình tốt hơn BESTCONFIG) Try( i+1); Bỏ ghi nhận Kj đã chọn cho Xi để chọn khả năng khác; } } Mã hóa23 Bài toán người du lịch Có n thành phố (được đánh số từ 1 đến n). Một người đi du lịch xuất phát từ một thành phố muốn đi thăm các thành phố khác, mỗi thành phố đúng một lần rồi quay về nơi xuất phát. Giả thiết biết được chi phí đi từ thành phố i đến thành phố j là C[i,j], 1£ i, j < n. Hãy tìm 1 hành trình cho người du lịch để tổng chi phí theo hành trình này là ít nhất. 4 1 3 21 3 2 1 2 4 0421 4012 2103 1230 Ma trận chi phí C Mã hóa24 Phân tích: • Cấu hình lời giải : X[1..n] – X[1] = 1 được xem là thành phố xuất phát. – Một hành trình là một hoán vị của các thành phố 2, .. ,n. • Tập khả năng đề cử : {2, 3,.., n} • Cấu hình BESTCONFIG: – Smin là tổng chi phí thấp nhất đã chọn trong các hành trình tìm được. Khởi tạo ban đầu cho Smin = Cmax * (n + 1), trong đó Cmax là chi phí lớn nhất trong các chi phí C[i, j] đã cho – BestWay[1..n] : chứa hành trình có chi phí thấp nhất. Mã hóa25 • Các vấn đề cần thực hiện khi xác định thành phần X[i]: 1. Kiểm tra khả năng đề cử cho thành phần X[i] hợp lệ: khả năng đó chưa được chọn cho các thành phần trước X[i]. 2. Ghi nhận tổng chi phí cho hành trình từ X[1] đến X[i]. 3. Dự đoán cấu hình lời giải tốt hơn hay xấu hơn BESTCONFIG Mã hóa26 2- Ghi nhận tổng chi phí cho hành trình từ X[1] đến X[i] • Mảng T[1..n] ghi nhận tổng chi phí tại mỗi bước • T[i] chứa tổng chi phí cho hành trình từ X[1] đến X[i] • Nếu thành phố j được đề cử cho thành phần X[i] thì: T[i] = T[i-1] + C[X[i-1], j] • Tổng chi phí của hành trình từ X[1] đến X[n] và trở về X[1] là: T[n] + C[X[n], 1] 4 1 3 21 3 2 1 2 4 Mã hóa27 3- Dự đoán cấu hình lời giải tốt hơn hay xấu hơn BESTCONFIG • Gọi Cmin là chi phí thấp nhất trong các chi phí C[i, j] đã cho. • Sau khi xác định X[i], nếu đi tiếp (n – i +1) thành phố nữa thì chi phí tối thiểu phải là T[i] + Cmin*(n-i+1). • Nếu T[i] + C[i,j]*(n-i+1) < Smin thì có khả năng tìm được hành trình tốt hơn BESTCONFIG, ngược lại thì hành trình tìm được sẽ không tốt hơn BESTCONFIG. Mã hóa28 Thuật giải xác định thành phần X[i] void Try(int i) { if ( i > n ) if ( T[n] + C[x[n] , 1] < Smin ) { Smin = T[n] + C[x[n] , 1]; Ghi nhận X là hành trình tốt nhất: Bestway = X; } else for (int j = 2; j <= n; j++) if (F[ j ] = 0) { X[ i ] = j; F[ j ] = 1; T[ i ] = T[i -1] + C[ x[i -1], j]; if ( T[ i ] + (n-i+1)*Cmin < Smin) Try( i + 1 ); F[ j ] = 0; } } Mã hóa29 Bài toán chuỗi 123 Tìm một chuỗi có độ dài n (n <= 100) chỉ gồm các số 1, 2, 3 thỏa mãn điều kiện: 1. Hai chuỗi con bất kỳ liền nhau đều khác nhau 2. Có ít số 3 nhất Ví dụ: n = 9. Chuỗi nào sau đây hợp lệ? 131213212 123212313 123212321 Mã hóa30 Phân tích • Cấu hình lời giải: X[1..n] • Tập khả năng đề cử: { 1, 2, 3 } • Cấu hình BESTCONFIG: 1. Min3: chứa số lượng số 3 ít nhất. Khởi tạo Min3 = n 2. BestStr[1..n]: chứa chuỗi có số lượng số 3 ít nhất. Mã hóa31 • Các vấn đề cần thực hiện khi xác định thành phần X[i]: 1. Kiểm tra khả năng đề cử cho thành phần X[ i ] hợp lệ: nghĩa là chuỗi X[1..i] không có 2 chuỗi con liền kề giống nhau. 2. Ghi nhận số lượng số 3 có trong chuỗi X[1..i] 3. Dự đoán cấu hình lời giải tốt hơn hay xấu hơn BESTCONFIG Mã hóa32 1- Kiểm tra chuỗi X[1..i] không có 2 chuỗi con liền kề giống nhau. int ChuoiHopLe(int i) { for (L = 1; L <= i / 2; L++) if ( X[(i–L+1) .. i] = X[(i–2L+1) .. (i- L)] ) return 0; return 1; } Ví dụ: 123212321 123212321 123212321 123212321 123212321 Mã hóa33 2- Ghi nhận số lượng số 3 trong chuỗi X[1..i] • Mảng T[1..n] ghi nhận số lượng số 3 tại mỗi bước • T[i] chứa số lượng số 3 trong chuỗi X[1..i ] • Nếu giá trị đề cử là 3 thì T[i] = T[i-1] +1, ngược lại thì T[i] = T[i-1] Mã hóa34 3- Dự đoán cấu hình lời giải tốt hơn hay xấu hơn BESTCONFIG Do 2 chuỗi con kề phải khác nhau nên: • Trong 4 số liên tiếp phải có một số 3. • Do đó, một dãy con có độ dài là k phải có ít nhất (k / 4) số 3. • Sau khi xác định thành phần X[i] và ghi nhận số lượng số 3 trong T[i], ta còn (n – i) thành phần cần xác định. • Do đó, cấu hình tìm được phải có ít nhất (T[i] + (n-i)/4) số lượng số 3. • Nếu (T[i] + (n-i)/4) < Min3 thì có khả năng tìm được cấu hình tốt hơn BESTCONFIG, ngược lại thì cấu hình tìm được sẽ không tốt hơn BESTCONFIG. 131213212 131213212 131213212 131213212 131213212 131213212 Mã hóa35 Thuật giải xác định thành phần X[i] void Try(int i) { if ( i > n ) { Min3 = T[n]; Ghi nhận X là chuỗi tốt nhất: BestStr = X; } else for (int j = 1; j <= 3; j++) { X[i] = j; if (ChuoiHopLe( i )) { if (j == 3) T[i] = T[i -1] + 1; else T[i] = T[i -1]; if ( T[ i ] + (n - i)/4 < Min3) Try( i + 1 ); } } } Mã hóa36 Giải thuật chia để trị (Devide and conquer) Mã hóa37 Tổng quan giải thuật chia để trị Kỹ thuật chia để trị bao gồm hai quá trình: • Phân chia bài toán đã cho thành các bài toán con cùng loại, lần lượt giải từng bài toán con đó một cách độc lập. • Tổng hợp kết quả từ bài toán con để có lời giải của bài toán ban đầu. Thông thường, chia bộ dữ liệu đầu vào thành các phần riêng rẽ, sau đó gọi 2 thủ tục đệ qui với bộ dữ liệu đầu vào là các phần vừa chia. Mã hóa38 Một số bài toán tiêu biểu • Tìm nhị phân • QuickSort • Nhân số nguyên lớn Mã hóa39 Tìm nhị phân trên mảng sắp thứ tự Bài toán : Cho mảng A[1..n] được sắp xếp theo thứ tự không giảm và x. Tìm i sao cho A[i] = x. Phân tích: Do mảng A sắp thứ tự tăng nên x: • Hoặc là bằng phần tử nằm ở vị trí giữa mảng A • Hoặc là nằm ở nửa bên trái (x<phần tử ở giữa mảng A ) • Hoặc là nằm ở nửa bên phải (x>phần tử ở giữa mảng A ) Mã hóa40 Thuật giải: Tìm nhị phân trên mảng sắp thứ tự int Bsearch(x, A[ ], int L, int R) { if (L > R) then return -1; else { M = (L + R)/2; If (x = A[M]) return M; If (x < A[M]) return Bsearch(x, A, L, M-1) return Bsearch (x, A, M+1, R) } } Mã hóa41 Bài toán tương tự: Tìm đường đi cho xe có tải trọng lớn nhất Có N thành phố, cho biết mỗi con đường nối từ thành phố i đến thành phố j (với i j) có thể cho xe với trọng tải không quá C[i, j] đi qua. Cho thành phố xuất phát x và thành phố đích y. Hãy tìm một đường đi từ thành phố x tới thành phố y mà trọng tải lớn nhất có thể được. Ý tưởng: • Khởi tạo: Cmax = MAX{Cij} với mọi i khác j; Cmin =Min{Cij} • Xét đoạn [ Cmin , Cmax] 1. Đặt Cm = (Cmax+Cmin) div 2. 2. Ta kiểm tra xem có tồn tại đường đi từ x tới y cho xe có trọng tải Cm hay không? a) Nếu tồn tại đường đi, ta ghi nhận kết quả và xét tiếp đoạn [Cm+1,Cmax]. b) Nếu không tồn tại đường đi, ta chuyển sang xét đoạn [Cmin ,Cm -1]. 3. Lặp lại cho tới khi đoạn có giá trị đầu lớn hơn giá trị cuối. Mã hóa42 Thuật giải chọn lộ trình có tải trong lớn nhất void Chon(int Cmin, int Cmax) { if (Cmin <= Cmax) { Cm = (Cmin + Cmax)/2; d = 0; //Độ dài lộ trình LoTrinh[0] = x; // Mảng ghi nhận lộ trình đi từ x đến y if (TonTai(LoTrinh, d, x, Cm ) ) { GhiNhan(LoTrinh, d, Cm); Chon(Cm+1, Cmax); } else Chon(Cmin, Cm-1) ; } } Mã hóa43 Thuật giải kiểm tra tồn tại lộ trình cho xe có tải trọng Cm đi qua int TonTai(LoTrinh[ ], int &d, int i, int Cm) { int j; if ( i = y ) return 1; for (j = 0; j < n; j++) if (F[ j ] = 0 && C[ i ][ j ] >= Cm) { F[ j ] = 1; d++; LoTrinh[d] = j; if (TonTai(LoTrinh, d, j, Cm)) return 1; d--; F[ j ] = 0; } return 0; } Mã hóa44 Bài toán tương tự Cho N và S là 2 số nguyên dương. Trong đó, N<= 100 và S <= 10100 Biết rằng căn bậc N của một số S là một số nguyên < 106. Hãy tìm căn bậc N của S Ví dụ: S = 30517578125 N = 15 KQ = 5 Mã hóa45 Thuật toán sắp xếp mảng Quick Sort Ý tưởng thuật toán sắp xếp tăng cho dãy X[L .. R] Bước 1: Phân chia dãy X[L .. R] thành 2 dãy con bằng cách: – Chọn giá trị P của 1 phần tử trên dãy X[L .. R] làm mốc phân hoạch. – Đổi chổ các phần tử X[i]>= P với các phần tử X[j]<= P, với i < j – Khi i > j, dãy ban đầu được phân thành 2 phần: 1. X[ L .. j ] chứa giá trị <= P 3. X[ j .. i ] chứa giá trị = P 2. X[ i .. R ] chứa giá trị >= P Bước 2: – Nếu X[L .. j] có hơn 1 phần tử thì sắp xếp tăng dãy X[L .. j] – Nếu X[i .. R] có hơn 1 phần tử thì sắp xếp tăng dãy X[i .. R] Mã hóa46 Minh họa thuật toán 95675312 95675312 i = j ji ji RijL 95635712 92635715 97655321 RiL = ji = RL = j 9765321 9567312 i = RLj 97 97 Mã hóa47 Thuật giải Quick Sort void QuickSort(X[L .. R]) { int i = L; int j = R; P = X[i]; while (i <= j) { while (X[i] < P) i++; while (X[j] > P) j--; if (i <= j) { if (X[i] X[j]) Hoanvi(X[i], X[j]); i++; j--; } } if (L < j) QuickSort(X[L ..j ]); if (i < R) QuickSort(X[i .. R]); } Mã hóa48 Nhân hai số nguyên X.Y có n chữ số Phân tích: • Chia X thành 2 số nguyên có n/2 chữ số: X=A.10n/2+B • Chia Y thành 2 số nguyên có n/2 chữ số: Y=C.10n/2+D X.Y = A.C.10n+(A.D+B.C)10n/2+B.D Mặt khác: R = (A + B)(C + D) = A.C + A.D + B.C + B.D A.D+B.C = R – A.C – B.D Khi đó: X.Y = A.C.10n+(R-A.C-B.D)10n/2+B.D • Phép nhân với 10n thực chất là thêm n chữ số 0 • 3 phép nhân số nguyên lớn n/2 chữ số :A.C, B.D, (A+B)(C+D) tiếp tục được phân chia cho đến khi 2 toán hạng chỉ có một chữ số. Mã hóa49 Ví dụ: nhân X=981 với Y=1234. • Trước tiên chúng ta điền thêm vào toán hạng ngắn hơn các số 0 vô nghĩa để làm cho hai toán hạng có cùng độ dài: 981 trở thành 0981. • Sau đó tách từng toán hạng thành hai nửa: X = 0981 cho ra A = 09 và B = 81 è 981 = A.102 + B Y = 1234 thành C = 12 và D = 34 è 1234 = C.102 + D • Do đó, tích cần tìm có thể tính được là: P = A.C = 09 * 12 = 108 Q = B.D = 81 * 34 = 2754 R = (A + B)(C + D) = 90 * 46 = 4140 và cuối cùng 981 x 1234 = P.104 + (R – P – Q).102 + Q = 1080000 + 127800 + 2754 = 1210554. Mã hóa50 Thuật giải: Nhân 2 số nguyên có n chữ số SoLon Nhan(SoLon X, SoLon Y, int n) { If ( n = 1) return X*Y; A=left(X,n/2); B=right(X,n/2); C=left(Y,n/2); D=right(Y,n/2); P = Nhan(A,C,n/2); Q = Nhan(B,D,n/2); R = Nhan(A+B,D+C,n/2); return (P*10n +(R-P-Q)*10n/2 + Q); } Mã hóa51 Một số bài toán buổi 3 1. Mỗi hột xí ngầu có 6 mặt, mỗi mặt chứa từ 1 đến 6 dấu chấm. Liệt kê các kết quả phân biệt có thể có khi đổ cùng lúc 3 hột xí ngầu, không kể thứ tự xuất hiện trên các hột xí ngầu, ví dụ {1, 2, 3} và {2, 3, 1} là như nhau. 2. Cho 1 mảng gồm n các số nguyên a[1], a[2],.., a[n] và một số nguyên S. Hãy tìm tất cả các dãy con : 1 <= x1 < x2 < .. < xk <= n sao cho: a[x1] + a[x2] + ..+ a[xk] = S 3. Tính số cách và in tất cả các cách phân tích số tự nhiên N >1 thành tổng các số tự nhiên nhỏ hơn nó (mọi phân tích chỉ kể đúng một lần: 4+3+1 và 1+4+3 chỉ là một) 4. Hãy tìm tập hợp các dấu '+’, ‘-‘ và không dấu giữa dãy số 123456789 sao cho được một biểu thức có giá trị bằng = N cho trước. Ví dụ: N = 280 ta có các tổ hợp sau: 1+2+345-67+8-9; 1+234-5+67-8-9; 123-4+5+67+89 5. Cho một dãy N số nguyên. Hãy loại bỏ khỏi dãy một số phần tử để được một dãy con, có ít nhất 2 phần tử, không giảm và dài nhất. In ra dãy con đó. Ví dụ: N = 10 2 6 -7 5 8 1 -3 5 15 9 Kết quả tìm được dãy con không giảm dài nhất có 4 phần tử: -7 -3 5 9 Mã hóa52 6. Trên bàn cờ ô vuông 4x4 xếp 8 quân cờ gồm 4 quân màu đen và 4 quân màu trắng sao cho trên mỗi hàng và mỗi cột có đúng một quân màu đen và 1 quân màu trắng. Thể hiện trên màn hình các cách sắp xếp này 7. Một người cha mang theo số tiền là M vào một cửa hàng để mua K món quà để tặng cho các con. Trong cửa hàng có N mặt hàng, mặt hàng thứ i có giá tiền là Ai. Người cha cần chọn K (K < N) mặt hàng khác nhau để làm quà sao cho tổng số tiền của K mặt hàng này không lớn hơn số tiền mang theo và độ chênh lệch giá tiền của K mặt hàng là thấp nhất. 8. Một dây chuyền sản xuất có N (N<=100) vị trí. Có N công nhân, cho biết năng suất của công nhân thứ i mà làm ở vị trí thứ j là Cij (Cij : Integer). Hãy sắp xếp N công nhân vào N vị trí sao cho đạt năng suất cao nhất. 9. Cho ma trận vuông cấp 8 chứa các số nguyên. Tìm giá trị lớn nhất của tổng 8 số hạng trên ma trận số trên sao cho 2 số hạng bất kỳ trong 8 số hạng trên không nằm trên cùng một hàng, không cùng nằm trên một cột và không cùng nằm trên đường chéo . 10. Cho một bảng A có M hàng, N cột (3 £ M, N £ 50), Mỗi phần tử của bảng là một số nguyên nhận giá trị từ 0 đến 99. Cho một số K (2 £ K £ Min(M, N)). Tìm K phần tử trong bảng A để tổng của K phần tử này là lớn nhất, với điều kiện là trên mỗi hàng chọn nhiều nhất một phần tử, mỗi cột chọn nhiều nhất một phần tử. 11. Một cơ sở sản xuất cần phân công M nhân viên tham gia thực hiện N hợp đồng sản xuất sản phẩm (M >= N). Mỗi nhân viên chỉ tham gia thực hiện một hợp đồng. Người ta dự tính rằng, nếu phân công i nhân viên tham gia thực hiện hợp đồng j thì có thời gian hoàn thành hợp đồng là T[i,j]. Hãy tìm phương án phân công mỗi hợp đồng bao nhiêu nhân viên sao cho tổng số thời gian hoàn thành N hợp đồng là ít nhất.