Thuật toán tìm tất cả các phương án đổi tiền 3 loại giấy bạc

#1

Cần có tổng 200.000 đồng từ 3 loại giấy bạc 1.000Đ, 2.000Đ, 5.000Đ. Lập chương trình để tìm ra tất cả các phương án có thể
em chưa hình dung ra thuật toán để xây dựng chương trình

1 Like
#2

x+2y+5z = 200 bài này cho chạy theo z, rồi đến y, cuối cùng tính x.

</thread>

4 Likes
#3

em muốn xây dựng một giải thuật mà em chưa hình dung ra các bước xây dựng lên một giải thuật hoàn chỉnh ạ???!:slight_smile: :clipboard:

#4

Bạn sử dụng thuật toán quay lui với 3 vòng for lồng nhau nhé

#5

Số loại đã biết trước là 3 thì 2 for thôi.

1 Like
#6

3 vòng lặp, mỗi vòng chạy từ 1 đến mệnh giá đó đạt 200k, chắc chạy tới mùa mít nhưng cũng ra đáp án, cái này là vét cạn.

2 Likes
#7

Chia xuống cho 1000 =)

Còn x thì trừ ra thôi.

#8

Tôi dám cá 2 vòng lặp không vét hết nổi kết quả. Đừng có ăn gian 2 trong 1 nha.

1 Like
#9

Vòng i duyệt số tờ 5k, vòng j duyệt số tờ 2k, rồi lấy 200 - 5i - 2j thì ra số tờ 1k :smiley:

2 Likes
#10

ý tưởng được nhưng chưa cover hết case. code js đây. có 2081 khả năng tất cả `
var result = [];
var total = 200000;

for(var i = 0 ; i < 41; i++){
var qty5k = i;
var qty2k = 0;
while (qty2k * 2000 + qty5k * 5000 <= total) {
let qty1k = (total - qty2k * 2000 - i * 5000) / 1000;
result.push({‘5000d’: qty5k, ‘2000d’: qty2k, ‘1000d’: qty1k});
qty2k++;
}

}
console.log(result)`

3 Likes
#11

Không ai giải bài tập hộ bạn đâu.

1 Like
#12

:smile: . Thua tụi nhỏ rồi :smile:

#13

vét hết chứ, http://rextester.com/AQE90089

#include <iostream>

int main()
{
    int count = 0;
    for (int i = 0; i <= 40; ++i)
        for (int j = 0; j <= 100; ++j)
            if (5*i + 2*j <= 200)
            {
                std::cout << i << " tờ 5000, " << j << " tờ 2000, " << 200 - 5*i - 2*j << " tờ 1000.\n";
                count++;
            }
    std::cout << count << "\n";
}

in ra 2081 cách luôn mà.

#14

4 Likes
#15

200k từ 3 loại giấy bạc thì từng loại phải xuất hiện ít nhất 1 lần trong phương án chứ. Sao tính cả trường hợp 0 (Zero) cho bất kỳ loại nào trong 3 loại vào được.

#16

Ban đầu mình cũng nghĩ thế =))

Chừng nào ghi “bằng cả ba loại” thì mới vậy.

#17

Nếu theo công thức như post 2, thì vấn đề là tìm nghiệm nguyên dương của pt bậc nhất, mình nhớ là có 1 thuật toán để tìm ra 1 nghiệm cơ sở, từ đó tìm các nghiệm còn lại.
Pt bậc nhất 3 ẩn có thể đơn giản về 2 ẩn, mà 2 ẩn thì có cái thuật toán đâu đó mà mình quên rồi, để đi tìm xem.

#18

Đây rồi https://en.wikipedia.org/wiki/Diophantine_equation
Và https://vi.wikipedia.org/wiki/Giải_thuật_Euclid_mở_rộng
Vấn đề của thớt là Linear Diophantine equations, link trên có trình bày cách giải luôn.

1 Like
#19

Mình thấy có x = 3z (mod 5) và x = y (mod 3).

Giải bằng CRT thì 5u+3v = 1 => u=2 (mod 3) và v=2 (mod 5). Chọn (-1, 2) thì x ở trên bằng 18z - 5y (mod 15) hay 3z - 5y.

#20 
Random ahjhj = new Random();
x=ahjhj.Next(1,201);
y=ahjhj.Next(1.201);
z=ahjhj.Next(1.201);

Kiểu gì cũng ra…

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?