TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH

5.15 Cóc

Thí dụ, số bước k = 2, b₁ = 2, b₂ = 3, đoạn đường dài N = 8.

Có 4 cách: (2,2,2,2) (2, 3, 3) (3, 3, 2) (3, 2, 3).

Thuật toán: Quy hoạch động.

Gọi S(n) là số cách để cóc vượt đoạn đường dài n. Dựa theo bước nhảy đầu tiên ta chia toàn bộ các phương án nhảy của cóc thành k nhóm không giao nhau. Như vậy,

• 
  Nhóm 1 sẽ gồm các phương án bắt đầu bằng bước nhảy độ dài b₁, tức là gồm các phương án dạng (b₁,...). Sau bước nhảy đầu tiên, cóc vượt đoạn đường b₁, đoạn đường còn lại sẽ là nb₁, do đó tổng số phương án của nhóm này sẽ là S(nb₁).
  
• 
  Nhóm 2 sẽ gồm các phương án bắt đầu bằng bước nhảy độ dài b₂, tức là gồm các phương án dạng (b₂,...). Sau bước nhảy đầu tiên, cóc vượt đoạn đường b₂, đoạn đường còn lại sẽ là nb₂, do đó tổng số phương án của nhóm này sẽ là S(nb₂).
  
• 
  ...
  
• 
  Nhóm i sẽ gồm các phương án bắt đầu bằng bước nhảy độ dài b_i, tức là gồm các phương án dạng (b_i,...). Sau bước nhảy đầu tiên, cóc vượt đoạn đường b_i, đoạn đường còn lại sẽ là nb_i, do đó tổng số phương án của nhóm này sẽ là S(nb_i).
  
• 
  ...
  
• 
  Nhóm k sẽ gồm các phương án bắt đầu bằng bước nhảy độ dài b_k, tức là gồm các phương án dạng (b_k,...). Sau bước nhảy đầu tiên cóc vượt đoạn đường b_k, đoạn đường còn lại sẽ là nb_k, do đó tổng số phương án của nhóm này sẽ là S(nb_k).
  

Vậy ta có,

S(n) = { S(nb_i) | n  b_i i = 1, 2, … , k } (*)

Để ý rằng khi đoạn đường cần vượt có chiều dài n = 0 thì cóc có 1 cách nhảy (là đứng yên), do đó S(0) = 1. Ngoài ra ta quy định S(n) = 0 nếu n < 0.

Sử dụng mảng s ta tính dần các trị s[0] = 1; s[1], s[2], ..., s[n] theo hệ thức (*) nói trên. Kết quả được lưu trong s[n].

Độ phức tạp Với mỗi giá trị n ta tính k bước nhảy, vậy độ phức tạp thời gian cỡ k.n.

Các chương trình dưới đây đọc dữ liệu từ input file "coc.inp" gồm các số k, n và độ dài các bước nhảy b_i, i = 1, 2, ..., k. Kết quả được hiển thị trên màn hình.

Nếu ta sắp tăng mảng b thì chỉ cần duyệt đến khi b[i] > d.

5.16 Trả tiền

Ucraina

Ngân hàng có m loại tiền giấy mệnh giá khác nhau b₁ = 1, b₂, ..., b_k với số lượng không hạn chế. Cần chọn ít nhất là bao nhiêu tở tiền để có tổng bằng t cho trước.

Thí dụ. Có m = 4 loại tiền mệnh giá lần lượt là 1, 2, 7 và 10 quan tiền. Cần trả lại t = 14 quan. Ta chọn 2 tờ tiền mệnh giá 7 quan.

Thuật toán

Gọi s(t) là số tờ tiền ít nhất có tổng bằng t. Nếu trong số này có tờ tiền mệnh giá b_i thì tổng số còn lại là tb_i và do đó số tờ tiền còn phải trả nốt là s(tb_i). Phương án tối ưu khi đó sẽ là

s(t) = min { s(tb_i)+1 | i = 1, 2, ... , m; b_i  t }

Để cài đặt ta dùng mảng s và tính lần lượt các giá trị s[1], s[2], ... , s[t]. Kết quả được hiển thị trên màn hình là s[t].

Độ phức tạp: tm.

Chú ý Điều kiện có loại tiền mệnh giá 1 với số lượng không hạn chế đảm bảo rằng bài toán luôn luôn có nghiệm. Thật vậy, trong trường hợp xấu nhất ta có thể dùng t tờ tiền mệnh giá 1 quan để trả lại.
(* money.pas *)

uses crt;

const fn = 'money.inp'; bl = #32; nl = #13#10;

var b: array[0..31] of integer;

s: array[0..1001] of integer;

m,t: integer;

procedure Doc;

var f: text; i: integer;

begin

assign(f,fn); reset(f);

read(f,m,t);

writeln(nl,m,bl,t);

for i := 1 to m do

begin

read(f,b[i]);

write(b[i],bl);

end;

close(f);

end;

function Min(a,b: integer): integer;

begin if a < b then Min := a else Min := b end;

procedure Tinhs(d: integer);

var i: integer;

begin

s[d] := d;

for i := 2 to m do

if (d >= b[i]) then s[d] := Min(s[d],s[d-b[i]]+1);

end;

function XuLi: integer;

var i: integer;

begin

for i := 1 to t do Tinhs(i);

XuLi := s[t];

end;

BEGIN

Doc;

writeln(nl,XuLi);

writeln(nl,' Fini'); readln;

END.
// DevC++: money.cpp

#include

#include

#include

using namespace std;

// D A T A A N D V A R I A B L E

const char * fn = "money.inp";

int b[31]; // cac loai menh gia

int s[1001];

int m, t;

// P R O T O T Y P E S

void Doc();

int XuLi();

void Tinhs(int);

// I M P L E M E N T A T I O N

int main() {

Doc();

cout << endl << XuLi() << endl;

system("PAUSE");

return EXIT_SUCCESS;

}

void Doc() {

int i;

ifstream f(fn);

f >> m >> t ;

cout << endl << m << " " << t << endl;

for ( i = 1; i < m; ++i) {

f >> b[i];

cout << b[i] << " ";

}

f.close();

}

int XuLi() {

for (int i = 1; i <= t; ++i) Tinhs(i);

return s[t];

}

int Min(int a, int b) {

return (a < b) ? a : b;

}

void Tinhs(int d) {

s[d] = d;

for (int i = 2; i <= m; ++i)

if (d >= b[i]) s[d] = Min(s[d], s[d-b[i]]+1);

}

Chú ý

Nếu ta sắp tăng mảng b thì chỉ cần duyệt đến khi b[i] > d.

Каталог: tailieu
tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning
tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm
tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc
tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI
tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1
tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng
tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp
tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam

tải về 2.51 Mb.

Chia sẻ với bạn bè của bạn: