Bài Toán đổi Tiền - HỌC TIN CÙNG THỦ KHOA

Đăng ký học

• ĐĂNG KÝ HỌC LẬP TRÌNH với thầy Nguyễn Tô Sơn - Thủ khoa Đại học Sư phạm Hà Nội (tương tác trực tiếp)
• THÔNG TIN về Giảng viên tại Trang chủ Đại học Sư phạm Hà Nội

Bài viết MỚI nhất

• Mật khẩu ứng dụng của Gmail
• Đăng ký thi thử trực tuyến Học sinh giỏi môn Tin học lớp 9 Hà Nội cho học sinh Hà Nội và các địa phương
• Themis Test Maker - Tiện ích tạo bộ test, quản lý Input cho phần mềm Themis
• Scratch Judge - Chấm điểm tự động ngôn ngữ Scratch tự động
• Make Test Pro sinh test tự động cho các ngôn ngữ Scratch, Python, C++, Pascal
• Giải đề thi Tin học trẻ Tiểu học các địa phương (Private)
• Video hướng dẫn sử dụng Rover của Yolo:bit
• PyGame: Bạn Trẩu thoát khỏi sự truy đuổi của lũ rô bốt
• CS 102 - PyGame nâng cao - STEAM for Vietnam
• CS 101 - Python và PyGame cơ bản - STEAM for Vietnam

Tìm kiếm

Search ...

Bài toán đổi tiền

Published: 12 June 2017 | Hits: 9520

Đề bài: Ở đất nước Omega người ta chỉ tiêu tiền xu. Có N loại tiền xu, loại thứ i có mệnh giá là ai đồng. Một người khách du lịch đến Omega du lịch với số tiền M đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiện tiêu dùng. Ông ta cũng muốn số đồng tiền đổi được là ít nhất (cho túi tiền đỡ nặng khi đi đây đi đó). Bạn hãy giúp ông ta tìm cách đổi tiền.

Mời các bạn download tại: Click here

const fi = 'DOITIEN.INP'; fo = 'DOITIEN.OUT'; MAXN = 10000; MAXW = 1000; oo = MAXINT div 2; var f: text; n, m: integer; a: array[1..MAXN] of integer; L: array[0..MAXN, 0..MAXW] of integer; //L[i, j] la so dong tien khi doi procedure Nhap; var i: integer; begin assign(f, fi); reset(f); readln(f, n, m); for i:= 1 to n do readln(f, a[i]); close(f); end; function min(a, b: integer): integer; begin if a < b then exit(a) else exit(b); end; procedure QHD; var i, j: integer; begin for i:= 0 to n do L[i, 0]:= 0; for j:= 1 to m do L[0, j]:= +oo; // L[0, 0] = ? for i:= 1 to n do for j:= 1 to m do begin L[i, j]:= L[i-1, j]; if a[i] <= j then L[i, j]:= min(1 + L[i, j-a[i]], L[i-1, j]); end; end; procedure TruyVet(i, j: integer); var t:integer; begin if i = 0 then exit; if j = 0 then exit; if j >= a[i] then begin if L[i, j] = 1 + L[i, j-a[i]] then // Chon loai tien thu i begin TruyVet(i, j-a[i]); writeln(f, 'chon loai tien ', i, ' menh gia la ', a[i]); end else TruyVet(i-1, j); end else // Khong chon loai tien thu i TruyVet(i-1, j); end; procedure InKQ; var i, j:integer; begin assign(f, fo); rewrite(f); if L[n, m] = +oo then writeln(f, 'khong co cach doi') else begin writeln(f, L[n, m]); TruyVet(n, m); end; close(f); end; BEGIN Nhap; QHD; InKQ; END.

Category: Mã nguồn các thuật toán điển hình

Danh mục bài viết

• Lập trình Pascal
• Lập trình C / C++
• Lập trình Java
• Lập trình Python
• Lập trình Scratch
• Robotics
• Thiết kế Web
• Mã nguồn các thuật toán điển hình
• SGK theo CTr GDPT mới
• Tin học thường thức

Đọc NHIỀU nhất

• Các kiểu dữ liệu số nguyên, số thực thường dùng trong Free Pascal
• Tiện ích sinh test tự động cho phần mềm chấm điểm tự động Themis của TS. Lê Minh Hoàng
• Hướng dẫn cài đặt Phần mềm chấm điểm tự động môn Tin học trên mạng LAN nội bộ hoặc Internet (Themis Web)
• Mảng 2 chiều trong Python
• Chuyển đổi ngôn ngữ sang tiếng Anh trên Winrar

Phần mềm

• Phần mềm tự viết
• Phần mềm thương mại

Thiết kế bởi Thủ khoa Nguyễn Tô Sơn.