Data Loading...

giao_trinh_bai_tap_ky_thuat_lap_trinh_c Flipbook PDF

giao_trinh_bai_tap_ky_thuat_lap_trinh_c

143 Views
21 Downloads
FLIP PDF 1.24MB

DOWNLOAD FLIP

REPORT DMCA

CÁC BÀI TOÁN DUYỆT 1. Robot quét vôi ( http://vn.spoj.pl/problems/NKROBOT ) Có 9 căn phòng (đánh số từ 1 đến 9) đã được quét vôi với màu trắng, xanh hoặc vàng. Có 9 robot (đánh số từ 1 đến 9) phụ trách việc quét vôi. Mỗi robot chỉ quét một số phòng nhất định. Việc quét vôi được thực hiện nhờ một chương trình cài sẵn theo qui tắc: Nếu phòng đang có màu trắng thì quét màu xanh Nếu phòng đang có màu xanh thì quét màu vàng Nếu phòng đang có màu vàng thì quét màu trắng Cần phải gọi lần lượt một số các robot ra quét vôi (mỗi lần một robot, một robot có thể gọi nhiều lần và có thể có robot không được gọi. Robot được gọi sẽ quét vôi tất cả các phòng mà nó phụ trách) để cuối cùng các phòng đều có màu trắng. Yêu cầu: Hãy tìm một phương án như vậy sao cho số lần gọi robot là ít nhất. Giả thiết rằng lượng vôi cho mỗi lượt quét đối với các phòng là như nhau.

Input 9 dòng đầu: dòng thứ i mô tả một danh sách các phòng do robot i phụ trách việc quét vôi. Mỗi dòng là một chuỗi các chữ số từ 1..9 biểu diễn các số hiệu của các phòng, các chữ số viết sát nhau. Dòng cuối mô tả mầu vôi ban đầu của các phòng. Dòng gồm 9 ký tự viết sát nhau gồm toàn các chữ cái T (trắng), X (xanh), V(vàng) biểu diễn mầu ban đầu của 9 căn phòng theo trật tự số hiệu của chúng.

Output gồm một dòng Nếu không có phương án thì in ra số 0 Trái lại thì in ra dãy thứ tự các robot được gọi (số hiệu các robot được viết sát nhau và in ra kết quả có thứ tự từ điển bé nhất)

Example Input: 159 123 357 147 5 369 456 789 258 XVXVXVTXT

Output: 2255799

Hướng dẫn: Chú ý rằng, sau 3 lần quét vôi thì màu của một căn phòng trở lại như cũ. Bởi vậy, việc sử dụng một robot ≥ 3 lần là không tối ưu. Ta có thể giải bài toán bằng cách sinh dãy tam phân độ dài 9, mỗi giá trị a[i] chính là số lần gọi robot i.

2. DÃY ABC Cho trước một số nguyên dương N (N 100), hãy tìm một xâu chỉ gồm các ký tự A, B, C thoả mãn 3 điều kiện: - Có độ dài N - Hai đoạn con bất kỳ liền nhau đều khác nhau (đoạn con là một dãy ký tự liên tiếp của xâu) - Có ít ký tự C nhất.

Hướng dẫn: Nếu dãy X1X2…Xn thoả mãn 2 đoạn con bất kỳ liền nhau đều khác nhau, thì trong 4 ký tự liên tiếp bất kỳ bao giờ cũng phải có 1 ký tự "C". Như vậy với một dãy con gồm k ký tự liên tiếp của dãy X thì số ký tự C trong dãy con đó bắt buộc phải

k div 4.

Tại bước thử chọn Xi, nếu ta đã có Ti ký tự "C" trong đoạn đã chọn từ X1 đến Xi, thì cho dù các bước đệ quy tiếp sau làm tốt như thế nào chăng nữa, số ký tự "C" sẽ phải chọn thêm bao giờ cũng (n - i) div 4. Tức là nếu theo phương án chọn Xi như thế này thì số ký tự "C" trong dãy kết quả (khi chọn đến Xn) cho dù có làm tốt đến đâu cũng

Ti + (n - i) div 4. Ta dùng con số này để

đánh giá nhánh cận, nếu nó nhiều hơn số ký tự "C" trong “Cấu hình tối ưu” thì chắc chắn có làm tiếp cũng chỉ được một cấu hình tồi tệ hơn, ta bỏ qua ngay cách chọn này và thử phương án khác.

Các bạn tham khảo Code: program ABC_STRING; const InputFile = 'ABC.INP'; OutputFile = 'ABC.OUT'; max = 100; var N, MinC: Integer; X, Best: array[1..max] of 'A'..'C'; T: array[0..max] of Integer; f: Text; function Same(i, l: Integer): Boolean; var j, k: Integer; begin j := i - l; for k := 0 to l - 1 do if X[i - k] X[j - k] then begin Same := False; Exit; end; Same := True; end; function Check(i: Integer): Boolean; var l: Integer; begin for l := 1 to i div 2 do if Same(i, l) then begin Check := False; Exit; end; Check := True;

end; procedure KeepResult; begin MinC := T[N]; Best := X; end; procedure Try(i: Integer); var j: 'A'..'C'; begin for j := 'A' to 'C' do begin X[i] := j; if Check(i) then begin if j = 'C' then T[i] := T[i - 1] + 1 else T[i] := T[i - 1]; if T[i] + (N - i) div 4 < MinC then if i = N then KeepResult else Try(i + 1); end; end; end; procedure PrintResult; var i: Integer; begin for i := 1 to N do Write(f, Best[i]); WriteLn(f); WriteLn(f, '"C" Letter Count : ', MinC); end; begin Assign(f, InputFile); Reset(f); ReadLn(f, N); Close(f); Assign(f, OutputFile); Rewrite(f); T[0] := 0; MinC := N; Try(1); PrintResult; Close(f); end.

3. BÀI TOÁN NGƯỜI DU LỊCH Cho n thành phố đánh số từ 1 đến n và m tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này được cho bởi bảng C cấp nxn, ở đây Cij = Cji = Chi phí đi đoạn đường trực tiếp từ thành phố i đến thành phố j. Giả thiết rằng Cii = 0 với

i, Cij = +

nếu không có đường trực

tiếp từ thành phố i đến thành phố j. Một người du lịch xuất phát từ thành phố 1, muốn đi thăm tất cả các thành phố còn lại mỗi thành phố đúng 1 lần và cuối cùng quay lại thành phố 1. Hãy chỉ ra cho người đó hành trình với chi phí ít nhất. Bài toán đó gọi là bài toán người du lịch hay bài toán hành trình của một thương gia (Traveling Salesman)

Hướng dẫn: Hành trình cần tìm có dạng (x1 = 1, x2, …, xn, xn+1 = 1) ở đây giữa xi và xi+1: hai thành phố liên tiếp trong hành trình phải có đường đi trực tiếp (Cij

+ ) và ngoại trừ thành phố 1, không thành

phố nào được lặp lại hai lần. Có nghĩa là dãy (x1, x2, …, xn) lập thành 1 hoán vị của (1, 2, …, n). Duyệt quay lui: x2 có thể chọn một trong các thành phố mà x1 có đường đi tới (trực tiếp), với mỗi cách thử chọn x2 như vậy thì x3 có thể chọn một trong các thành phố mà x2 có đường đi tới (ngoài x1). Tổng quát: xi có thể chọn 1 trong các thành phố chưa đi qua mà từ xi-1 có đường đi trực tiếp tới (1

i

n).

Nhánh cận: Khởi tạo cấu hình BestConfig có chi phí = + . Với mỗi bước thử chọn xi xem chi phí đường đi cho tới lúc đó có < Chi phí của cấu hình BestConfig?, nếu không nhỏ hơn thì thử giá trị khác ngay bởi có đi tiếp cũng chỉ tốn thêm. Khi thử được một giá trị xn ta kiểm tra xem xn có đường đi trực tiếp về 1 không ? Nếu có đánh giá chi phí đi từ thành phố 1 đến thành phố xn cộng với chi phí từ xn đi trực tiếp về 1, nếu nhỏ hơn chi phí của đường đi BestConfig thì cập nhật lại BestConfig bằng cách đi mới. Sau thủ tục tìm kiếm quay lui mà chi phí của BestConfig vẫn bằng +

thì có nghĩa là nó không tìm

thấy một hành trình nào thoả mãn điều kiện đề bài để cập nhật BestConfig, bài toán không có lời giải, còn nếu chi phí của BestConfig < +

thì in ra cấu hình BestConfig - đó là hành trình ít tốn

kém nhất tìm được Input: file văn bản TOURISM.INP Dòng 1: Chứa số thành phố n (1

n

20) và số tuyến đường m trong mạng lưới giao

thông m dòng tiếp theo, mỗi dòng ghi số hiệu hai thành phố có đường đi trực tiếp và chi phí đi trên quãng đường đó (chi phí này là số nguyên dương

100)

Output: file văn bản TOURISM.OUT, ghi hành trình tìm được. TOURISM.INP TOURISM.OUT 2

1 1 4

3

2 2

4

1

3

46

1->3->2->4->1

123

Cost: 6

132 141 231 242 344

Các bạn tham khảo Code: program TravellingSalesman; const InputFile

= 'TOURISM.INP';

OutputFile = 'TOURISM.OUT'; max = 20; maxC = maxlongint div 2; var C: array[1..max, 1..max] of longint; X, BestWay: array[1..max + 1] of longint; T: array[1..max + 1] of longint; Free: array[1..max] of Boolean; m, n: longint; MinSpending: longint; procedure Enter; var i, j, k: longint; f: Text; begin Assign(f, InputFile); Reset(f); ReadLn(f, n, m); for i := 1 to n do for j := 1 to n do if i = j then C[i, j] := 0 else C[i, j] := maxC; for k := 1 to m do begin ReadLn(f, i, j, C[i, j]); C[j, i] := C[i, j]; end; Close(f); end; procedure Init; begin FillChar(Free, n, True); Free[1] := False; X[1] := 1; T[1] := 0; MinSpending := maxC; end;

procedure Try(i: longint); var j: longint; begin for j := 2 to n do if Free[j] then begin X[i] := j; T[i] := T[i - 1] + C[x[i - 1], j]; if T[i] < MinSpending then if i < n then begin Free[j] := False; Try(i + 1); Free[j] := True; end else if T[n] + C[x[n], 1] < MinSpending then begin BestWay := X; MinSpending := T[n] + C[x[n], 1]; end; end; end; procedure PrintResult; var i: longint; f: Text; begin Assign(f, OutputFile); Rewrite(f); if MinSpending = maxC then WriteLn(f, 'NO SOLUTION') else for i := 1 to n do Write(f, BestWay[i], '->'); WriteLn(f, 1); WriteLn(f, 'Cost: ', MinSpending); Close(f); end; begin Enter; Init; Try(2); PrintResult; end.

4. Tour du lịch của Sherry ( http://vn.spoj.pl/problems/LEM3 ) Trong kì nghỉ hè năm nay sherry được bố thưởng cho 1 tour du lịch quanh N đất nước tươi đẹp với nhiều thắng cảnh nổi tiếng ( vì sherry rất ngoan ). Tất nhiên sherry sẽ đi bằng máy bay. Giá vé máy bay từ đất nước i đến đất nước j là Cij ( dĩ nhiên Cij có thể khác Cji ). Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng sherry cũng muốn tìm cho mình 1 hành trình với chi phí rẻ nhất có thể để dành tiền mua quà về tặng mọi người ( Các chuyến bay của sherry đều được đảm bảo an toàn tuyệt đối ). Bạn hãy giúp sherry tìm 1 hành trình đi qua tất cả các nước, mỗi nước đúng 1 lần sao cho chi phí là bé nhất nhé.

Input Dòng 1: N (5 < N < 16) Dòng thứ i trong N dòng tiếp theo: Gồm N số nguyên, số thứ j là Cij (0 < Cij < 10001)

Output Gồm 1 dòng duy nhất ghi chi phí bé nhất tìm được

Example

Input:

Output:

6

8

012134 503234 410212 425043 253502 543310

5. Chấm điểm ( http://vn.spoj.pl/problems/V8SCORE ) Có N vị giám khảo trong kỳ thi chọn đội tuyển tin học. Kỳ thi bao gồm K bài. Vị giám khảo thứ i đề nghị số điểm của bài j là Aij. Hội đồng giám khảo muốn xác định số điểm cho mỗi bài sao cho: Tổng số điểm bằng S. Điểm của mỗi bài không bé hơn điểm của bài trước đó. Số điểm của mỗi bài bằng điểm đề nghị cho bài này của một vị giám khảo nào đó. Dữ liệu Dòng đầu tiên chứa ba số nguyên S (1 ≤ S ≤ 200), (1 ≤ K ≤ 20), (1 ≤ N ≤ 20). Dòng thứ i trong số N dòng tiếp theo chứa K số nguyên, số thứ j cho biết giá trị Aij là số điểm vị giám khảo thứ i đề nghị cho bài thứ j. Kết qủa Nếu tồn tại một cách cho điểm thỏa mãn yêu cầu: o

Dòng thứ nhất: in ra 'YES'.

o

Dòng thứ hai: in ra K số nguyên là điểm của mỗi bài tìm được.

Nếu không tồn tại cách cho điểm, in ra 'NO'.

Ví dụ

Dữ liệu

Kết quả

100 3 2 30 20 40 50 30 50

YES 30 30 40

100 2 3 11 22 33

NO

Hướng dẫn: Kết quả của bài toán (nếu có) sẽ có dạng X1X2…Xk. Trong mỗi bước duyệt, ta sẽ thử chọn Xi trong tập Aji (1