Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



Có N loại tiền mệnh giá mi và số lượng si , i = 1..N. Xác định số lượng mỗi loại để có thể trả lại V đồng.

TRATIEN.INP
TRATIEN.OUT

6 156
1 2 5 10 20 50
4 7 2  3  6  2


0 3 0 0 5 1  



  Dữ liệu vào: tệp văn bản TRATIEN.INP
  Dòng đầu tiên: hai số tự nhiên N và V, 2 £ N £ 15.
  Dòng thứ hai: N số tự nhiên m1, m2,…,mN.
  Dòng thứ ba: N số tự nhiên s1, s2,…,sN.
  Dữ liệu ra: tệp văn bản TRATIEN.OUT
  N số tự nhiên c1, c2,…,cN thể hiện số lượng tờ tiền mỗi loại cần trả, c1m1 + c2m2+ …+ cNmN = V. Nếu vô nghiệm: ghi số 0.
Trong các tệp *.INP và *.OUT các số trên cùng dòng cách nhau qua dấu cách.

Thuật toán

Đây là loại toán Balo với dữ liệu nhỏ vì trong thực tế số mệnh giá không nhiều, thí dụ, tiền Việt chỉ có các loại sau đây là thông dụng 100, 200, 500, 1.000, 2.000, 5.000, 10.000, 20.000, 50.000, 100.000,  200.000, 500.000. Nếu tính theo đơn vị 100 đồng thì ta có thể viết lại dãy trên cho gọn hơn như sau:
1, 2, 5, 10, 20, 50, 100, 200, 500, 1.000,  2.000, 5.000.
Ta duyệt các tổ hợp số tờ tiền phải trả cho mỗi loại mệnh gía, cận dưới là 0 cận trên là min(si, v div mi) vì để trả lại v đồng bằng loại mệnh giá mi ta dùng tối đa (v div mi) tờ.
Độ phức tạp: (b1-a1+1)(b2-a2+1)...(bv-av+1), v = M+N.
Chú ý: Sau này ta sẽ xây dựng thuật toán tốt hơn cho bài toán trả tiền. Thuật toán này dựa  trên một số kiến thức số học.
(*  Pascal  *)
(****************************************
                Tra tien
*****************************************)
program TraTien;
uses crt;
const mn = 20; bl = #32; nl = #13#10;
    fn = 'TRATIEN.INP'; gn = 'TRATIEN.OUT';
type mi1 = array[0..mn] of integer;
(*----------------------------------
    n – so luong cac loai tien
    v – so tien can tra lai
    vt – gia tri tam thoi
    m[1..n] – cac menh gia
    s[1..n] – so luong to tien
    c[1..n] – so luong can chon
------------------------------------*)
var n,v,vt: integer;
   m,s,c: mi1;
   f,g: text;
procedure Doc;
  var i: integer;
begin
  assign(f,fn); reset(f); readln(f,n,v);
  for i := 1 to n do read(f,m[i]);
  for i := 1 to n do read(f,s[i]);
  close(f);
end;
function Min(a,b: integer): tự viết
function Next: Boolean;
  var i: integer;
begin
  Next := false;
  i := n;
  while (c[i] = s[i]) do
    begin
      vt := vt - c[i] * m[i];
      c[i] := 0;
      i := i - 1;
    end;
  if (i = 0)  then exit;
  c[i] := c[i] + 1;
  vt := vt + m[i];
  Next := true;
end;
function Duyet: Boolean;
  var i: integer;
begin
  { Khoi tri }
  for i := 1 to n do
   begin
     s[i] := min(s[i],v div m[i]);
     c[i] := 0;
   end;
  c[0] := -1;  vt := 0; { tong gia tri cua 1 phuong an }
  Duyet := true;
  repeat
    if (vt = v) then exit;
  until not Next;
  Duyet := false;
end;
procedure Run;
  var i: integer;
begin
  Doc;  assign(g,gn);  rewrite(g);
  if (Duyet) then
     for i := 1 to n do write(g,c[i],bl);
    else writeln(g,0);
  close(g);
end;
BEGIN
  Run;
END.


Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts