Thuật toán sinh nhị phân, tổ hợp, hoán vị cơ bản

Discussion in 'Trao đổi về thuật toán' started by kimcy1992, 21/5/13.

  1. kimcy1992

    kimcy1992 Active Member

    Chả là dạo này em có học lại giải thuật và Java nên trong quá trình làm bài có làm với một bài cơ bản về thuật toán sinh kế tiếp, từ một cấu hình ban đầu để sinh ra tiếp các cấu hình tiếp theo. Đây là thuật toán liệt kê điển hình. Mong muốn share cho mọi người, giúp bạn nào đang muốn tìm hiểu về nó, vì code theo giải thuật kiểu pascal nên trong vấn đề tối ưu hóa code là chưa đầy đủ, có gì mọi người cứ comment vào để em sửa ra bài viết tốt hơn a. Một điều nữa là em chỉ đưa code thôi a, ai muốn tìm thuật toán thì có thể search google là ra, cũng giúp nâng cao kỹ năng tìm kiếm luôn(nói thiệt có nhiều bạn có chả biết tìm kiếm nữa cơ lý do vẫn là key word). Xin cảm ơn mọi người đã xem. Nếu topic là linh tinh thì admin cứ xóa thẳng tay và không cần thông báo đâu ạ, cũng nhứ có thể ban nick cho em vài ngày cho nhớ đời.
    Đầu tiên là thuật toán sinh xâu nhị phân độ dài n.
    PHP:
    import java.util.Scanner;

    /**
    *
    * @author vanchung
    */
    public class SinhNhiPhan {
        private 
    int ina[];
        public 
    void Init() {
            
    Scanner input = new Scanner(System.in);
            do {
                
    System.out.print("Nhập vào độ dài xâu nhị phân > 0:");
                
    this.input.nextInt();
            } while ( 
    this.<= );

            
    = new int[n];
            for (
    int j 0nj++)
                
    a[i] = 0;
        }
    //hiển thị kết quả
        
    public void Result() {
            for (
    int j 0j++) {
                
    System.out.print(a[j] + "  ");
            }
            
    System.out.println();
        }
    //Sinh nhị phân
        
    public void GenerBinary() {
            do  {
                
    Result();  //In ra cấu hình hiện tại
                
    1;
                while(
    this.>= && a[i] == 1) --i;
                if (
    this.>= 0) {
                    
    a[i] = 1;
                    for (
    int j 1<j++) {
                        
    a[j] = 0;
                    }
                }
            } while (
    this.>= 0);

        }

        public static 
    void main(String[] agrs) {
            
    SinhNhiPhan generbinary = new SinhNhiPhan();
            
    generbinary.Init();
            
    generbinary.GenerBinary();
            
    System.gc();
        }
    }
    Thuật toán sinh tổ hợp châp k của n
    PHP:
    import java.util.Scanner;

    /**
    *
    * @author vanchung
    */
    public class ToHop {
        private 
    int inka[];

        public 
    void Init() {
            
    Scanner input = new Scanner(System.in);
            do {
                
    System.out.print("Nhập vào số phần tử n >=0:");
                
    this.input.nextInt();
                
    System.out.print("Nhập vào số tổ hợp  k <= n:");
                
    this.input.nextInt();
            } while (
    this.|| this.this.n);

            
    = new int[n+1];
            for (
    int j 1<= this.kj++)
                
    a[j] = j;
        }

        
    //Hiển thị kết quả
        
    public void Result() {
            for (
    int j 1<= kj++)
                
    System.out.print(a[j] + "  ");
            
    System.out.println();
        }
        
    //Sinh tổ hợp
        
    public void sinhToHop() {
            do {
                
    Result();
              
    this.this.k;
              while (
    this.&& a[i] == this.-this.i) -- i;
              if (
    this.0) {
                  
    a[i]++;
                  for (
    int j 1<= this.kj++) {
                      
    a[j] = a[j-1] + 1;
                  }
              }

            } while (
    this.!= 0);

        }
        public static 
    void main(String[] agrs) {
            
    ToHop tohop = new ToHop();
            
    tohop.Init();
            
    tohop.sinhToHop();
            
    System.gc();
        }
    }
    Thuật toán hoán vị n số
    PHP:
    import java.util.Scanner;

    /**
    *
    * @author vanchung
    */
    public class HoanVi {
        private 
    int ina[];
        
    //Khởi tạo
        
    public void Init() {
            
    Scanner input = new Scanner(System.in);
            do {
                
    System.out.print("Nhập vào số phần tử cần hoán vị:");
                
    input.nextInt();
            } while (
    <= 0);

            
    = new int[n+1];
            for (
    int j 1<= nj++) {
                
    a[j] = j;
            }
        }

        
    //Hiển thị kết quả
        
    public void Result() {
            for (
    int j 1<= nj++)
                
    System.out.print(a[j] + "  ");
            
    System.out.println();

        }
        
    //Sinh hoán vị
        
    public void sinhHoanVi() {
            do {
                
    Result();
                
    1;
                while (
    && a[i] > a[i+1]) --i;
                if (
    0) {
                    
    int k n;
                    while (
    a[k] < a[i]) --k//lùi dần từ cuối dãy để tìm phân tử đầu tiên lớn hơn x[i]
                    //đổi chỗ sau khi tìm thấy
                    
    int temp a[k];
                        
    a[k] = a[i];
                        
    a[i] = temp;
                        
    //Lật ngược đoạn cuối cùng
                    
    n;
                    for (
    int j 1j++, k--) {
                            
    temp a[j];
                            
    a[j] = a[k];
                            
    a[k] = temp;
                    }
                }
            } while (
    != 0);
        }
        public static 
    void main(String[] args) {
            
    HoanVi hoanvi = new HoanVi();
            
    hoanvi.Init();
            
    hoanvi.sinhHoanVi();
            
    System.gc();
        }
    }
    Thêm một giải thuật khớp chuỗi cổ nhất nhưng hầu như các phương pháp khác đều dựa trên nó như giải thuật KMP,... Đây là thuật toán dựa trên tư tưởng so sánh tuyến tính do vậy độ phức tạp của nó là O(n-m)*m) khá lớn so với KMP là O(n). Mình đang cố hiểu thật sự và hoàn thiện KMP nếu được sẽ post lên sau. :D
    PHP:
    /**
    *Thuật toán khớp chuỗi Naive_String_Matcher
    * @author vanchung
    */
    public class Naive_String_Matcher {
        public static 
    void main(String[] agrs) {
            
    String T "000010001010001";
            
    String P "0001";

            
    //So sánh khớp chuỗi
            
    int n T.length();
            
    int m P.length();
            
    boolean flag true;
            for (
    int s 0<= ms++) {
                
    flag true;
                for (
    int i 0mi++) {
                    if (
    P.charAt(i) == T.charAt(i))
                        
    flag true;
                    else {
                        
    flag false;
                        break;
                    }
                }
                if (
    flag)
                    
    System.out.println("Posittion of s:" s);
            }
        }
    }
    /** Kết quả
    *run:
    *Posittion of s:1
    *Posittion of s:5
    *Posittion of s:11
    */
    Tiếp theo mình xin bổ sung vào loạt thuật toán của mình. Lần này là giải thuật phân tích một số thành tổng các chữ số theo phương pháp vét cạn_quay lui. Ngoài ra còn có thể làm theo quy hoạch động nhưng mình vẫn là gà nên chịu
    PHP:
    import java.util.Scanner;

    /**
     *
     * @author vanchung
     */
    public class PhanTichTong {
        private 
    int t[], x[], n;
        
        public 
    PhanTichTong() {
            
    Init();  
        }
        
        public 
    void Init() {
            
    Scanner input = new Scanner(System.in);
            
    System.out.print("Nhập vào n:");
            
    input.nextInt();
            
    = new int[n+1];
            
    t[0] = 0;
            
    = new int[n+1];
            
    x[0] = 1;
            
        }
        
        public 
    int getValue() {
            return 
    n;
        }
        
        public 
    void printResult(int k) {
            for (
    int j 1kj++) {
                
    System.out.print(x[j] + " + ");
            }
            
    System.out.println(x[k]);
        }
        
        public 
    void Attemp(int i) {
            for (
    int j x[1]; <= (t[1])/2j++) { //Các giá trị x[i] có thể chọn
                
    x[i] = j;//Mảng chứa các giá trị tổng
                
    t[i] = t[i-1] + j//Mảng lưu trữ tổng
                
    Attemp(1);
            }
            
    //System.out.println("Giá trị của i là: " + i);
            
    x[i] = t[i-1];//Nếu x[i] là phần tử cuối thì buộc nó phải có giá trị
                
    printResult(i);
        }
        public static 
    void main(String[] args) {
            
    PhanTichTong pt = new PhanTichTong();
            
    System.out.println("Số cách phân tích " pt.getValue() + " thành tổng là:");
            
    pt.Attemp(1);
        }
        
    }
    Những thuật toán cơ bản này thật ra tìm trên google cả đống nhưng với code java em thấy ít trao đổi hay là em không biết mà toàn là mã pascal hay C&C++. Thôi có hay không thì em vẫn share, vì đâu phải ai cũng biết, biết nhưng lại không cài đặt được :D. Dốt nhưng cố code vậy được gì hay đấy :D.
    P/s Với những thuật toán thể này các bạn nên nhớ cho nhanh, đừng mất công phát minh lại cái bánh xe làm gì.

Chia sẻ trang này