Tài liệu bồi dưỡng học sinh giỏi Tin học 9 - Vũ Thị Thêm

DÃY CON TĂNG DÀI NHẤT
TÀI LIỆU BỒI DƯỠNG HỌC SINH GIỎI TIN HỌC 9
 Giáo viên : Vũ Thị Thêm
Cô trò trong buổi học đầu tiên về dãy con tăng dài nhất
Trong thời gian dạy đội tuyển tin học 9, khi chưa sắp xếp lại các bài toán vào từng dạng thì việc học sinh hiểu sâu và nắm rõ thuật toán của mỗi dạng toán thật không dễ dàng chút nào. Sau khi đầu tư thời gian vào nghiên cứu, tìm hiểu, phân loại các bài toán giải bằng phương pháp quy hoạch động thì kết quả thay đổi rất lớn, học sinh đã nắm vững hơn từng dạng toán, việc dạy của giáo viên cũng đỡ vất vả hơn, đặc biệt là kết quả làm bài của các em thay đổi rõ ràng, nhiều học sinh vận dụng giải quyết các bài toán ngoài cả sự mong đợi của giáo viên.
	Ở bài viết này tôi xin chia sẻ với bạn đọc một số bài toán áp dụng thuật toán của bài dãy con tăng dài nhất. Khi dạy dạng toán này trước tiên tôi đưa ra cho học sinh bài toán nguyên bản “cho một dãy số, tìm dãy con tăng dài nhất của dãy số đã cho”, sau đó tôi cho học sinh làm các bài tương tự từ đơn giản đến phức tạp. Sau đây là các bài tập khi dạy chuyên đề dãy con tăng dài nhất. 
Bài toán: Cho n số nguyên dương và một dãy A1, A2, A3, , An các số nguyên. Tìm trong dãy đã cho một dãy con tăng dần thỏa mãn các điều kiện:
Ai1, Ai2, , Aik thì Ail < Ail+1
ij<ij+1
k lớn nhất.
Dữ liệu vào: file daycontang.inp có cấu trúc như sau:
Dòng thứ nhất ghi số n
Các dòng tiếp theo chứa dãy A1, A2, A3, , An mỗi dòng 10 số ( trừ dòng cuối cùng), các số cách nhau ít nhất một dấu cách.
Dữ liệu ra có cấu trúc như sau:
Dòng thứ nhất ghi số k
Các dòng tiếp theo ghi k số Ai1, Ai2, , Aik các số cách nhau ít nhất một dấu cách.
INP
OUT
12
12 8 11 3 4 1 7 5 9 10 2
5
3 4 7 9 10
 Hướng dẫn : 
Học sinh làm bài theo hướng dẫn của giáo viên
- Xây dựng mảng T và D với ý nghĩa:
T[i]=j là chỉ số j trong dãy đã cho của phần tử đứng ngay trước Ai trong dãy kết quả. Cách tính T[i], duyệt mảng A từ vị trí 1 đến vị trí i-1. Tìm vị trí j có D[j] lớn nhất trong các vị trí j thỏa mãn A[j]<A[i].
D[i] là độ dài của dãy kết quả và được tính theo công thức truy hồi 
D[i]=max(D[j]+1 với j=1..i-1và A[j]<A[i]).
 Chương trình tham khảo:
Program daycontangdainhat;
Var fa,fz:text;
n,i,j:longint;
T,A,L:array[0..1001] of longint;
BEGIN
Assign(fa,’daytang.inp’); reset(fa);
Assign(fz,’daytang.out’); rewrite(fz);
Readln(fa,n);
For i:=1 to n do read(fa,A[i]);
D[1]:=1; T[1]:=0;
For i:=1 to n do 
For j:=1 to i-1 do
If (A[j]D[i]) then 
Begin 
 D[i]:=D[j] + 1;
 T[i]:=j;
 End;
Vt:=1;
Max:=D[1];
For i:=1 to n do if D[i]>max then begin max:=D[i]; vt:=i; End;
While vt0 do 
 Begin 
 D[vt]:=-D[vt]; 
 Vt:=T[vt]; 
 End ;
 	 For i :=1 to n do if D[i]<0 then write(fz,A[i],’ ‘);
Close(fa); 
Close(fz);
END.
Sau đây là kết quả học sinh học sinh tự viết
Bài viết của học sinh đội tuyển
BÀI TẬP TƯƠNG TỰ CHO HỌC SINH TỰ LUYỆN
Học sinh làm bài tương tự, nâng cao, phát triển
Bài 1: Dãy con chia hết hoàn toàn dài nhất (CHHT.PAS)
Cho dãy A gồm N số nguyên dương (N ≤ 10000, A[i] ≤ 109). Một dãy con của A là một dãy thu được sau khi xóa bớt một số phần tử của A.Ví dụ với dãy A là 6,3,11,5,7,4,3,11,5,3 thì 3,7,11,3 là một dãy con của A trong khi 3,3,7 không phải là dãy con của A. Một dãy được gọi là chia hết hoàn toàn nếu với mọi i < j thì a[j] chia hết cho a[i]. 
Cho dãy A, bạn cần tìm dãy con chia hết hoàn toàn dài nhất của A.Dữ liệu vào file FDSEQ.INP 
Dòng thứ nhất ghi số N 
Dòng thứ i trong N dòng sau ghi số A[i]. 
Dữ liệu ra file FDSEQ.OUT 
Ghi duy nhất một số là độ dài của dãy con chia hết hoàn toàn dài nhất. 
(Giải thích: 1 – 3 – 6)
Bài 2: Dãy biến động nhẹ:
Dãy biến động nhẹ là dãy là dãy số trong đó hai phần tử liên tiếp a và b chênh lệch nhau không quá 5 đơn vị(|b-a|≤5).
Cho một dãy số tự nhiên. Hãy xóa khỏi dãy đã cho một số phần tử và giữ nguyên thứ tự các phần tử còn lại để được một dãy biến động nhẹ có tổng tất cả các phần tử lớn nhất.
Input: Dữ liệu vào cho trong file văn bản DAYCON.INP. Dòng đầu tiên của file có số tự nhiên N cho biết số phần tử của dãy số ban đầu với N ≤10000. N dòng tiếp theo mỗi dòng chứa một số tự nhiên của dãy ban đầu theo đúng thứ tự. Mỗi số của dãy không lớn 100.
Output: Kết quả đưa ra file văn bản có tên DAYCON.OUT. File này chứa một số duy nhất là tổng lớn nhất tìm được.
Ví dụ:
DAYCON.INP
DAYCON.OUT
9
3
8
2
3
1
2
8
3
10
32
Bài 3: Làm việc tập thể:
Trong công ti X có N nhân viên rất xuất sắc. Tuy nhiên do tất cả đều quá giỏi và quá tự tin. Cứ khi nào hai nhân viên cùng làm việc với nhau thì hiệu suất gần như bằng không. Họ tốn thời gian vào việc tranh cãi và không quyết định được công việc gì. Mỗi nhân viên có giờ làm việc là một khoảng thời gian liên tiếp từ thời điểm ai đến thời điểm bi. Giờ làm việc của mỗi nhân viên là không thể thay đổi do đặc điểm công việc mà họ đảm trách và tính kì quặc của họ. Do các khoảng thời gian này không giống nhau hoàn toàn, có thể có những lúc chỉ có một nhân viên làm việc. Lúc này thì họ làm việc rất hiệu quả. Giám đốc muốn giữ lại một số nhân viên sao cho tổng thời gian làm việc hiệu quả là lớn nhất có thể.
Dữ liệu: Vào từ tệp văn bản WORK.INP
- Dòng đầu tiên ghi N là số nhân viên (1<=n<=104)
- N dòng tiếp theo mỗi dòng ghi hai số ai và bi là thời điểm bắt đầu và kết thúc làm việc của nhân viên I (0<=ai<=bi<=109) 
Kết quả: Ghi ra tệp văn bản WORK.OUT là một số nguyên duy nhất là tổng thời gian làm việc hiệu quả lớn nhất có thể.
Ví dụ:
WORK.INP
WORK.OUT
7
100 150
0 1000
900 1000
1800 2000
900 1800
272 314
1900 2000
1900
Bài 4: Nối điểm 
Trên hai đường thẳng song song L1 và L2 người ta đánh dấu trên mỗi đường N điểm. Các điểm trên đường thẳng L1 được đánh số thứ tự từ 1 đến N từ trái qua phải, còn các điểm trên đường thẳng L2 được đánh số p1,p2,,pn cũng đánh số từ trái qua phải với p1,p2,,pn là một hoán vị của 1,2,.,n (hình vẽ dưới đây) là một. Ví dụ: với n=9:
Ta gọi số gán cho các điểm là số hiệu của chúng. Cho phép nối 2 điểm trên hai đường thẳng có cùng số hiệu.
Yêu cầu: Tìm số cách nối được nhiều cặp điểm nhất 
với điều kiện các đoạn thẳng không cắt nhau.
Dữ liệu: Vào từ file văn bản WIRES.INP
· Dòng đầu tiên chứa số nguyên dương N (N ≤ 1000)
· Dòng thứ 2 chứa các số nguyên p1,p2,,pn cách nhau bởi dấu trắng
Kết quả: Ghi ra file văn bản WIRES.OUT. 
- Dòng đầu tiên chứa số đoạn nối tìm được
- Dòng tiếp theo chứa k số hiệu của các đầu mút của các đoạn nối được chi theo thứ tự tăng dần.
WIRES.INP
WIRES.OUT
9
2 5 3 8 7 4 6 9 1
5
2 3 4 6 9
Học sinh hào hứng luyện bài
Bài 5: Supernumber.pas
Cho dãy số nguyên A[1], A[2], , A[N] khác nhau đôi một (N <105, 1<=A[i]<=N). Số A[i] được gọi là một số đặc biệt đối với dãy số trên nếu A[i] thuộc ít nhất một dãy con tăng dài nhất của A. Yêu cầu tìm một số dặc biệt của dãy A.
Dữ liệ vào từ file SPECIAN.INP : Dòng đầu là số T(1<=T<=10) là số bộ test; T nhóm dòng sau mỗi nhóm 2 dòng, dòng thứ nhất là số N, dòng thứ hai chứa N số nguyên từ số có thứ tự 1 đến số có thứ tự N.
Kết quả ghi ra file SPECIAN.OUT Gồm T dòng, mỗi dòng ghi các số đặc biệt của bộ test tương ứng, theo giá trị tăng dần.
Ví dụ
SPECIAN.INP
SPECIAN.OUT
2
7
1 2 3 7 4 5 6
5
1 4 3 2 5
6
1 2 3 4 5 6 
5
1 2 3 4 5
Bài 6: Dãy con lồi : 
Dãy giá trị nguyên A = (A1, A2, , AN) được gọi là lồi, nếu nó giảm dần từ A1 đến một Ai nào đó, rồi tăng dần tới AN. Ví dụ dãy lồi (10, 5, 4, 2, -1, 4, 6, 8, 12)
Lập trình nhập vào một dãy số nguyên, bằng cách xóa bớt một số phần tử của dãy và giữ nguyên trình tự các dãy còn lại, ta nhận được dãy con lồi dài nhất.
Dữ liệu vào trong file văn bản DAYLOM.INP có cấu trúc:
Dòng đầu tiên ghi số tự nhiên N(N< 30 000)
N dòng tiếp theo, mỗi dòng ghi một số nguyên có giá trị tuyệt đối < 30 000.
Dữ liệu ra trong file DAYLOM.OUT: chứa duy nhất một số chỉ số lượng phần tử của dãy lõm tìm được.
Ví dụ:
DAYLOM.INP
DAYLOM.OUT
5
1
2
3
1
2
4
(Chỉ bỏ phần tử thứ 5)
Bài 7: Dãy ổn định
 Trong thống kê, một dãy số gọi là ổn định khi nó là tập hợp của nhiều số nhất và tuân theo một quy luật nào đó. Trong thời điểm khủng hoảng kinh tế hiện nay, giá vàng trên thế giới biến động theo từng ngày, người ta ghi nhận lại giá vàng trong n ngày liên tiếp. Ví dụ với n=10 số liệu thu thập được như sau 9, 6, 4, 5, 8, 3, 4, 6, 1, 8
Trong dãy này, chúng ta chọn ra được một dãy con dài nhất có quy luật đi xuống rồi lại đi lên là: 9 6 4 3 4 6 6 
Dãy này gọi là dãy ổn định. Có thể có nhiều dãy con thỏa cùng quy luật
Yêu cầu: Hãy xác định điểm thấp nhất trong dãy ổn định đi xuống rồi lại đi lên lại trong n ngày của giá vàng.
Dữ liệu vào từ file ONDINH.INP
 - Dòng đầu là số n (1<=n<=50000)
 - n dòng tiếp theo, mỗi dòng là một số nguyên dương a[i] (a[i] <=100000) giá vàng của ngày thứ i
Kết quả ghi ra file ONDINH.OUT
 - Dòng đầu là số thứ tự của ngày có giá vàng thấp nhất tìm được 
 - Dòng thứ hai là giá vàng tại ngày đó.
Ví dụ : 
ONDINH.INP
ONDINH.OUT
10
9
6
4
5
8
3
4
6
1
6
6
3
Bài 8:Renting
Tại thời điểm 0 ông chủ cho thuê máy tính nhận được đơn đặt hàng thuê sử dụng máy tính của N khách hàng. Các khách hàng được đánh số từ 1 đến N. Khách hàng thứ i cần sử dụng máy từ thời điểm di đến thời điểm ci (di và ci là các số nguyên và 0 < di < ci <= 1000000000) và sẽ trả tiền sử dụng máy tính là pi (pi nguyên, 0 < pi<=10000000). Bạn cần xác định xem ông chủ cần nhận phục vụ những khách hàng nào sao cho khoảng thời gian sử dụng máy tính của hai khách hàng được nhận phục vụ bất kì không được giao nhau và tổng tiền thu được từ phục vụ là lớn nhất.
Dữ liệu vào: từ file văn bản RENTING.INP
- Dòng đầu ghi số N ( 0 < N <= 1000)
- Dòng thứ i trong N dòng tiếp theo ghi ba số di, ci, pi cách nhau bởi dấu trống, i=1,2,..,N.
Kết quả ghi ra file văn bản RENTING.OUT
 - Dòng đầu tiên ghi hai số nguyên dương theo thứ tự là số lượng khách hàng nhận phục vụ và tổng số tiền thu được.
 - Dòng tiếp theo ghi chỉ số của các khách hàng được phục vụ.
Ví dụ :	
RENTING.INP
RENTING.OUT
RENTING.INP
RENTING.OUT
3
150 500 150
1 200 100
400 800 80
2 180
2 3
4
400 821 800
200 513 500
100 325 200
600 900 600
2 1100
2 4
Bài 9: NHÀ HÀNG 
Có N vị khách đến nhà hàng, vị khách thứ i đến vào thời điểm ti và dự đinhị tiêu hết pi đồng. Cửa nhà hàng có k +1 trạng thái. Mỗi trạng thái được thể hiện bằng một số nguyên trong khoảng [0..k], trạng thái s có nghĩa là các bóng đèn trang trí ở cửa hàng có màu s, sau mỗi đơn vị thời gian trạng thái s của cửa hàng có thể thay đổi bằng trạng thái trước s là s-1 (nếu s>0),hoặc có thể thay đổi bằng trạng thái sau s là s+1 ( nếu s <k) hoặc có thể giữ nguyên trạng thái s. Vị khách thứ i sẽ vào nhà hàng nếu tại thời điểm anh ta đến, màu bóng đèn trang trí tại cửa hàng là màu ci (màu anh ta thích), nếu không anh ta sẽ bỏ đi ngay và không bao giờ quay trở lại.
 Cửa hàng bắt đầu mở cửa tại thời điểm 0 và có trạng thái 0. Hãy tính xem nhà hàng có thể thu được nhiều nhất bao nhiêu tiền.
Dữ liệu vào : file NHAHANG.INP có dạng :
 - Dòng đầu là hai số nguyên N và k (1<=N<=1000, 1<=k<=100)
 - N dòng sau mỗi dòng 3 số nguyên ti, pi, ci (0<=ti,pi<=106, 0<=ci<=k)
Kết quả : ghi ra file NHAHANG.OUT có dạng: một dòng duy nhất chứa số tiền lớn nhất có thể thu được
Ví dụ: 
NHAHANG.INP
NHAHANG.OUT
3 10
9 10 5
11 20 8
12 3 9
23
Với các bài tập cùng dạng có sự nâng cấp từ đơn giản đến rất phức tạp học sinh rất hứng thú và say mê luyện tập cũng như tìm lời giải của bài toán. Học sinh nắm được bản chất của bài toán và bớt dần cảm giác “khó” khi học về quy hoạch động.