01/10/2018, 08:46
Hỏi thuật toán bài toán tìm tổng số cách đổi tiền có thể được
.
Mình có đề về bài toán ATM và dùng for để tìm ra số cách rút nhưng bị giới hạn thời gian hết 50%. Mạo muội đăng lên hỏi mọi người có cách nào để nó chạy nhanh hơn ko ạ :((
P.s: m20 m50 m100 m200 m500 tương ứng với số tiền 20k, 50k, 100k, 200k, 500k ạ. Em gán sẵn vậy cho nó ngắn ^^
int SoCach(int n)
{
int dem = 0;
for (int a = 0; a <= n / m20; a++)
for (int b = 0; b <= n / m50; b++)
for (int c = 0; c <= n / m100; c++)
for (int d = 0; d <= n / m200; d++)
for (int f = 0; f <= n / m500; f++)
if (a*m20 + b*m50 + c*m100 + d*m200 + f*m500 == n)
dem++;
return dem;
}
Bài liên quan
Phát triển thuật toán lên nhé:
https://daynhauhoc.com/t/help-thuat-toan-doi-tien-3-loai-giay-bac-tim-phuong-an-tat-ca/
Mình nghĩ là có thể quy về tìm nghiệm số tự nhiên của 50x + 20y + 10z + 5w + 2v = n
Cái này có thể cắt ra làm 2 phương trình:
50x + 20y + 10z = 10w và 10w + 5w + 2v = n
Rồi tìm cách giải tiếp như link ở trên, hoặc ở link này https://www.reddit.com/r/learnmath/comments/2zkmr8/number_theory_linear_diophantine_equations_on_3/ để tìm ra công thức nghiệm nguyên tổng quát, rồi bắt đầu khoanh vùng solution từ công thức đó với nghiệm số tự nhiên.
Mình thấy rằng nếu phương trình gốc có n variable thì công thức tổng quát sẽ phụ thuộc tiếp vào n - 1 variable, tính mệt thấy mồ, không biết có đường tắt không.
Bài này không có liệt kê nghiệm
http://diendan.congdongcviet.com/threads/t386516::bai-toan-quy-hoach-dong.cpp?p=890568#post890568
Các thánh trong đó dùng kí hiệu cao siêu quá, mình đọc chẳng ghi nhận được gì @@
Bài này dùng QHĐ mới ra cho test mảng dữ liệu 10^6 mảng mệnh giá 1000 mới fer
hì. Vấn đề là chỗ QHĐ đó anh ei. Mới năm nhất mà… Coi coi lơ tơ mơ chứ ko hiểu lắm… Nên ko dám chép code bừa bãi để nộp ạ.
Cùng 1 người hỏi bài này trên congdongcviet mà a E chĩ mong là có hướng lẹ hơn 5 dòng for này thôi. Chứ QHĐ hay Đệ Quy là thua. Ko dám chép vào vì chưa hiểu ngọn ngành
Chưa cần tới mấy khái niệm cao siêu các bác trên nói, bạn trả lời hộ mình 2 câu hỏi.
À…
Khác nhau chứ, làm ngược lại thì sẽ lợi dụng được kết quả của phép tính trước để ngắt sớm vòng for, hơn nữa nếu tinh ý thì sẽ thấy ngắt bỏ được hẳn 1 vòng lặp
À. Tức h là em chuyển lại chạy từ 500k trở về phải ko a??
Yep, mà nhớ ở mõi vòng for phải trừ dần số tiền đã đổi được, thêm code check ngắt sớm vòng for vì không phải lúc nào cũng có thể trả tiền được, ở vòng for trong cùng có thể bỏ vì chỉ còn đúng 1 mệnh giá cần đổi, chia lấy mod trực tiếp luôn cũng được, lúc này bạn sẽ thấy kết quả của phép tính trước được dùng lại, suy rộng ra cũng là kiểu quy hoạch động đấy
Yes. Em mới test chạy từ 500k rồi biến sau là 200k chạy đến n-a*500k (a là biến chạy của 500k)
Viết chưa sạch nước cản mà đụng vào bài dạng này thì khó cả cho bạn và người trả lời thật. Chủ đề này bên HSG sau khi bạn học quay lui chán chê rồi mới dạy đấy.
Hic.Em cũng đâu muốn đụng đâu anh ơi! BT trên trường cho thì phải làm để hiểu + có điểm thôi ^^
Cách này là nhanh nhất rồi vì giới hạn số tiền khá nhỏ nên không xơi mem nhiều, phù hợp với QHĐ (tức là chỉ cần vài nghìn bước truy cập mem). Để ý kết quả lên đến hàng triệu, nghĩa là phải hàng chục triệu phép tính được thực hiện để thử sai.
Mình đang hỏi chủ thớt để khai sáng thôi chứ bạn không cần phải thể hiện gì với mình đâu, mục tiêu vẫn là chủ thớt có thể tự làm được bài 1 cách tối ưu nhất với kiến thức mà chủ thớt đang có
Hic. Tính t2 t3 t4 sai à anh?
Chính xác phải là n - số tiền đã được đổi
VD: t2 = n - a500 - b 200
Ủa đâu anh. Thì ở trên em ghi ko có n- nhưng trong vòng lập ở đằng sau em vẫn để
VD như chạy từ 500k
Thì t1= a*500k
chạy b(200k)
Thì chạy từ 0 cho đến <=n-t1 rồi đó… Là vẫn trừ rồi