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

 
Google+ ra mắt tính năng chat circles

Google+ ra mắt tính năng chat circles

Tính năng chat circles vừa được Google+ cho ra mắt ngày 18/11/2011. Theo Google, việc ra mắt này nhằm làm phương thức chat Google dễ dàng với người dùng hơn.

Hướng dẫn hoàn chỉnh tạo Custom Post Types trong Wordpress

Hướng dẫn hoàn chỉnh tạo Custom Post Types trong Wordpress

WordPress has been gaining a foothold in the general content management system (CMS) game for a few years now, but the real breakthrough was the custom post type mechanism which allows for the creation of a wide variety of content

Apple thua kiện 5 triệu USD vì xâm phạm bằng sáng chế

Apple thua kiện 5 triệu USD vì xâm phạm bằng sáng chế

Theo thông tin từ công ty Elan Microelectronics biết, Apple sẽ phải trả 5 triệu USD để giải quyết đơn kiện của hãng vì vi phạm bằng sáng chế cho công nghệ cảm ứng đa điểm.

Công ty diệt chuột T&C

 

Diet con trung