Bài Tập Java Số 16: Liệt Kê Các Chuỗi Nhị Phân

Đề bài

Viết chương trình liệt kê tất cả chuỗi nhị phân có độ dài n.

Giải Thuật

Ta có 2ⁿ chuỗi nhị phân có độ dài n tương ứng với các số thập phân từ 0 đến 2ⁿ-1. Ta sử dụng phép biến đổi số thập phân sang số nhị phân để thực thi bài toán này. Phép biến đổi như sau ta chia số thập phân cho 2 thì số dư ta thu được sẽ bit của số nhị phân tương ứng. Sau đó tiếp tục lấy thương chia cho 2 tiếp. Khi nào thương bằng 0 thì ta dừng lại.

Code mẫu

package baitap16;

import java.util.Scanner;

public class baitap16 {

  public static void main(String[] args) {
    int n=0;
    Scanner nhap = new Scanner(System.in);
    System.out.println("Nhap do dai chuoi nhi phan");
    n = nhap.nextInt();
    while(n<=0)
    {
      System.out.println("Do dai phai là mot so nguyen duong. Nhap lai")
      n = nhap.nextInt();
    }
    int sochuoi = (int) Math.pow(2,n);
    for(int i=0;i<sochuoi;i++)
    {
      String s = "";
      int so = i;
      int bit;
      do
      {
        bit=so%2;
        so=so/2;
        s=bit+s;
      }while(so>0);
      int l=s.length();
      for(int j=0; j<n-l;j++)
      {
        s="0"+s;
      }
      if((i+1)%4!=0)
        System.out.print(s+", ");
      else
        System.out.print(s+"\n");   
   }
 }
}