01/10/2018, 15:34
Đổi tiền bằng backtracking
Mình muốn liệt kê các cách đổi tiền bằng các tờ VND có sẵn. Input là tiền cần đổi
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <conio.h>
int VND[9] = { 1,2,5,10,20,50,100,200,500 };
int t = 8;
void doiTienLe(int tien, int tienle)
{
tienle = VND[t];
if (tienle == VND[0])
printf(" %d
", tien * 1000);
else
{
for (int i = 0; i <= tien / tienle; i++)
{
if (i == 0)
continue;
printf("%d * %d +", tienle * 1000, i);
t--;
doiTienLe(tien - tienle * i, VND[t]);
t++; //quay lui
}
}
}
int main()
{
printf("Nhap vao so tien muon doi: ");
int tien;
scanf("%d", &tien);
doiTienLe(tien / 1000, VND[t]);
_getch();
return 0;
}
Trên là code của mình, nhưng chạy không ra kết quả mong muốn
Mn người góp ý giúp mình với ạ
Bài liên quan
YĐây là code biểu diễn 1 số dương theo 1 hệ sinh gồm các phần tử dương của mk. (C#)
Dựa vào n là triển khai được bài kia.
Ví dụ input:
N= 4
Hệ sinh: 1 3 5 7
Số cần biểu diễn m=8
Output:
8=81
8=13 + 1*5
…
Vân vân
http://codepad.org/2z6DtlqE
Code bạn mình không hiểu lắm
mình vẫn chưa học tới.
Bài này mình muốn dùng đệ quy quay lui để giải
Cái của mình dùng quay lui mà.
Ý tưởng:
m là tiền cần biểu diễn
Mảng x chứa hệ sinh (chứa các giá trị tiền có thể đổi)
Mảng tong chứa tổng giá trị khi đã lựa chọn tới bước thứ i,Tức là giả sử lần 1 chọn x1,lần 2 chọn x2…
Thì lần i tổng giá trị tiền đã chọn là x1+x2+… +xi,mục đích mảng này là để đánh giá xem còn chọn được bao nhiêu tiền nữa để đủ.
Mảng appear là số lần xuất hiện của tiền có giá trị x[i] ở kết quả.Tức là số lần đã chọn tiền ấy.
// item “truoc” là để xác định xem lần trước đã chọn tới x mấy rồi,giả sử lần trước chọn tới x2 thì truoc là 2,mục đích là để tránh sự lặp lại ở kết quả (có thể xóa truoc đi test là thấy nếu khó hiểu)
static void SelectItem(int i, int truoc)
{
int j;
// Nếu ở lần chọn trước mà tổng giá trị chọn đã bằng m thì xuất dữ liệu
if (tong[i - 1] == m)
Result();
// Còn không thì tiếp tục chọn
else
{
for (j = truoc; j <= n; j++)
{
// Nếu đồng tiền x[j] định chọn thỏa mãn không vượt quá số lượng tiền đang còn thiếu
if (m - tong[i - 1] - x[j] >= 0)
{
// Chọn x[j] --> tăng số lượng đồng tiền x[j] lên
appear[j]++;
// Cập nhật giá trị mảng tổng
tong[i] = tong[i - 1] + x[j];
// Tiếp tục chọn lần thứ i +1 ,đánh dấu là đang chọn tới đồng tiền x[j] có chỉ số là j
SelectItem(i + 1, j);
// Quay lui lại thì trả appear về giá trị cũ
appear[j]–;
}
}
}
Chắc là dòng này rồi.