markdown:
Tải bản đầy đủ
Công Nghệ Thông Tin
Kỹ thuật lập trình
Chuyên Đề Quy Hoạch Động CĐ2
QUY HOẠCH ĐỘNG
I. Đặt vấn đề
Các Bài toán quy hoạch động chiếm một vị trí khá quan trọng trong việc tổ chức hoạt động và sản
xuất (Nhất là việc giải quyết các bài toán tối ưu). Chính vì lẽ đó mà trong các kỳ thi học sinh giỏi
Quốc Gia và Quốc Tế chúng ta thường gặp loại toán này. Tư tưởng chủ đạo của phương pháp này dựa
trên nguyên lí tối ưu của BellMan phát biểu như sau:
“Nếu một dãy các lựa chọn là tối ưu thì mọi dãy con của nó cũng tối ưu”
Ngoài ra khi thiết kế các thuật toán quy hoạch động ta thường dùng kỹ thuật “Phân vùng để xử lí”,
Nghĩa là để giải quyết một bài toán lớn ta chia nó thành nhiều bài toán con có thể giải quyết độc lập.
Trong phương pháp quy hoạch động, việc thể hiện nguyên lí này được đẩy đến cực độ. Để giải quyết
các bài toán quy hoạch động ta có thể theo sơ đồ sau:
a. ) Lập hệ thức: Lập hệ thức biểu diễn tương quan quyết định của bước đang xử lí với các bước đã xử
lí trước đó. Hệ thức này thường là các biểu thức đệ quy do đó dễ thấy hiện tượng tràn bộ nhớ
b. ) Tổ chức Dữ liệu chương trình: Tổ chức giữ liệu tính toán dần theo từng bước. Nên tìm cách khử đệ
quy. Thông thường, trong các bài toán tin chúng ta hay gặp đòi hỏi một vài mảng lớn.
c. ) Làm tốt: Làm tốt thuật toán bằng cách thu gọn hệ thức quy hoạch động và giảm kích thước miền
nhớ.
Các thao tác tổng quát của quy hoạch động:
1. Xây dựng hàm quy hoạch động
2. Lập bảng lưu lại giá trị của hàm
3. Tính các giá trị ban đầu của bảng
4. Tính các giá trị còn lại theo kích thước tăng dần của bảng cho đến khi đạt được giá trị tối ưu cần
tìm
5. Dùng bảng lưu để truy xuất lời giải tối ưu.
II. Giải quyết vấn đề.
Vấn đề về QHĐ đã được nhiều sách, báo đề cập đến. Chúng ta có thể phân loại theo một số phần
như sau:
- Sử dụng QHĐ giải quyết bài toán Dãy con đơn điệu tăng dài nhất
- Sử dụng QHĐ giải quyết bài toán Dãy con chung dài nhất
- Sử dụng QHĐ giải quyết bài toán Chia kẹo
- Sử dụng QHĐ giải quyết bài toán Hình vuông
Về công thức cũng như code mẫu thì chúng ta có thể tham khảo DSAP của thầy Lê Minh Hoàng,
hay Tài liệu giáo khoa chuyên Tin
Ngoài ra có 1 hướng phân chia khác của thầy Lê Văn Hùng mà tôi đề cập lại sau đây để mọi
người tham khảo.
III. Tài liệu của thầy Lê Văn Hùng
Trong các lời Hướng dẫn các bài toán, chúng tôi sẽ đưa các bạn đi theo từng phần như sơ đồ giải
quyết trên. Chúng ta có thể phân loại các bài toán quy hoạch động theo nhiều cách. Để các bạn tiện
theo dõi, tôi xin phân loại theo cách lưu (tức là tổ chức chương trình) là các mảng một chiều hay nhiều
chiều.
I. Dạng Một:
Đưa Phần dạng bài toán thường gặp trong loại này đó là loại có công thức truy hồi như sau:
Mind[I]:=Min Mind[J] +Giá Trị Để tồn tại JI ;J=0. . I Hoặc là:
Maxd[I]:=MaxMaxd[J]+Giá Trị Để tồn tại JI ;J=0. . I.
Chúng ta có thể thấy rõ ràng đối với các bài toán mà chúng ta sẽ xét sau đây:
Bài Toán 1:
Bài Đổi Tiền
"Cho một ngân hàng có N loại tiền mệnh giá A[1], A[2], . . . A[N] với số lượng tiền mỗi loại
1
không giới hạn. Cần chi trả cho khách hàng một số tiền M đồng. Hãy cho biết cần bao nhiêu tiền mỗi
loại để chi trả sao cho số lượng tờ là ít nhất.
Dữ liệu vào từ File: Tien. Inp Như sau:
• Dòng đầu tiên ghi 2 số N, M. (N<=100, M<=10000)
• Dòng thứ hai ghi N Số: A[1], A[2], . . . A[N], (a[i]
Kết quả: ghi ra File: Tien. Out Như Sau:
• Dòng đầu tiên ghi số tờ cần dùng, Nếu không thể đổi được thì ghi số 0 và không cần thực hiện tiếp.
• Dòng tiếp theo ghi n số biểu hiện cho số tờ cần dùng cho mỗi loại.”
Hướng dẫn:
Chúng ta gọi Mind[I] là số lượng tờ ít nhất để trả số tiền I, Như vậy bài toán Yêu cầu chúng ta
xác định Mind[M]. Ta nhận thấy rằng để được số tiền là I thì chúng ta sẽ có các cách để tạo thành số
tiền đó khi chúng ta dùng thêm một tờ Là: I-A[K1], I-A[K2], . . . I-A[KJ], Trong đó KJ Là số Thoả
mãn mà A[KJ]
Mind[I-A[K2]]+1, . . . Mind[I-A[KJ]]+1. Có Công thức quy hoạch động như sau:
Mind[I]:=Min Mind[I-A[J]]+1, J Thoả Mãn: A[J]
Từ đó chúng ta có thủ tục quy hoạch động như sau:
Procedure Quy_Hoach_Dong;
Begin
Mind[0]:=0;
For I:=1 To M Do
Begin
Min:=Maxint;
For J:=1 To N Do
If (Mind[I-A[J]]+1
Begin
Min:=Mind[I-A[J]]+1;
Luu[I]:=J;
End;
Mind[I]:=Min;
End;
End;
Trong đó mảng Luu là mảng chứa đựng là loại tiền nào cần dùng cuối cùng để đến số tiền I.
Như vậy chúng ta có cách để tìm lại các loại tiền cần dùng bằng mảng Luu như sau:
J:=Luu[M];
I:=M;
While J<>0 Do
Begin
Write (A[J]) ;
I:=I-J;
J:=Luu[I];
End;
Như vậy chúng ta sẽ giải quyết bài toán trên một cách ngắn gọn và đơn giản. Để tăng tính tự
sáng tạo của các bạn, kể từ bài toán sau chúng tôi chỉ nêu qua các thủ tục và công thức quy hoạch
động. Nếu các bạn không giải quyết được vấn đề nhỏ đó thì có thể tham khảo phần lời giải của chúng
tôi. Tiếp sau đây là một loạt bài toán tương tự bài toán 1. mà thực chất chúng chỉ là một dạng bài cố
định, nó chỉ biến dạng đi về lời lẽ nhưng đều giống nhau về bản chất.
Bài Toán 2:
Bài Toán Nối Điểm (Wires)
"Trên Hai đuờ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ố 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ố bởi P[1], P[2], . . . P[N] cũng từ trái qua phải, trong đó P[1], P[2], . . P[N] là một hoán vị của
các số 1, 2, . . . N
2
Ta gọi các số gán cho các điểm là số hiệu của chúng. Cho phép nối hai điểm trên 2 đường thẳng có
cùng số hiệu.
Yêu cầu: Tìm cách nối được nhiều cặp điểm nhất với điều kiện các đoạn nối không được cắt nhau.
Dữ liệu: Vào từ File BaiToan2. Inp:
• Dòng Đầu tiên chứa số Nguyên Dương N (N<=1000)
• Dòng thứ hai chứa các số P[1], P[2], . . . . P[N]
Kết quả Ghi Ra File: BaiToan2. Out
• Dòng Đầu tiên chứa K là số lượng đ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 ghi theo thứ tự tăng
dần.
Ví Dụ:
WIRES. INP
WIRES. OUT
9
5
253874691
23469
Hướng dẫn:
Gọi Maxd[I] là số đoạn thẳng tối đưa của các cặp nối của các điểm t 1I. Chúng ta sẽ có công
thức quy hoạch động như sau:
Maxd[I]:=MaxMaxd[P[J]]+1;J:=0ViTri (I) Trong đó ViTri (I) Là hàm cho biết Vị trí Của I
Trong Dãy P[1], P[2], . . P[N] (Tức là I=P[X] Thì ViTri (I) =X) ;
Bằng cách phân tích hoàn toàn tương tự như bài toán 1 mà ta có công thức truy hồi như trên.
Các bước giải bài toán có thể được nói gọn trong hai thủ tục và hàm:
Funtion ViTri (I:Integer):Integer;
Var J:Integer;
Begin
For J:=1 To N Do
If P[J]=I Then
Begin
ViTri:=J;
Exit;
End;
End;
Thủ Tục Quy Hoạch động như sau:
Procedure Quy_Hoach_Dong;
Begin
Maxd[0]:=0;
For I:=1 To N Do
Begin
Max:=0;
For J:=0 To ViTri (I) Do
If Maxd[P[J]]>Max Then
Begin
Luu[I]:=J;
Max:=Maxd[P[J]];
End;
Maxd[I]:=Max;
End;
End;
Mảng Luu là mảng luu[I] lưu lại điểm trước I mà tiếp đó sẽ nối I. Chính vì điều đo chúng ta có
thể ghi ra ngược lại một cách dễ dàng. Hoàn tương tự, chúng ta có thể giải quyết tương tự cho các bài
3
toán sau:
Bài Toán 3:
Dạo Chơi Bằng Xe Buýt
“Trên một tuyến đường ở thành phố du lịch nổi tiếng X có ô tô Buýt công cộng phục vụ việc đi
lại của du khách. Bến xe buýt có ở từng Km của tuyến đường. Mỗi lần đi qua bến xe đều đỗ cho du
khác lên xuống. Mỗi bến đều có xe xuất phát từ nó, nhưng mỗi xe chỉ chạy không quá B Km kể từ bến
xuất phát của nó. Hành khách khi đi xe sẽ phải trả tiền cho độ dài đoạn đường mà họ ngồi trên xe. Cớc
phí cần trả để đi đoạn đường độ dài i là Ci (I=1, 2, . . B). Một du khách xuất phát từ một bến nào đó
muốn đi dạo L Km trên tuyến đường nói trên. Hỏi ông ta phải lên xuống xe như thế nào để tổng số tiền
phải trả cho chuyến dạo chơi bằng xe buýt là nhỏ nhất.
Dữ liệu: Vào Từ File:
Bus. Inp
• Dòng đầu tiên chứa 2 số nguyên dương B, L (B<=100, L<=10000)
• Dòng thứ hai chứa B số Nguyên dương C1, C2, . . Cn , được ghi cách nhau bởi dấu trắng
Kết quả: Ghi ra File Văn Bản:
Bus. Out
• Dòng đầu tiên ghi chi phí tìm được, và số lần xuống xe K.
• Dòng tiếp theo ghi K số là độ dài của các đoạn đường của K lần ngồi xe.”
Ví Dụ:
BUS. INP
10 15
12 21 31 40 49 58 69 79 90 101
BUS. OUT
147 3
3 6 6
"Hướng dẫn:
Gọi Mind[I] Là số tiền ít nhất cần trả khi người đó cần đi I Km. Chúng ta sẽ có công thức quy
hoạch động:
Mind[I]:=MinMind[I-J]+A[J]; J: J<=I ;
Giá trị Mind[L] là giá trị cần tính.
Bài Toán 4:
Dãy Con Tăng Cực Đại
Cho một dãy số nguyên dương A1, A2, . . An. Hãy tỉa bớt một số ít nhất các phần tử của dãy số
nguyên đó vầ giữ nguyên thứ tự các phân tử còn lại sao cho dãy số còn lại là một dãy tăng dần. Ta gọi
dãy số nguyên tăng dần còn lại sau khi đã tỉa bớt một số phần tử là dãy con của dãy đã cho.
Dữ liệu: Vào từ File BaiToan4. Inp:
• Dòng đầu tiên ghi số N là số phần tử (N<=10000)
• Dòng tiếp theo ghi N số là các số nguyên của dãy
Kết Qủa: Ghi Ra FIle: BaiToan4. Out
• Dòng đầu tiên ghi số phần tử của dãy con lớn nhất đó
• Dòng thứ hai ghi các số của dãy cần tìm.
Hướng dẫn:
Gọi Maxd[I] là số phần tử lớn nhất của dãy con dài nhất của các phần tử từ 1I. Chúng ta sẽ có
công thức quy hoạch động:
Maxd[I]:=MaxMaxd[J]+1; Với J=1. . I-1, và A[J]
Bài Toán 5:
Bố Trí Phòng Họp
Có N cuộc họp đánh số từ 1 đến N đăng ký làm việc tại một phòng hội thảo. Cuộc họp i cần
được bắt đầu tại thời điểm Ai và kết thúc tại thời điểm Bi (i=1, 2, . . . N). Hai cuộc họp bất kỳ chỉ được
nhận phục vụ nếu các khoảng thời gian làm việc tương ứng chỉ có thể được giao nhau tại đầu mút.
Hãy tìm một lịch cho phòng hội thảo để có thể phục vụ được nhiều cuộc họp nhất.
Dữ liệu: Vào được cho trong file Activity. Inp gồm:
• Dòng đầu tiên ghi giá trị N.
4
• Dòng thứ i trong số N dòng tiếp ghi 2 số nguyên Ai và Bi cách nhau ít nhất một dấu trắng.
Kết quả: Cần ghi ra file Activity. Out như sau:
• Dòng đầu tiên ghi giá trị K là số cuộc họp tối đưa có thể bố trí được
• K dòng tiếp theo, mõi dòng ghi số hiệu của cuộc họp được phục vụ theo trình tự lịch bố trí.
Giới Hạn kích thước:
• N không quá 10000
• Các giá trị Ai, Bi (i=1, 2, . . N) không quá 32000.
Ví Dụ:
Activity. Inp
Activity. Out
5 13 24 16 35 79
3 1 4 5
Hướng dẫn:
Đầu tiên ta sắp xếp các cuộc họp theo chiều tăng của dãy b
Chúng ta gọi Maxd[i] là số cuộc họp nhiều nhất có thể bố trí nếu có cuộc họp i ở trong đó. Ta
sẽ có:
Maxd[i]:=MaxMaxd[j]+1; j=0. . i-1 ;
Sau đó số cuộc họp nhiều nhất có thể bố trí là giá trị lớn nhất trong số các Maxd[i].
Chú ý: bài toán trên có thể thay đổi cách ra đề: coi một cuộc họp là một lần ghi âm chẳng hạn.
Chính vì thế thực chất bài CDWrite và bài này là một (nếu các bạn đã đọc bài CDWrite, nếu chưa thì
các bạn chỉ cần làm bài này thôi).
Bài toán 6:
Vòng Quanh Thế Giới
(Đề Thi Học Sinh Giỏi Quốc Gia 2000-2001 - Bảng A)
Trên tuyến đường của xe chở khách du lịch vòng quanh thế giới xuất phát từ bến X có N khách
sạn đánh số từ 1 đến N theo thứ tự xuất hiện trên tuyến đường, trong đó khách sạn N là địa điểm cuối
cùng của tuyến đường mà tại đó xế bắt buộc phải dừng. Khách sạn I cách địa điểm xuất phát Ai Km
(I=1, 2, . . N) ;A1
Để đảm bảo sức khoẻ cho khách hàng, theo tính toán của các nhà chuyên môn, sau khi đã chạy
được P (Km) xe nên dừng lại cho khách nghỉ ở khách sạn. Vì thế, nếu xe dừng lại cho khách nghỉ ở
khách sạn sau khi đã đi được Q (Km) thì lái xe phải trả một lượng phạt là: (q-p) * (q-p). Ví Dụ:
Với N=4, P=300, A1=250, A2=310, A3=550, A4=590. Xe bắt Buộc phải dừng lại ở khách sạn 4
là địa điểm cuối cùng của hành trình. Nếu trên đường đi lái xe chỉ dừng lại tại khách sạn thứ 2 thì
lượng phạt phải trả là:
(310-300) * (310-300) + ((590-310) -300) * ((590-310) -300) = 500
Yêu cầu: Hãy xác định xem trên tuyến đường đến khách sạn N, xe cần dừng lại nghỉ ở những khách
sạn nào để tổng lượng phạt mà lái xe phải trả là nhỏ nhất.
Dữ liệu: Vào từ File văn bản có tên Bai5. Inp:
• Dòng đầu tiên chứa số nguyên dương N (N<=10000) ;
• Dòng thứ hai chứa số nguyên dương P (P<=500) ;
• Dòng thứ ba chứa các số nguyên dương A1, A2, A3, . . An (hai số liên tiếp cách nhau ít nhất
bởi 1 dấu cách) (Ai<=2000000, i=1, 2, . . N)
Kết quả: Ghi ra File Văn Bản Bai5. Out:
• Dòng đầu tiên ghi Z là lượng phạt mà lái xe phải trả ;
• Dòng thứ hai ghi K là tổng sô khách sạn mà lái xe cần dừng lại cho khách nghỉ;
• Dòng thứ ba chỉ chứa chỉ số của K khách sạn mà xe dừng lại cho khách nghỉ (Trong đó nhất
thiết phải có khách sạn thứ N)
Ví Dụ:
BAI5. INP
BAI5. OUT
5
4 300 250 310 550 590
500 2 2 4
Hướng dẫn:
Gọi Mind[i] là lượng phạt ít nhất nếu người lái xe dừng lại địa điểm i. Chúng ta sẽ có công thức
truy hồi:
Mind[i]:=MinMind[j]+sqr (a[i]-a[j]-p) ; j=1, . . i-1
Tuy nhiên bài toán này chưa phải là đã được giải quyết. Bởi vì nó còn quá nhiều vấn đề cần giải quyết
khác:
Lượng phạt có thể rất lớn, vượt quá longint mà nếu chứa trong real thì sẽ không thể lưu được
mảng có 10000 phần tử. Chính vì thế chúng ta cần giải quyết tốt Dữ liệu bài toán này.
Nếu N=10000 thì chương trình sẽ phải chạy: (9999+1) *9999/2. Tức là rất lâu.
Chính vì thế các bạn cần phải hoàn thành một cách đúng đắn các điều kiện trên.
Hoàn toàn biến dạng về ngôn ngữ diễn tả bài toán, nhưng có rất nhiều bài toán đã ẩn rõ hơn về
thuật toán này, chúng ta xét các bài toán sau:
Bài toán 7:
Car
Cho một đoàn xe hộ tống có n chiếc đi trên một đường một chiều đã được bố trí theo thứ tự từ
1 đến n. Mỗi một xe trong đoàn tren thì có một vận tốc là V và trọng lượng là W.
Khi đi qua một chiếc cầu có trọng tải không quá là P thì phải chia đoàn xe trên thành các nhóm
sao cho tổng trọng lượng của mỗi một nhóm là không quá P. Thêm vào đó nữa là các nhóm phải đi
tuần tự. Nghĩa là nhóm thứ i chỉ đi được khi mà toàn bộ xe của nhóm thứ i-1 đã qua cầu.
Vận tốc đi của mỗi một nhóm là hoàn toàn khác nhau và phụ thuộc vào xe có tốc độ chậm nhất
có thể được.
Dữ liệu: vào từ file Car. Inp gồm:
• Dòng đầu tiên ghi 3 số n (n 1000) và P, L thể hiện cho số xe, trọng lượng tối đưa của cầu và L
là độ dài của cầu
• N dòng kế tiếp, mỗi dòng gồm 2 số W và V thể hiện cho trọng lượng và vận tốc của xe
Kết quả: ra file Car. Out như sau:
• Dòng đầu tiên là tổng thời gian nhỏ nhất để đoàn xe qua cầu
• Dòng kế tiếp gồm các số X1, X2, . . . Xk thể hiện: Nhóm 1là từ 1. . X1, nhóm 2 là từ X1+1. .
X2, . . .
Ví Dụ:
Car. inp
Car. out
10 100 100
25
40 25
1 3 6 8 10
50 20
70 10
12 50
9 70
49 30
38 25
27 50
19 70
Hướng dẫn:
Gọi Mind[i] là tổng thời gian nhỏ nhất để cho đoàn xe có số hiệu từ 1 đến i qua cầu. Ta có công
thức truy hồi:
Mind[i]:=MinMind[j]+Time (j, i) ; j = 1, . . i-1
Với time (j, i) là thời gian để cho đoàn xe gồm từ chiếc thứ j cho tới chiếc thứ i qua cầu cùng
một lúc. (có nghĩa là nếu vượt quá trọng tải thì Time (j, i) =. )
6
Bài toán 8:
Khuyến Mại
Vào này No-en, N cửa hàng trong thành phố tặng quà cho các khách hàng. Các cửa hàng có tên
1. . N, N<=100. Một lần tặng quà được thể hiện bằng ba số nguyên dương X, Y, Z với ý nghĩa cửa hàng
X tại thời điểm Y tặng món quà giá trị Z. Với mỗi lần tặng quà, người muốn nhận phải có mặt không
muộn hơn thời điểm phát quà và các cửa hàng đều rất chu đáo đến mức thời gian nhận quà xem như
bằng 0. Không có hai lần tặng quà nào diễn ra tại một thời điểm.
An muốn tận dụng ngày đó để hy vọng có nhiều món quà hấp dẫn. An xuất phát từ nhà tại thời
điểm 0 và phải quay về đến nhà không muộn hơn thời điểm M. Hãy lập cho An kế hoạch đi nhận quà
sao cho tổng số giá trị thu được là lớn nhất.
An biết được thời gian cần đi từ nhà đến từng cửa hàng và giữa các cửa hàng cũng như chi phí trên
từng chặng đường tương ứng. Thời gian và chi phí trên mỗi chặng đường là tối ưu, không nhất thiết
như nhau theo hai chiều. Trong khi đi từ một cửa hàng này đến một cửa hàng khác, An không ghé thăm
qua cửa hàng nào khác. Tổng giá trị An thu được bằng tổng giá trị quà tặng được trừ đi tổng chi phí
mà An phải trả trên các chặng đường từ nhà đến cửa hàng đầu tiên, từ đó lần lượt đến các cửa hàng
khác và quay về đến nhà.
Dữ liệu: vào được cho bởi file văn bản: KM. INP trong đó dòng thứ nhất ghi ba số N, M, K mà K là
số lần phát quà, N<=100, M<=60000, K <= 5000. Tiếp theo là K dòng, dòng thứ i trong K dòng này ghi
ba số X, Y, Z thể hiện một lần phát quà và ta quy ước gọi lần phát quà thứ i. Sau đó là N + 1 dòng,
dòng thứ i ghi N + 1 số mà số thứ j là thời gian đi từ cửa hàng i đến cửa hàng j. Cuối cùng là N + 1
dòng, dòng thứ i trong n + 1 dòng ghi N + 1 số , mà số thứ j là chi phí để đi từ cửa hàng thứ i đến cửa
hàng thứ j. Nhà của An xem như cửa hàng thứ N + 1. Với mọi cửa hàng i, thời gian và chi phí từ i đến i
là bằng 0. Tổng giá trị lớn nhất AN thu được không quá 2 tỷ.
Kết quả: ghi ra file: KM. OUT như sau:
• Dòng thứ nhất ghi số S là tổng giá trị An thu được
• Tiếp theo là một số dòng, mỗi dòng ghi số hiệu một lần nhận qùa mà theo trình tự đó An lần lợt
đến nhận
Ví Dụ:
KM. INP
2 13 5
KM. OUT
52 1 3 4 5
1 2 10
2 3 20
1 4 25
1 5 10
2 10 10
022
203
110
011
101
110
Hướng dẫn:
Các cửa hàng này sắp xếp trên một con đường thẳng theo trật tự tăng dần của thời gian khuyến
mại. Nếu cửa hàng nào có nhiều lần khuyến mại thì chúng ta coi nó như một cửa hàng khác mới hơn.
Bài toán sẽ trở thành một bài toán mới:
Trên đường đi trên con đường đó thì chúng ta cần ghé thăm những cửa hàng nào để số tiền
khuyến mại là lớn nhất.
Gọi Maxd[i] là số tiền khuyến mại lớn nhất nếu ta đến nhận khuyến mại tại thời điểm i (bởi vì
tại một thời điểm thì chỉ có một cửa hàng khuyến mại, nên coi nó như một ánh xạ duy nhất). Nếu
7
không nhận khuyến mại tại thời điểm i thì số tiền sẽ là 0. và ta sẽ tìm theo công thức:
Maxd[i]:=Maxmaxd[j]+tiền nhận được từ i tới j - tiền mất đi; j=1, . . i-1 với điều kiện tại thời
điểm j thì phải có một khuyến mại nào đó maxMaxd[i] ;i=1, . . k chính là số tiền cần lấy.
Bài Toán 9:
Xây tháp
Có N khối đá hình hộp chữ nhật. Người ta muốn xây một cái tháp bằng cách chồng các khối đá
này lên nhau. Để đảm bảo an toàn, các khối đá được đặt theo nguyên tắc:
+ chiều cao của mỗi khối là kích thước nhỏ nhất trong ba kích thước,
+ các mép của các khối được đặt song song với nhau sao cho không có phần nào của khối nằm
trên bị chìa ra ngoài so với khối nằm dưới.
Hãy tìm phương án xây dựng để tháp đạt được độ cao nhất.
Dữ liệu vào được cho trong file Tower. INP gồm:
+ Dòng đầu là số N,
+ N dòng sau, mỗi dòng ghi 3 số nguyên dương là kích thước một khối đá. Các khối đá được
đánh số từ 1 theo trình tự xuất hiện trong file.
Kết quả ghi ra file Tower. OUT theo quy cách:
+ dòng thứ nhất ghi số M là số lượng khối đá dùng xây tháp,
+ M dòng tiếp theo ghi các khối xếp từ đáy tháp lên đỉnh, mỗi dòng gồm 4 số theo thứ tự: K A
B C, trong đó K là số hiệu khối đá, A là kích thước chọn làm đáy nhỏ, B là kích thước chọn làm đáy
lớn, C là kích thước chọn làm chiều cao.
Các số trên cùng một dòng trong các file được ghi cách nhau ít nhất một dấu trắng. Giới hạn số
khối đá không quá 5000 và các kích thước của các khối đá không quá 255.
Ví dụ:
Tower. INP
Tower. OUT
9
4
7 5 5
1 5 75
4 4 8
9 5 5
1 1 5
55 5 5
4 2 2
14 2 4 2
5 1 5
4 2 7
2 9 2
1 3 3
5 5 5
Hướng dẫn:
Chúng ta thấy rằng một hình nếu ở dưới một hình khác thì các kích thước ngang và dọc đều lớn
hơn hoặc bằng kích thước trên. Chúng ta không mất tổng quát, quy định chiều của các tháp theo một
chiều nhất định (ví dụ: dài là độ dài có kích thước lớn nhất tròn ba kích thước, rộng là lớn thứ hai và
cuối cùng là cao).
Sắp xếp các tháp theo chiều giảm dần của diện tích. Sau đó thì Maxd[i] là độ cao nhất nếu xếp
tháp thứ i trên cùng (trong dãy sau khi đã sắp xếp).
Maxd[i]:=maxmaxd[j]+cao[i] ; với j =1, . . i-1 và rộng [j]>=rộng[i], dài[j]>=dài[i];
Sau đó ta lấy giá trị lớn nhất của các Maxd[i] chính là độ cao của tháp cần xếp.
Bài toán 10:
RenTing
Tại một thời điểm 0, ông chủ một máy tính năng suất cao nhận được đơn đặt hàng thuê sử dụng
máy của N khách hàng. Các khách hàng I cần sử dụng máy từ thời điểm Di đến thời điểm Ci (Di, Ci là
các số nguyên và 0
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
của 2 khách hàng được nhận phục vụ bất kỳ không đuợc giao nhau, đồng thời tổng số tiền thu được là
8
nhiều nhất .
Dữ liệu: Vào Từ File vân bản RENTING. INP:
• Dòng đầu tiên ghi số N (0
• Dòng thứ I+1 trong số n dòng tiếp theo ghi 3 số Di, Ci, Pi cách nhau bởi dấu cách (I=1, . . 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 tiền thu được từ việc phục vụ họ
• Dòng tiếp theo ghi chỉ số của các khách hàng được nhận phục vụ.
Ví Dụ:
RENTING. INP
RENTING. OUT
3 150 500 150 1 200 100 400 800 80
325 200 600 900 600 2 1100 2 4
RENTING. INP
2 180 2 3
RENTING. OUT
4 400 821 800 200 513 500 100
Hướng dẫn:
Sắp xếp theo thứ tự tăng dần của Di. Sau đó gọi Maxd[i]laf tổng số tiền nhận được khi phục vụ
người thứ i (trong dãy sau khi đã sắp). Lúc đó ta sẽ có:
Maxd[i]:=MaxMaxd[j]+Pi; j=1. . i-1; và Di>=Cj;
Vậy số tiền lớn nhất là = Max maxd[i];i=1. . n.
II. Dạng Hai:
Các Bài toán dạng này thường có chương trình giống thuật toán Ford-Bellman.
Repeat
Ok:=True ;
IF tìm được Mind[i] nào thoả mãn Mind[i]>Mind[j]+giá trị từ j đến i Then
Begin
Ok:=False ;
Mind[i]:=Mind[j]+giá trị từ j đến i
End ;
Until Ok ;
Tương tự cho Maxd [i]. Với quá trình j đến i là một quá trình thoả mãn điều kiện của bài toán.
Bài Toán 11:
Apower
Chúng ta định nghĩa hàm AR (m, n), với m, n là những số tự nhiên (0
số tự nhiên sao cho khi chúng ta biểu diễn n bằng các phép toán: +, -, *, / và các phép toán ghép số, thì
số nhỏ nhất cần thiết các chữ số n để được Kết quả là số m là giá trị của hàm AR (m, n).
Để cho các bạn dễ hiểu chúng ta xét hàm AR (42, 2) =4 vì ta có cách biểu diễn:
2*22-2=42 hay chúng ta có AR (22, 1) = 4 vì:
11* (1+1) =22.
Bài toán đặt ra cho chúng ta là hãy tìm AR (m, n), với m, n biết trước.
Dữ liệu:
Vào từ file văn bản Apower. Inp gồm nhiều bộ số m, n. Mỗi dòng viết một bộ số.
Kết quả:
Ghi ra file văn bản Apower. Out gồm nhiều dòng, mỗi dòng ứng với kết qủa của mỗi
dòng của file input.
Ví Dụ:
APOWER. INP
APOWER. OUT
42 2 22 1 6 3
4 4 3
Hướng dẫn:
Chúng ta sẽ gọi Ar[m, n] là giá trị hàm Ar (m, n). Ta có thủ tục quy hoạch động:
Fillchar (Ar, Sizeof (Ar), Maxint) ;
Ar[0]:=2 ;
9
Ar[n]:=1;
RePeat
Ok:= True ;
For i:=1 to (m+1) *n do
if Ar[m, i]<>maxint then
For j:=1 to (m+1) *n do
Begin
If (Ar[i]+Ar[j]
Begin
Ok:=false ;
Ar[i+j]:=ar[i]+ar[j];
End ;
If (Ar[i]+Ar[j]
j) then
Begin
Ar[i-j]:=Ar[i]+Ar[j];
Ok:=False ;
End ;
If (Ar[i]+Ar[j]
Begin
Ok:=False ;
Ar[i*j]:=Ar[i]+Ar[j];
End ;
If (I mod j = 0) and (Ar[i]+Ar[j]
Begin
Ok:=False ;
Ar[i div j]:=Ar[i]+Ar[j];
End ;
End ;
Until OK ;
Nhưng để tránh những trường hợp đặc biệt như:333 với 3 thì Ar (333, 3) =3. Cho nên trước hết
chúng ta tính Ar[3. . 3, 3]:=số số 3 có trong nó. Rồi sau đó thì ta sẽ dùng thủ tục trên.
Bài Toán 12:
Giá Trị Biểu Thức
Giả thiết X, Y là hai số nguyên dương. Kí hiệu Sx là tổng các chữ số trong dạng biểu diễn cơ số 10
của X, Dmax_y và Dmin_y là chữ số lớn nhất và nhỏ nhất trong dạng biểu điễn cơ số 10 của Y. Phép
tính hai ngôi # với các toán hạng nguyên dương X, Y được định nghĩa như sau:
(X#Y) =Sx*Smax_y+Dmin_y
Ví Dụ:
(30#9) =3*9+9=36 hay (9#30) =9*3+0=27
Với X cho trước, một số biểu thức hợp lệ là:
(X#X) và ((X#X) #X) và (X# (X#X) # (X#X) #X). . .
Ký hiệu Kết quả biểu thức là K. Cho X và K (0
phép # để từ đó có thể xây dựng biểu thức thuộc dạng đang xét với X cho Kết quả K và biểu thức
biểu diễn của biểu thức.
Dữ liệu: vào từ file văn bản Bai16. Inp dòng thứ nhất chứa số X, dòng thứ hai chứa K
Kết quả: Ghi ra file văn bản Bai16. Out: dòng thứ nhất chứa số m, dòng thứ hai chứa biểu thức.
Ví Dụ:
718
BAI16. INP
81
BAI16. OUT
3 ((718# (718#718) ) #718)
10
Hướng dẫn:
Ta thấy 0
Nên 1<=X*X<=9*9*9+9=738 ; Vậy giá trị của một biểu thức hợp lệ bất kỳ phải nằm trong đoạn [1,
738], đây chính là cốt lõi lời giải cho bài toán. Nếu K nằm ngoài khoảng này thì chắc chắn vô nghiệm.
Xét biểu thức X#X có 1 dấu #, dễ thấy có 3 cách mở rộng biểu thức 1 dấu # này là:
- X# (X#X) ; (X#X) #X ; (X#X) # (X#X) ;
Giả sử B là một biểu thức tạo bởi X và n dấu # thế thì có 3 cách mở rộng biểu thức này:
• X#B (n+1 dấu #) ; B#X (n +1 dấu #) ; B#B (2 * n+1 dấu #).
Ta lập mảng một chiều Mind[1. . 738] trong đó Mind[i] cho biết số phép # ít nhất để tạo từ X. Ta có
các bước giải quyết bài toán:
• Bước 1: Khởi tạo mảng A[1. . 738]:=0 đánh dấu các giá trị đã tạo được từ biểu thức ó X và #,
Khởi tạo mảng Mind nhận các giá trị Maxint.
• Bước 2: Tìm T=X#X ; A[T]:=1 ; Mind[T]:=1 ;
• Bước 3: Thực hiện cho đến khi mảng Mind không bị thay đổi:
For i:=1 to 738 do
If A[i]=1 then
Begin
T:=X#i;
If Mind[T]>Mind[i]+1 then begin Mind[T]:=Mind[i]+1 ;A[T]:=1 ; end ;
T:=i#X ;
If Mind[T]>Mind[i]+1 then begin Mind[T]:=Mind[i]+1 ;A[T]:=1 ; end ;
T:=i#i ;
If Mind[T]>2*Mind[i]+1 then
begin
Mind[T]:=2*Mind[i]+1 ;A[T]:=1 ;
end ;
End ;
Bài Toán 13:
Đọc Đĩa
(Đề Thi Học Sinh Giỏi Quốc Gia 2001-2002 - Bảng B)
Các kĩ sư của một công ti tin học đang thử nghiệm chế tạo đĩa từ có dung lượng thông tin cực
lớn. Đĩa có nhiều đường ghi và khoảng cách giữa 2 đường ghi liên tiếp nhau là rất nhỏ. Các đường ghi
được đánh số từ 0 đến N, từ ngoài vào trong. Đối với loại đĩa này, việc dịch chuyển đầu đọc từ một
đường ghi sang một đường ghi kế tiếp là rất khó đảm bảo độ chính xác cao cho các chuyển động cơ
học trên khoảng cách quá bé do không có đủ thời gian để khởi động và phanh đầu đọc.
Người ta thiết kế mạch điều khiển với 2 lệnh: Lệnh T và lệnh L.
Lệnh T- đưa đầu đọc tiến lên phía trước P đường ghi (P>0). Ví dụ đầu đọc đang ở đường ghi K.
Sau khi thực hiện lệnh T thì nó chuyển tới đường ghi số K +P. Lệnh T không áp dụng được khi
K+P>N.
Lệnh L đưa đầu đọc lùi Q đường ghi (Q>0). Nếu đầu đọc đang ở đường ghi K, sau khi thực
hiện lệnh L thì đầu đọc sẽ chuyển tới đường ghi K-Q. Lệnh L không áp dụng khi K-Q<0. Để di chuyển
đầu đọc từ đường ghi U tới đường ghi V có thể phải áp dụng một dãy các lệnh T, L. Dãy m lệnh T (L)
liên tiếp nhau được viết gọn dạng Tm (Lm), trong đó m - số nguyên dương, m>=1.
Yêu cầu: Với N, P, Q cho trước (N<=20000, 0
đọc từ đường ghi U tới đường ghi V (0<=U, V<=N) hoặc cho biết không tồn tại dãy câu lệnh như vậy.
Dữ liệu: Vào từ file văn bản DISK. INP gồm L dòng 5 số nguyên N, P, Q, U, V, các số trên một dòng
cách nhau ít nhất một dấu cách.
Kết quả: Đưa ra file văn bản DISK. OUT:
• Dòng đầu tiên là số nguyên K - số câu lệnh cần thực hiện, K=-1 nếu không tồn tại cách đưa đầu
11
•
đọc về đường ghi V.
Dòng thứ 2 chứa dãy câu lệnh cần thực hiện, trước tên lệnh T (L) phải có một dấu cách.
Ví Dụ:
DISK. INP
10 5 3 7 6
DISK. OUT
3 L2 T1
Hướng dẫn:
Chúng ta có Mind[i] là số lần thực hiện các lệnh chuyển đĩa ít nhất khi chuyển từ ƯU đến i. ta
thực hiện như sau:
Khởi tạo toàn bộ Mind[i] = maxint ;
Mind[ưu]:=0 ;
Repeat
Ok:=True ;
For i:=0 to n do
if mind[i]<>maxint then
Begin
If (i-q>0) and (mind[i]+1
begin
mind[i-q]:=mind[i]+1;
luu[i-q]:=-q ;
ok:=false ;
end ;
If (i+p<=n) and (mind[i]+1
Begin
Mind[i+p]:=mind[i]+1 ;
Ok:=False ;
Luu[i+p]:=p;
End ;
End ;
Until Ok ;
Ta dùng mảng luu[i] để khi lần ngược trở nên dễ dàng hơn.
Bài Toán 14:
Busways
Một hệ thống các xe buýt có nhiệm vụ chuyên chở hành khách đi lại giữa một số ga sao cho
đảm bảo tính liên thông hai chiều giữa các ga này. Hệ thống bao gồm một số tuyến đường, mỗi tuyến
đường bao gồm một số ga khác nhau theo thứ tự mà xe buýt đi qua. Xe buýt thuộc tuyến đường nào
chỉ chạy trên tuyến đường đó, lần lợt qua các ga thuộc tuyến cho đến hết, sau đó lại quay lại chạy theo
hướng ngược lại. Có thể có một số ga chung cho một số tuyến đường. Một hành khách muốn đi từ ga
đầu đến ga cuối, có thể đi trên một tuyến hoặc phải chuyển tuyến một số ga cuối sao cho số lần phải
chuyển tuyến là ít nhất. Nếu tồn tại nhiều phương án như vậy, hãy tìm phương án đi qua ít nhất.
Dữ liệu: vào trong file: Busways. inp gồm:
• Dòng đầu tiên là số tuyến đường
• Các dòng tiếp theo, mỗi dòng mô tả một tuyến đường, gồm một chuỗi ký tự viết liền nhau, mỗi
kí tự mô tả một tên ga theo đúng thứ tự của các ga trên tuyến (chú ý các ga trên cùng một
tuyến là khác nhau, nhưng các ga trên các tuyến khác nhau có thể trùng nhau, tên ga là một ký
tự bất kì hiển thị được trong bảng mã ASCII)
• Dòng tiếp theo là số hành trình cần tìm
• Các dòng tiếp theo, mỗi dòng môt tả một hành trình cần tìm, gồm một cặp ký tự viết liền nhau,
12
xác định tên ga đầu và tên ga cuối.
Giả thiết rằng Dữ liệu cho là hợp lệ, không cần kiểm tra. Giới hạn kích thước 100 cho số các tuyến
đường, và 50 cho số các ga trên một tuyến đường.
Kết quả:
Ghi ra file BusWays. Out:
Trong đó hành trình được viết trên một dòng, gồm các ký tự biểu diễn tên ga viết theo thứ tự
được đi. Các tên ga này được viết thành từng nhóm theo tuyến đường: nếu thuộc cùng một tuyến
đường thì viết liền nhau, nếu sàn tuyến đường khác thì viết cách nhau một dấu trắng, tên ga chung
được viết lặp lại.
Ví Dụ:
BUSWAYS. INP
3 ABC DBE GAEH 2 HC GB
BUSWAYS. OUT
HEA ABC GA AB
Hướng dẫn:
Đầu tiên chúng ta coi một ga là một đỉnh có số hiệu là vị trí nó trong bảng mã Ascii. Sau đó ta
tạo một đồ thị có các cung mà nếu các ga trong một tuyến thì có độ dài 1 nếu trái tuyến thì độ dài
1000. Sau đó dùng thuật giải giả Ford-Bellman (giống các bài toán trên). để tìm đường đi ngắn nhất.
Hoàn toàn tương tự các bạn có thể giải quyết bài toán sau:
(bài 5 - Phần nâng cao, bài tập lập trình pascal - Nguyễn Xuân My)
Bài toán phụ:
Bài toán 15:
“ Có M tuyến xe buýt, M<=20. Mỗi tuyến xe được cho bởi dãy tên các bến liên tiếp từ đầu đến
cuối của tuyến đó, mọi tuyến xe đều đi được hai chiều. Tên bến là các số nguyên dương. Các tuyến xe
có thể có các bến chung. Nếu đi từ một bến đến một bến tiếp theo trên cùng tuyến thì mất 1 đồng còn
nếu đang đi trên một tuyến mà chuyển sang tuyến khác tại cùng một bến để đi đến bến trên tuyến khác
đó thì mất thêm 3 đồng. Cho tên hai bến I và J. Hãy tìm một hành trình đi từ I đến J sao cho:
1. Chi phí là ít nhất
2. Số lần chuyển tuyến ít nhất.
Dữ liệu vào được cho bởi file INP. B5 trong đó dòng thứ nhất ghi hai số nguyên dương I, J; trong
các dòng tiếp theo (không quá 20 dòng), mỗi dòng ghi không quá 20 số nguyên dương khác nhau từng
đôi thể hiện một tuyến xe. Các tuyến xe nhận số hiệu từ 1, 2, 3, . . . kể từ trên xuống dưới.
Kết quả ghi ra file OUT. B5 như sau:
Câu 1: dòng thứ nhất ghi chi phí, dòng thứ hai ghi hành trình từ I đến J bằng cách viết các bến liên tiếp
trên hành trình, mỗi bến ghi như sau: tên bến/số hiệu tuyến. Ví dụ bến 25 trên tuyến 6 sẽ ghi 25/6.
Câu 2: dòng thứ ba ghi số lượng tuyến xe, dòng thứ t ghi hành trình từ I đến J tương tự như câu 1.”
III. Dạng ba: Lưu dữ Dữ liệu và cách tiết kiệm biến:
Bài toán 16:
Palindrome
(Đề thi Quốc Tế năm 2000)
Palindrome là một xâu đối xứng tức là một xâu mà đọc từ trái sang phải cũng như đọc từ phải
sang trái. Bạn cần viết một chương trình với một xâu cho trước, xác định số ít nhất các kí tự cần chèn
vào xâu để nhận được một palindrome .
Ví dụ: Bằng cách chèn 2 kí tự vào xâu ‘ Ab3d ‘ ta nhận được một palindrome. Tuy nhiên nếu chèn ít
hơn 2 kí tự thì không thể tạo được một palindrome.
Dữ liệu:
Vào file input: PALIN.IN
• Dòng thứ nhất gồm một số nguyên là độ dài N của xâu, 3<=N<=5000.
• Dòng thứ hai gồm một xâu có độ dài N. xâu gồm các kí tự là các chữ cái hoa A. . Z, các chữ cái
thường: a. . z và các chữ số thập phân 0. . 9, các chữ cái hoa và thường xem như khác nhau.
Kết quả: file output: PALIN.OUT
• Dòng một là số lượng các kí tự cần chèn vào
13
Ví dụ:
PALIN. IN
PALIN. OUT
5 Ab3bd
2
Hướng dẫn:
Gọi xâu Dữ liệu vào là s. Ta sẽ tìm chiều dài của dãy con đối xứng cực đại trích từ s là s1. Khi
đó số ký tự cần thêm sẽ là =Length (s) -Length (s1). Dãy con ở đây được hiểu là dãy thu được từ s
bằng cách xoá đi một số phần tử trong s.
Gọi Maxd[i, j] là chiều dài của dãy con dài nhất thu được từ đoạn s[i. . j]. Ta sẽ có:
Nếu S[i]=S[j] thì Maxd[i, j]=Maxd[i+1, j-1]+2 ;
Nếu S[i]<>S[j] thì Maxd[i, j]:=Max Maxd[i, j-1], Maxd[i+1, j]
Tức là chúng ta cần tính Maxd[1, n]. Nhưng với Dữ liệu N<=5000 thì điều này trở thành hoang
tưởng. Ta có thể nhìn nhận rõ hơn thì thấy rằng chúng ta có thể hoàn toàn tiết kiệm được rất nhiều bộ
nhớ:
Gọi Luu[0. . N+1] là mảng cập nhật các bước thực hiện. Tại bước cập nhật thứ j ta có
Luu[j]:=Maxd[i, j].
Ta sẽ có lại bảng truy hồi như sau:
Nếu S[i]=S[j] thì Luu[i]:=Luu[i+1] cũ + 2
Nếu S[i]<>S[j] thì Luu[i]:=Max Luu[i] cũ, Luu[i+1] cũ
Ta tính từ dưới lên, tức là tính Luu[i] với i:=n. . 1 thì D[i+1] cũ sẽ bị ghi đè. Và lúc đó dùng tg
để lưu lại.
Thủ tục quy hoạch động như sau:
procedure qhd;
begin
for j:=1 to n do
begin
luu[j]:=1;
tg:=0;
for i:=j-1 downto 1 do
begin
t:=luu[i];
if s[i]=s[j] then luu[i]:=tg+2 else
Luu[i]:=max (Luu[i], Luu[i+1]) ;
tg:=t;
end;
end;
end;
Như vậy số ký tự cần thêm vào: N-Luu[1].
Bài toán 17 :
Sign
Giám đốc một công ti trách nhiệm hữu hạn muốn xin chữ kí của ông kiến trúc sư trưởng thành
phố phê duyệt dự án xây dựng trụ sở làm việc của công ty. ông kiến trúc sư trởng chỉ ký vào giấy phép
khi bà thư ký của ông ta đã ký duyệt vào giấy phép. Bà thư kí làm việc tại tầng thứ M của một toà nhà
được đánh số từ 1 đến M, từ thấp lên cao. Mỗi tầng của toà nhà có N phòng được đánh số từ 1 đến N,
từ trái sang phải. Trong mỗi phòng chỉ có 1 nhân viên làm việc. Giấy phép của bà thư kí ký duyệt khi
có ít nhất một nhân viên ở mỗi tầng của toà nhà đã kí xác nhận. Một nhân viên bất kỳ có thể chỉ kí xác
nhận vào giấy phép khi có ít nhất một trong các điều kiện sau được thoả mãn:
• Nhân viên đó làm việc ở tầng 1
• Giấy phép đã được kí xác nhận bởi một nhân viên làm việc ở phòng liền kề (hai phòng được gọi
là liền kề khi chỉ số phòng sai khác nhau một đơn vị)
• Giấy phép được ký xác nhận bởi nhân viên làm việc ở phòng cùng số phòng ở tầng dưới.
14
Mỗi nhân viên khi đã kí xác nhận đều phải có một chi phí nhất định. hãy chỉ ra cách xin chữ kí sao cho
xin được chữ kí của ông kiến trúc sư trưởng mà chi phí bỏ ra là ít nhất.
Dữ liệu:
Vào từ file Sign. Inp như sau:
• Dòng đầu tiên ghi M, N (1 <= M <=100 ; 1<=N<=500) ;
• Dòng thứ i trong số M dòng ghi N số biểu diễn chi phí khi phải kí ở phòng đó. (Cij<=109)
(Tổng chi phí cần trả là ít hơn 109)
Kết quả:
Ghi ra file: Sign. Out như sau:
• Dòng đầu tiên ghi hai số F, K theo thứ tự là chi phí cần trả và số lượng phòng cần đi qua
• Các dòng tiếp theo chỉ ghi số của các phòng theo thứ tự cần đi qua, mỗi chỉ số ghi trên một
dòng.
Ví Dụ:
Sign. Inp
3 4 10 10 1 10 2 2 2 10 1 10 10 10
Sign. Out
853321
Hướng dẫn:
Bài Toán thực chất là Bài Toán con gián đi từ một ô nào đó trên ô trên cùng để đến một ô ở
hàng cuối với chi phí đi là nhỏ nhất.
Gọi Mind[i, j] là số tiền ít nhất để đi đến ô (i, j).
Ta có:
Mind[i, j]:=Min (mind[i-1, j];Mind[i, j-1];Mind[i, j+1]) +C[i, j];
Nhưng ta thấy rằng trong chương trình này thì ta có phải lưu dưới dạng một mảng [100*500]
Of longint , thêm vào đó để lưu lại đường đi thì ta phải dùng các biến lưu toạ độ, mà như thế thì Dữ
liệu sẽ không đáp ứng được.
Sau đây là cách làm chương trình đáp ứng được điều ấy:
Type
tang
tru
tr
= Array [0. . maxN] of Longint ;
= Array [0. . maxN] of Integer ;
= Array [0. . maxM] of ^tru ;
Var
C, Mind
: Array [0. . maxM] of ^tang ;
try, trx
: tr ;
Procedure Quy Hoạch Động ;
Begin
new (d[1]) ; new (trx[1]) ; new (try[1]) ;
Fillchar (trx[1]^, sizeof (trx[1]^), 0) ;
Fillchar (try[1]^, sizeof (try[1]^), 0) ;
For i:= 1 to N do Mind[1]^[i]:= c[1]^[i] ;
For ưu:= 2 to M do
Begin
new (Mind[u]) ; new (trx[u]) ; new (try[u]) ;
Fillchar (trx[u]^, sizeof (trx[u]^), 0) ;
Fillchar (try[u]^, sizeof (try[u]^), 0) ;
For i:= 1 to N do
Begin
Mind[u]^[i]:= Mind[u-1]^[i]+c[u]^[i];
trx[u]^[i]:= u-1 ;try[u]^[i]:= i;
End ;
For i:= 1 to N-1 do
If Mind[u]^[i]+c[u]^[i+1] < Mind[u]^[i+1] then
15
Begin
Mind[u]^[i+1]:= Mind[u]^[i] + c[u]^[i+1];
trx[u]^[i+1]:= ưu ;try[u]^[i+1]:= i;
End ;
For i:= N downto 2 do
If Mind[u]^[i]+c[u]^[i-1] < Mind[u]^[i-1] then
Begin
Mind[u]^[i-1]:= Mind[u]^[i] + c[u]^[i-1] ;
trx[u]^[i-1]:= ưu ;try[u]^[i-1]:= i;
End ;
dispose (c[u-1]) ;dispose (Mind[u-1]) ;
End ;
Chúng ta thấy Dữ liệu được đóng mở một cách khéo léo mà không tốn bộ nhớ. Còn ta chỉ quan
tâm đến Kết quả cuối cùng là Mind[m]^. Còn đường đi thì đã được lưu bởi hai bảng Trx và Try.
Chính vì thế chúng ta có thể đóng đi những Mind[i] mà không dùng đến trong quá trình quy hoạch về
sau (Cũng đóng luôn mảng C [i] không cần thiết). Với cách giải quyết thông minh như trên, các bạn
hoàn toàn giải quyết rất nhiều bài toán quy hoạch động đòi hỏi nhiều bộ nhớ khác.
Bài toán 18:
RTicket
Trên tuyến đường sắt từ thành phố A đến thành phố B đi qua một số ga. Tuyến đường có thể
biểu diễn bởi một đoạn thẳng, các nhà ga là các điểm ở trên nó. Tuyến đường bắt đầu từ A (có số hiệu
là 1) và B là ga cuối cùng.
Giá vé đi lại giữa hai nhà ga chỉ phụ thuộc vào các khoảng cách giữa chúng. Cách tính giá vé
được cho trong bảng sau:
Khoảng cách giữa hai nhà ga -X
Giá vé
0
C1
L1
C2
L2
C3
Vé để đi thẳng từ nhà ga này đến nhà ga khác chỉ có thể đặt mua nếu khoảng cách giữa chúng không
vượt quá L3. Vì thế nhiều khi để đi từ ga này đến ga khác ta phải đặt mua một số vé.
Ví dụ, trên tuyến đường sắt cho bởi đoạn thẳng sau:
Ga: 1
2
3
4
L1
5 6
7
L2
L3
Để đi từ ga 2 đến ga 6 không thể mua vé đi thẳng. Có nhiều cách đặt mua vé để đi từ ga 2 đến ga 6.
Chẳng hạn, đặt mua vé từ ga 2 đến ga 3 mất chi phí C2 và sau đó mua vé đi từ ga 3 đến ga 6 mất chi
phí C3 và chi phí tổng cộng để đặt mua vé đi từ ga 2 đến ga 6 theo cách này là C2+C3. Lưu ý rằng
mặc dù khoảng cách từ ga 2 đến ga 6 là 2*L2 nhưng không thể đặt mua vé với giá vé để đi từ ga 2 đến
ga 6 là 2*C2vì mỗi vé chỉ có giá trị đi lại giữa hai ga nào đó.
Yêu cầu:
Tìm cách đặt mua vé để đi lại giữa hai nhà ga cho trước với chi phí mua vé là nhỏ nhất.
Dữ liệu:
Vào từ file văn bản Rticket. Inp:
• Dòng đầu tiên ghi các số nguyên L1, L2, L, C1, C2, C3 (1 L1< L2
theo đúng thứ tự vừa liệt kê.
• Dòng thứ hai chứa số lượng nhà ga N (2 N 10000).
• Dòng thứ ba ghi hai số nguyên S, T là các chỉ số của hai nhà ga cần tìm đặt mua vé với chi phí
16
nhỏ nhất để đi lại giữa chúng
Dòng thứ i trong số N-1 dòng còn lại ghi số nguyên là khoảng cách từ nhà ga A (ga 1) đến nhà
ga thứ i+1 (i=1, 2, . . N-1). Chi phí từ nhà ga A đến nhà ga cuối cùng B không vượt quá 109.
Kết quả:
Ghi ra file Rticket. Out là chi phí nhỏ nhất tìm được.
Ví Dụ:
•
RTICKET. INP
3 6 8 20 30 40 7
26
3
7
8
RTICKET. OUT
13 15 23
70
Hướng dẫn :
Tuy công thức truy hồi của bài toán này hết sức đơn giản, như các công thức truy hồi của các bài
toán trước, nhưng Dữ liệu bài toán là rất lớn. Chính vì thế vòng lặp của quy hoạch động trở nên phải ít
hơn. áp dụng trong bài toán này chúng ta chỉ việc so sách với các ga gần nhất của nó có khoảng cách
nhỏ hơn L1, L2, L3. các công đoạn chính của bài toán có thể được mô ta như sau:
Procedure ReadFile;
Begin
readln (f1, l1, l2, l3, c1, c2, c3) ;
readln (f1, n) ;
readln (f1, x1, x2) ;
if (x1
begin
i:=x1;
j:=x2;
end
else
begin
i:=x2;
j:=x1;
end;
x1:= i;
x2:= j;
A^[1]:= 0;
for i:=2 to n do
begin
readln (f1, t) ;
a^[i]:=t;
end;
End;
Procedure Xuli;
Begin
i1:= x1;
i2:= x1;
i3:= x1;
for i:=x1+1 to x2 do
begin
while (A^[i]-A^[i1]) >l1 do inc (i1) ;
while (A^[i]-A^[i2]) >l2 do inc (i2) ;
while (A^[i]-A^[i3]) >l3 do inc (i3) ;
17
B^[i]:= B^[i3] + c3;
if (i<>i2) then
if (B^[i2]+c2)
if (i<>i1) then
if (B^[i1]+c1)
end;
IV. Các Bài toán Khác:
Bài toán 19:
RoBot1
Đề Bài:
Để thám hiểm, khảo sát các vùng đất nguy hiểm ngoài trái đất, người ta chế tạo các RoBốt đơn
giản, hoạt động theo chương trình cài sẵn hoặc theo lệnh điều khiển phát đi từ Trái Đất. Các lệnh điều
khiển là: L: rẽ trái (so với hướng đang chuyển động), R: rẽ phải (so với hướng đang chuyển động), U:
tiến thẳng, D:quay lui. Với mỗi lệnh rôbốt di chuyển một đơn vị khảng cách. Vùng cần khảo sát được
kẻ thành lưới ô vuông và các nút lưới có toạ độ nguyên. Ban đầu rôbốt được đưa tới điểm có toạ độ
(X0, Y0) và hướng theo chiều song song với một trục toạ độ. Nhiệm vụ là phải đưa rôbốt tới điểm có
toạ độ (X1, Y1) bằng đúng K lệnh di chuyển (0<=| X0-X1|, |Y0-Y1|<=16, 0
xem tồn tại bao nhiêu chương trình khác nhau có thể cài đặt vào bộ nhớ của rôbốt.
Dữ liệu: Vào từ file văn bản: Bai18. Inp gồm 5 số nguyên K, X0, Y0, X1, Y1 các số thuộc phạm vi
Integer, cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản: Bai18. Out một số nguyên xác định số lượng chương trình tìm được.
Ví Dụ:
BAI18. INP
BAI18. OUT
30010
9
Hướng dẫn:
Chúng ta thấy rằng để đến ô (i, j) thì có 4 ô từ đó có thể đến nó là: (i, j+1), (i, j-1), (i-1, j), (i+1, j).
Gọi Count[i, j, k] là số cách đi có thể để đến ô (i, j) từ ô xuất phát (x0, y0) sau k bước.
Ta sẽ có:
Count [i, j, k]:= Count[i, j-1, k-1 ] + Count[i, j+1, k-1] + Count[i-1, j, k-1 ] +
Count [i +1, j, k - 1];
Nhưng để tránh trùng lặp nên chúng ta phải xuất phát đặc biệt: cho i, j chạy từ (xo, yo) về sau k
bước, rồi sau đó lại cho (i, j) chạy từ (xo, yo) về trước.
Bài toán 20:
RoBot2
Một xưởng sản xuất có mặt là một hình chữ nhật kích thước M x N, M, N là các số nguyên
dương không lớn hơn 100. Mặt bằng được chia thành các ô vuông đơn vị gồm các dòng đánh số từ 1
đến M từ trên xuống dưới và các cột được đánh số từ 1 đến N đánh số từ trái sáng phải. Cuối ca làm
việc, để thu gom các sản phẩm, người ta dùng một số con robot phải xuất phát từ ô [1, 1]. robot chỉ có
thể chuyển động từ trái sang phải, trên xuống. Khi robot đến nơi đặt máy nào, nó có thể thu hết mọi
sản phẩm của máy đó. Robot kết thúc hành trình tại ô [ M, N].
Yêu cầu:
Hãy bố trí một số ít nhất robot để thu gom sản phẩm.
Dữ liệu:
Nhập vào từ file Robot. inp trong đó đòng thứ nhất ghi hai số M, N. Tiếp theo là M dòng
mô tả mặt bằng của xởng, mỗi dòng ghi N số chỉ gồm các số 0 / 1 mà 0 có nghĩa là ô tương ứng không
có máy, ngược lại ghi số 1.
Kết quả:
Xuất ra file robot. out trong đó: dòng thứ nhất ghi số r là số ro bot cần dùng. R dòng
tiếp theo ghi hành trình của các con robot đó. chỉ gồm các kí tự liên tiếp:
D, R: D có nghĩa là đi xuống, R có nghĩa là sang phải.
Ví dụ:
18
Robot. Inp
Robot. Out
10 12 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0
100000000010010000000100001111000 111111000100 100000000
100 100000000100
5
DDDDDDDDDRRRRRRRRRRR
RDDDDDDDRRRRRRRRDDRR RRRRRDDDDDDRRRRRRDDD RRRDDDDRRRRRRRRRDDDD
RRRRRRRDDDDDDDDDDRRR
Hướng dẫn:
Gọi cc là số Robot ít nhất cần dùng. Dùng mảng p[i, j] để lưu lại các giá trị. Ta sẽ có xét với các
hàng i, thì ta có các bước sau:
FillChar (P, SizeOf (P), 0) ;
cc:=0 ;
Với hàng i:
+ bước i: Ta tìm vị trí cuối cùng của hàng này có chứa máy cần thu gom (kí hiệu mm
). Nếu không có thì quy định: Ok:=False nếu có thì Ok:=True ;
+ bước ii: Xét các vị trí trong hàng theo thứ tự giảm dần của cột (j)
Nếu P[i-1, j]>0 thì :
Nếu j <= mm thì: P[i, mm]:=P[i-1, j]; Ok:=False ;thực hiện tiếp bước i
Nếu j>mm thì: P[i, j]:=P[i-1, j]
Nếu cuối cùng mà Ok:=True thì cc:=cc+1 ; tức là tăng số robot lên một con.
Cứ như vậy thực hiện chúng ta sẽ ra được số con robot ít nhất cần dùng.
Bài toán 21:
Truyền Tin
(Đề Thi học sinh giỏi quốc gia 2000-2001-bảng B)
Người ta cần truyền n gói tin được đánh số từ 1 đến n từ một điểm phát đến một điểm thu. Để
thực hiện việc truyền tin có thể sử dụng m đường truyền được đánh số từ 1 đến m. Biết rằng nếu
truyền j gói tin theo đường truyền tin j thì phải trả là Sij (Sij là một số nguyên dương, Sij 32767, i=1,
2. . . m, j=1, 2. . . n)
Yêu cầu: Hãy xác định số lượng gói tin cần truyền theo mỗi đường truyền tin để việc truyền tin n gói
tin được thực hiện với tổng chi phí phải trả là nhỏ nhất.
Dữ liệu: Vào từ file Bl3. Inp như sau:
• Dòng đầu tiên chứa hai số nguyên dương n và m (n, m 100)
• Dòng thứ i trong số m dòng tiếp theo chứa n số nguyên dương Si1, Si2, . . . Sin, i=1, 2. . m
Kết Qủa: Đưa ra file văn bản Bl3. Out như sau:
• Dòng đầu tiên chứa số S là tổng chi phí phải trả theo cách truyền tin tìm được
• Dòng thứ hai chứa m số nguyên không âm Q1, Q2. . . Qm, trong đó Qi là số gói tin cần truyền
theo đường truyền i.
Ví Dụ:
Bl3. Inp
3 3 20 20 20
4 3 10 1 3 20
Bl3. Out
4 021
Hướng dẫn:
Gọi Mind[i, j] là tổng chi phí nhỏ nhất cần trả cho việc truyền i gói tin mà sử dụng j đường tin (1, , j),
Chúng ta có công thức truy hồi như sau:
Mind[i, j]:=MinMind[i-1, k]+S[i, j-k]; K=0, . . j ;
Bài toán 22:
Cửa Hàng Bán Hoa
Tại 1 cửa hàng người ta muốn cắm một số loài hoa vào chậu hoa nhỏ, tất cả có F loài hoa và V
chậu hoa (F<=V). Các chậu hoa được đánh số từ 1 đến V và xếp theo thứ tự từ trái sang phải. Mỗi loài
19
hoa cũng được đánh số tuân theo điều kiện: với i
cách khác hoa i được cắm ở chậu Vi và hoa j được cắm ở chậu Vj thì ta phải có Vi
Ta có bảng hệ số thẩm mỹ của việc cắm hoa :
HOA
1 (đỗ quyên)
2 (hải đường)
3 (cẩm chướng)
1
7
5
-21
2
23
21
5
Chậu Hoa
3
-5
-4
-4
4
-24
10
-20
5
16
23
20
bảng Ai, j với 1<=i<=F, 1<=j<=V. có ý nghĩa: nếu hoa i được cắm ở chậu j thì đạt điểm thẩm mỹ ại. ví
dụ ta có bảng hệ số trên.
Yêu cầu bài toán là tìm một phương án camứ hoa sao cho đạt tổng số điểm lớn nhất.
Hạn chế kỹ thuật:
• 1<= F<=100 với F là số các loài hoa.
• F<=V <=100 với V là số các chậu hoa.
• -50<= Ai, j <=50 với Ai, j là hệ số thẩm mỹ thu được khi loài hoa i cắm vào chậu hoa j.
5Dữ liệu : Cho từ file Bai22. Inp như sau:
• Dòng đầu tiên ghi 2 số F, V.
• F dòng tiếp theo: mỗi dòng ghi V số nguyên, như vậy số Ai, j là ghi ở vị trí j tại dòng i+1.
Kết quả: Ghi ra file Bai22. Out như sau:
• Dòng đầu tiên ghi tổng số điểm thẩm mỹ của cách xếp.
• Dòng thứ 2 ghi lần lợt F số, số thứ K ghi số chậu hoa của loài hoa thứ k đã xếp.
Yêu cầu chạy không quá 2 giây.
Ví dụ:
Bai22. Inp
Bai22. Out
3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20
53 245
Hướng dẫn:
Chúng ta có Maxd[i, j] là giá trị thẩm mĩ lớn nhất khi cắm các tranh từ 1 đến i vào các vị trí 1. .
j. Ta sẽ có công thức truy hồi như sau:
i<= j then Maxd[i, j]:=MaxMaxd[i-1, j-1]+A[i, j], Maxd[i, j-1]
i>j then Maxd[i, j]:=Maxd[i-1, j] ;
Bài toán 23:
Treo Tranh
Cho n bức tranh mã số từ 1 đến n, không vượt quá 50. Người ta cần chọn ra 1 bức tranh để đặt ở
cửa ra vào phòng tranh, số còn lại được treo thẳng hàng trong phòng treo theo trật tự nghiêm ngặt sau
đây: tranh có số hiệu nhỏ phải treo ở trên trái tranh có số hiệu lớn. Biết các thông tin sau về mỗi tranh:
• Tranh thứ i treo tại của sẽ đạt giá trị thẩm mỹ C[i]
• Tranh thứ i treo tại vị trí thứ j sẽ đạt giá trị thẩm mỹ V[i, j].
Hãy xác định một phuơng án treo tranh để có giá trị thẩm mỹ là lớn nhất.
Dữ liệu: Vào từ file văn bản: TRANH. INP
• Dòng thứ nhất: hai trị số: N , M
• Dòng tiếp theo là n giá trị C.
Tiếp theo là N dòng, dòng thứ i gồm m số V[i, 1], V[i, 2], . . . . . V[i, m]
Kết quả
Ra tệp văn bản: TRANH. OUT
• Dòng thứ nhất: giá trị thẩm mỹ lớn nhất tìm được
• Dòng thứ hai: mã hiệu bức tranh treo ở cửa phòng tranh
Từ dòng thứ ba: N - 1 số tự nhiên là số hiệu vị trí được chọn để treo tranh trong phòng
20
Ví Dụ:
TRANH. INP
1 20 1
1 10 1
212
130
40 2 2
TRANH. OUT
40
3
2
10
4
Hướng dẫn:
Trước tiên chúng ta xét bài toán: Cho N tranh, treo vào M vị trí, biết các giá trị A[i, j] là giá trị
thẩm mĩ của cách treo tranh thứ i vào vị trí thứ j. Biết quy định treo như quy định bài toán. Chúng ta
có Maxd[i, j] là giá trị thẩm mĩ lớn nhất khi cắm các tranh từ 1 đến i vào các vị trí 1. . j. Ta sẽ có công
thức truy hồi như sau:
i<= j then Maxd[i, j]:=Max (Maxd[i-1, j-1]+A[i, j], Maxd[i, j-1]) ;
i>j then Maxd[i, j]:=Maxd[i-1, j] ;
áp dụng vào bài toán: chúng ta sẽ thử từng tranh một khi để ở cửa, sau đó chúng ta giải quyết cho bài
toán N-1 tranh để vào M vị trí để có giá trị thẩm mĩ lớn nhất. Trong các trường hợp như vậy chúng ta
lấy trường hợp có tổng giá trị thẩm mĩ lớn nhất. Chính là cách treo tranh cần đặt.
Bài toán 24:
Project
Giám đốc điều hành của một công ti tin học cần xác định số lượng nhân công cần sử dụng
trong mỗi tháng để thực hiện một dự án phát triển tin học. Ông giám đốc nắm được số lượng nhân
công tối thiểu cho mỗi tháng. Mỗi lần thuê hoặc sa thải một công nhân luôn mất thêm một khoản chi
phí. Mỗi khi một thợ nào đó được thuê, anh ta luôn nhận được tiền lương ngay cả khi anh ta không
phải làm việc. Giám đốc nắm được chi phí thuê một công nhân mới, chi phí sa thải một nhân công,
lương một tháng của một công nhân. vấn đề đặt ra cho giám đốc là phải xác định số lượng công nhân
cần thuê hoặc sa thải trong mỗi tháng để cho chi phí thực hiện dự án là tối thiểu.
Dữ liệu: Vào từ file văn bản Project. Inp :
• Dòng thứ nhất ghi thời gian thực hiện dự án n (đơn vị thời gian: số tháng, n <=12)
• Dòng thứ hai ghi ba số nguyên dương theo thứ tự là chi phí thuê một công nhân mới, lơng
tháng của một công nhân, chi phí để sa thải một nhân công.
• Dòng cuối cùng ghi n số nguyên dương D1, D2, . . . . Dn trong đó Di là số lượng nhân công tối
thiểu cần cho tháng i.
Kết quả: Ghi ra file : Project. Out:
• Dòng thứ nhất ghi chi phí tối thiểu cần cho công việc
• Mỗi dòng trong số N dòng tiếp theo ghi số Si, trong đó nếu Si > 0 thì nó là số lượng nhân công
thuê thêm ở tháng thứ i, còn nếu Si <0 thì |Si| là số lượng nhân công cần sa thải ở tháng thứ i
của dự án, Si = 0 thì khong có biến động về sa thải hay thuê thêm.
Ví Dụ:
PROJECT. INP
3
456
10 9 11
PROJECT. OUT
199
10
0
1
Hướng dẫn:
Gọi T_max là số công nhân của tháng nhiều nhất công nhân. mảng Scn[1. . T] cho biết số công
nhân tối thiểu cần cho tháng ấy. C[T, T_max], trong đó C[i, j]cho biết chi phí tối thiểu của i tháng đầu
tiên của dự án nếu tại tháng thứ i có j công nhân trong biên chế.
21
C[i, j]:=minc[i-1, k]+chi phí để từ k người thành j người , i =1, . . T, j=Scn[i]. . . T_max, k =
scn[i-1]. . T_max
Bài toán 25:
Đề Bài:
Triangle
7
3
8
1 0
2 7 4 4
4 5 2 6 5
Hình trên là một bảng tam giác các số nguyên không âm. Hãy viết chương trình để tính tổng
lớn nhất các số trên đường đi từ đỉnh tam giác và kết thúc tại một điểm nào đó ở trên đáy tam giác.
• Mỗi nước đi ta được quyền đi thẳng xuống bên trái hay bên phải của số đó
• Số hàng trong tam giác lớn hơn 1 và 100.
• Các số trong tam giác đều là các số nguyên không âm và nhỏ hơn 100.
Dữ liệu: cho trong file triangle. Inp như sau:
• Dòng đầu tiên ghi số lượng các dòng trong tam giác (N)
• Dòng i+1 (1 i N) ghi i số
Kết quả xuất ra file triangle. Out là tổng lớn nhất tìm được
Ví Dụ:
8
Triangle. Inp
triangle. Out
Triangle. Inp
Triangle. Out
5738810274445265
30
10 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 3 4
86353515378357178378653145783516743213
58
Hướng dẫn:
Maxd[i, j] là độ dài lớn nhất khi đi từ ô[1, 1] đến ô[i, j]. Ta có công thức truy hồi sau:
Maxd[i, j]:=MaxMaxd[i-1, j]+a[i, j], maxd[i-1, j-1]+a[i, j] ;
Trong đó maxd[1, 1]:=a[1, 1] ;
Bài toán 26:
Mua hàng
N hàng ở nước ngoài (một nước có thể được ghé nhiều lần) người ta quay về nước 1, bán tất cả
các hàng và thu được nhiều tiền nhất. (Lần mua cuối cùng tại nước 1 xem như lần K+1).
Dữ liệu: Cho trong file văn bản Muahang. Inp gồm M+1 dòng:
• Dòng 1 gồm các số M, N, S, K
• Dòng thứ i+1 trong các hàng còng lại ghi N số C[i, 1], C[i, 2], . . . C[i, n.
Kết quả: ghi ra file văn bản Muahang. Out gồm:
• Dòng 1: tổng số tiền thu được theo phương án tối ưu
• Các dòng còn lại biểu diễn cách mua tối ưu:
+ Dòng đầu tiên ghi tên đơn vị hàng mua ở nước 1, và số lượng của nó.
+ k Dòng tiếp, mỗi dòng ghi 3 số: tên nước bán cần bán hàng trước và cần tiêu thụ và mua tiếp,
tên hàng mua ở nước đó, số lượng mua ở nước đó.
Ví Dụ:
Muahang. Inp
Muahang. Out
5 10 100 4 1 3 5 5 5 5 5 5 5 4 5 1 1 1 5 5 5 5 4 5 4 5 5 5 1 5 5 4 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5 1 5
55545555
187500 1 100 3 500 1 1 2500 1 3 12500 1 5 62500 1
Hướng Dấn:
Gọi Maxd[i, j, k] là số hàng i tối đưa mua tại nước j sau k lần mua bán. (S0, K0 là số tiền ban
22
đầu, và số lần bán mua).
Maxd[i, j, k]:= maxMaxd[i, t, k-1]
Số tiền tối đưa các bạn có thể kiếm được sau K0 lần mua bán sẽ là MaxMaxd[i, j, k0] ;
i=1, . . M , j =1, . . N
Nhưng trong công thứ truy hồi, bài toán sẽ đòi hỏi một bộ nhớ khá lớn. Chúng ta sẽ thực hiện
như sau để giảm tối thiểu bộ nhớ:
Gọi S là mảng sao cho S[i, j] là số hàng i tối đưa mua tại nước j
Gán toàn bộ S = 0 ;
S[1, i]:=S0 div C[1, i] ;
For k:= 1 to K0 do
Begin
+ Gán toàn bộ S2=0
+ For i:=1 to m do
for j:=1 to n do
for i1:=1 to m do
if (i1<>i) then
for j1:=1 to n do
if (j1<>j) then
nếu S[i1, j1]*c[i, j1]div c[i, j] >s2[i, j]
thì S2[i, j]:=S[i1, j1]*c[i, j1] div c[i, j] ;
+ S:= S2 ;
End ;
Bài Toán 27:
Mua Ximăng
Một tổng công ti xây dựng nhận thầu một công trình. Người ta dự kiến chia công trình thành N
công đoạn, mỗi công đoạn kéo dài trong 1 tháng. Lượng xi măng cần thiết cho mỗi công đoạn thứ i là
Mi tấn (Mi nguyên dương). Vì xi măng tồn kho cần phải trả một chi phí tổn thất nhất định nên người ta
không mua đủ lượng xi măng cho cả công trình ngay từ đầu mà chia thành nhiều đợt, mua vào các đầu
tháng. Tuy vậy, do giá xi măng thay đổi theo từng tháng nên không nhất thiết tháng nào cũng phải mua
đúng số lượng xi măng cho tháng đó .
Yêu cầu: Hãy cho biết số lượng xi măng cần mua cho từng tháng là bao nhiêu để phí tổn tổng cộng
(mua và bảo quản) là ít nhất. Biết rằng gí xi măng cho tháng thứ i là Ci (trăm ngàn đồng) mỗi tấn.
Ngoài ra, nếu số lượng xi măng tại một tháng nào đó còn thừa trong kho là d tấn thì chi phí bảo quản
trong tháng đó là qd2 (trăm ngàn đồng). Để đơn giản, ta quy ớc đơn vị mua xi măng nhỏ nhất là tấn và
mọi tham số ở đây đều là nguyên.
Dữ liệu: vào từ file văn bản ximang. Inp với:
• Dòng đầu tiên chứa n, q (n 10).
• Dòng thứ hai chứa n giá trị: m1, m2, . . Mn (30 Mi, i) ;
• Dòng thứ ba chứa n gía trị: C1, C2, . . Cn.
Kết quả: ghi ra file văn bản Ximang. Out với:
• Dòng đầu tiên chứa S là phí tổn tối ưu.
• Dòng thứ hai ghi n gía trị X1, X2, . . Xn là lượng xi măng cần mua của từng tháng một.
Ví Dụ:
42
XimangInp
5 3 10 6 14 20 10 30
Ximang. Out
356 6 2 15 1
Hướng dẫn:
Gọi A[i, j] là lượng chi phí bỏ ra để mua và bảo quản từ tháng thứ i cho hết N tháng, với lượng
xi măng có hiện tại trong kho là j tấn. Ta sẽ có công thức truy hồi như sau (đối với A[i, j]):
23
For i:= n downto 1 do
begin
T:= M[i]+M[i+1]+. . . +M[n].
For j:=0 to T do
begin
if i = n then
begin a[i, j]:=c[n]* (m[n]-j) ; k:= m[n]-j ; end
else if j>=m[i] then
begin a[i, j]:=Sqr (j-m[i]) +a[i+1, j-m[i]] ; k:= 0 ; end
else
begin a[i, j]:= (m[i]-j) *c[i]+a[i+1, 0] ; k:= m[i]-j ; end ;
A[i, j]:=Minx*c[i]+sqr (j+x-m[i]) *q+a[i+1, j+x-m[i]] ;
x:= k + 1, . . . T
end ;
end ;
Bài Toán 28:
Cung Cấp Vật Liệu
Có N công trình cần vật liệu thi công. Công trường i cần cung cấp D[i] đơn vị hàng. Hàng được
cung cấp từ hai kho A và B. Cớc vận chuyển một đơn vị hàng từ kho A đến công trường i là A[i]. Cước
vận chuyển từ một đơn vị hàng từ kho B đến công trường i là B[i]. Biết A có r đơn vị hàng và tổng số
hàng của cả hai kho vừa đủ cung cấp cho N công trường.
Yêu cầu: Hãy phân phối hàng từ hai kho đến các công trường sao cho tổng cước phí vận chuyển là
nhỏ nhất.
Dữ liệu: Cho trong file CungCap. Inp gồm 4 dòng:
• Dòng thứ nhất ghi N và R (N 100)
• Dòng thứ hai ghi N số biểu diễn D[1], D[2], . . . . D[n]
• Dòng thứ ba ghi N số: A[1], A[2], . . A[n].
• Dòng cuối cùng ghi N số: B[1], B[2], . . . B[n]
Kết Qủa: xuất ra file Cungcap. Out như sau:
• Dòng 1: ghi một số nguyên dương là tổng chi phí vận chuyển ít nhất
• Dòng 2: Ghi N số nguyên dương tương ứng số đơn vị hàng mà khi A cung cấp cho từng công
trình theo thứ tự
• Dòng 3:Ghi N số nguyên dương tương ứng số đơn vị hàng mà khi B cung cấp cho từng công
trường theo thứ tự.
Ví Dụ:
Cungcap. Inp
Cungcap. Out
5 100 30 80 80 50 40 3 5 10 4 23 4 6 2 7 4 1070 30 20 0 50 0 0 60 80 0 40
Hướng dẫn:
Gọi Mind[i, j] là cước phí nhỏ nhất mà kho 1 phải cung cấp j đơn vị hàng cho các công trường 1. . i
Ta sẽ có công thức truy hồi:
Mind [i, j]:=MinA[i]*K+B[i]* (D[i]-K) +Mind[i-1] (j-K)
Với K=0. . D[i] ; và K<=j ;
Bài toán 29:
Mua hàng giảm giá
Trong một cửa hàng, mỗi loại hàng có một giá. Ví dụ gía một bông hoa là 2 đồng và giá một cái
bình là 5 đồng. Để thu hút nhiều khách hàng, cửa hàng đề ra một số cách bán đặc biệt
Một cách bán giá đặc biệt liên quan đến việc bán một hay một số hàng với giá chung được
giảm.
24
Ví dụ: 3 bông hoa bán với giá 5 đồng thay vì 6 đồng.
2 cái bình và 1 bông hoa bán với giá 10 đồng thay vì 12 đồng.
Viết chương trình tính giá mà một khách hàng phải trả cho một nhu cầu mua hàng để tận dụng
một cách tối ưu các cách bán đặc biệt, nghĩa là phải trả ít nhất. Ví dụ: với các giá và các cách bán đặc
biệt, nêu trên, giá thấp nhất để mua 3 bông hoa và 2 cái bình là 14 đồng ; 2 bình và 1 hoa là 10 đồng ; 2
hoa với giá bình thường là 4 đồng.
Dữ liệu: cho trong 2 file offer. In1 và Bai24. In2 như sau:
File thứ nhất Bai24. Inp mô tả nhu cầu mua:
• Dòng đầu tiên chứa số B là số loại hàng cần mua (0 B 5)
• Mỗi dòng trong B dòng tiếp theo ghi 3 số c, k, p. Giá trị c là mã của loại hàng (1 c 999). Giá trị
k là số đơn vị hàng cần mua với mã c (1k 5). Giá trị p là giá bình thường của một đơn vị hàng
với mã c (1 p 999).
File thứ hai offer. In2 mô tả các cách mua bán đặc biệt:
• Dòng đầu tiên chứa số s là số cách bán đặc biệt (0 s 99)
• Mỗi dòng trong s tiếp theo mô tả một cách bán đặc biệt. Số đầu tiên n của mỗi dòng như vậy là
số loại hàng trong cách bán đặc biệt tương ứng với dòng đó (1 n 5) ; n cặp số tiếp theo (c, k)
trong đó c là mã loại hàng, k là số đơn vị hàng đó (1 k 5;1 c 999). Số p cuối cùng trong dòng là
giá đã được giảm trong lô hàng nay. Giá đã được giảm nhỏ hơn tổng các giá trị bình thường
Kết quả:xuất ra file offer. Out là số tiền nhỏ nhất để mua hàng
Biết rằng hàng và tiền phải nguyên.
Ví Dụ:
offer. In1
3 2 5 10 1 4 6 5 3 4
offer. In2
offer. Out
4 2 2 3 1 8 20 3 8 2 9 3 10 2 9 2 7 5 9 8 6 3 2 1 1 1 5 1 10 56
Hướng dẫn:
Dùng phương pháp quy hoạch động để giải. Giả sử ta có một Yêu cầu mua 5 loại mặt hàng với
số lượng tương ứng là SL[1], SL[2], SL[3], SL[4], SL[5]. Ta phải sử dụng các cách mua đặc biệt sao
cho tổng giá mua vừa đúng Yêu cầu mua thấp nhất. Quá trình tổ chức việc mua được hình dung như
một quá trình quy hoạch nhiều giai đoạn. Nếu ký hiệu A[i1, i2, i3, i4, i5] là tổng giá mua thấp nhất để
mua các loại hàng với các số lượng tương ứng là i1, i2, i3, i4, i5 thì theo quy hoạch động, nó phải là
nhỏ nhất trong mọi giá trị có thể có của A[j1, j2, j3, j4, j5]+giá mua theo giá gốc/giá mua theo cách
mua đặc biệt của phần hàng hoá thêm với mọi bộ j1, j2, j3, j4, j5 <= i1, i2, i3, i4, i5. Mỗi cách tính
toán thể hiện bởi một thủ tục TIM1/TIM2.
Sau đây là Chương trình và giai thích chương trình bằng tiếng việt:
Uses crt;
Const
fn='input. txt';
fn1='offer. txt';
gn='output. txt';
Type
mang=array[1. . 5] of record vat, sl:integer; end;
{Kiểu Dữ liệu này để ghi nhận về loại hàng và số lượng trong một cách bán đặc biệt}
Var
ten, sl, gt:array[1. . 5] of integer;
{Ghi nhận một Yêu cầu mua}
num:array[1. . 100] of integer;
c:array[1. . 100] of mang;
cost:array[1. . 100] of integer;
{Ba mảng NUM, C, COST dùng để ghi nhận các cách bán đặc biệt}
b:array[1. . 100] of boolean;
25
Tài liệu liên quan
Phương pháp quy hoạch động
Thuật toán quy hoạch động với dữ liệu lớn
Thuật toán sinh dữ liệu với Quy Hoạch Động
Quy hoạch động
QUY HOẠCH ĐỘNG
Tài liệu Chuyên đề tin học - Lý thuyết quy hoạch động docx
Chuyên đề quy hoạch động
Phương pháp quy hoạch động
Phương Pháp Quy Hoạch Động
BÀI TOÁN QUY HOẠCH ĐỘNG
Tài liệu bạn tìm kiếm đã sẵn sàng tải về
(443.5 KB) - Chuyên Đề Quy Hoạch Động CĐ2
Tải bản đầy đủ ngay
×


markdown:
Tải bản đầy đủ
Ngoại Ngữ
Tổng hợp
Objective FCE 2e student book(4)
Here are some other expressions followed by the
past tense.
a as if / as though
It wasn't like a smoke cloud, it was as if it were
alive — it wasn't alive.
What is the difference between:
You talk as if / as though you were an expert on
disasters!
You talk as if / as though you are an expert on
disasters.
b would rather
This takes an infinitive without 'to' or a past tense.
I'd rather not tell you what really happened.
I'd rather you didn't ask me about the experience.
(Don't confuse I'd rather and I'd better (= I had
better) — they mean different things.)
Say what you would rather do in each situation.
EXAMPLE: Would you like to go camping?
— I'd rather stay in a hotel.
— I'd rather we stayed in a hotel.
a Would you like to come with us for a pizza?
b Would you like to study engineering?
c Would you like to travel to the Moon?
d Would you like me to teach you Latin?
e Would you like me to buy you an iPod?
6 I'd prefer you not to repeat what I've just told you.
rather
I.............................................repeat what I've just
told you.
0
•.:
page 207
Vocabulary
8 Liz and Dave had to 'unroll' their trousers to empty
out the ash that had collected in them.
What sort of things do you:
a untie
b unbutton
undo
d unwrap
e uncover
f unearth
g unfasten
h untangle
unwind
EXAMPLE: unzip — your trousers, a dress
7 For the following questions, complete the second
sentence so that it has a similar meaning to the first
sentence, using the word given. Do not change the
word given. You must use between two and five
words, including the word given.
1 I regret not taking the park ranger's advice.
taken
I.............................................the park ranger's
advice.
2 I think it's better for the children to stay inside in
bad weather.
rather
I ......................................... inside in bad weather.
3 What a pity we didn't see any wildlife on our trip.
only
If.............................................wildlife on our trip.
4 I don't like living in an earthquake zone.
wish
I............................................somewhere else.
5 Don't walk so fast, I can't keep up with you!
wish
I............................................walk so fast, I can't
keep up with you!
9 Fill in the missing letters for these weather words.
a The Mid-West states of the USA suffer from
b Last winter we had huge S___D___ T S and
had to dig our way out of the house.
c The meteorological office have issued a G
W----------G to all shipping.
d The weather F ___C___ for tomorrow is quite
good.
e The sky's a bit 0--------------T this morning.
f I got caught in a S
and got soaked to the
skin.
g H-----------------S are usually found in the
Caribbean.
h Global warming has led to D R____T
conditions in parts of the world.
i Britain is famous for being D ___, while parts of
UNEXPECTED EVENTS
/ 149
India are often H____.
Exam
folder
12
Paper 1 Part
text
2
Gapped
What makes
intelligent?
This part of the Reading paper requires you
to read a text from which seven sentences
have been removed, and then choose the
correct sentences to fill in the gaps. There
is always one extra sentence which you
don't need.
Although there are fewer questions in this
part than in Part 3, like Part 1, each question
Advice
• Read the skeleton text quickly, in order to get an
idea of what the text is about.
3 mins
Underline key words in the text, to predict what a
gap might contain. Look for linking and reference
words too.
5 mins
Scan the missing sentences for matching
information and note down likely
answers.
5 mins
Read through the whole text with your
answers
place,
check
that it all
makes sense. 3
• Make
sureinthat
thetoextra
sentence
does
not fit anywhere.
is 'double-weighted, that is, it is worth two
marks instead of one. Part 2 is a difficult task
and you must allow enough time for it.
Complete the exam task below using the
steps in the Advice box. Try to keep to the
suggested timings.
You are going to read a magazine article
about intelligence. Seven sentences have
been removed from the article. Choose from
the sentences A—H the one which fits each
gap (1-7). There is one extra sentence which
you do not need to use.
The days when all you needed to make a living was
sufficient physical strength to bring in the harvest are long
gone. To survive today you need to be educated to rocket
scientist level just to program a DVD recorder, make sense
of a public transport timetable, or follow a complicated pia:
on TV. In short, what you have in your head has never beemore important.
But what exactly is intelligence? Are there ways of getting
smarter, or are you stuck with what you were born with?
There aren't any easy answers. Despite the progress that
has been made in genetics and psychology, human
intelligence has remained one of the most controversial
—
areas of modern science. 11
Robert Plomin of the Institute of Psychiatry in London and his
colleagues in the US have been looking into genetic make-up
2 mins
From their research, they have established that a slightly
different gene is more common in those with a high 10.
Plomin analysed DNA from two groups of 51 children aged
between six and 15. What he found was that the first group had
an IQ of 136, putting them in the top 5% of the population,
while the other group had an average IQ of 103 An analysis of
their genes revealed that 32% of children in the higher group
had the gene in question, while only 16% in the second group
did.
2
He suggests that there are probably many genes
that contribute to intelligence, rather than just one.
If you were born with a full set of intelligence-enhancing
genes, then you'd expect to be very clever indeed. But just how
important are genes in intelligence? Most of the early research
150 \ EXAM FOLDER
12
someone
A This may seem remote from everyday
concerns, but does illustrate what the
human brain is capable of.
E.nce it is difficult to find many who have
been separated at : firth, recent studies
have concentrated on adopted children
stead. One does suggest that adopted
children become creasingly like their
biological parents as they get older.
.
-
BOne example is the idea of 'multiple
intelligences', which was developed in
the 1980s by Harvard psychologist
Howard Gardner.
-
r the past, the idea that intelligence is
mainly inherited .Nacame an excuse for
prejudice and discrimination. The ::incept of
IQ itself was first developed a century
ago by =-ench psychologist Alfred Binet.
C The tests were meant to select bright
but socially-disadvantaged children, to
ensure that they got a good education.
-
14
IQ measures omething called
general intelligence, testing word and
,:tuber skills, as well as spatial ability.
DUntil now, that is, for the discovery of a
gene linked to intelligence has made the
experts think again.
.
-
averal studies have shown a strong link
between IQ and :areer success,
although some psychologists remain
_unconvinced about this. 5
people with the
ighest IQs are not usually the ones who
do best in their :areers, but there's a big
business out there with :ccupational
psychologists offering all kinds of
selection its for companies. They
won't go away because there's 2 lot of
money to be made. But intelligence is
not like e—iperature, and you cannot
measure it in the same way. :s much
more complicated than that.'
-
EHe lists Alexander the Great, Pablo
Picasso and Albert Einstein as
examples.
F Professor Michael Rowe, who has
written a book called Genius Explained,
is one of these.
GHowever, there is a lot more research to be
done, and Plomin himself is cautious at
this early stage.
HOn the other hand, if differences in their
IQs were found, this would point to
background or environmental factors.
-
EXAM FOLDER
12
151
'any psychologists now believe
that when it comes to :elligence, IQ
isn't everything. Many alternative
views ave been put forward
recently. 6 I This offers a
—
,uch broader view than the IQ
theory, including creativity aid
communication skills as relevant factors
in intelligence.
-
-
−
Buzan, brain expert and author of
Master your
'emoty, is enthusiastic about this belief,
arguing that true :--niuses do indeed
appear to combine high levels of each
7I
.oe of intelligence.
time, Buzan
-
I
ceceves that everyone can develop their
intelligence, if only ey take the trouble to
exercise their brain. Perhaps there's ope
for us all!
--
PM'
-
Priceless or
1 Discuss the two paintings and decide
which one you like best and why. If you
were very rich, would you spend any
money on works of art? Do you have a
favourite artist or sculptor? Describe in
detail a work of art you admire.
2 Read this title and opening paragraph.
Decide what you think the article is
going to be about.
A New Genius?
The artist had some difficulty pointing out the features of his 3-metre•
wide painting, which had just been sold for $19,000 to an adoring crowd
at the opening night in Beverly Hills - perhaps because he is only 1 m 40
cms tall.
3 Now read through the whole article and answer the questions
which follow.
THE ART WORLD'S LATEST CHILD PRODIGY, ten-year-old Beso
discovered Alexandra than parents from all over the world began
sending me their kids' work. Yet none measured up to Beso, and
I went to see him. Lightning can strike twice. Beso's work is
deeper. After Alexandra the door is open. People believe a child's
art is worthy of serious consideration, so Beso won't meet the
earlier scepticism. I believe he's a genius, and I'm prepared for
the verdict of time.'
10
Kazaishvili from the Republic of Georgia, looked resplendent in
traditional costume: a belted cream wool tunic with sewn-in
gunpowder tubes and a sinister curved dagger. He was 'very
happy' about the sale but emphasised: 'Money is not everything.'
Beso has burst upon the art scene two years after the Romanianborn Alexandra Nechita was hailed as a genius at the age of ten.
She has now made $10 million from her paintings. Her family
has moved from a cramped bungalow by a Los Angeles freeway
to a $1 million mansion. Alexandra began in California and made
15
a successful European tour. Beso began with some success in
London, where his family stayed with the Georgian ambassador,
and he is now touring the United States. His work is mostly in
oils of human figures and faces, executed in a lively way in
bright, sometimes almost garish, colours. Many tell stories with
admit that sales of the children's works are market driven. 'If
Beso makes $19,000 in half an hour, it's because people want
his work. Dozens of other youngsters haven't made that mark.
Well, that's the market. Who knows what will happen next'?'
symbolic themes of good and evil, death and time, and all are
executed remarkably quickly. Ink drawings, which sold for £200
in London, are fetching up to $3,000 in Beverly Hills, where they
are very highly thought of.
Beso's parents, Badri an engineer, and Irma, a schoolteacher,
believe their son's work was influenced by Georgia's civil war of
1993-1995. They were often without water and electricity, and
food was scarce. Short of money to buy paper, Beso made a
drawing on the blank side of a card from his mother's stockings
packet. 'That one is priceless and not for sale,' said Mr Valenty,
5
20
25
Beso and Alexandra are managed by the Californian art publisher
Ben Valenty. Beso has signed a contract in the 'mid-six figures'.
Mr Valenty always takes half but pays all expenses. It is good
money for both sides — Beso's sales hit $30,000 in an hour in
the USA. Cynics like myself may question a second genius
arriving so soon, but Mr Valenty argues that there are probably
half a dozen or more in the world. He adds: 'No sooner had I
Mr Valenty and his colleague Rick Lombardo, a television
producer preparing a documentary on child prodigies, cheerfully
who acknowledges that Beso's 'story' helps sales. 'He's not like
other kids,' Mr Lombardo says. 'He's structured. Sure, he'll watch
television, play baseball, do his homework, but then start
painting. He's never distracted from that. We're only just
beginning to find out about these kids. Nobody studied it before.
Who knows what Picasso was like at 11? We don't know.'
1
1
30
35
40
45
50
1 5 2 \ U N IT 24
1 Beso and Alexandra both
A come from the same country in Europe.
Bare American citizens now.
C paint similar kinds of pictures.
D have an unusual gift.
possible to put a price on a work of art?
Vocabulary Collocations
5 Look at this example from the article.
2 What do we find out about Beso's painting?
A He enjoys doing portraits.
BHe spends time getting the details right.
C He prefers using subtle colours.
DHe uses ideas from famous fairytales.
She has now made $10 million from her paintings.
3 What does Mr Valenty say about child artists?
A He knows at least six possible geniuses at the
moment.
BHe wants to meet as many as possible.
C He believes that their work will be easier to sell in
the future.
A
break
sit
get
spend
taste
keep
have
do
wear
DTheir work improves as they get older.
4 What do you think 'measured up to' means in line
28?
A had the same height
Bwas the same standard
C was the same age
Dhad the same experience
5 What does Mr Valenty say about the money that
Beso earns?
A Beso could earn a lot more when he is older.
BIt's hard to put a price on Beso's works.
C Beso only earns what people are prepared to pay.
DIt's crazy for people to pay so much for a child's
work.
6 What do we find out about Beso from the article?
A His only interest is painting.
BHe is a good student.
C He is surprised that he is making so much
money.
DHe loves being in the USA.
7 What does `it' in line 50 refer to?
A the subject of young artists
Bthe particular style of painting
C the way Picasso painted when young
Dhow history can affect young people
8 How do you think the writer feels about Beso and his
paintings?
A He was impressed by how good the paintings are.
BHe isn't sure that Beso is really as good as
Alexandra.
C He's not convinced about child geniuses.
DHe thinks that money is Beso's real motive. 4 What
do you think about Beso and his new career? Is it
The collocation is 'to make money.
Can you match each verb in A with a word or
phrase in B? Some are used more than once.
B
a conversation
a promise
20 kilometres to the litre
a look
an expression
still
a fortune
awake
funny
a secret
a week
a holiday
better
6 4 a You will hear people talking in three different
situations. For questions 1-3, choose the best
answer (A, B or C).
1 You overhear a conversation in a cafe. What
does the woman say about seeing the Mona
Lisa?
A It hadn't been worthwhile.
BShe got to see some other good paintings
too.
C She went too early in the morning.
2 You overhear this man talking on the phone.
What does he say about his choice of painting?
A It makes his office look brighter.
BIt is appropriate for his position in the
company.
C It is worth more than the ones his
colleagues have.
3 You overhear this woman speaking about the
first night of an exhibition she recently
attended. Why was the artist unhappy?
A He hadn't sold enough paintings.
BFew people attended the exhibition. C
One of his favourite paintings had been
bought.
P R I C E L E SS O R W O RT H L E SS ? /
153
Adverbs and word order
1 Read the following information about adverbs.
Adverbs are usually formed by adding -ly to an
adjective. However, some words ending in -ly are
adjectives and have no adverb.
friendly, lonely, lovely, ugly, silly
If you want to use these words as adverbs you need to
add 'in a ... way'.
He held out his hand in a friendly way.
•Some adverbs keep the same form as the adjective. She
walks fast.
She is a fast walker.
He works hard.
He is a hard worker.
•Some adverbs have two forms, with a difference in meaning.
She works hard. (a great deal)
She hardly does any work. (almost no work) I
came home late yesterday. (not on time)
Have you seen Peter lately? (recently)
Adverb or adjective? Complete these sentences by using
a word or phrase based on the word in capitals. Some
sentences do not need to be changed.
a He seemed to be a very SILLY person.
b He drives quite GOOD for someone with so little
experience.
c The gallery owner shook my hand FRIENDLY.
d I think Picasso painted GOOD pictures than Braque.
e Don't paint so FAST, you'll make a mess of it.
f Women painters were often GOOD than men, it's
just they are less GOOD known.
g She draws CAREFUL than anyone else in the class.
h If you painted a little INTERESTING, people might
buy more of your paintings.
i A painter's life can be very LONELY.
Luckily my art teacher's drawing was BAD than
mine.
k I've eaten HARD any dinner.
1 Your hem isn't very STRAIGHT.
2 Read the information about adverbs and word
order.
n ev er se l d om r a re l y ha r d l y n o s o one r
These adverbs can be put in the normal
adverbial position. However, if they are put at
the beginning of a sentence, the word order
must be changed — this is called 'inversion. This
is because the subject and verb are 'inverted',
that is, the word order is changed so that it
looks like a question. It is done to give greater
emphasis.
No sooner had I discovered Alexandra than
parents all over the world began sending me their
kids' work.
I had no sooner discovered Alexandra, than
parents all over the world began sending me their
kids' work.
Corpus spot
The Cambridge Learner Corpus shows that FCE
candidates often have problems with adverbs
and word order.
I like Van Gogh very much.
NOT 4-141(c very much Van Gogh.
Correct the mistakes that FCE candidates
have made with word order in these
sentences.
a I yesterday visited an art gallery in London.
b My mother goes often to the
shops. Never I have seen a
house like that.
d She drew quickly the cat.
e Zoos can be sometimes nice.
f Only I will be able to travel in July.
g Peter shook politely her hand.
h Always there is a queue for the
cinema. He hardly can sleep at
night.
She hard works in an office.
0........page 207
154
\
U N I T 24
1
Vocabulary
beginning (0).
Example: o TALENTED
Vocabulary spot
Some words in English are easily confused, either because they
look or sound similar, or because they exist in another
language with a different meaning.Take special care when
learning these words.
Words often
confused
The article about
Beso
talked
about a work of
art
being
'priceless. This
means that you
can't
buy
it
because it is so
valuable: it has
no price.
In the following sentences there are two words or
phrases which are often confused by students.
Decide which one is correct, then write another
sentence to show how the other word or phrase
is used.
a My sister spent so long talking on the phone
every day that at the end / in the end my parents
bought her a mobile phone.
b My next door neighbour's help has been
invaluable / priceless while my mother was in
hospital.
c You don't see many people smoking nowadays /
actually.
d Prices of impressionist paintings have raised /
risen a great deal in the last few years.
e Lie / lay down on the bed and have a rest.
f Tell / say me the story about how you met Monet.
g My mother is an excellent cook / cooker.
h The bank in town was stolen / robbed this
morning.
i I damaged / injured the piano when I tried to
move it.
The watch I got for my birthday was very priceless
/ valuable.
k My friend was very sympathetic / friendly when I
broke my arm.
1 Jean is so sensible / sensitive that she cries
whenever she watches a sad film.
4 Read the text below. Use the word
given in capitals at the end of
some of the lines to form a word
that fits in the gap in the same
line. There is an example at the
PABLO PICASSO
Pablo Picasso was born in Spain on October 25,1881.
He showed
himself to be a (o) ........... artist as a child and when
he was................................TALENT
19 he went to Paris to paint... He experimented
with (1) ........................ styles,.......................................
DIFFER
for a time painting sad subjects in shades of blue.
During a
happier time, he used reds and pinks to paint more (2)
............................................................................
subjects such as dancers and (3) ............... in circuses.
..............................................................PERFORM
It did not take Picasso long to become (4) ....................
was........................................................................ SUCCE
constantly looking for new (5)....................He became intereste
INSPIRE
African masks, particularly in the•simple but very (6)
...........................................................................
EXPRESS
that they distorted the human face. He saw that it
was possible
to build up an image using simple lines and angular
shapes. This
was the beginning of cubism. Even though his cubist
pictures are
(7) ........................we still understand what they are meant to
about...........................................................................
In 1937 Picasso created one of his most (8)
............................................................................
paintings — Guernica, a protest against an air raid
on a
Basque village. In Guernica, Picasso used (g)
..................................................................
forms that
...............................................................................
SYMBOL
are (io) ...............found in his later works—things
like a dying horse.REPEAT
or weeping woman.
Prado Museum.
Guernica now hangs in the
P R I C E L E SS O R W O RT H L E SS ?
155
Writing folder
Nr
-
12
Articles
2
In Part 2 of Paper 2 you might
be asked to write a description
INTERNATIONAL ARTS MONTHLY
of a place, a person or an
• Do you have a favourite
object as part of the task.
1 Look at this exam
painting or sculpture?
question.
• Why do you think it is
interesting?
You see this notice in an
We are looking for short articles
Look carefully at this painting and then read through a student's
answering these questions and
answer to the question.
we will publish some of the best
articles next month. international arts magazine
and decide to write to
them.
Write your article.
My favourite painting is of a woman, a.
servant in a large house and it was
painted about 1660 in Holland by
Vermeer Van Delft. The young woman is
a cook and is quite tall and I'd say -fairly
strong, probably as a. result of having to
carry heavy objects from an early age. I
would, say she is about 18 or 19 years
old. She's wearing a white cap or scarf,
which completely covers her hair, a
yellow blouse, which buttons at the front,
a blue apron and an orange floor-tength
skirt. This painting gives you a, good idea
of what ordinary working women wore in
the seventeenth century.
The girt seems fairly happy and is
concentrating very hard on what she is
doing. I think she probably enjoys her job
and her life even though it is likely to be
quite hard. Perhaps she already
knows who her husband will be and is looking
-forward to getting married,
the only option open to a. young girt in those
days. I find this an
interesting painting
because it isn't of
someone rich or
,
famous, but of an ordinary person going
about her daily tasks. Although she isn't
dressed, in silks and lace she is, in her on
way, rather beautiful.
.
1 1 1
7 1
1•11
1
I-
9
-
.
I
i
.
I
-
anuii:
WRITING FOLDER
12
1
6 1
i
1F
I.
•
.
■
1
, I
- -1.
- II
Now think about what information the answer has given you
about the cook and her life. Which of these titles would be best
for this article?
A Everyday L ife in the seventeenth century
B A painting i s a s r o d a s a photograph
(:
I
Bringing, the past to 11,f e
2 Look again at the painting of the cook and complete this
short paragraph which describes the room she is in. Join the
words together — you must keep them in the same order. You
may need to add some words.
EXAMPLE: The
room she / probably / kitchen / house. The
room she is standing in is probably the kitchen of
the house.
The walls / bare / painted white. There / window / wall / basket
/ hanging / it. the window / there / table / basket / bread, /
bowl / milk, / cakes. Jug / milk / bowl / make / brown
pottery. There / blue and white tiles / wall / joins / floor. floor
/ box / containing / pot / handle.
3 Look at this exam question.
You see this competition in an international nature and
science magazine and decide to enter it.
I
.
EARTH MATTERS MAGAZINE
* Have you ever been caught in severe
*
weather conditions?
Write and tell us where you were and what you
did.
I
We will print the six best articles we receive and
the writers will get a year's subscription to the
magazine.
Write your article.
4 How many synonyms can you think of for the following
words? Use your dictionary to help you.
I.
a big
b small
c rich
d poor
e hot
f cold
g fat
h thin
i pretty
j bad
Advice
gni
• Make a plan — Remember there
are two parts to this question.
• Think of a title.
• Use your own experience, or
what you have read or seen on
or heard
• TV
Think
about about.
what kind of person
reads the magazine.
• Try not to repeat yourself,
especially when you use
adjectives.
W R I T I N G F O L D E RT F
Units 19 24 Revision
Topic review
1 Answer these questions, giving your own
opinions.
a What should someone do to lose weight?
b When should you tell someone it's time for them to
leave a party?
c Even if someone has committed a crime, is prison
the best form of punishment?
d Would you rather spend your money on
entertainment or clothes?
e Is there a luxury you regret not having?
f Do you ever wish you were famous?
g What do you hope to do after you have passed FCE?
h What would you do if you were stranded in a storm?
i How often do you go to art exhibitions?
Are modern painters and sculptors exceptionally
talented professionals or totally worthless con artists?
Vocabulary
2 Read the statements or questions and choose the best
option, A, B or C.
1 You have been out in the wind and your hair looks a
mess. Should you
A untie it? B unwind it? C untangle it?
2 If you give away your friend's secret even though you
agreed not to, have you
A broken a promise? B kept your word?
C spent a fortune?
3 Which performer would you not see at a
classical recital?
A a violinist B a cellist C a bass guitarist
4 You are driving in torrential rain and a tree falls across
the road 200 metres in front of you. Are you in
danger of being
A cut down? B cut off? C cut out?
158
REVISION
5 While a photograph is being taken of you, should you
keep
A quiet? B calm? C still?
6 If you have a steady income but enjoy paying
everyone's expenses, are you likely to be A tight?
B broke? C loaded?
7 What should you do about a large debt?
A pay it off B break it off C call it off
8 It's about time you found a glass of water.
Are you
A fainting? B hiccuping? C sneezing?
3 The twenty words below have all appeared in
Units 19-24. Decide what they are with the
help of the information given and then use one
from each set to complete the sentences a—e.
•two verbs to do with illness or injury:
1 S P_A__
2C___H
•three words to do with volcanoes:
3
E
4
U
H
5L___
•four musical instruments:
6
0
7 I
8
0
U
1
9_L__E
•five serious crimes:
10 _ _ P _
11 F
D
12
GG
13
S
14 _ I J
K___
•six adjectives to describe works of art:
15 W___H_E_S
16 _X___S_IV_
17 _R_C____S
18 _ _ L _ _ B L _
19 G__ISH
2 0 SY 0 C
a She picked up the shiny silver......................................and began to
play her favourite piece.
b A flow of......................................that is one metre thick would
probably take more than two days to cool and become solid.
c If only that painting weren't so ................................... ! I would
rather look at softer colours.
d It is very easy to.......................................your ankle when running
to the back of the court for a difficult ball.
e Firemen found a half-full can of petrol near the incident, so
..................................seemed a certainty.
Grammar
4 Read the text below and think of the word which best fits each
gap. Use only one word in each gap. There is an example at the
beginning (0).
How to
make a
small
fortune
Have you ever wished you had
some savings to fall back (0)
o n
Perhaps you already have something
put aside for a rainy day, but if
(1) ...................., here are some unusual
ways to make a pile (2) ......................
cash. Look critically at your old toys.
Very
(3)...................... remain in a condition
that is good (4) ..................... for them to
be sold, (5) ............. that a pre-1950,
well-looked-after teddy bear can be
worth
(6) to £2,000. Musical
instruments can also raise
(7)
large sum, sometimes
unexpectedly. Hazel Morgan hadn't
played her violin for more (8) ...... forty
years, so she decided to sell
(9) ....................... To her surprise, the
violin itself was valued (10) ............
£2,500 and the bow, despite
U N I T S 19-24 /159
Urban decay, suburban
hell
'1111111111111
A
111/111
-
-
."1
,„
r • --T"
REST,,, ANT
•
.••••••--
1 Compare and contrast these
two pictures, and talk about
the advantages and
disadvantages of living in each
city area. You can use some of
the words below to help you.
Neighbourhood:
peaceful, quiet, calm/noisy,
polluted, dangerous deprived,
derelict, run-down/regenerated,
improved
Buildings:
low-rise/high-rise spacious/
cramped
Amenities:
entertainment centre,
multiplex cinema, mall,
pedestrian/shopping precinct,
out-of-town shopping
Listening
2 o a You will hear an extract from a radio programme called Challenge
the expert. Listen to the introduction to decide what profession the
expert is in.
3
nmight
Read the sentences below before you listen, to predict what you
hear. Then listen and complete the sentences.
Julia explains that some ig6os architecture came about because of
T o d a y ,
they were in the past.
2
I
regulations are stricter than
Julia used to live in a 13 poor part of Bristol.
I as a child, in a
The 14 I
improved since the ig6os. used for new buildings have
Julia mentions I 5
as
People are unhappy about damage to their health caused an example of an
environmental requirement for new buildings in Britain.
When explaining what she sees as a problem today,Julia refers to the
6
I
as'urbansprawl'.
Services:
litter/refuse collection,
maintenance, street-lighting
Some city centre shops have shut because of171
facilities.
Transport:
congestion, traffic jam,
parking restrictions
for city centres.
Julia believes that architects should design 18
In a multi-use building, there might be 9 I
downstairs.
by Ho II in cities.
16C\ UNIT 25
Do you consider any of these rude or offensive?
In what other ways can a speaker or listener direct
a conversation?
4 p Compare your answers with another student.
Then listen again to check.
5 G .3 These words with up all occurred in the
recording. Match them to 1-5. Do you know any
other words with up-?
a uprooted
b upheld
c upkeep
d upmarket
eupside
8 Now practise these turn-taking skills. Get into groups
of four to discuss the following statements. For each
statement, one person in the group should stay silent
and time how long each of the others speaks for.
1 maintenance
2 expensive
3 made to leave
4 advantage
5 supported
• There are both good and bad examples of modern
architecture.
6 Explain what you think each speaker meant by the
following statements. Do you agree with them?
a Lack of consultation over new buildings is rarely
an issue with the public.
b City expansion isn't very good news for the
countryside either.
c What I believe in is the regeneration of our city
centres.
d Living in the city has to become a healthier and
more acceptable option.
• Living conditions in our
cities have got worse.
• City centres should be
traffic-free.
• Urban sprawl is a
serious threat to
nature.
Speaking
Exam spot
Turn-taking skills are important, especially in Part 4 of the
Speaking Test, where there is a three-way discussion involving
both candidates and the examiner. This Part lasts 4 minutes
and each candidate needs to have adequate opportunities to
speak, which means being sensitive to the other people in the
conversation.
7 Say whether the purpose of these turn-taking
expressions is
i to involve someone in the discussion
ii to encourage someone to be quiet
iii to support what someone is saying
a You clearly know a lot about this, but let's
move on.
b Would you say that this is true in your case?
c I believe your own view is slightly different?
d Come on, you're talking rubbish!
eWell, I have to admit you have a point.
f I'm going to say something here.
g What do you think?
h Absolutely, I couldn't agree more.
I
i
w
Mixed conditionals
1 Look at these two quotes from the recording in
25.1, which are examples of mixed conditionals.
Explain what tenses are used and why.
If we were meant to live up in the sky, we would
have been born with wings!
If 60s architecture hadn't happened, we would
be making similar mistakes today.
In both examples, the second and third
conditional forms are mixed.
2 You can use a mixed conditional to talk about
a past action affecting a present situation, as
in the second example above. Finish these
mixed conditional sentences in a suitable way.
EXAMPLE: If
we had bought that house, we
would be short of money now,
a If people hadn't objected to the plans, the
building ...
b If Tom had remembered to book
a table at the restaurant, we ...
c If I hadn't seen that programme, I ...
d If we had set off earlier, we ...
e If she hadn't answered the advert, she ...
You can
also use mixed conditionals to talk about how a different
present situation would have affected a past situation, as in
this example:
If the city centre was traffic -free, the council wouldn't have
needed to build all these car parks.
Finish these sentences in a similar way, using the ideas in
brackets.
a If high-rise buildings were of better quality, more people
(choose to live in them in the first place)
b If there weren't so many distractions, you (tidy up your
bedroom by now)
c If the suburbs were smaller, local taxes (be so high for the
last 20 years)
d If the supermarket was open 24 hours, I (go out at 3 am
this morning to buy you some paracetamol)
0........page 2o7
4 Imagine a city with no advantages to it whatsoever.
Discuss the impact of these problems.
•no refuse collection
•no shops
EXAMPLE:
• no bus service
• no police
If there was no refuse collection service, rubbish
would pile up on the streets and there might be
rats.
162
UNIT 25
5 Read the article about the architect Sir Norman
Foster. For questions 1-12, decide which answer,
A, B, C or D, best fits each space. There is an
example at the beginning (0).
Example:
0 A chose
B fixed
0 A B C D
C dealt
D wished
The grand designer
When asked to select his favourite
building, Sir Norman Foster (0) ....
a Jumbo jet. His own buildings
frequently (1) ..... materials and
technology developed by the
aerospace industry. Perhaps his most
(2) ..... building is the Hongkong and
Shanghai Bank, a massive
construction of three linked towers
41 (3) ..... high. His most ambitious
European (4) ....... has been the
reconstruction of the Reichstag as the
new German parliament building.
He has also built a metro (5) ...... in
Bilbao, and two space-age
communications towers in Barcelona
and Santiago de Compostela.
Foster (6) ...... in the vertical city,
an architect's dream that began a
hundred years ago and is still (7) . . .
consider construct
generate
open possess
write
Tài liệu liên quan
Cambridge.University.Press.A.Student.Grammar.of.Spanish.Feb.2006.pdf
Cambridge.University.Press.Class.Counts.Student.Edition.Jul.2000.pdf
objective ielts advanced student''''s book
objective ielts intermediate student''''s book
fce listening and speaking 1 for the rivised cambridge fce examination student book
postcards 2e 1 student''''''''''''''''s book
Ready for FCE (Student's book Unit 4)
FCE student - Learning English
Objective FCE 3e WB
Gold fce student book
Tài liệu bạn tìm kiếm đã sẵn sàng tải về
(5.42 MB) - Objective FCE 2e student book(4)
Tải bản đầy đủ ngay
×

WARC-Type: response

Content-Type: application/http; msgtype=response

WARC-Identified-Payload-Type: text/html

Server: nginx

Connection: close

Vary: Accept-Encoding

Content-Type: text/html; charset=UTF-8