Diễn Đàn Lớp 09CT112


 
IndexPortalCalendarTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập
News & Announcements
  • Gallery
163 Số bài - 27%
82 Số bài - 13%
77 Số bài - 13%
56 Số bài - 9%
53 Số bài - 9%
43 Số bài - 7%
39 Số bài - 6%
36 Số bài - 6%
33 Số bài - 5%
33 Số bài - 5%
Similar topics
Tài khoản gmail chung cho lớp
Tue Sep 13, 2011 10:58 pm by haily2312
tên tài khoản: 09ct112@gmail.com.
password: Khongb!t

Comments: 2
Lịch thi sớm môn Cơ bản học kỳ 1 năm học 2011-2012
Tue Oct 04, 2011 9:42 am by haily2312
Theo thông báo của khoa lớp chúng ta sẽ thi môn PPNCKH vào ngày 19/11/2011 lúc 17h30 địa điểm chưa xác định. Sẽ tiếp tục cập nhật thông báo mới

Link chi tiết http://cs.lhu.edu.vn/?CID=8&NewsID=12708

Comments: 2
Lý thuyết đồ thị
Fri May 27, 2011 5:11 pm by ღ♂→√ô◦Tìnђ♥ №¹ღ
Ai có tài liệu lý thuyết đồ thị của thầy share với " love " đi nào ??? 4rum gì chán dữ vậy? Ko có cả 1 bóng ma

Comments: 3
Đề thi Online Final cho những ai không may
Thu Jun 23, 2011 10:10 am by nguyenluuphat
các bạn vào đây download về xem nhé.
www.mediafire.com/phatdeptrai
hoặc
http://www.mediafire.com/?6h9y7452s1gch9f

Comments: 0
TIN HOT...về cuộc thi Đố vui tin học năm 2011
Wed Feb 23, 2011 4:51 pm by [N]
ĐOÀN TRƯỜNG ĐH LẠC HỒNG
ĐOÀN KHOA CÔNG NGHỆ THÔNG TIN
SỐ:../../../..
ĐOÀN TNCS HỒ CHÍ MINH
Biên Hòa, ngày 20 tháng 02 năm 2011
------------------------

KẾ HOẠCH
Tổ chức Cuộc thi Đố vui tin học năm 2011



Hưởng ứng phong trào Đoàn trong nhà
trường năm 2011. Được sự cho phép của BCH Đoàn trường và Ban lãnh đạo
khoa, BCH …

[ Full reading ]
Comments: 2
CƠ HỘI CHỨNG TỎ BẢN LĨNH... tham gia nào.
Wed Feb 23, 2011 4:39 pm by [N]
Trường ĐH Lạc Hồng
Khoa Công Nghệ Thông Tin

Đoàn Trường ĐH Lạc Hồng
Biên Hòa, Ngày 21 Tháng 12 Năm 2010
-------------------------------



KẾ HOẠCH TỔ CHỨC CUỘC THI ICTCUP 2011



1. Giới thiệu về cuộc thi
Trường Đại học Lạc Hồng là một trường
thành viên của Đại học có nhiệm vụ đào tạo nguồn nhân lực công …


[ Full reading ]
Comments: 3
LichThiLan2_ChinhThuc_Ngay_18_19_20
Sat Feb 12, 2011 9:27 pm by Krong Ana
Lớp ------ Môn Thi ----- Thứ ---- Ngày Thi --- Giớ Thi --- Phòng Thi

09CT112 ---- TOÁN RỜI RẠC ---- 7 ----- 2/19/2011 --- 09H30 --- B305

09CT112 ----- TOEIC 3-NÓI --- CN ---- 2/20/2011 --- 07H30 ---- G201


Comments: 1
Lich thi lần 2 lớp 09ct112 các ngày 14-15-16-17
Fri Feb 11, 2011 1:27 pm by (™•†•[pinv_a]•†•™)
CẤU TRÚC DỮ LIỆU
thứ 2.... 14/2/2011 ......... 09H30......... B201

Toán A3
thứ 3...... 15/2/2011 ...... 09H30 D305 & D403

TOEIC 3(nghe,đọc hiểu)
thứ 4 ........ 16/2/2011 ......... 07H30..... PM6-C404

MẠNG MÁY TÍNH


[ Full reading ]
Comments: 0
Lịch Thi lại lần 2 update ngày 2-2-2011
Fri Feb 04, 2011 12:02 am by (™•†•[pinv_a]•†•™)
xem lich thi ùi thi lại nhe mấy ku.

download Tại Đây

Comments: 0

Share|

DE THI 60% THUAT GIAI

Xem chủ đề cũ hơn
Xem chủ đề mới hơn
Go down
Tác giảThông điệp
vuongchau90

Tổng số bài gửi : 13
Join date : 21/02/2011
Age : 27
Tài Sản của : vuongchau90
Bài gửiTiê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
Về Đầu Trang Go down
Xem lý lịch thành viên
ღ♂→√ô◦Tìnђ♥ №¹ღ

Tổng số bài gửi : 5
Join date : 14/03/2011
Age : 25
Đến từ : ĐẾN TỪ .....?????
Tài Sản của : ღ♂→√ô◦Tìnђ♥ №¹ღ
Bài gửiTiêu đề: Re: DE THI 60% THUAT GIAI Thu May 26, 2011 6:47 pm

ღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
có ai giải chưa vậY?
Về Đầu Trang Go down
Xem lý lịch thành viên
[N]

Tổng số bài gửi : 39
Join date : 17/01/2011
Tài Sản của : [N]
Bài gửiTiê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 = (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 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 = (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á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
Về Đầu Trang Go down
Xem lý lịch thành viên
vuongchau90

Tổng số bài gửi : 13
Join date : 21/02/2011
Age : 27
Tài Sản của : vuongchau90
Bài gửiTiê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);
}
Về Đầu Trang Go down
Xem lý lịch thành viên
[N]

Tổng số bài gửi : 39
Join date : 17/01/2011
Tài Sản của : [N]
Bài gửiTiêu đề: Re: DE THI 60% THUAT GIAI Mon May 30, 2011 4:57 pm

ღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
BAI GIAI CUA 16 DE GIAI THUAT DAY!
http://www.mediafire.com/?4bnxsa5cu9wyt61
Về Đầu Trang Go down
Xem lý lịch thành viên
Sponsored content

Tài Sản của : Sponsored content
Bài gửiTiêu đề: Re: DE THI 60% THUAT GIAI Today at 7:29 am

ღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
Về Đầu Trang Go down

DE THI 60% THUAT GIAI

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang
Trang 1 trong tổng số 1 trang

* Viết tiếng Việt có dấu, là tôn trọng người đọc.
* Chia sẻ bài sưu tầm có ghi rõ nguồn, là tôn trọng người viết.
* Thực hiện những điều trên, là tôn trọng chính mình.
...-Nếu chèn smilies có vấn đề thì bấm A/a trên phải khung viết bài-...
Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn Đàn Lớp 09CT112 :: ĐẠI SẢNH
Hội trường của Forum
 :: ● Sự Kiện Của Lớp ●
-