Chương trình cài đặt bằng đệ quy quay lui.
//chương trình sẽ liệt kê tất cả các hoán vị của tập X={1,2,3,4} bằng phương pháp đệ quy quay lui. //Kết quả của chương trình sẽ được ghi ra file HOANVI.OUT #include<iostream> using namespace std; #define n 4 //Định nghĩa tập X gồm 4 phần tử X = {1,2,3,4} int arr[n+1][2];//giá trị của arr[k][0] là mảng chứa các phần tử của mảng X (1 <= k <= n+1) //giá trị của arr[k][1] là biến đánh dấu phần tử đó đã xuất hiện trong hoán vị hay chưa (1 <= k <= n+1) int permute[n+1];// mảng 1 chiều ghi kết quả của các lần hoán vị. void toPermute(int index){ if(index > n){// nếu chỉ số trong bước lặp đệ quy lớn hơn n -> in ra kết quả hoán vị. for(int i=1;i<=n;i++){ cout<<permute[i]; if(i<n)cout<<","; } cout<<endl; return; } //Đệ quy để sinh ra hoán vị tiếp theo. for(int i=1;i<=n;i++){ if(arr[i][1] == false){// kiểm tra phần tử i của tập X chưa xuất hiện trong hoán vị permute[index] = arr[i][0]; arr[i][1] = true; toPermute(index+1); arr[i][1] = false; } } } int main(){ freopen("HOANVI.OUT","w",stdout); for(int i=1;i<=n;i++){ arr[i][0] = i; arr[i][1] = false; } toPermute(1); return 0; }Output của chương trình
1,2,3,4 1,2,4,3 1,3,2,4 1,3,4,2 1,4,2,3 1,4,3,2 2,1,3,4 2,1,4,3 2,3,1,4 2,3,4,1 2,4,1,3 2,4,3,1 3,1,2,4 3,1,4,2 3,2,1,4 3,2,4,1 3,4,1,2 3,4,2,1 4,1,2,3 4,1,3,2 4,2,1,3 4,2,3,1 4,3,1,2 4,3,2,1
0 Comment to "[Bài toán] Liệt kê tất cả các hoán vị của n phần tử."
Post a Comment