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: 2 (1 vote)
Ả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: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
www.processing.org: Ngôn ngữ lập trình Processing

www.processing.org: Ngôn ngữ lập trình Processing

Processing là một ngôn ngữ lập trình hiện đại( ra đời năm 2001) cho phép lập trình các ứng dụng đồ họa trên môi trường Window, Linus, Mac Android và cả Web. Nếu bạn đã học C thì bạn có thể tự học Processing rất dễ dàng. Định dang một tập tin Processing là *pde

Why we're skipping upgrading to Drupal 7

Tại sao chúng ta skipping upgrading to Drupal 7

This website was created using Drupal 6. Normally Drupal sites get upgraded to each new major version. This can be complex, but manageable with an upgrade path one can follow

Drupal 8 Module Development, Phần 3 - viết Plugins

As with any new version of Drupal, a number of contributed modules will be refactored, and pulled into core.