Bài tập liệt kê dãy nhị phân độ dài n bằng C/C++

Bài tập liệt kê dãy nhị phân độ dài n bằng C/C++

Liệt kê dãy nhị phân độ dài n.

Viết dãy nhị phân dưới dạng b1b2..bn, trong đó bi∈{0, 1 }. Xem mỗi dãy nhị phân b=b1b2..bn là biểu diễn nhị phân của một số nguyên p(b). Khi đó thứ tự hiển nhiên nhất có thể xác định trên tập các dãy nhị phân là thứ tự từ điển được xác định như sau:

Ta nói dãy nhị phân b = b1b2..bn đi trước dãy nhị phân b’ = b’1b’2..b’n theo thứ tự từ điển và kí hiệu b<b’nếu p(b) <p(b’).

Ví dụ với n=4, các xâu nhị phân độ dài 4 được liệt kê theo thứ tự từ điển là:

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

Như vậy, dãy đầu tiên là 0000 dãy cuối cùng là 1111. Nhận xét rằng, nếu xâu nhị phân chứa toàn bít 1 thì quá trình liệt kê kết thúc, trái lại dãy kế tiếp sẽ nhận được bằng cách cộng thêm 1(theo modul 2 có nhớ) vào dãy hiện tại.

Từ đó ta nhận được qui tắc sinh kế tiếp như sau:

  1. Tìm i đầu tiên từ phải xang trái (i=n, n-1,..,1) thoả mãn bi =0.
  2. Gán lại bi =1 và bj=0 với tất cả j>i. Dãy thu được là dãy cần tìm.

Ví dụ ta có xâu nhị phân độ dài 10: 1100111011. Ta có i = 8, ta đặt b8 =1, b9,b10 =0 ta được xâu nhị phân kế tiếp: 1100111100.

Thuật toán sinh kế tiếp được mô tả trong thủ tục sau:

#include<iostream>

using namespace std;

int n = 4;

int* arr;

bool nextBinary(int* arr){

 // in mảng.

 for(int j=0;j<n;j++){

  cout<<arr[j]<<" ";

 }

 cout<<endl;

 //sinh mảng binary kế tiếp

 int index = n -1;

 while(arr[index]==1 && index >= 0) index--;

 //mảng binary cuối cùng -> return false.

 if(index == -1) return false;

 arr[index] = 1;

 for(int i=index+1;i<n;i++){

  arr[i]=0;

 }

 return nextBinary(arr);

 

}

int main(){

 freopen("BINARY.OUT","w",stdout);

 //init first binary array.

 arr = new int[n];

 for(int i=0;i<n;i++){

  arr[i]=0;

 }

 nextBinary(arr);

 return 0;

}
Bạn thấy bài viết này như thế nào?: 
Average: 1.5 (2 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Hoa hậu Tiểu Vy muốn làm diễn viên

Phụ nữ có kinh tế tốt thần thái tốt sẽ hấp dẫn nhiều đàn ông kém tuổi hơn

Thực tế cho thấy, phụ nữ 'có kinh tế' tốt, thần thái tốt sẽ hấp dẫn nhiều đàn ông kém tuổi hơn.

Bán con bò nào ngân hàng siết nợ luôn thì làm sao sống nổi

Bán con bò nào ngân hàng siết nợ luôn thì làm sao sống nổi

Được biết, sau khi bàn bạc nhiều phương án và đi đến quyết định cuối cùng, tại ĐHĐCĐ bất thường diễn ra vào ngày 8/1/2021

Biểu phí chương trình truyền thông - khảo sát và tôn vinh thương hiệu quốc gia 2019

Biểu phí chương trình truyền thông - khảo sát và tôn vinh thương hiệu quốc gia 2019

Mời tham dự buổi Lễ Công bố, truyền thông và Vinh danh “Thương hiệu Mạnh quốc gia” và “Doanh nghiệp - Doanh nhân xuất sắc” được truyền hình trực tiếp (THTT) trên HTVI

Tomdesgin.vn

 

Drupal Services