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

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>

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 ạ???!

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

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

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.

Chia xuống cho 1000 =)

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

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.

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

ý 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)`

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

. Thua tụi nhỏ rồi

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à.

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

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à.

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.

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

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

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.

Đâ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.

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.

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…

Đưa phương trình x + 2y + 5z = 200 vào trang này: http://mathafou.free.fr/exe_en/exedioph3.html
Được công thức x, y, z phụ thuộc vào 2 biến k,m.
x,y,z >= 0 từ đó suy ra những ràng buộc của k và m, dùng thuật toán cho chạy hết tất cả k, m và kiểm tra ràng buộc, đúng ràng buộc thì tính kết quả

Mình tính được thế này:
Nghiệm nguyên tổng quát: {x = 2k-m, y = 100-k-2m, z = m, k ∈ Z, m ∈ Z}
Do {x ≥ 0, y ≥ 0, z ≥ 0}
Suy ra {0 ≤ k ≤ 20, k mod 2 = 0, 0 ≤ m ≤ 2k}
Vậy có thể làm cái thuật toán kiểu này (javascript)

for (let k = 0; k <= 20; k += 2)
{
   for (let m = 0; m <= 2*k; m++)
   {
      // Tính x, y, z theo m và k
   }
}

diễn đàn có thêm tool tạo biểu thức toán học thì hay