02/10/2018, 15:06
[C++ Quay lui] Liệt kê hoán vị các số từ 1 đến n
Cho một tập hợp gồm n phần tử có giá trị từ 1 đến n. Yêu cầu xuất ra các hoán vị của tập hợp này theo thứ tự tăng dần. Dữ liệu đầu vào: số nguyên dương n (n<10) Dữ liệu đầu ra: gồm n! dòng ghi các hoán vị theo thứ tự tăng dần, mỗi phần tử của tập hợp ngăn cách nhau bởi khoảng ...
Cho một tập hợp gồm n phần tử có giá trị từ 1 đến n. Yêu cầu xuất ra các hoán vị của tập hợp này theo thứ tự tăng dần.
Dữ liệu đầu vào: số nguyên dương n (n<10)
Dữ liệu đầu ra: gồm n! dòng ghi các hoán vị theo thứ tự tăng dần, mỗi phần tử của tập hợp ngăn cách nhau bởi khoảng trắng.
Ví dụ:
Input: 3
Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Code tham khảo
#include <iostream>
using namespace std;
int n, kq[11], dd[10];
void xuat()
{
for (int j=1; j<=n; j++)
cout<< kq[j]<<" ";
cout << endl;
}
void backtrack(int i)
{
if (i>n) xuat();
for (int j=1; j<=n; j++)
if (dd[j]==0)
{
dd[j]=1;
kq[i]=j;
backtrack(i+1);
dd[j]=0;
}
}
int main()
{
cin >> n;
for (int i=1; i<=9; i++)
dd[i]=0;
backtrack(1);
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <iostream> using namespace std; int n, kq[11], dd[10]; void xuat() { for (int j=1; j<=n; j++) cout<< kq[j]<<" "; cout << endl; } void backtrack(int i) { if (i>n) xuat(); for (int j=1; j<=n; j++) if (dd[j]==0) { dd[j]=1; kq[i]=j; backtrack(i+1); dd[j]=0; } } int main() { cin >> n; for (int i=1; i<=9; i++) dd[i]=0; backtrack(1); } |
