vuongchau90 Tài Sản của : vuongchau90 Tiêu đề: DE THI 60% THUAT GIAI Tue May 17, 2011 10:08 pmღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ Đề 3 Câu 1 (4 điểm) Cho dãy số: 45 26 20 50 32 15 10 17 a) Nêu thuật toán sắp xếp nổi bọt (Bublesort) b) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho dãy a = (a¬1, a2, . . ., an ) gồm các số đôi một khác nhau. Thiết kế thuật toán liệt kê tất cả các tổ hợp chặp k trong tập gồm n phần tử cuả a. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1 + 1/3 + 1/5 + … 1/(2n-1) Đề 4 Câu 1 (4 điểm) Cho dãy số: 20 50 32 45 10 17 26 15 c) Trình bày thuật toán sắp xếp đổi chỗ trực tiếp (Interchangesort) d) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho bàn cờ n x n ô. Một con ngựa được phép đi theo luật cờ vua (theo đường chéo hình chữ nhật 2 x 3). Thiết kế thuật toán tìm tất cả các hành trình của ngựa, bắt đầu từ ô <x0, y0 > đi qua tất cả các ô của bàn cờ, mỗi ô đúng một lần. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1 + 1/3 + 1/8 + … 1/(n2-1) Đề 5 Câu 1 (4 điểm) Cho dãy số: 20 10 17 26 50 32 45 15 e) Trình bày thuật toán sắp xếp đổi chỗ trực tiếp (Interchangesort) f) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho 3 ký tự A, B, C và một số nguyên n. Lập thuật toán liệt kê tất cả các chuỗi tạo ra từ 3 ký tự trên, với chiều dài n, thoả điều kiện không có 2 chuỗi con liên tiếp nào giống nhau. Câu 3 (3 điểm) Viết thủ tục đệ quy thực hiện tìm kiếm nhị phân trên một dãy số trong hai trường hợp: a) (1,5 điểm) Dãy số tăng dần b) (1,5 điểm) Dãy số giảm dần Đề 6 Câu 1 (4 điểm) a) Cho dãy số: 20 10 17 26 50 32 45 15 Áp dụng thuật toán MergeSort để sắp xếp dãy số tăng dần, nêu rõ từng bước b) Hãy cho biết trong đoạn lệnh sau có bao nhiêu phép so sánh các dữ liệu trong mảng: for (i = 1; i < = n-1; i ++) { j = i + 1; do { if (A[i] < A[j]) swap (A[i], A[j]); j ++; } while (j <= n) } so lan so sanh : phep nhan cua 2 vong lap n Câu 2 (3 điểm) Cho 3 ký tự A, B, C và n là một số nguyên dương (n>3) Thiết kế thuật toán liệt kê tất cả các chuỗi tạo ra từ 3 ký tự trên, với chiều dài n sao cho số ký tự A là 3. Câu 3 (3 điểm) Thiết kế thuật toán tìm giá trị min trong một dãy số theo phương pháp chia để trị Đề 7 Câu 1 (4 điểm) Cho dãy số: 45 26 20 50 32 15 10 17 Áp dụng phương pháp nổi bọt cải tiến (ShakerSort) để sắp xếp dãy số trên tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho bàn cờ n x n ô. Một con ngựa được phép đi theo luật cờ tướng (theo đường chéo 1 x 2). Thiết kế thuật toán liệt kê tất cả các hành trình của ngựa, bắt đầu xuất phát từ ô <x0, y0 > đi qua tất cả các ô của bàn cờ, mỗi ô đi qua đúng một lần. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/13 + 1/33 + 1/53 + … + 1/(2n-1)3
ღ♂→√ô◦Tìnђ♥ №¹ღ Đến từ : ĐẾN TỪ .....?????
Tài Sản của : ღ♂→√ô◦Tìnђ♥ №¹ღ Tiêu đề: Re: DE THI 60% THUAT GIAI Thu May 26, 2011 6:47 pmღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
[N] Tài Sản của : [N] Tiêu đề: Re: DE THI 60% THUAT GIAI Fri May 27, 2011 9:04 pmღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ ĐỀ 1 Câu 1 (4 điểm) Cho dãy số: 32 17 45 26 10 50 22 15 Nêu thuật toán sắp xếp chọn trực tiếp (Selectionsort) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Giải: Thuật toán: Chọn đúng phần tử lớn thứ i và đưa về vị trí thứ i trong dãy Thực hiện đưa lần lượt N-1 phần tử về đúng vị trí của nó để được dãy có thứ tự Áp dụng: Ta có N = 8: B1: xét vị trí thứ 0< N-1: chọn phần tử 10 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 0, dãy mới: 10 17 45 26 32 50 22 15 B2: xét vị trí thứ 1< N-1: chọn phần tử 15 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 1, dãy mới: 10 15 45 26 32 50 22 17 B3: xét vị trí thứ 2< N-1: chọn phần tử 17 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 2, dãy mới: 10 15 17 26 32 50 22 45 B4: xét vị trí thứ 3< N-1: chọn phần tử 22 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 3, dãy mới: 10 15 17 22 32 50 26 45 B5: xét vị trí thứ 4< N-1: chọn phần tử 26 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 4, dãy mới: 10 15 17 22 26 50 32 45 B6: xét vị trí thứ 5< N-1: chọn phần tử 32 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 5, dãy mới: 10 15 17 22 26 32 50 45 B7: xét vị trí thứ 6 < N-1: chọn phần tử 45 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 6, dãy mới: 10 15 17 22 26 32 45 50 B8: xét vị trí thứ 7 = N-1: kết thúc => dãy đã được sắp xếp tăng dần. Câu 2 (3 điểm) Giả sử ổ khóa có n công tắc. Mỗi công tắc có một trong 2 trạng thái “đóng” hay “mở”. Khóa mở được nếu có ít nhất [n/2] công tắc có trạng thái mở. Thiết kế thuật toán liệt kê tất cả các cách mở khóa. Giải: Bài toán có dạng liệt kê dãy nhị phân có độ dài N bit: Tổ chức dữ liệu: Biểu diễn dãy nhị phân N bit dưới dạng mảng 1 chiều X[0], X[1],…,X[N-1] Phần tử của mảng X[i] có tập giá trị {0,1} với 0 thể hiện trạng thái đóng và 1 thể hiện trang thái mở của công tắc. Ý tưởng: Thử gán cho X[i] lần lượt mang các giá trị {0,1} Với mỗi giá trị chọn được cho X[i], thử các giá trị có thể có cho X[i+1] Tiếp tục thực hiện cho tới phần tử cuối cùng X[N-1], khi đó kiểm tra xem nếu dãy X có trạng thái mở(1) >= N/2 thì ta được 1 dãy nhị phân của bài toán Giải thuật: Try(i) For(j = {0,1}) X[i] = j; If(I == n-1) If (số trạng thái 1 >=N/2 nếu N chẵn,N lẻ >=N/2+1) Xuất X là dãy nhị phân tìm được End if Else Try(i+1) Bỏ chọn j để thử khả năng khác End if End for End try Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/(1*5) + 1/(2*5) + 1/(3*5) + …. + 1/(n*5) Giải: Thông số hóa bài toán: n Đk dừng: n =1 Mô hình tông quát: Si = 1/(1*5) + 1/(2*5) + 1/(3*5) + …. + 1/(i*5) 2<=i<=n Cài đặt hàm đệ quy: Float S(int n) { If(n==1) return 1.0/5; Return S(n-1) + 1.0/(5*n); }ĐỀ 2 Câu 1 (4 điểm) Cho dãy số: 20 15 45 26 10 50 22 17 Nêu thuật toán sắp xếp chèn trực tiếp (Insertionsort) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Giải: Thuật toán: Chọn đúng phần tử lớn thứ i và đưa về vị trí thứ i trong dãy Thực hiện đưa lần lượt N-1 phần tử về đúng vị trí của nó để được dãy có thứ tự Áp dụng: Ta có N = 8: B1: xét vị trí thứ 0 < N-1: chọn phần tử 10 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 0, dãy mới: 10 15 45 26 20 50 22 17 B2: xét vị trí thứ 1 < N-1: chọn phần tử 15 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 1, dãy mới: 10 15 45 26 20 50 22 17 B3: xét vị trí thứ 2 < N-1: chọn phần tử 17 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 2, dãy mới: 10 15 17 26 20 50 22 45 B4: xét vị trí thứ 3 < N-1: chọn phần tử 20 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 3, dãy mới: 10 15 17 20 26 50 22 45 B5: xét vị trí thứ 4 < N-1: chọn phần tử 22 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 4, dãy mới: 10 15 17 20 22 50 26 45 B6: xét vị trí thứ 5 < N-1: chọn phần tử 26 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 5, dãy mới: 10 15 17 20 22 26 50 45 B7: xét vị trí thứ 6 < N-1: chọn phần tử 45 nhỏ nhất từ vị trí đó đến cuối dãy và đổi chỗ với vị trí 6, dãy mới: 10 15 17 22 26 32 45 50 B8: xét vị trí thứ 7 = N-1: kết thúc => dãy đã được sắp xếp tăng dần. Câu 2 (3 điểm) Cho dãy a = (a1, a2, . . ., an ) gồm các số đôi một khác nhau. Thiết kế thuật toán liệt kê tất cả các hoán vị của dãy n phần tử của a. Giải: Bài toán có dạng liêt kê các hoán vị của dãy n phần tử. Phân tích bài toán: Mỗi hoán vị được biểu diễn dưới dạng 1 dãy các phần tử (X0X1X3…Xn-1) Các phần tử Xi của 1 hoán vị là khác nhau đôi 1. Sử dụng mảng 1 chiều X[0],X[1],…,X[n-1] để biểu diễn 1 hoán vị Ý tưởng: Sử dụng mảng đánh dấu C[j] = {0,1} cho biết khả năng A[j] có được chọn hay không (1:được chon 0:không được chọn) Thử lần lượt các khả năng chưa được các phần tử khác chọn cho X[i] Với những khả năng còn lại chưa được chọn, thử lần lượt cho X[i+1] và cứ thế tiếp tục cho đến X[n-1] Giải thuật: B1: khởi tạo C[j] =1, với mọi j: 0<=j<n ban đầu tất cả các giá trị đều được chọn B2: gọi thủ tuc Try(i) để tìm giá trị cho X[i]: Xét các giá trị A[j] được phép chọn cho X[i] Đặt C[j] = 0 đánh dấu khả năng j đã được chọn Gọi hàm đệ quy Try(i+1) để tìm giá trị cho X[i+1] Đặt C[j] = 1 để trả tự do cho j khi dừng đệ quy Hàm Try Try(i) For(int j = 0;j<n;j++) If(C[j] == 1) X[i] = A[j] If(i == n-1) Xuất ra 1 hoán vị Else C[j] = 0; Try(i+1) C[j] = 1; Cuối if Cuối if Cuối for Cuối Try Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/(2*3) + 1/(4*3) + 1/(6*3) + …. + 1/(2n*3) Giải: Thông số hóa bài toán: n Đk dừng: n =1 Mô hình tông quát: Si = 1/(2*3) + 1/(4*3) + 1/(6*3) + …. + 1/(2i*3) 2<=i<=n Cài đặt hàm đệ quy: Float S(int n) { If(n==1) return 1.0/6; Return S(n-1) + 1.0/(6*n); }ĐỀ 3 Câu 1 (4 điểm) Cho dãy số: 45 26 20 50 32 15 10 17 Nêu thuật toán sắp xếp nổi bọt (Bublesort) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Giải: Thuật toán: Xét từ đáy (cuối mảng) lên mặt nước (đầu mảng) và cho nổi bọt những cặp phần tử kề nhau, phần tử nhẹ hơn (có giá trị nhỏ hơn) sẽ được nổi lên trên. Sau mỗi đợt nổi bọt phần tử nhỏ nhất sẽ nổi lên trên (đầu mảng) Áp dụng Xét i = 0: 10 nhỏ hơn 15,32,50,20,26,45 đổi chỗ lần lượt ta được 45 26 20 50 32 15 10 17 10 45 26 20 50 32 15 17 Xét i=1: 15 nhỏ hơn 32,50,20,26,45 đổi chỗ lần lượt ta được 10 45 26 20 50 32 15 17 10 15 45 26 20 50 32 17 Xét i = 2:17 nhỏ hơn 32,50,20,26,45 đổi chỗ lần lượt ta được 10 15 45 26 20 50 32 17 10 15 17 45 26 20 50 32 Xét I = 3: 32 nhỏ hơn 50 đổi chỗ ta được 10 15 17 45 26 20 50 32 10 15 17 45 26 20 32 50 20 nhỏ hơn 26,45 đổi chỗ ta được 10 15 17 20 45 26 32 50 Xét I = 4: 26<45 10 15 17 20 26 45 32 50 Xét I = 5: 32<45 10 15 17 20 26 32 45 50 Xét I =6 không phải đổi chỗ Xet I = 7 = n-1 =>dãy được sắp tăng. Câu 2 (3 điểm) Cho dãy a = (a1, a2, . . ., an ) gồm các số đôi một khác nhau. Thiết kế thuật toán liệt kê tất cả cáctổ hợp chặp k trong tập gồm n phần tử cuả a. Giải: Bài toán có dạng liệt kê tổ hợp chặp k trong tập n phần tử Ý tưởng: Trong mảng các phần tử của mảng có vị trí không đổi nên ta sẽ tìm tổ hợp của các vị trí của phần tử rồi xuất ra các phần tử Ban đầu khởi tạo X[0] = 0 Với mỗi X[i] (1<=i<=k) gán lần lượt từng giá trị trong miền giá trị của X[i].khi đến phần tử thứ k ta được 1 cách chọn Miền giá trị cua X[i]: X[i-1]+1<=X[i]<=n-k+i Thuật toán: Try(i) For(j=X[i-1]+1;j<=n-k+I;i++) X[i] = j; If(i==k) Tìm được 1 cách chọn các vị trí của mảng Else Try(i+1) Cuối if Cuối for Cuối Try Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1 + 1/3 + 1/5 + … 1/(2n-1) Giải: Thông số hóa bài toán: n Đk dừng: n =1 Mô hình tông quát: Si = 1 + 1/3 + 1/5 + … 1/(2i-1) 2<=i<=n Cài đặt hàm đệ quy: Float S(int n) { If(n==1) return 1; Return S(n-1) + 1.0/(2*n-1); }ĐỀ 4 Câu 1 (4 điểm) Cho dãy số: 17 26 20 45 50 10 32 Trình bày thuật toán sắp xếp đổi chỗ trực tiếp (Interchangesort) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Giải: Thuật toán: Dãy tăng dần là dãy mà mọi phần tử đứng sau đều lớn hơn hoặc bằng phần tử đứng trước (mọi j>i: A[j]>=A[i]) Xét tất cả các phần tử của dãy, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì hoán vị chúng. Áp dụng Xét vt 0: 17 > 10 => hoán vị ta được 10 26 20 45 50 17 32 Xét vt 1: 26 > 20 => hoán vị ta được 10 20 26 45 50 17 32 20 > 17 => hoán vị ta được 10 17 26 45 50 20 32 Xét vt 2: 26 > 20 => hoán vị ta được 10 17 20 45 50 26 32 Xét vt 3: 45 > 26 => hoán vị ta được 10 17 20 26 50 45 32 Xét vt 4: 50 > 45 => hoán vị ta được 10 17 20 26 45 50 32 45 > 32 => hoán vị ta được 10 17 20 26 32 50 45 Xét vt 5: 50 > 45 => hoán vị ta được 10 17 20 26 32 45 50 => dãy đã được sắp tăng Câu 2 (3 điểm) Cho bàn cờ n x n ô. Một con ngựa được phép đi theo luật cờ vua (theo đường chéo hình chữ nhật 2 x 3). Thiết kế thuật toán tìm tất cả các hành trình của ngựa, bắt đầu từ ô <x0, y0> đi qua tất cả các ô của bàn cờ, mỗi ô đúng một lần. Giải: Tổ chức dữ liệu: ma trận vuông n*n Ban đầu khởi tạo tất cả các ô gt 0 Giá trị các phần tử của mảng là số nước đi qua của con ngựa Ý tưởng: Xét lần lượt các khả năng đi tiếp theo của con mã Nếu tìm được 1 khả năng Đi con mã đến ô tương ứng Nếu số nước là n*n thì tìm được 1 hành trình Ngược lại nếu không tìm được khả năng nào thì quay lại nước đi trước đó để chọn khả năng khác Giải thuật: Try(row,col,step) For(tất cả các nước có thể đi từ ô [row,col] If(ô [I,j] chưa qua) Ô [I,j] = step If(step = n*n) Xuất ra 1 hành trình Else Try(I,j,step+1) Cuối if Hủy nước đi tại ô I,j Cuối if Cuối for Cuối Try Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1 + 1/3 + 1/8 + … 1/(n2-1) Giải: Thông số hóa bài toán: n Dk dừng: n = 1 Mô hình tổng quát: Si = 1 + 1/3 + 1/8 + … 1/(i2-1)2<=i<=n Cài đặt hàm đệ quy: Float S(int n) { If(n==1) return 1; Return S(n-1) + 1.0/(n*n-1); }ĐỀ 5 Câu 1 (4 điểm) Cho dãy số: 20 10 17 26 50 32 45 15 Trình bày thuật toán sắp xếp đổi chỗ trực tiếp (Interchangesort) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Giải: Thuật toán: Dãy tăng dần là dãy mà mọi phần tử đứng sau đều lớn hơn hoặc bằng phần tử đứng trước (mọi j>i: A[j]>=A[i]) Xét tất cả các phần tử của dãy, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì hoán vị chúng. Áp dụng Xét vt 0: 20>10 hoán vị ta được: 10 20 17 26 50 32 45 15 Xét vt 1: 20>17 hoán vị ta được: 10 17 20 26 50 32 45 15 17>15 hoán vị ta được: 10 15 20 26 50 32 45 17 Xét vt 2: 20>17 hoán vị ta được: 10 15 17 26 50 32 45 20 Xét vt 3: 26>20 hoán vị ta được: 10 15 17 20 50 32 45 26 Xét vt 4: 50>32 hoán vị ta được: 10 15 17 20 32 50 45 26 32>26 hoán vị ta được: 10 15 17 20 32 26 45 50 Xét vt 5: 10 15 17 20 32 26 45 50 => dãy đã được sắp tăng Câu 2 (3 điểm) Cho 3 ký tự A, B, C và một số nguyên n. Lập thuật toán liệt kê tất cả các chuỗi tạo ra từ 3 ký tự trên, với chiều dài n, thoả điều kiện không có 2 chuỗi con liên tiếp nào giống nhau. Câu 3 (3 điểm) Viết thủ tục đệ quy thực hiện tìm kiếm nhị phân trên một dãy số trong hai trường hợp: (1,5 điểm) Dãy số tăng dần (1,5 điểm) Dãy số giảm dần Giải: Dãy số tăng Int tknp(int A[],int l,int r,int x) { If(l>r) return -1; Else { Int m = (l+r)/2; If(A[m] == x) Return m; Else If(A[m]>x) Return tknp(A,l,m-1,x); Else Return tknp(A,m+1,r,x); } } Dãy số giảm Int tknp(int A[],int l,int r,int x) { If(l>r) return -1; Else { Int m = (l+r)/2; If(A[m] == x) Return m; Else If(A[m]<x) Return tknp(A,l,m-1,x); Else Return tknp(A,m+1,r,x); } }ĐỀ 6 Câu 1 (4 điểm) Cho dãy số: 20 10 17 26 50 32 45 15 Áp dụng thuật toán MergeSort để sắp xếp dãy số tăng dần, nêu rõ từng bước Hãy cho biết trong đoạn lệnh sau có bao nhiêu phép so sánh các dữ liệu trong mảng: for (i = 1; i < = n-1; i ++) { j = i + 1; do { if (A[i] < A[j]) swap (A[i], A[j]); j ++; } while (j<= n) } Giải: Áp dụng 20 10 17 26 50 32 45 15 B1:Phân phối các đường chạy từ dãy A sang 2 dãy con B,C theo quy tắc luân phiên ta được: B: 20 32 45 C: 10 17 26 50 15 B2: thực hiện trộn các đường chạy của B,C 20 vs 10 17 26 50; 32 45 vs 15 ta được A: 10 17 20 26 50 15 32 45 B3:Phân phối các đường chạy từ dãy A sang 2 dãy con B,C theo quy tắc luân phiên ta được: B: 10 17 20 26 50 C: 15 32 45 B4: trộn 2 đường chạy trên B,C ta được: A: 10 15 17 20 26 32 45 50 B5: Phân phối các đường chạy từ dãy A sang 2 dãy con B,C theo quy tắc luân phiên ta được: B: 10 15 17 20 26 32 45 50 Vì đường chạy chỉ nằm trên dãy B => dãy đã được sắp tăng Ta có: hàm swap(A[i],A[j]) nằm trong câu lệnh do while =>if (A[i] < A[j]) được lặp n lần Mà câu lệnh do while lại nằm trong vòng lặp for =>if (A[i] < A[j]) được lặp n*n lần =>Có n*n phép so sánh. Câu 2 (3 điểm) Cho 3 ký tự A, B, C và n là một số nguyên dương (n>3) Thiết kế thuật toán liệt kê tất cả các chuỗi tạo ra từ 3 ký tự trên, với chiều dài n sao cho số ký tự A là 3. Giải: Bài toán có dạng liệt kê dãy nhị phân có độ dài N bit: Tổ chức dữ liệu: Biểu diễn dãy nhị phân N bit dưới dạng mảng 1 chiều X[0], X[1],…,X[N-1] Phần tử của mảng X[i] có tập giá trị {A,B,C} Ý tưởng: Thử gán cho X[i] lần lượt mang các giá trị {A,B,C} Với mỗi giá trị chọn được cho X[i], thử các giá trị có thể có cho X[i+1] Tiếp tục thực hiện cho tới phần tử cuối cùng X[N-1], khi đó kiểm tra xem nếu dãy X có số gt =A là 3 thì ta được 1 dãy nhị phân của bài toán Giải thuật: Try(i) For(j = {A,B,C}) X[i] = j; If(I == n-1) If (số ký tự A = 3) Xuất X là dãy nhị phân tìm được End if Else Try(i+1) Bỏ chọn j để thử khả năng khác End if End for End try Câu 3 (3 điểm) Thiết kế thuật toán tìm giá trị min trong một dãy số theo phương pháp chia để trị Giải: Ý tưởng: Chia: chia dãy số thành 2 dãy con Trị: tìm giá trị min của 2 dãy con theo phương pháp chia để trị Gộp: so sánh 2 giá trị min của 2 dãy giá trị nào nhỏ hơn là giá trị nhỏ nhất của mảng Cài đăt: Int min(int A[],int l,int r) { If(l==r) return A[l]; Else { Int m=(l+r)/2; Int minl = min(A,l,m); Int minr = min(A,m+1,r); Return minl>minr ? minr : minl; } } CHÚ Ý: CÁC ĐỀ BÀI VÀ BÀI GIẢI TRÊN CHỈ MANG TÍNH THAM KHẢO, CÁC BẠN PHẢI HỌC THÌ MỚI LÀM BÀI ĐƯỢC TỐT!!!CHÚC LỚP 09CT112 THI TỐT
vuongchau90 Tài Sản của : vuongchau90 Tiêu đề: THUAT GIAI(BO SUNG) Sat May 28, 2011 7:07 pmღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ ĐỀ 7 Câu 1 (4 điểm) Cho dãy số: 45 26 20 50 32 15 10 17 Áp dụng phương pháp nổi bọt cải tiến (ShakerSort) để sắp xếp dãy số trên tăng dần, nêu rõ từng bước Giải: Ý tưởng: Cải tiến lại phương pháp nổi bột là phần tử nhẹ nổi lên rất nhanh,phần tử nặng chìm rất chậm Tại mỗi bước sắp xếp thực hiện nổi phần tử nhẹ lên trên sau đó đẩy phần tử nặng xuống Ghi nhận những đoạn đã có thứ tự để tránh các phép so sánh thừa Áp dụng: B1: l = 0;r = 7 Cho phần tử từ l->r phần tư nhẹ nổi lên: 10 45 26 20 50 32 15 17 =>L=1 - phần tử nặng chìm xuống: 10 26 20 45 32 15 17 50 => r = 6 B2: l =1; r =6 Cho phần tử từ l->r phần tư nhẹ nổi lên: 10 15 26 20 45 32 17 50 - phần tử nặng chìm xuống: 10 15 20 26 32 17 45 50 B3: l =2; r =5 Cho phần tử từ l->r phần tư nhẹ nổi lên: 10 15 17 20 26 32 45 50 - phần tử nặng chìm xuống: 10 15 17 20 26 32 45 50 B3: l =3; r =4 Cho phần tử từ l->r phần tư nhẹ nổi lên: 10 15 17 20 26 32 45 50 - phần tử nặng chìm xuống: 10 15 17 20 26 32 45 50 B4: l =4; r =3 => l>r => dãy đã được sắp xếp Câu 2 (3 điểm) Cho bàn cờ n x n ô. Một con ngựa được phép đi theo đường chéo 2 x 2. Thiết kế thuật toán liệt kê tất cả các hành trình của ngựa, bắt đầu xuất phát từ ô <x0, y0 > đi qua tất cả các ô của bàn cờ, mỗi ô đi qua đúng một lần. Giải: Ý tưởng: Xét tất cả các nước đi tiếp theo của quân mã Nếu tìm được 1 khả năng: Đi quân mã tới ô tương ứng Nếu là nước n*n thì tìm được 1 hành trình Ngược lại không tìm được khả năng nào Quay lại ô trước đó để chọn khả năng khác Thuật toán: Try(row,col,step) For(các nước đi tiếp theo của con ngựa từ ô row col) If(ô [i,j] chưa qua) Ô [I,j] = step; If(step == n*n) Xuất ra 1 hành trình; Else Try(I,j,step++) Cuối if Hủy nước đi tại ô [I,j] Cuối if Cuối for Cuối Try Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/13 + 1/33 + 1/53 + … + 1/(2n-1)3 Giải: Thông số hóa bài toán: n Điều kiện dừng: 1 Mô hình tổng quát: Si = 1/13 + 1/33 + 1/53 + … + 1/(2i-1)32<=i<=n Cài đặt: Float S(int n) { If(n==1) return 1; Return S(n-1) + 1.0/(2*n-1)/(2*n-1)/(2*n-1); } ĐỀ 8 Câu 1 (4 điểm) Cho dãy số: 17 26 20 10 50 32 15 Áp dụng thuật toán Quicksort để sắp xếp dãy số tăng dần, nêu rõ từng bước Giải: Ý tưởng: Chọn 1 giá trị trong dãy làm giá trị chốt Chia dãy ra làm 2 dãy con: dãy 1 gồm những phần tử <= gt chốt,dãy 2 gồm những phần tử > chốt Sắp xếp 2 dãy con theo tư tưởng trên Áp dụng B1 chọn 10 làm chốt i=0 về cuối dãy, j = 6 về đầu dãy …….. 17 26 20 10 50 32 15 10 26 20 17 50 32 15 Kai’ nay` trinh` bay` khó qua’ cac’ ban tu xu nha :d Câu 2 (3 điểm) Cho một lưới hình vuông cấp n, mỗi ô được gán với một số tự nhiên. Tại một ô có thể di chuyển đến ô khác theo các hướng : lên trên, xuống dưới, rẽ trái, rẽ phải (4 ô kề cạnh). Áp dụng phương pháp nhánh cận tìm đường đi từ ô đầu tiên (1,1) đến ô (m,m) sao cho mỗi ô đi qua đúng 1 lần và tổng các ô là nhỏ nhất. (1≤ m≤n). Giải: Ý tưởng: Khơi tạo 1 cấu hình BEST cho bài toán: khởi tạo cận Tính chi phí của cấu hình ngay trong quá trình xây dựng: Nếu tốt hơn BEST: cập nhật cấu hình tối ưu và tiếp tục Ngược lại quay lui tìm phương án khác Thuật toán: Try(row,col,i) For( j thuộc tập khả năng đi tiếp theo của ô [row,col]) If(nếu ô [I,j] chưa đi qua) Chon khả năng j cho X[i] If( [I,j] là ô [m,m]) Cập nhật đường đi else if(vẫn còn tốt hơn BEST ) Try(I,j,i+1); Cuối if Bỏ dánh dấu đã đi qua ô [i,j] Cuối if Cuối for Cuối Try Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/(1*2) + 1/(2*2) + 1/(3*2) + …+ 1/(n*2) Giải: Thông số hóa bài toán: n điều kiện dừng: 1 mô hình tổng quát: Si = 1/(1*2) + 1/(2*2) + 1/(3*2) + …+ 1/(i*2) 2<=i<=n cài đặt: float S(int n) { If(n ==1) return 1.0/2; Return S(n-1) + 1.0/(n*2); } ĐỀ 9 Câu 1 (4 điểm) Cho dãy số: 10 50 17 26 20 32 15 45 Áp dụng thuật toán Shellsort để sắp xếp dãy số tăng dần, nêu rõ từng bước Giải: Ý tưởng: Mỗi bước h, áp dụng phương pháp chèn trực tiếp để sắp xếp các dãy con Giảm dần bước nhảy h dần dần về 1 khi đó dãy được sắp xếp Áp dụng: H = 3: 10 50 17 26 20 32 15 45 D1: 10 26 15 D2: 50 20 45 D3: 17 32 Sắp xếp từng dãy con theo pp chèn trự tiếp ta được: D1: 10 15 26 D2: 20 45 50 D3: 17 32 H =2: 10 20 17 15 45 32 26 50 D1: 10 17 45 26 D2: 20 15 32 50 Sắp xếp từng dãy con theo pp chèn trự tiếp ta được: D1: 10 17 26 45 D2: 15 20 32 50 H =1: 10 15 17 20 26 32 45 50 dãy đã được sắp xếp Câu 2 (3 điểm) Cho n loại tiền xu tương ứng với các giá trị k1< k2..<kn xu. Thiết kế thuật toán để đổi T đồng tiền giấy ra tiền xu sao cho số đồng xu cần dùng là ít nhất. Cho 1 đồng bằng 100 xu. Giải: Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/(12+5) + 1/(22+5) + 1/(32+5) + …. + 1/(n2+5) Giải: Thông số hóa bài toán: n Đk dừng: 1 Mô hình tổng quát: Si = 1/(12+5) + 1/(22+5) + 1/(32+5) + …. + 1/(i2+5) 2<=i<=n Cài đặt Float S(int n) { If(n==1) return 1.0/5; Return S(n-1) + 1.0/(n*n+5); }
[N]