Xu đã dùng
Số tiền đã tạo
Ít nhất có thể

    Đồng xu (¢)

      Tìm hiểu thêm về bài toán đổi tiền xu

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

      Cho vài loại đồng xu, làm sao trả đúng một số tiền bằng ít đồng xu nhất có thể, và có tất cả bao nhiêu cách để làm điều đó? Lời giải tham lam, lấy đồng lớn nhất trước, hiệu quả với tiền thật nhưng thất bại với một số bộ xu. Một bảng xây dựng mỗi số tiền từ các số tiền nhỏ hơn thì luôn cho kết quả đúng. Chạm vào một đồng xu trong khay để thêm nó lên quầy, và chạm vào một đồng xu trên quầy để lấy lại. Thanh đo đầy dần tới số tiền: hãy tạo đúng số tiền đó với càng ít xu càng tốt. Ít xu nhất cho thấy đáp án tốt nhất, còn Tham lam cho thấy kết quả khi luôn lấy đồng xu lớn nhất còn vừa, mà kết quả đó không phải lúc nào cũng ít nhất. Thay đổi các đồng xu (tính bằng cent) và số tiền trong bảng điều khiển. Chế độ xem Bảng cho thấy quy hoạch động tìm ra ít xu nhất, hoặc đếm số cách tạo số tiền, như thế nào: nhấn Phát để xem bảng được điền dần, hoặc Bước và Lùi để đi từng bước một, và kéo thanh trượt bước để nhảy tới bất kỳ đâu. Mỗi đồng xu có thể dùng bao nhiêu lần tùy thích. Khi bảng được chọn, các phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy tới đầu và cuối.

      Cách nó hoạt động

      1. Chạm vào các đồng xu trong khay để tạo đúng số tiền, và xem thanh đo đầy dần theo xu.
      2. Hãy cố dùng ít đồng xu nhất có thể, rồi nhấn Ít xu nhất hoặc Tham lam để so sánh.
      3. Mở chế độ xem Bảng và nhấn Phát để xem mỗi ô đọc số tiền nhỏ hơn mà nó phụ thuộc vào.

      Ít xu nhất

      Số tiền 0 không cần đồng xu nào. Với mỗi số tiền lớn hơn, thử từng đồng xu không lớn hơn nó: phần còn lại sau đồng xu đó là một số tiền nhỏ hơn, đã có trong bảng, nên thêm một đồng xu nữa cho ra một ứng viên. Ứng viên nhỏ nhất được ghi vào ô, và đồng xu tạo ra nó được lưu ở hàng bên dưới. Khi bảng đã đầy, các đồng xu được đọc ngược từ số tiền đích: lấy đồng xu cuối cùng của nó, chuyển đến số tiền còn lại, và lặp lại cho đến 0.

      Số cách

      Để đếm tổ hợp chứ không phải thứ tự, bảng thêm một đồng xu cho mỗi hàng. Một ô đếm số cách tạo số tiền của nó bằng các đồng xu tính đến hàng của nó: số cách không dùng đồng xu mới nhất, tức là ô phía trên, cộng với số cách dùng đồng xu mới nhất ít nhất một lần, tức là ô trên cùng hàng cách về bên trái số cột bằng mệnh giá đồng xu đó. Vì các đồng xu được thêm theo một thứ tự cố định, 1 + 2 và 2 + 1 là cùng một cách và chỉ được tính một lần.

      Câu hỏi thường gặp

      Vì sao phương pháp tham lam thất bại?

      Tham lam luôn lấy đồng xu lớn nhất còn vừa và không bao giờ xem xét lại. Với các đồng xu 1, 3 và 4 và số tiền 6, nó lấy 4, rồi 1 và 1: ba đồng xu, trong khi hai đồng 3 là đủ. Với những hệ tiền xu như euro hay đô la Mỹ, tham lam tình cờ lại tối ưu; những hệ như vậy được gọi là chính tắc.

      Đếm số cách khác với đếm số thứ tự như thế nào?

      Đếm cách coi 1 + 2 và 2 + 1 là cùng một tổ hợp; đếm thứ tự thì tính riêng từng cái. Ứng dụng đếm số cách bằng cách thêm các đồng xu từng hàng một. Còn để đếm thứ tự, ta đi qua các số tiền và thử mọi đồng xu cho mỗi số tiền.

      Thuật toán đổi tiền xu nhanh đến mức nào?

      Cả hai bảng đều mất số bước bằng số loại đồng xu nhân với số tiền. Như vậy là nhanh với số tiền cỡ hàng nghìn, nhưng một số tiền có thể là một số rất lớn, nên nếu đo theo số chữ số thì bài toán nói chung là NP-khó.

      Nếu một số tiền không tạo được thì sao?

      Ô của nó giữ nguyên ∞, ví dụ số tiền 1 và 3 với các đồng xu 2 và 5. Trong chế độ Số cách, giá trị của nó đơn giản là 0.

      Có dữ liệu nào được gửi đi đâu không?

      Không. Mọi thứ được tính toán trong trình duyệt của bạn, và các cài đặt gần nhất của bạn được lưu trong bộ nhớ cục bộ của trình duyệt này.

      Sẵn sàng thử chưa?

      Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

      Tới trình chỉnh sửa