Hoan Vi [Archive] - Diễn Đàn Tin Học

Diễn Đàn Tin Học > Lập trình > Các vấn đề khác trong lập trình > Data Structures + Algorithms > Hoan vi PDA

View Full Version : Hoan vi

tranvu09-10-2005, 08:27Các bạn giúp mình giải bài này với cho mảng A[1..n] tìm tất cả hoán vị của nó. VD: A[1..3] 123 132 231 213 321 312 Cảm ơn nhiều ! Nếu có code càng tốt! duytanghostlake09-10-2005, 22:37Với bài toán Hoán vị. theo tôi có hai cách giải. Một cách giải bằng thuật toán đệ qui. Tôi xin trình bày cách giải thuất toán không đệ qui như sau : Giả sử chúng ta tìm tất cả các hoán vị của mảng A[1..n]. Ta sử dụng một mảng hv để lưu trữ một hoán vị của nó. sau khi tìm được một hoán vị của nó thì xuất ra màn hình hoặc lưu lại.Rồi tìm hoán vị khác. Thuật toán : - với phần tử thứ i của hoán vị hv[i], ta chọn cho một phần tử trong mảng a[1..n] và phần tử này phải chưa được trọn trước đó. sau khi chọn được phần tử hv[i] thì chuyển sang tìm phầu tử hv[i+1] cho đến khi hv[n] thì kết thúc. Sử dụng một mang kt[1..n] dùng để đanh dấu phần tử đã được chọn - ma3ng hv dùng để lưu lại một hoán vị của mảng A[1..n] bước 1 : nếu i = n thì xuất mảng hv ngược lại thì sang bước 2 bước 2 ; duyệt mảng A[1..n] j=1 2.aNếu kt[j] = true thì : hv[i] = a[i], kt[i] = false, tang i = i+1. chuyển sang bước 2 Nếu kt[j] = false thi j = j+1 - bước 2a 2.b { sau khi đã chọn được a[j] cho hv[i]. ta tiếp tục chọn phần tử khác kt[j] = true; Code : procedure try(i) { Nếu i=n+1 thì xuất hv ra màn hình ngược lại : for j=1 to n do if kt[j] = true then { hv[i] = a[j]; kt[j] = false; try(i+1) kt[j] = true } } Đoạn chương trình chỉ là mã giã thôi. Ngày mai tồi sẽ gởi toàn bộ code = C++ và Passcal. Ngoài ra còn có một cách khác nửa. Bửa sau tôi sẽ giới thiệu ( nếu rảnh ) TrongThaiVN09-10-2005, 22:45Chào bạn, Bạn thích sử dụng ngôn ngữ nào? nếu là Pascal thì tốt. Vấn đề sinh hoán vị nói chung là phải dùng đệ qui, hoặc nếu không thì chính là dạng khử đệ qui. Tôi muốn gửi một thuật giải đơn giản sử dụng mã giả ngôn ngữ Pascal như sau: var pt: array[1..max] of kieu // Mảng các phần tử. procedure swap(var a, b: kieu); begin { đổi chỗ 2 ptử a và b } end; procedure hoanvi(n: integer); var i: integer; begin if n <= 1 then begin { tìm được 1 hoán vị } end else begin for i := 1 to n do begin swap(pt[i], pt[n]); hoanvi(n-1); swap(pt[i], pt[n]); end; end; end; - Yêu cầu của thủ tục hoanvi(n): 1. Sinh ra tất cả các hoán vị của n phần tử từ pt[1]..pt[n]; 2. Khi kết thúc thủ tục, phải bảo tồn trạng thái mảng pt giống như lúc bắt đầu thủ tục. - Thủ tục được thiết kế trên đây khá đơn giản và dễ hiểu vì vận dụng theo cách mà công thức tính giai thừa thực hiện: n! = n * (n-1)!. Cách thực hiện như sau: + Lấy lần lượt từ vị trí i đặt vào vị trí n. + Kết hợp trạng thái này với tất cả các hoán vị của n-1 phần tử còn lại. - Dù vậy, thủ tục có vẻ không tối ưu do thực hiện 2 lần swap. Các bạn có thể tìm thấy các thuật giải tương tự trong cách sách có cách swap tối ưu hơn nhưng việc tính vị trí swap khá phức tạp. Tuy nhiên, việc tối ưu ở đây sẽ không mang lại nhiều lợi ích vì 2 nguyên nhân: + Tốc độ tính toán hiện nay là quá nhanh. + Tối ưu ở đây sẽ làm cho thuật giải trở nên quá khó hiểu, dễ dẫn đến lỗi và khó kiểm soát. Hy vọng là thuật giải trên hoạt động tốt. Chúc bạn thành công! tranvu10-10-2005, 03:37Thanks! cách thường dùng nhất có lẻ là cách của duytanghostlake Nếu mình ko lầm thì cách của TrongThai_VN là đệ quay lui phải ko. Theo như các bạn thì thuật toán tối ưu nhất để giải quyết vấn đề này là gì? TrongThaiVN11-10-2005, 01:14Ái chà, Cả hai cách đều là đệ qui cả. Còn đệ qui hay đệ qui quay lui thì cũng đều là một. Ở một khía cạnh nào đó thì cách của duytanghostlake có vẻ dễ hiểu hơn. Khi nào các bạn đã nghiên cứu xong độ phức tạp, các bạn sẽ nhận ra rằng cách của tôi có độ phức tạp O(n!) còn cách của duytanghostlake có độ phức tạp là O(n^n). Hiển nhiên O(n^n) > O(n!), mặc dù cả hai độ phức tạp này đều là rất lớn. Các bạn có thể tìm thấy các giải thuật sinh hoán vị khác cũng có độ phức tạp O(n!) nhưng có thứ tự sinh tương tự như trong ví dụ, tức là cách liệt kê kết quả giống như tự nhiên. tranvu11-10-2005, 03:32thanks a lot ! Minh hieu roi. Chi thay dung de qui hoi met thoi,vd neu n>1000 thi sao chắc tới năm sao no mới ra wa duytanghostlake13-10-2005, 22:25Bài toán hoán vị : Cách giải không đệ qui: Cách giải dựa trên giải thuật sau đấy : Đối với dãy hoán vị của N phấn tử A[1..n] ,t a thất đó là một dãy có thứ tự. Ví dụ : n=3, ta có dãy hoán vị sau : 123 132 213 231 312 321 Ta thấy các dãy số được sắp theo thứ tự tăng dần. Như vây , giả sử với một hoán vị cho trước (đã tìm được ), ta chỉ cần tìm số nhỏ hơn ( lớn hơn) nhưng là số lớn nhất (nhỏ nhất). Bài toán kết thúc khi ta không thể tìm số nhỏ hơn ( lớn hơn) với một hóan vị cho trước. Ví dụ; n = 3 , ta tìm được hoán vị :123 Vậy số lớn hơn 123 đồng thới là nhỏ nhất sẽ là :132 Tiếp tục như vậy ta có :132-->213-->231-->312-->321. từ 321 không thể tìm số nhỏ hơn nó. Bài toán kết thúc. Như vậy tới đây, chắc có lẻ bạn cũng đã hình dung ra cách giải bài toán Hoán vị không dùng đệ qui rồi phải không. Sau đây là thuật toán tổng quát : 1. Tìm điểm gãy: Duyệt ngược mảng a để tìm vị trí i đầu tiên thoả mãn a[i] > a[i+1]. 2. Xét điều kiện kết thúc: Nếu không tìm được chỉ số i như trên, tức là các chữ số của số đã cho xếp theo thứ tự giảm dần do đó a chính là số lớn nhất, sau nó không còn số nào có thể nhận được bằng một phép hoán vị được nữa. 3. Tìm điểm vượt: Ta tìm a[j] đầu tiên trong khoảng n..i để a[j]>a[i]. 4. Hoán vị: Hoán vị a[i] và a[j]. 5. Lật: Lật ngược đoạn a[i+1..n] sẽ thu được một hoán vị cấn tìm Code : C++ #include <iostream.h>; void doi_cho(int &a,int &b) { int tg; tg = a; a = b; b =tg; } void hoanvi(int a[],int n) { int j,i; /* for (int i=0;i<=n-2;i++) for (j=i+1;j<=n-1;j++) if (a[i]>a[j]) { doi_cho(a[i],a[j]); };*/ // hon vi dau tien for(i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl; bool kt = true; while (kt) { kt = false; for (int i=1;(i<n)&(kt==false);i++) if (a[i]<a[i+1]) kt=true; if (kt == true) { // tim diem gay j=n; while (a[j]>a[j+1]) j--; // tim diem vuot i = n; while (a[i]<a[j]) { i--; } doi_cho(a[i],a[j]); //lat nguoc doan a[i+1..n] j++; i=n; while (j<i) { doi_cho(a[i],a[j]); i--; j++; } // xuat ra man hinh mot hoan vi for(i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl; } } } void chuong_trinh() { int a[1000]; int n=4; for (int i=1;i<=n;i++) a[i] =i; a[0] = 1001; hoanvi(a,n); } main() { chuong_trinh(); } Code : Pascal const max = 100; var a:array[0..max] of integer; n : integer; procedure hoan_vi; var i,j,tg:integer; kt:boolean; begin kt:=true; a[0]:=max+1; n:=4; writeln('---------------------------------------------------'); for i:=1 to n do begin a[i]:=i; write(a[i],' '); end; writeln; while kt do begin kt:=false; for i:=1 to n-1 do if a[i]<a[i+1] then kt:=true; if kt then begin i:=n-1; while (a[i]>a[i+1])and(i>=1) do dec(i); j:=n; while (a[j]<a[i])and(j>=1) do dec(j); tg:=a[i]; a[i]:=a[j]; a[j]:=tg; inc(i); j:=n; while i<j do begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; i:=i+1; j:=j-1; end; for i:=1 to n do write(a[i],' '); writeln; end; end; end; begin hoan_vi; end. Powered by vBulletin® Version 4.2.0 Copyright © 2025 vBulletin Solutions, Inc. All rights reserved.