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 Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

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

 
Hướng dẫn thêm CSS Classes vào Blocks ở Drupal 8

Hướng dẫn thêm CSS Classes vào Blocks ở Drupal 8

The idea of Modular CSS really appeals to me, especially having worked on large complex sites with multiple front-end developers collaborating together

Điểm mặt ba đối thủ mới của iPad 2

Điểm mặt ba đối thủ mới của iPad 2

Những người sử dụng máy tính bảng sẽ có thêm 3 thiết bị mới để so sánh với iPad 2 trong mùa lễ hội này, trong đó có Asus Eee Pad Transformer, máy tính bảng đầu tiên được trang bị chip lõi tứ Tegra 3 mới nhất của Nvidia.

Kiểm soát côn trùng Ruồi - Dịch vụ Diệt Ruồi

Kiểm soát côn trùng Ruồi - Dịch vụ Diệt Ruồi

Các bệnh mà ruồi đóng vai trò lây nhiễm bao gồm bệnh qua đường tiêu hóa như lỵ trực trùng, lỵ amíp , tả, thương hàn, giun đũa

Wordpress Freelancer

 

Wordpress Freelancer