[Bài toán] Liệt kê các xâu nhị phân độ dài n bằng thuật toán Back Track

Lý thuyết Back Track bạn có thể xem thêm ở đây.
     Biểu diễn các xâu nhị phân dưới dạng b1, b2,..., bn, trong đó bi∈{0, 1 }. Thủ tục đệ qui Try(i) xác định bi với các giá trị đề cử cho bi là 0 và 1. Các giá trị này mặc nhiên được chấp nhận mà không cần phải thoả mãn điều kiện gì (do đó bài toán không cần đến biến trạng thái). thủ tục Init khởi tạo giá trị n và biến đếm count. thủ tục kết quả in ra dãy nhị phân tìm được. Chẳng hạn với n =3, cây tìm kiếm lời giải được thể hiện như hình.

Chương trình cài đặt:

#include <stdio.h> 
#include <alloc.h> 
#include <conio.h> 
#include <stdlib.h> 
void Result(int *B, int n){
 int i;
 printf("\n ");
 for (i = 1; i <= n; i++)
  printf("%3d", B[i]);
}
void Init(int *B, int n){
 int i;
 for (i = 1; i <= n; i++)
  B[i] = 0;
}
void Try(int i, int *B, int n){
 int j;
 for (j = 0; j <= 1; j++){
  B[i] = j;
  if (i == n) {
   Result(B, n);
  }
  else Try(i + 1, B, n);
 }
}
void main(void){
 int *B, n; clrscr();
 printf("\n Nhap n=");
 scanf("%d", &n);
 B = (int *)malloc(n*sizeof(int));
 Init(B, n);
 Try(1, B, n);
 free(B);
 getch();
}

[Bài tập mẫu] Vẽ hình tròn.

[Bài tập] Tuấn viết một chương trình đồ họa, chương trình đó vẽ n hình tròn màu trắng lên màn hình màu đen. Màn hình là màn hình đen trắng có độ phân giải là w * h pixels. Pixels được đánh số từ góc trên bên trái (0,0) tới góc dưới bên phải (w-1,h-1).
Một hình tròn có tâm O(xc,yc) bán kính r chứa các pixel có tọa độ (x,y) thỏa mãn
 sqrt((xc -x)*(xc -x) +(yc -y)*(yc -y)) ≤ r. Nếu hình tròn tràn quá màn hình thì hình tròn đó sẽ bị cắt.
Nếu một điểm cùng thuộc hai hay nhiều hình tròn thì điểm đó có màu trắng.
Tuấn khá hài lòng với bức tranh được vẽ ra, vì vậy Tuấn quyết định vẽ bức tranh đó lên bức tường màu trắng trong phòng ngủ của mình, và anh ấy chỉ vẽ một phần bức tranh bằng màu đen. Bây giờ Tuấn muốn biết số lượng màu đen anh ấy cần. Tuấn copy bức tranh theo ánh xạ pixel - to - pixel. Vì vậy anh ấy viết chương trình tính số lượng pixel màu đen trên màn hình sau khi vẽ n hình tròn.

[Input]
* Dữ liệu đầu vào được được ghi trong file "CIRCLES.INP"
* Dòng đầu tiên chứa 3 số nguyên dương: w, h và n (1 ≤ w, h ≤ 20 000; 1 ≤ n ≤ 100). n dòng tiếp theo mô tả hình tròn với tâm (xi, yi) và bán kính r.
[Output]
* Ghi số lượng pixel màu đen còn lại trên màn hình ra file "CIRCLES.OUT".
[Input example]
5 3 2
1 1 1
3 1 1
[Output example]
6
[Giải thuật]
* Với mỗi hình tròn tâm (x,y) bán kính r luôn được bao phủ bởi một hình chữ nhật có cạnh trái là đoạn thẳng đi qua điểm  (x - r, y), có cạnh phải là đoạn thẳng đi qua điểm (x + r, y), cạnh trên là đoạn thẳng đi qua điểm (x, y -r), có cạnh đáy đi qua điểm (x, y + r).

* Duyệt tất cả các điểm nằm trong hình chữ nhật ở trên nếu điểm đó thỏa mãn: sqrt((xc -x)*(xc -x) +(yc -y)*(yc -y)) ≤ r  thì điểm đó nằm trong hình tròn và đánh dấu pixel đó là trắng đồng thời tăng biến đếm số pixel trắng lên 1, ngược lại điểm đó không nằm trong hình tròn.
* Duyệt tất cả các hình tròn theo cách trên để đếm số điểm trắng được bao phủ bởi tất cả hình tròn.
* Số điểm đen không được tô trắng bằng số pixel của màn hình trừ đi số điêm trắng, đây là kết quả cần tìm của bài toán.
Chương trình cài đặt.

#include<iostream>
#include <cstdio>
using namespace std;
#define WMAX 20001
#define HMAX 20001
#define max(a,b) a > b ? a:b
#define min(a,b) a > b ? b:a
bool matrix[WMAX][HMAX];
int main(){
 freopen("CIRCLES.INP", "r", stdin);
 freopen("CIRCLES.OUT", "w", stdout);
 int w, h, n;
 cin >> w >> h >> n;
 int  countWhite = 0;
 int rightRecX, leftRecX, bottomRecY, topRecY;
 int centerX, centerY, radius;
 for (int i = 0; i<n; i++){
  cin >> centerX >> centerY >> radius;
  //so sánh cạnh bên trái của hình chữ nhật với oy.
  leftRecX = max(0, centerX - radius);
  //so sánh cạnh bên phải của hình chữ nhật với đường thẳng đi qua điểm x = w -1.
  rightRecX = min(w - 1, centerX + radius);
  //so sánh cạnh đáy của hình chữ nhật với ox.
  bottomRecY = max(0, centerY - radius);
  //so sánh cạnh trên của hình chữ nhật với đường thẳng đi qua điểm y = h-1.
  topRecY = min(h - 1, centerY + radius);
  for (int x = leftRecX; x <= rightRecX; x++){
   for (int y = bottomRecY; y <= topRecY; y++){
    if (matrix[x][y] == false && ((centerX - x)*(centerX - x) + (centerY - y)*(centerY - y) <= radius*radius)){
     matrix[x][y] = true;
     countWhite++;
    }
   }
  }
 }
 cout << (w*h - countWhite) << endl;
 return 0;
}

[Bài tập mẫu] Hệ thống phòng thủ.

[Bài tập] Hãy tưởng tượng bạn đang tham gia một trò chơi có tên là " Hệ thống phòng thủ". Ở mỗi mức chơi (level) người chơi phải bảo vệ một vùng đất hình chữ nhật có dạng mạng lưới các ô vuông. Người chơi xây dựng các tháp phòng thủ tại một vài vị trí trên vùng đất đó. Một tháp phòng thủ sẽ bảo vệ toàn bộ vùng đất nằm trên dòng và cột mà tháp canh đó đặt. Không có hai tháp phòng thủ nào nằm trên cùng một dòng hay một cột.
Khi đặt tháp phòng thủ như vậy sẽ có những vùng đất không được bảo vệ. Hãy tính số ô vuông lớn nhất mà không được tháp canh bảo vệ.
Ở ví dụ dưới đây vùng đất lớn nhất mà không được tháp canh bảo vệ là 12 ô vuông.

[Input] 
Dữ liệu được đọc vào từ file "DEFENSE.INP".
*Dòng đâu tiên chứa 3 số nguyên dương. w - chiều rộng của ma trận lưới các ô vuông. h - chiều cao của ma trận lưới các ô vuông và n là số lượng tháp phòng thủ.
* n dòng tiếp theo là vị trí của các tháp phòng thủ.
[Output]
Ghi số ố vuông lớn nhất không được bảo vệ ra file "DEFENSE.OUT".
[Input sample]
15 8 3
3 8
11 2

8 6
[Output sample]
12

[Giải thuật]
- Các tháp phòng thủ được đặt trên một ma trận mạng lưới và không có 2 tháp nào cùng nằm trên cùng một hàng hay một cột. Thực hiện phép chiếu vuông góc tới 2 trục tọa độ x và y, được tọa tọa độ của các tháp trên trục x và trục y.
- Sắp xếp tọa độ của các tháp phòng thủ theo chiều tăng dần của x và xét hiệu ci = Xi – Xi-1 đây là khoảng cách giữa hai tháp theo trục x.
- Sắp xếp tọa độ của các tháp phòng thủ theo chiều tăng dần của y và xét hiệu di = Yi – Yi-1 đây là khoảng cách giữa hai tháp theo trục y.
- Vùng đất có kích thước w*h, ta có thể đặt thêm một tháp canh tại vị trí [w+1][h+1] để tính khoảng cách từ tháp cuối ( tận cùng bên phải) tới cuối vùng đất.
- Giả sử khu đất không được bảo vệ có kích thước a*b ô vuông, khi đó a <= ci max , b <= di max. Vậy vùng đất lớn nhất mà không được bảo vệ là ci max * di max là lời giải của bài toán.
Chương trình cài đặt:

#include<iostream>
#include <cstdio>
using namespace std;
#define WMAX 40002
#define HMAX 40002
int xAxis[WMAX],yAxis[HMAX];
int main(){
 freopen("DEFENSE.INP","r",stdin);
 freopen("DEFENSE.OUT","w",stdout);
 int w, h,n;
 cin>>w>>h>>n;
 int tempx,tempy;
 for(int i=0;i<n;i++){
  cin>>tempx>>tempy;
  xAxis[tempx] = 1;
  yAxis[tempy] = 1;
 }
 // đặt 1 tòa tháp vào góc trên bên phải.
 xAxis[w+1] = 1;
 yAxis[h+1] = 1;
 int maxX = 0;
 int tempMax = 0;
 for(int i=1;i<= w + 1;i++){
  if(xAxis[i]==0){
   tempMax++;
  }else{
   if(tempMax > maxX) maxX = tempMax;
   tempMax = 0;
  }
 }
 int maxY = 0;
 tempMax =0;
 for(int i=1;i <= h + 1;i++){
  if(yAxis[i]==0){
   tempMax++;
  }else{
   if(tempMax > maxY) maxY = tempMax;
   tempMax = 0;
  }
 }
 cout<<maxX*maxY;
 return 0;
}

[Bài toán] Chuỗi số nguyên tố.

Trong chuối số nguyên tố thì chữ số đầu tiên là số nguyên tố, số đến chữ số thứ n là số nguyên tố. Để hiểu hơn ta sét ví dụ sau:
Số 7331 là chuỗi số nguyên tố có 4 chữ số, trong đó chữ số đầu tiên (7) là số nguyên tố, số đến chữ số thứ 2 (73) là số nguyên tố, số đến chữ số thứ 3 (733) là số nguyên tố, và số đến chữ số thứ 4 (7331) là số nguyên tố.
Yêu cầu: Hãy liệt kê tất cả các chuỗi số nguyên tố có độ dài n.
[Input]
Dữ liệu đầu vào được chứa trong file Input.txt.
Dòng đầu ghi số lượng test case. Các dòng sau là test case tương ứng. Trong mỗi test case ghi số chữ số của chuỗi số.
[Output]
Kết quả của chương trình được ghi ra file Output.txt ,tương ứng với mỗi test case ghi ra chuỗi số nguyên tố, các chuỗi số này được ghi tương ứng nên mỗi dòng.
Kết quả của từng test case được ngăn cách bởi một dòng trắng.
[Input example]
5
1
2
3
4

5
[Output example]
2
3
5
7

23
29
31
37
53
59
71
73
79

233
239
293
311
313
317
373
379
593
599
719
733
739
797

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

23333
23339
23399
23993
29399
31193
31379
37337
37339
37397
59393
59399
71933
73331
73939
[Giải thuật]
*Chuỗi số nguyên tố có độ dài n được tạo thành nhờ phép ghép các chữ số (0,1,2,3,4,5,6,7,8,9). Nhưng vì số đến chữ số thứ i (1 <= i <= n) là số nguyên tố nên ta loại bỏ các chữ số (0,2,4,6,8), khi đó chuỗi số nguyên tố chỉ còn được tạo ra bằng việc ghép các chữ số (1,3,5,7,9).
*Để tìm chuối số nguyên tố, bằng giải thuật đệ quy ta điền từng vị trí i (1 <= i <= n) sao cho số được tạo thành đến chữ số i là số nguyên tố.
*Giải thuật kết thúc khi ta đã tìm đủ n chữ số cho chuỗi số nguyên tố.
Chương trình cài đặt.

#include<iostream>
using namespace std;
int primeNumber[6] = {1,2,3,5,7,9};
int digitLength;
bool isPrime(int n){
 if(n == 2 || n == 3) return true;
 if(n==1 || n%2 == 0 || n%3 == 0) return false;
 int k=-1;
 do{
  k+=6;
  if(n%k == 0 || n%(k+2) == 0) break;
 }while(k*k<n);
 return k*k > n;
}
void find(int index, int previousValue){
 if(index == digitLength){
  cout<<previousValue<<"\n";
  return;
 }
 for (int loop = 0;loop <6; loop ++){
  int value = previousValue*10+ primeNumber[loop];
  if(isPrime(value)){
   find(index+1,value);
  }
 }
}
int main(){
 freopen("Input.txt","r",stdin);
 freopen("Output.txt","w",stdout);
 int t;
 cin>>t;
 for(int i=1;i<=t;i++){
  cin>>digitLength;
  find(0,0);
  cout<<"\n";
 }
 return 0;
}

Bài tập mẫu

Dưới đây là danh sách bài tập mẫu của blog.

1. Liệt kê các hoán vị của một tập có lặp.
2. Biểu diễn n thành tổng các số tự nhiên không lớn hơn n.
3. Các thao tác vào ra cơ bản và các câu lệnh có cấu trúc trong C.
4. Xếp hạng học sinh trong lớp.
5. Đổi chỗ các phần tử trong mảng để được số lớn nhất.
6. Mảng và con trỏ trong C/C++.
7. Hàm trong C/C++.
8. Liệt kê tập con của tập n phần tử.
9. Liệt kế tất cả các hoán vị của n phần tử.
10. Sắp xếp mảng một chiều bằng Quicksort.
11. Tìm đường đi Hamiton ngắn nhất.
12. Tìm đường đi trong ma cung.
13. Liệt kê dãy nhị phân có đọ dài n.
14. 500 bài tập mẫu C/C++ 
15. Chuỗi ký tự trong C/C++ 
16. Bài tập Java cơ bản (phần 1)
17. Bài tập Java cơ bản (phần 2)
18. Bài tập Java cơ bản (phần 3)
19. Chuỗi số nguyên tố.
20. Hệ thống phòng thủ. 
21. Vẽ hình tròn. 
22. Con đường Tùng Cúc
23. Đa giác số.
24. Xây ựng đường sắt - Ứng dụng thuật toán Prim

[Bài toán] Liệt kê dãy nhị phân độ dài n.

[Bài toán] Liệt kê dãy nhị phân độ dài n.
[Giải] 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;
}