Giúp đỡ về in xâu nhị phân!

Discussion in 'Xây dựng ứng dụng chạy console, applet' started by Ck-boy, 23/1/13.

  1. Ck-boy

    Ck-boy New Member

    Mình có 1 bài toán: liệt kê tất cả các xâu nhị phân độ dài n.
    Mình làm theo hướng:
    - Với n = 0, in ra 2 chuỗi "0", "1".
    - Với n = 1, thêm "0" hoặc "1" vào đầu các xâu tương ứng với n = 0 để tạo ra các xâu mới: "00", "01", "10", "11".
    ...
    - Với n = k, thêm "0" hoặc "1" vào đầu các xâu tương ứng với n = k - 1 để tạo ra các xâu mới.
    Mình ko viết dc giải thuật cho suy nghĩ này. Mong các bạn giúp đỡ.
    Thanks all !
  2. monday0rsunday

    monday0rsunday Active Member

    cái này thì ko phức tạp lắm. bạn cần in các dãy số từ
    00...0 (n số 0) --> 11...1 (n số 1)
    nếu chuyển mỗi dãy nhị phân thành 1 số thập phân thì bạn cần in từ 0--> 2 mũ n -1
    Do đó tư tưởng ở đây sẽ là bạn in các dãy ứng với số thập phân tăng dần.
    00..000, 00..001, 00...010, 00.011, .... 11...111
    Thuật toán: dùng 1 vòng lặp in các dãy n số ứng với số thập phân 0,1,2,..,x,x+1,...,(2 mũ n-1)
    Giả sử bạn đang in số x, ứng với dãy xxxxxxxxxxx, khi đó, bạn muốn in số x+1 thì bạn làm như sau: cộng nhị phân với 1, cộng nhị phân giống như cộng thập phân thôi.
    mô tả ví dụ(5 chữ số), giả sử có : x=10011
    bạn sẽ duyệt chữ số từ phải qua trái, nếu gặp 1, thì bạn lật số đó thành 0, duyệt tiếp. nếu gặp 0, bạn lật số đó thành 1 và dừng lại. khi đó bạn có số x+1
    ta bắt đầu:
    chữ số cuối cùng là 1 --> lật sang 0, tiếp
    chữ số trước cuối cùng là 1 --> lật sang 0, tiếp
    chữ số ở giữa là 0--> lật sang 1, dừng.
    và số bạn thu được sẽ là 10100
    thuật toán cứ áp dụng như thế đến maxium
    Duoi day la code minh viet, do dang cai lai window nen minh chua chay thu
    Code:
    // in day so ra man hinh
    public void println(byte[] cs){
        if(cs!=null){
            for(int i=0;i<cs.length;i++){
                System.out.print(cs[i]);
            }
        }
        System.out.println();
    }
    // liet ke tat ca day so 0,1 do dai n
    public void list(n){
        if(n>0){
            byte[] seq = new byte[n];
            for(int i=0;i<n;i++){
                seq[i] = 0;
            }
            int i=n-1;
            // moi vong lap la 1 lan tinh so moi
            while(i!=-1){
                i = n-1;
                println(seq);
                // moi vong lap la 1 lan duyet tu phai sang trai cho den khi gap so 0
                // khi seq = {1,1,1,....,1,1} thi i se bi giam xuong -1, chuong trinh se dung lai vi (while(i!=-1))
                while(i>=0 && seq[i]!=0){// minh vua sua lai thu tu, phai cho i>=0 dung truoc, neu ko ArrayIndexOutOf....
                    seq[i] = 0;// lat 1 --> 0
                    i--;
                }
                if(i>=0)
                    seq[i] = 1;// lat 0 --> 1
            }
        }
    }
    
    minh vua sua lai code, doi lai vi tri i>=0, neu khong khi i=-1 thi seq se khong ton tai, va xay ra loi ArrayIndexOutOf....
    Vinh Phat and Ck-boy like this.
  3. Joe

    Joe Moderator

    Hi ck-boy
    The way MondayOrSunday described works best with a recursive method. Sorry that I don't spoonfeed you with a snippet :D
    Ck-boy likes this.
  4. nguyenson197

    nguyenson197 Member

    PHP:
    /**
    *
    * @author NguyenSon
    */
    public class NhiPhan {
        static 
    int x[] = new int[30];
        static 
    void deQuy(int iint n) {
            for (
    int k 0<= 1k++) {
                
    x[i] = k;
                if (
    == 1) {
                    for (
    int j 0nj++) {
                        
    System.out.print(x[j]);
                    }
                    
    System.out.println("");
                } else {
                    
    deQuy(1n);
                }
            }
        }
        static 
    void nhiPhan(int n) {
            
    deQuy(0n);
        }
        public static 
    void main(String[] args) {
            
    nhiPhan(4);
        }
    }

    output:
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    0111
    1000
    1001
    1010
    1011
    1100
    1101
    1110
    1111
    Ck-boy likes this.
  5. monday0rsunday

    monday0rsunday Active Member

    @Joe: cách mình nêu ko cần phải dùng đến đệ quy, 2 vòng for, 1 vòng để duyệt từ 1-->n (có thể thay bằng vòng while, để tránh tràn số khi n lớn, khi đó chỉ việc kiểm tra chỉ số lật quay lui về vị trí index 0 mà chưa kết thúc là được), 1 vòng để lật số như trên
    đệ quy được cái ngắn gọn mạch lạc nhưng cực tốn bộ nhớ , vì thế ko nên dùng đệ quy khi có thể ko dùng, hoặc dùng khi cảm thấy đệ quy tối ưu hơn so với ko đệ quy
    PS: sao bạn ko viết tiếng việt nhỉ?
    Ck-boy likes this.
  6. Joe

    Joe Moderator

    MondayOrSunday,
    I am a whitey:)and my girlfriend is an American Vietnamese. She taught me to speak and read Vietnamese but not how to write Vietnamese because of the weird accents and strange grammar ;) I don't understand all the postings here. For example, you wrote "sao bạn ko viết tiếng việt nhỉ? " What is KO? I guess CO (to have or an aunt?)
    Well, to your question: Your question touches a very thorny point. Optimal code or beautiful code is not only the question of taste but a religious belief. Nguyenson's recursive method deQuy() is fine. Dot!
    Ck-boy likes this.
  7. monday0rsunday

    monday0rsunday Active Member

    nếu thế thì bạn rất giỏi tiếng Việt đó. "ko" là mình viết tắt của "không", cũng như tiếng Anh "good night" bạn viết là "g9"
    Ck-boy likes this.
  8. Joe

    Joe Moderator

    Ahhhhh:)) Thanks a lot. It's because my parents are from different nations. My father is French, my mother is German, I was born in San Diego and fall in love with an American Vietnamese...Dad in French, mom in German, outside in English, with girlfriend in broken Vietnameseb-) g9? Gosh! Where did you grasp this "language"?
    Ck-boy likes this.
  9. anhdiepmmk

    anhdiepmmk Member

    Code:
    /*
    * To change this template, choose Tools | Templates
    * and open the template in the editor.
    */
    package algorithms;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    /**
    *
    * @author anhdiepmmk
    */
    public class Algorithms {
    
        private static int[] mangNhiPhan;
        private static int n;
    
        /**
        * @param args the command line arguments
        */
        public static void main(String[] args) throws IOException {
            // TODO code application logic here
     
            System.out.print("Mời nhập n: ");
          n = Integer.parseInt(br.readLine());
    
            mangNhiPhan = new int[n];
    
            nhiPhan(0);
     
        }
    
        /**
        * In mảng 1 chiều ra màn hình
        *
        * @param array mảng muốn in ra
        */
        private static void xuat(int[] array) {
            for (int i = 0; i < array.length; ++i) {
                System.out.print(array[i] + " ");
            }
            System.out.println();// Xuống dòng
        }
        private static void nhiPhan(int i) {
            for (int j = 0; j <= 1; ++j) {
                mangNhiPhan[i] = j;
                if (i == n - 1) {
                    xuat(mangNhiPhan);
                } else {
                    nhiPhan(i + 1);
                }
            }
        }
    
    }
    
    Ck-boy likes this.
  10. Vinh Phat

    Vinh Phat New Member

    Mình chưa hiểu thuật toán quay lui này lắm, Ck-boy bạn có thể giải thích cho mình một lần nữa được không.
    Cám Ơn Bạn :(
  11. nguyenson197

    nguyenson197 Member

    Show code được không monday0rsunday
    Ck-boy likes this.
  12. Ck-boy

    Ck-boy New Member

    Tks all!!!
    Mình chưa hiểu rõ thuật toán quay lui lắm, cũng có code rồi, code giống của 2 bạn nguyenson197 với cả anhdiepmmk đấy, nhưng đọc ko hiểu được thuật toán của nó là như nào :(
    @mondayOrsunday: đọc phần giải thích trong bài của bạn thấy sáng ra nhiều rồi :D, cảm ơn nhiều.

Chia sẻ trang này