bài tập về sắp xếp
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (129.79 KB, 4 trang )
TÍNH ĐỆ QUY CỦA CHƯƠNG TRÌNH CON - THUẬT TỐN SẮP XẾP NHANH
1. Đệ qui:
- Một chương trình con (hàm hay thủ tục) được gọi là đệ quy nếu trong q trình thực hiện nó có phần phải gọi đến
chính nó
- Ví dụ: xét CTC để tính giai thừa của một số như sau:
Function GT (x : integer) : longint;
BEGIN
If x = 0 then GT := 1 Else GT := x *GT(x-1);
End;
- Chương trình con GT có tính đệ quy vì trong bản thân chương trình con đó có lời gọi chính nó.
2. Sắp xếp nhanh:
Ở trong chương trình tin học 11 chúng ta thường quen với thuật toán sắp xếp tráo đổi, ưu điểm của thuật
toán này là dễ cài đặt nhưng nhược điểm là độ phức tạp của thuật tốn lớn (độ phức tạp = O(n 2)). Vì vậy, một trong
những thuật toán hay được sử dụng khi giải bài toán sắp xếp là thuật toán sắp xếp nhanh. Ý tưởng của thuật toán sắp
xếp nhanh dựa vào tìm kiếm nhị phân như sau:
+ Chọn phần tử x là phần tử chính giữa của dãy để so sánh. Khi đó, mục tiêu của chúng ta chia dãy ban đầu thành
ba dãy con và sắp xếp chúng theo thứ tự như sau:
* Dãy 1: gồm các phần tử nhỏ hơn x
* Dãy 2: gồm các phần tử bằng x
* Dãy 3: gồm các phần tử lớn hơn x
+ Sau đó áp dụng lại ý tưởng trên cho dãy 1 và dãy 3 nếu các dãy này có nhiều hơn một phần tử.
* Cài đặt thuật toán này ta sử dụng chương trình con sau:
type arr = array[1..100] of integer; Var A: arr;
procedure sxn(l,r: integer);
var i, j : integer; x, tg : integer;
begin
i:=l; j:=r; x:=A[(l + r) div 2];
while i <= j do
begin
while A[i] < x do i:=i+1;
while x
if i<=j then
begin
tg:=A[i]; A[i]:=A[j]; A[j]:=tg;
i:=i+1; j:=j-1;
end;
end;
if l < j then sxn(l,j);
if i < r then sxn(i,r);
end;
Lưu ý: Muốn sắp xếp nhiều mảng, ta đưa mảng A vào làm tham số hình thức. Khi đó phần đầu của thủ tục có thể
kahi báo theo cách 1 hoặc cách 2
Cách 1:
Cách 2:
type arr = array[1..100] of integer; Var A: arr;
type arr = array[1..100] of integer; Var A: arr;
procedure sx(var A: arr);
procedure sxn(l,r:integer; var A);
procedure sxn(l,r:integer);
- Lệnh gọi đệ qui trong chương trình con ta phải gọi sxn(l,j,A);
và sxn(i,r,A);
* Áp dụng để giải quyết các bài toán sau:
Bài 1: Số thực. Cho dãy số thực a1, a2, .., aN. Hãy đếm xem có bao nhiêu số có giá trị lớn thứ nhì trong dãy số đã cho.
Dữ liệu vào: từ tệp văn bản SOTHUC.INP gồm:
- Dòng 1 ghi số nguyên dương N (2 ≤ N ≤ 10000);
- Dòng thức i trong N dòng tiếp theo ghi số thực ai.
Kết quả: ghi ra tệp văn bản SOTHUC.OUT gồm 1 số duy nhất là kết quả tìm được.
Ví dụ:
SOTHUC.INP
SOTHUC.OUT
5
2
100
15.5
2
15.5
10.123
Bài 2: Cho dãy gồm N (N<=30000) số tự nhiên khơng vượt q 109, tìm số tự nhiên nhỏ nhất khơng xuất hiện
trong dãy
Dữ liệu vào trong tệp SN.INP có dạng:
Dòng đầu là số nguyên N
Dòng thứ hai gồm N số
Kết quả ra ghi vào tệp SN.OUT là số tự nhiên nhỏ nhất không xuất hiện trong dãy.
-
SN.INP
SN.OUT
5
50314
2
Bài 3: Một máy phát nhạc tự động có một băng nhạc đủ lớn để ghi n bài hát, thời gian phát mỗi bài tính theo phút
và được biết trước. Biết rằng, để phát bài thứ i thì máy phải trở về vị trí đầu băng và quay để bỏ qua i – 1 bài trước
đó. Máy có thể trở về đầu băng với thời gian không đáng kể và thời gian quay để bỏ qua mỗi bài bằng thời gian
phát bài đó. Hãy tìm cách ghi các bài hát trên băng nhạc sao cho tổng số thời gian quay băng trong ngày là nhỏ
nhất. Biết rằng mỗi bài hát được phát một lần.
Dữ liệu vào : đọc từ tệp văn bản BANGNHAC.INP có cấu trúc như sau: Dịng thứ nhất chứa số N ( N ≤1000). Các
dòng tiếp theo chứa các số nguyên t1, ..., tn lần lượt là thời gian phát các bài 1, .., n
Các số cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi vào tệp BANGNHAC.OUT có cấu trúc như sau:
- Dòng một là tổng thời gian nhỏ nhất phát cả băng nhạc
- Dòng tiếp theo là thứ tự phát bài hát, mỗi số cách nhau một dấu cách
Ví dụ:Bangnhac.inp
Bangnhac.out
3
18
326
213
Bài 4: Đoạn thẳng chia đều
Trên trục tọa độ Ox, cho N điểm khác nhau P 1, P2, …., PN. Đoạn thẳng AB được gọi là đoạn thẳng chia đều nếu nó
được xác định bởi ba điểm cho trước A, B, M sao cho M là trung điểm của AB.
Yêu cầu: Cho biết tọa độ của N điểm P1, P2, …., PN. Hỏi có bao nhiêu đoạn thẳng chia đều được tạo ra từ các điểm
đã cho?
Dữ liệu: vào từ tệp văn bản CHIADEU.INP gồm:
- Dòng 1: Ghi số nguyên dương N
- Dòng 2: Ghi lần lượt các số x1, …, xN (|xi| ≤ 105) tương ứng là tọa độ của các điểm P1, P2, …., PN
Kết quả: Ghi ra tệp văn bản CHIADEU.OUT gồm một số duy nhất là kết quả tìm được của bài tốn.
Ví dụ:
CHIADEU.INP
CHIADEU.OUT
Giải thích
5
3
Đoạn 1: 5 -1, trung điểm 2
3 -1 2 5 4
Đoạn 2: 2 4, trung điểm 3
Đoạn 3: 3 5, trung điểm 4
Bài 5: Bán sữa (Milk.Pas)
Một cửa hàng bán sữa hiện có n hộp sữa trong kho. Mỗi ngày cửa hàng phải đem giao k hộp sữa cho
khách hàng nếu trong kho còn từ k hộp sữa trở lên, và nếu cịn ít hơn thì sẽ giao hết các hộp sữa. Nhưng có một
vấn đề với các hộp sữa là ngày hết hạn của chúng. Mỗi hộp sữa có một ngày hết hạn mà sau ngày đó thì hộp sữa
không thể dùng được và phải bỏ đi. Cửa hàng khơng muốn những hộp sữa bị q hạn, vì thế khi giao một hộp sữa
cho khách hàng, cửa hàng sẽ chọn hộp sữa cịn hạn sử dụng ít hơn để giao trước. Chiến lược này sẽ giúp cửa hàng
hạn chế tối đa các hộp sữa không giao kịp và bị quá hạn.
Biết rằng, cửa hàng đã biết hạn sử dụng của mỗi hộp sữa. Hạn sử dụng được thể hiện bằng một con số cho biết số
ngày còn lại mà hộp sữa còn dùng được. Chẳng hạn, hạn sử dụng là 1 cho biết hộp sữa phải giao trong ngày hôm
nay, số 2 là không thể để trễ hơn ngày mai, ...
u cầu:
Hãy cho biết có ít nhất bao nhiêu hộp sữa bị quá hạn sử dụng phải bỏ đi vì cửa hàng khơng giao kịp
Để hộp sữa khơng bị quá hạn sử dụng thì mỗi ngày cửa hàng cần phải giao được ít nhất bao nhiêu hộp.
Dữ liệu vào: Cho từ tệp văn bản Milk.inp gồm 2 dòng
Dòng thứ nhất ghi hai số n, k là số hộp sữa hiện có và số hộp sữa cửa hàng phải giao mỗi ngày (1≤k, n ≤ 10 6)
Dòng thứ hai ghi n số nguyên dương a1, a2, ..., an (0
- Dòng 1 ghi số hộp sữa bị quá hạn sử dụng ít nhất nếu mỗi ngày cửa hàng giao được k hộp
-
Dịng thứ 2 ghi số hộp sữa ít nhất mà mỗi ngày cửa hàng cần phải giao được để không có hộp sữa nào bị
q hạn sử dụng.
Ví dụ:
Milk.inp
Milk.out
62
1
211232
3
Bài 6:Tàu biển (SHIP.PAS- Đề thi tỉnh Đồng Tháp năm 15 - 16)
Một công ty xuất khẩu thủy sản cần xuất khẩu một kho hàng bằng đường biển. Kho hàng được đóng thành n kiện
hàng có khối lượng lần lượt là a1, a2, ..., an tấn. Cơng ty chỉ có một tàu biển trọng tải m tấn. Để vận chuyển hết kho
hàng, con tàu cần vận chuyển nhiều lần, số lần vận chuyển phụ thuộc rất nhiều vào cách xếp các kiện hàng lên tàu.
Yêu cầu: Tính số lần vận chuyển ít nhất của tàu biển để vận chuyển hết kho hàng
Dữ liệu vào: Cho từ tệp văn bản SHIP.INP có dạng:
- Dòng thứ nhất ghi hai số nguyên dương n, m (1 ≤N≤104)
- Dòng thứ hai ghi N số nguyên dương a1, a2, ..., an (1 ≤ai≤ m). Các số ghi trên cùng một dịng ghi cách nhau
ít nhất một dấu cách.
Dữ liệu ra: Ghi vào tệp văn bản SHIP.OUT gồm một dòng ghi một số nguyên duy nhất là số lần tàu biển vận
chuyển tính được.
Ví dụ:
SHIP.INP
SHIP.OUT
56
3
42551
Bài 7: Mua hàng (BUY.PAS)
Một cơng ty muốn mua M máy tính. Sau khi lấy thông tin tại N cửa hang (1<=N<=10000), người ta biết được rằng
cửa hàng i có bán Ai máy tính với mỗi máy tính có giá là Bi. (Ai, Bi là những số nguyên dương: Ai<=100, Bi<=2000).
Giả sử các cửa hàng đủ máy tính để bán cho cơng ty. Hãy tìm cách mua rẻ nhất.
Dữ liệu vào từ tệp BUY.INP theo cấu trúc sau:
- Dòng1: ghi 2 số M, N cách nhau ít nhất một dấu cách
- N dịng tiếp theo, dòng thứ i ghi 2 số Ai và Bi cách nhau ít nhất một dấu cách
Kết quả: ghi vào tệp BUY.OUT theo cấu trúc sau:
- Dòng 1 ghi tổng số tiền phải trả- N dòng tiếp theo, dong thứ i ghi số máy tính mua ở cửa hàng i
VD:
BUY.INP
BUY.OUT
22 5
168
3 30
0
5 10
5
68
6
10 5
10
2 20
1
Bài 8: Trong cửa hàng sách, mỗi quyển sách được đánh dấu bởi một số nguyên, hai loại sách khác nhau được đánh
bởi hai số nguyên khác nhau. Em hãy lập trình giúp bác bán sách tìm ra loại sách cịn nhiều nhất. Biết
- Dữ liệu vào từ tệp sach.inp gồm dòng đầu ghi số nguyên dương N ( 0 < N < 106) dòng tiếp theo ghi ai là kí
hiệu của mỗi quyển sách, mỗi số cách nhau ít nhất 1 dấu cách.
- Dữ liệu ra ghi vào tệp sach.out ghi số hiệu sách và số quyển cịn lại nhiều nhất
- Ví dụ:
Sach.inp
Sach.out
11
24
12232452676
Bài 9. Tổng đoạn thẳng
Cho n (n ≤ 10000) đoạn thẳng trên trục số với các điểm đầu xi và độ dài di (|xi|, di là những số nguyên
9
không vượt quá 10 ). Tính tổng độ dài trên trục số bị phủ bởi n đoạn trên.
Ví dụ: Có 3 đoạn x1=-5, d1=10; x2=0, d2=6; x3=-100, d3=10 thì tổng độ dài trên trục số bị phủ bởi 3 đoạn trên là 21.
Dữ liệu vào từ tệp văn bản TONGDD.INP có cấu trúc như sau:
• Dịng 1: chứa số ngun dương n (1≤n ≤ 10000).
•
Dịng thứ i trong n dòng tiếp theo ghi tọa độ điểm đầu và độ dài của đoạn thẳng thứ i (các số cách nhau
một dấu cách)
Kết quả: Ghi ra tệp văn bản TONGDD.OUT: ghi tổng độ dài trên trục số bị phủ bởi n đoạn thẳng đã cho.
Ví dụ:
TONGDD.INP
TONGDD.OUT
3
-5 10
06
-100 10
21
Bài 10. Khiêu vũ Trên hành tinh Omega xinh đẹp, thế giới của những người khổng lồ và tí hon. Ở Vương quốc
Hạnh Phúc có � chàng trai đánh số từ 1 đến � và � cô gái đánh số từ 1 đến �. Chàng trai thứ �có chiều cao � �(�
= 1,2,…,�), cơ gái thứ �có chiều cao � �(� = 1,2,…,�). Trong lễ kỷ niệm 1000 năm quốc khánh của Vương quốc,
Quốc Vương tổ chức một buổi khiêu vũ. Ban tổ chức muốn chọn ra một số cặp nhảy. Mỗi cặp nhảy gồm đúng 1
chàng trai và 1 cơ gái, trong cặp đó chàng trai phải cao hơn cô gái. Mỗi chàng trai, cô gái trong Vương quốc không
được tham gia quá 1 cặp nhảy. Em hãy giúp ban tổ chức tìm một số nhiều nhất các cặp nhảy thỏa mãn yêu cầu trên.
* Input: đọc vào từ file văn bản DANCE.INP gồm:
- Dòng 1 ghi hai số nguyên dương �,� ≤ 105;
- Dòng 2 ghi � số nguyên dương �1,�2,…,�� (∀
∀ :�� ≤ 109);
- Dòng 3 ghi � số nguyên dương �1,�2,…,�� (∀
∀:�� ≤ 109); Các số trên một dịng được ghi cách nhau ít
nhất một dấu cách.
* Output: ghi ra file văn bản DANCE.OUT gồm:
- Dòng 1: ghi một số nguyên là số cặp nhảy theo phương án tìm được;
- Nếu có từ 1 cặp nhảy trở lên thỏa mãn, những dòng tiếp theo mỗi dòng ghi 2 số i, j là số của chàng trai i
và cơ gái j.
* VD:
DANCE.INP
DANCE.OUT
DANCE.INP
DANCE.OU
* Chú ý: có 50% số điểm ứng
T
với các test có �,� ≤ 1000
32
1
45
3
132
21
4231
23
23
22145
31
12
Bài 11. Trò chơi với dãy số: Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. M ỗi bạn chọn trước một
dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là: b1, b2, ..., bn còn dãy số mà bạn thứ hai chọn là c1,
c2, ..., cn
Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng b i (1 <= i <= n),
còn bạn thứ hai đưa ra số hạng cj (1 <= j <= n) thì giá của lượt chơi đó sẽ là |b i+cj|.
Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể
của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có
thể là 0 tương ứng với giá của lượt chơi (-2, 2).
Yêu cầu: Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.
INPUT: vào từ file văn bản SEQGAME.INP
- Dòng đầu là số nguyên dương (1 <= n <= 105)
- Dòng thứ hai chứa các số là dãy b (|b i| <= 109)
- Dòng thứ hai chứa các số là dãy c (|ci| <= 109)
OUTPUT: ghi ra file văn bản SEQGAME.OUT giá trị nhỏ nhất tìm được
Ví dụ:
Ràng buộc: 60% số test ứng với 60% số điểm có 1<= n <= 1000
Hướng dẫn giải
Bài tốn có thể giải bằng 2 cách:
Cách 1: Sử dụng 2 vòng lặp lồng nhau để tìm giá trị nhỏ nhất. Độ phức tạp là O(N2)
Cách 2: Sử dụng phương pháp tìm kiếm nhị phân như sau:
Bước 1: Sắp xếp dãy A tăng dần
Bước 2: xét các giá trị B[i].
Xét các giá trị A[g] (g = (d + c) div 2 với d = 1, c = N)
Min := A[g] + B[i]
- Nếu A[g] + B[i] < 0 thì phải tăng g lên để tổng gần 0 hơn khi đó d := g + 1
- Nếu A[g] + B[j] > 0 thì phải giảm g xuống để tổng gần 0 hơn khi đó c := g – 1.
- Nếu Min = 0 thì thốt
Kq = |Min|
Độ phức tạp là O(NlogN).
