Bài toán
Liệt kê tất cả các hoán vị của dãy số 1..n.
Độ phức tạp
O(n.n!)
Code này của Nguyễn Tiến Trung Kiên.
#include <stdio.h>
int n;
bool used[123];
int a[123];
void show() {
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
printf("\n");
}
void back(int pos) {
if (pos == n + 1) {
show();
return;
}
for (int i = 1; i <= n; i++)
if (not used[i]) {
a[pos] = i;
used[i] = true;
back(pos + 1);
used[i] = false;
}
}
int main() {
scanf("%d", &n);
back(1);
return 0;
}
Nhận xét
Mô tả
int a[]
mảng này chứa các phần tử đang được xây dựng.
void show()
in ra mảng a.
bool used[]
used[i]=true nếu giá trị i đã được sử dụng trước đó.
void back(int pos)
gọi hàm này với mục đích là đang đứng ở vị trí pos, cần đặt cho a[pos] một giá trị mà chưa được sử dụng, sau đó gọi lời gọi tới hàm back(pos+1).
Các lỗi thường gặp
Runtime error
- Do quên không xét trường hợp pos=n+1
- Do quên không return trong trường hợp pos=n+1.
Wrong answer
- Do thiếu mất lệnh used[i]=false, nhớ rằng sau khi gọi hàm back con, phải "undo" lại cái quyết định của mình.
- Do không kiểm tra điều kiện if (not used[i]).
Đánh giá
Các bạn có thể đánh giá bài viết, yêu cầu giải thích hoặc gửi nhận xét tại đây.
http://goo.gl/forms/NrDT889TkK