[Bài toán] Xây dựng đường sắt

Bài toán: Bộ xây dựng đang có kế hoạch xây dựng hệ thống đường sắt nối liền các thành phố với nhau, sao cho chỉ có duy nhất 1 tuyến đường sắt nối liền hai thành phố bất kỳ. Sau khi nhiên cứu tính toán chi phí xây dựng các tuyến đường sắt nối liền các thành phố, bộ xây dựng thu được ma trận chi phí hai chiều.
Hãy giúp bộ xây dựng xây dựng xây dựng hệ thống đường sắt với yêu cầu trên với chi phí xây dựng nhỏ nhất.
[Input]
Dữ liệu đầu vào được chứa trong file WELLPROJECT.INP, dòng đầu chứa số lượng test case T ( T ≤ 10). Tiếp đó là N - Số thành phố. N dòng tiếp theo là ma trận chi phí xây dựng đường sắt nối liền 2 thành phố bất kỳ.
[Output]
In ra file WELLPROJECT.OUT chi phí nhỏ nhất xây dựng hệ thống đướng sắt trên. Kết quả của mỗi test case đươc in ra trên một dòng.
[Input example]
5
3
0 1 4
1 0 2
4 2 0
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
6
0 45 86 12 61 51
45 0 80 99 18 2
86 80 0 9 37 14
12 99 9 0 14 90
61 18 37 14 0 52
51 2 14 90 52 0
10
0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0
10
0 40613 19297 99549 27948 50416 95139 82856 99082 79380
40613 0 96888 46784 65549 8396 18128 31348 94809 16773
19297 96888 0 83011 20456 42383 34635 86957 85569 95179
99549 46784 83011 0 24003 66861 44068 11524 97968 22654
27948 65549 20456 24003 0 16590 54758 37348 62125 17814
50416 8396 42383 66861 16590 0 67234 14142 90848 64960
95139 18128 34635 44068 54758 67234 0 81632 81223 19101
82856 31348 86957 11524 37348 14142 81632 0 38508 16462
99082 94809 85569 97968 62125 90848 81223 38508 0 37607
79380 16773 95179 22654 17814 64960 19101 16462 37607 0
[Output example]
3
28
51
9
162602
Chương trình giải bài toán trên được cài đặt theo thuật toán Prim như sau:

#include<iostream>
#include<conio.h>
using namespace std;
#define NMax 101
int map[NMax][NMax];
bool isVisited[NMax];
#define LENGTHMAX 1000000
int main(){
 freopen("WELLPROJECT.INP","r", stdin);
 freopen("WELLPROJECT.OUT","w", stdout);
 int T;
 cin>>T;
 for(int tc = 0; tc < T; tc++){
  int verticeCount;
  cin>>verticeCount;
  for(int i =1; i<= verticeCount; i++){
   // khởi tạo giá trị mảng visited.
   isVisited[i] = false;
   for(int j= 1;j <= verticeCount ; j++){
    cin>>map[i][j];
   }
  }
  // Prim algorithm.
  // bắt đầu từ đỉnh 1.
  isVisited[1] = true;
  int countEdge = 0;
  int sumOfEdge = 0;
  // Vòng lặp, thăm các đỉnh để tạo cây khung nhỏ nhất.
  while(countEdge < verticeCount - 1){
   int tempLength = LENGTHMAX;
   int tempVertice = 1;
   for(int i=1 ;i <= verticeCount; i++){
    if(isVisited[i]){
     for(int j=1; j <= verticeCount ; j++){
      if(j != i && !isVisited[j] && map[i][j] > 0 && map[i][j] < tempLength){
       tempLength = map[i][j];
       tempVertice = j;
      }
     }
    }
   }
   countEdge++;
   isVisited[tempVertice]= true;
   sumOfEdge += tempLength;
  }
  cout<<sumOfEdge<<endl;
 }

}

[Bài tập mẫu] Đa giác số

Bài toán: Trên vòng tròn đánh dấu n điểm phân biệt. Các điểm này được chọn làm n đỉnh của đa giác lồi P. Vẽ tất cả các đường chéo của đa giác P. Cho N là một họ gồm n số nguyên dương. Mỗi số của họ N sẽ được viết bên cạnh một đỉnh của đa giác P. Ta gọi việc làm này là phân bố các số của họ N cho các đỉnh của đa giác P. Tiếp theo, mỗi đường chéo của đa giác P sẽ được gán cho một số nguyên bằng tích của hai số gán cho đỉnh đầu mút của nó.
Ví dụ: n = 7, N = <15, 12, 2, 12, 10, 11, 10>. Một cách phân bố các số của họ N cho các đỉnh của đa giác được chỉ ra trong hình vẽ dưới đây:

Yêu cầu: Tìm cách phân bố các số của họ N cho các đỉnh của đa giác sao cho tổng các số gán cho các đường chéo là lớn nhất.
Dữ liệu: Vào từ file văn bản NUMPOLY.INP:

• Dòng đầu tiên chứa số nguyên n (3 < n ≤ 105).
• Dòng thứ hai chứa n số nguyên dương của họ N, mỗi số không vượt quá 106, hai số liên tiếp phân tách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản NUMPOLY.OUT 5 chữ số cuối cùng của tổng các số gán trên đường chéo theo cách phân bố tìm được. Chú ý là file kết quả phải chứa đúng 5 chữ số (như vậy, số gồm 5 chữ số trên file kết quả có thể có các số 0 đứng đầu).

NUMPOLY.INP	NUMPOLY.OUT
7 15 12 2 12 10 11 10	01487

Giải thích: Cách phân bố cho trong hình vẽ minh họa ở trên có tổng các số gán cho đường chéo là số có tận cùng bởi 5 chữ số ‘01487’.

Phát biểu lại bài toán:

• Cho N số nguyên: a0, a1,…, an-1 (3 < n ≤10^5);
• Tìm cách phân bố n số cho các đỉnh của đa giác n đỉnh sao cho tổng các số gán cho các đường chéo ( bằng tích của hai số ở hai đỉnh đầu mút) là lớn nhất.

Giải thuật

• Ta có khai triển: (SUM(ai))^2 = SUM((ai)^2) + 2* SUM(ai*a(i+1)mod n) + 2* SUM(ai*aj); trong đó  i = 0 to n-1
• Ta tính được bình phương tổng của các số (ký hiệu là ∑) và tổng các bình phương của các số S1, nên nếu ký hiệu S2 là tổng của tích các cặp số liên tiếp thì tổng các số trên đường chéo S được tính bởi công thức sau: S = (∑ - S1 – 2S2)/2.
• Từ đó suy ra bài toán dẫn về tìm cực tiểu tổng S1.
• Nhận xét này cho phép giảm độ phức tạp, bởi vì số lượng đường chéo là n(n-3)/2, trong đó n là số đỉnh của đa giác.
• Hơn nữa, ta có thuật toán đơn giản đê tìm cấu hình cho cực tiểu tổng S1: Sắp xếp các số a1, sau đó bắt đầu từ hai đầu dãy, tiến hành hoán đổi các số và dịch chuyển sang bên cạnh: phái trái dịch từ trái sang phải, phái phải dịch từ phải sang trái cho đến khi chờm qua nhau. Khi phân bố chú ý tiến hành tính chỉ số theo model.

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

#include <cstdio>
#include <iostream>
#include<stdlib.h>
#include<conio.h>
using namespace std;
#define nmax 1000000
int array[nmax];
unsigned long long sum;
unsigned long long SIGMA, sigma, sumS1;
int compare(const void * a, const void * b)
{
 return (*(int*)a - *(int*)b);
}
int main(int argc, char** argv)
{
 freopen("NUMPOLY.INP", "r", stdin);
 freopen("NUMPOLY.OUT", "w", stdout);


 int n;
 cin >> n;
 for (int i = 0; i < n; i++){
  cin>> array[i];
  SIGMA += array[i];
  sigma += array[i] * array[i];
 }
 SIGMA *= SIGMA;
 qsort(array, n, sizeof(int), compare);
 
 for (int i = 1; i < n/2; i = i+ 2){
  int temp = array[i];
  array[i] = array[n - 1 - i];
  array[n - 1 - i] = temp;
 }
 for (int i = 0; i < n; i ++){
  sumS1 += (unsigned long long) array[i] * array[(i + 1) % n];
 }

 sum = (unsigned long long)(SIGMA - sigma - 2 * sumS1) / 2;
 if (sum < 10){
  cout << "0000" << sum;
 }
 else if (sum < 100){
  cout << "000" << sum;
 }
 else if (sum < 1000){
  cout << "00" << sum;
 }
 else if (sum < 10000){
  cout << "0" << sum;
 }
 else{
  cout<< sum%100000;
 }
 
 return 0;
}

[Bài tập mẫu] Con đường Tùng - Trúc.

[Bài toán] Địa điểm du lịch Dailai nổi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng,dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất a cây tùng và có ít nhất b cây trúc để trang trí. Sau khi khảo sát, Ban quản lý ghi nhận được vị trí của từng cây tùng và cây trúc. Trên con đường có tất cả n cây, không có hai cây nào ở cùng một vị trí. Cây thứ i ở vị trí có khoảng cách đến vị trí bắt đầu con đường là di (i = 1, 2, …, n). Với kinh phí có hạn, Ban quản lý muốn chọn đoạn đường thỏa mãn điều kiện đã nêu với độ dài là ngắn nhất.
Yêu cầu: Cho a, b và vị trí của n cây. Hãy tìm đoạn đường có độ dài ngắn nhất mà dọc theo đó có ít nhất a cây tùng và có ít nhất b cây trúc.
Dữ liệu: Vào từ file văn bản MINROAD.INP:
* Dòng đầu chứa 3 số nguyên dương n, a, b (a + b ≤ n);
* Dòng thứ i trong n dòng tiếp theo, mỗi dòng chứa hai số nguyên dương di (di ≤ 109) và ki, trong đó di là khoảng cách của cây tính từ vị trí bắt đầu của con đường, ki = 1 nếu là cây tùng, ki = 2 nếu là cây trúc.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản MINROAD.OUT một số nguyên là độ dài đoạn đường ngắn nhất tìm
được, quy ước ghi số -1 nếu không tồn tại đoạn đường nào thỏa mãn điều kiện đặt ra.
[Input example]
7 2 2
20 2
30 1
25 1
35 1
60 2
65 2
10 1
[Output example]
35
[Giải thuật]
* Sắp xếp dãy vị trí của các cây theo thứ tự tăng dần: d[1] < d[2] <...
* Bắt đầu từ đầu dãy, duyệt từ trái qua phải để tìm các đoạn gồm dãy các phần tử liên tiếp chứa ít nhất a cây tùng và ít nhất b cây trúc. Mỗi lần tìm được đoạn như vậy ghi nhận độ dài để tìm ra đoạn ngắn nhất.

#include <cstdio>
#include <iostream>
#include<stdlib.h>
using namespace std;
#define nmax 300000
long data[nmax][2];
int compare(const void *arg1, const void *arg2)
{
 int const *lhs = static_cast<int const*>(arg1);
 int const *rhs = static_cast<int const*>(arg2);
 return (lhs[0] < rhs[0]) ? -1
  : ((rhs[0] < lhs[0]) ? 1
  : (lhs[1] < rhs[1] ? -1
  : ((rhs[1] < lhs[1] ? 1 : 0))));
};
int main(int argc, char** argv)
{
 freopen("MINROAD.INP", "r", stdin);
 freopen("MINROAD.OUT", "w", stdout);

 int n, a, b;
 scanf("%d %d %d", &n, &a, &b);
 if (a == 0 && b == 0){
  printf("%d", -1);
  return 0;
 }
 for (int i = 0; i < n; i++)
  scanf("%d %d", &data[i][0], &data[i][1]);

 qsort(data, n, 2 * sizeof(int), compare);

 long min = 1000000000;
 int head, tail = 0;
 int countTung = 0;
 int countTruc = 0;

 for (int i = 0; i < n; i++){
  if (data[i][1] == 1){
   countTung++;
  }
  else{
   countTruc++;
  }
  if (countTung >= a && countTruc >= b){
   head = i;
   min = data[head][0] - data[tail][0];
   break;
  }
 }

 bool isSub = false;
 while (head < n){ 
  for (int j = tail; j < head; j++){
   isSub = false;
   if (data[j][1] == 1 && countTung >a){
    countTung --;
    tail += 1;
    isSub = true;
   }
   if (data[j][1] !=1 && countTruc >b){
    countTruc--;
    tail += 1;
    isSub = true;
   }
   if(!isSub) break;
   if (data[head][0] - data[tail][0] < min){
     min = data[head][0] - data[tail][0];
    }

  }
  head++;
  if (head < n){
   if (data[head][1] == 1){
    countTung++;
   }
   else{
    countTruc++;
   }
  }
 }
 if (min == 1000000000){ min = -1; }
 printf("%d", min);
 return 0;
}

[Bài toán] Xếp hậu

Bài toán:  Liệt kê tất cả các cách xếp n quân hậu trên bàn cờ n x n sao cho chúng không ăn được nhau bằng thuật toán Back Track.
Giải. Bàn cờ có n hàng được đánh số từ 0 đến n-1, n cột được đánh số từ 0 đến n-1; Bàn cờ có n*2 -1 đường chéo xuôi được đánh số từ 0 đến 2*n -2, 2 *n -1 đường chéo ngược được đánh số từ 2*n -2. Ví dụ: với bàn cờ 8 x 8, chúng ta có 8 hàng được đánh số từ 0 đến 7, 8 cột được đánh số từ 0 đến 7, 15 đường chéo xuôi, 15 đường chéo ngược được đánh số từ 0..15.
     Vì trên mỗi hàng chỉ xếp được đúng một quân hậu, nên chúng ta chỉ cần quan tâm đến quân hậu được xếp ở cột nào. Từ đó dẫn đến việc xác định bộn thành phần x1, x2,.., xn, trong đó xi= j được hiểu là quân hậu tại dòng i xếp vào cột thứ j. Giá trị của i được nhận từ 0 đến n-1; giá trị của j cũng được nhận từ 0 đến n-1, nhưng thoả mãn điều kiện ô (i,j) chưa bị quân hậu khác chiếu đến theo cột, đường chéo xuôi, đường chéo ngược.
     Việc kiểm soát theo hàng ngang là không cần thiết vì trên mỗi hàng chỉ xếp đúng một quân hậu. Việc kiểm soát theo cột được ghi nhận nhờ dãy biến logic aj với qui ước aj=1 nếu cột j còn trống, cột aj=0 nếu cột j không còn trống. Để ghi nhận đường chéo xuôi và đường chéo ngược có chiếu tới ô (i,j) hay không, ta sử dụng phương trình i + j = const và i - j = const, đường chéo thứnhất được ghi nhận bởi dãy biến bj, đường chéo thứ 2 được ghi nhận bởi dãy biến cj với qui ước nếu đường chéo nào còn trống thì giá trị tương ứng của nó là 1 ngược lại là 0. Như vậy, cột j được chấp nhận khi cả 3 biến aj, bi+j, ci+j đều có giá trị 1. Các biến này phải được khởi đầu giá trị 1 trước đó, gán lại giá trị 0 khi xếp xong quân hậu thứ i và trả lại giá trị 1 khi đưa ra kết quả.

#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
#include <dos.h> 
#define N  8 
#define D  (2*N-1) 
#define SG  (N-1) 
#define TRUE 1 
#define FALSE 0 
void hoanghau(int);
void inloigiai(int  loigiai[]); FILE *fp;
int  A[N], B[D], C[D], loigiai[N];
int soloigiai = 0;
void hoanghau(int i){
 int j;
 for (j = 0; j < N; j++){
  if (A[j] && B[i - j + SG] && C[i + j]) {
   loigiai[i] = j;
   A[j] = FALSE;
   B[i - j + SG] = FALSE;
   C[i + j] = FALSE;
   if (i == N - 1){
    soloigiai++;
    inloigiai(loigiai);
    delay(500);
   }
   else
    hoanghau(i + 1);
   A[j] = TRUE;
   B[i - j + SG] = TRUE;
   C[i + j] = TRUE;
  }
 }
}
void inloigiai(int *loigiai){
 int j;
 printf("\n Lời giải %3d:", soloigiai);
 fprintf(fp, "\n Lời giải %3d:", soloigiai);
 for (j = 0; j < N; j++){
  printf("%3d", loigiai[j]);
  fprintf(fp, "%3d", loigiai[j]);
 }
}
void main(void){
 int i; clrscr();
 fp = fopen("loigiai.txt", "w");
 for (i = 0; i < N; i++)
  A[i] = TRUE;
 for (i = 0; i < D; i++){
  B[i] = TRUE;
  C[i] = TRUE;
 }
 hoanghau(0);
 fclose(fp);
}

Dưới đây là số cách xếp hậu ứng với n.

n	4	7	8	9	10	11	12	13	14
Hn	2	40	92	352	724	2680	14200	73712	365596

Nghiệm đầu tiên mà chương trình tìm được ứng với n =8 là x =(1, 5, 8, 6, 3, 7, 2, 4).

[Bài toán] Liệt kê các hoán vị của tập n phần tử bằng thuật toán Back Track

     Biểu diễn hoán vị dưới dạng p1, p2,.., pn, trong đó pi nhận giá trị từ 1 đến n và pi≠pj với i≠j. Các giá trị từ 1 đến n lần lượt được đề cử cho pi, trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì vậy, cần phải ghi nhớ với mỗi giá trị j xem nó đã được dùng hay chưa. Điều này được thực hiện nhờ một dãy các biến logic bj, trong đó bj= true nếu j chưa được dùng. Các biến này phải được khởi đầu giá trị true trong thủ tục Init. Sau khi gán j cho pi, cần ghi nhận false cho bj và phải gán true khi thực hiện xong Result hay Try(i+1). Hình sau mô tả cây tìm kiếm lời giải bài toán liệt kê hoán vị của 1, 2,.., n với n = 3.

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

#include  <stdio.h> 
#include  <conio.h> 
#include  <stdlib.h> 
#define MAX 100 
#define TRUE 1 
#define FALSE 0 
int P[MAX], B[MAX], n, count = 0;
void Init(void){
 int i;
 printf("\n Nhap n="); scanf("%d", &n);
 for (i = 1; i <= n; i++)
  B[i] = TRUE;
}
void Result(void){
 int i; count++;
 printf("\n Hoan vi thu %d:", count);
 for (i = 1; i <= n; i++)
  printf("%3d", P[i]);
 getch();
}
void Try(int i){
 int j;
 for (j = 1; j <= n; j++){
  if (B[j]) {
   P[i] = j;
   B[j] = FALSE;
   if (i == n) Result();
   else Try(i + 1);
   B[j] = TRUE;
  }
 }
}
void main(void){
 Init();
 Try(1);
}

[Bài toán] Liệt kê các tập con k phần tử của tập n phần tử 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 tập con k phần tử dưới dạng c1, c2,.., ck, trong đó 1< c1các giá trị đề cử cho ci là từ ci-1+ 1 cho đến n - k + i. Cần thêm vào c0= 0. Các giá trị đề cử này
mặc nhiên được chấp nhận mà không cần phải thêm điều kiện gì. 

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

#include <conio.h> 
#include <stdio.h> 
#include <stdlib.h> 
#define MAX  100 
int B[MAX], n, k, count = 0;
void Init(void){
 printf("\n Nhap n="); scanf("%d", &n);
 printf("\n Nhap k="); scanf("%d", &k);
 B[0] = 0;
}
void Result(void){
 int i; count++;
 printf("\n Tap thu %d:", count);
 for (i = 1; i <= k; i++){
  printf("%3d", B[i]);
 }
 getch();
}
void Try(int i){
 int j;
 for (j = B[i - 1] + 1; j <= (n - k + i); j++){
  B[i] = j;
  if (i == k) Result();
  else Try(i + 1);
 }
}
void main(void){
 clrscr();
 Init();
 Try(1);
}

[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;
}

[Bài toán] Tìm đường đi trong ma cung.

[Bài toán] Một mê cung được cho như hình bên dưới. Mê cung là một ma trận có kích thước 100x100. Trong đó màu trắng là đường đi, màu vàng là tường. Hãy tìm đường đi từ điểm bắt đầu có giá trị 2 đến điểm kết thúc có giá trị 3.
 Giả sử đỉnh trên cùng bên trái có tọa độ là (0,0). Điểm bắt đầu là (1,1), điểm kết thúc là (13,13).
Hãy viết chương trình kiểm tra có thể đi từ điểm đầu đến điểm cuối. Nếu có đường đi in ra 1 ngược lại in ra 0.

[Input]
Dữ liệu đầu vào được ghi trong file MAZE.INP.
Dòng đầu ghi số thứ tự test case.
Các dòng tiếp theo là ma trận 100x100.
[Output]
Kết quả ghi ra file MAZE.OUT bắt đầu bằng ký tự #C theo sau là khoảng trắng, 0 nếu không có đường đi, 1 nếu có đường đi.
[I/O example]
Tải file input tại đây..
[Output]
#1 1
#2 1
#3 1
#4 0
#5 0
#6 1
#7 1
#8 0
#9 1
#10 0
Chương trình cài đặt:

#include<iostream>
#include<conio.h>
#define nMax 100
using namespace std;
char matrix[nMax][nMax];
bool isReached;
void visit(char matrix[nMax][nMax], int x,int y){
 if(matrix[x][y] == '3'){
  isReached = true; return;
 }
 matrix[x][y] = '1';
 if(isReached == false && x-1 >=0 && (matrix[x-1][y] == '0' || matrix[x-1][y] == '3')) visit(matrix,x-1,y);
 if(isReached == false && x+1 <nMax && (matrix[x+1][y] == '0' || matrix[x+1][y] == '3')) visit(matrix,x+1,y);
 if(isReached == false && y-1 >=0 && (matrix[x][y-1] == '0' || matrix[x][y-1] == '3')) visit(matrix,x,y-1);
 if(isReached == false && y+1 <nMax && (matrix[x][y+1] == '0' || matrix[x][y+1] == '3')) visit(matrix,x,y+1);
}
int main(){
 freopen("MAZE.INP","r", stdin);
 freopen("MAZE.OUT","w", stdout);
 int testCase;
 int loop =1;
 int beginX, beginY;
 while(loop++ <= 10){
  isReached = false;
  cin>>testCase;
  for(int i=0;i<nMax;i++){
   cin>>matrix[i];
   for(int j=0;j<nMax;j++)
    if(matrix[j][i] == '2'){
     beginX = j; beginY = i;
   }
  }
  visit(matrix,beginX,beginY);
  if(isReached){
   cout<<"#"<<testCase<<" "<<1<<endl;
  }else{
   cout<<"#"<<testCase<<" "<<0<<endl;
  }
  
 }
 return 0;
}

[Baì toán] Tìm đường đi Hamiton ngắn nhất.

[Bài toán] Nhân viên giao bánh piza phải giao bánh cho N khách hàng. Từ cửa hàng bánh , anh ta phải đi giao bánh cho N khách hàng sau đó trở về nhà của mình. Vị trí của của hàng bánh, nhà của anh ta và của khách hàng theo mẫu sau (x,y). Khoảng cách giữa 2 vị trí (x1,y1) và (x2,y2) được tính theo công thức sau: |x1-x2| + |y1-y2|.
Hãy viết chương trình tính đường đi ngắn nhất cho nhân viên trên.
[Input]
Có 10 test case được chứa trong file dữ liệu đầu vào OPTIMALPATH.INP. Dòng đầu ghi số khách hàng N. Dòng sau ghi vị trí (x,y) của văn phòng, nhà của nhân viên và của N khách hàng.
[Output]
Ghi ra file OPTIMALPATH.OUT đường đi ngắn nhất cho mỗi test case. Với mỗi test case được bắt đầu bằng #C.
[I/O example]
5
0 0 100 100 70 40 30 10 10 5 90 70 50 20
6
88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
7
22 47 72 42 61 93 8 31 72 54 0 64 26 71 93 87 84 83
8
30 20 43 14 58 5 91 51 55 87 40 91 14 55 28 80 75 24 74 63
9
3 9 100 100 16 52 18 19 35 67 42 29 47 68 59 38 68 81 80 37 94 92
10
39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36
10
26 100 72 2 71 100 29 48 74 51 27 0 58 0 35 2 43 47 50 49 44 100 66 96
10
46 25 16 6 48 82 80 21 49 34 60 25 93 90 26 96 12 100 44 69 28 15 57 63
10
94 83 72 42 43 36 59 44 52 57 34 49 65 79 14 20 41 9 0 39 100 94 53 3
10
32 79 0 0 69 58 100 31 67 67 58 66 83 22 44 24 68 3 76 85 63 87 7 86
[Output]
#1 200
#2 304
#3 265
#4 307
#5 306
#6 366
#7 256
#8 399
#9 343
#10 391
Chương trình cài đặt.

#include<iostream>
#define myABS(value) ((value < 0) ? -(value) : (value))
using namespace std;
int matrix[12][12];
int position[12][2];
int minPath;
bool isVisited[12];
int customerNo;
void DFS(int vertice, int pathLength, int verticeCount){
 if(verticeCount == customerNo+1){
  if(pathLength + matrix[vertice][1] < minPath){
   minPath = pathLength + matrix[vertice][1];
  }
  return;
 }
 for(int i=2;i<customerNo+2;i++){
  if(!isVisited[i] && i != vertice && pathLength + matrix[vertice][i] < minPath){
   isVisited[i] = true;
   DFS(i, pathLength + matrix[vertice][i], verticeCount+1);
   isVisited[i] = false;
  }
 }
}
int main(){
 freopen("OPTIMALPATH.INP","r",stdin);
 freopen("OPTIMALPATH.OUT","w", stdout);
 customerNo;
 int tc;
 for(tc=1;tc<=10;tc++){
  cin>>customerNo;
  for(int i=0;i<customerNo + 2;i++){
   cin>>position[i][0]>>position[i][1];
  }
  for(int i=0;i<customerNo+1;i++){
   for(int j=i;j<customerNo+2;j++){
    if(i==j){
     matrix[i][j]=0;
    }else{
     matrix[i][j] = matrix[j][i] =  myABS(position[i][0] - position[j][0]) + myABS(position[i][1] - position[j][1]);
    }
   }
  }
  minPath = 1000000000;
  for(int i=0;i<customerNo+2;i++) isVisited[i] = false;
  isVisited[0] = true;
  DFS(0,0,1);// office's index.
  cout<<"#"<<tc<<" "<<minPath<<endl;
  
 }

 return 0;
}

[Bài toán] Sắp xếp mảng 1 chiều bằng QuickSort

[Bài toán] Cho mảng một chiều a. Hãy cài đặt QuickSort để sắp xếp mảng trên theo thứ tự tăng dần.
[Thuật toán]
QuickSort là một thuật toán sắp xếp được sử dùng rộng rãi nhất và vì lý do: trong hầu hết mọi trường hợp, nó là phương pháp nhanh nhất, thời gian chạy thuật toán là O(N*logN). Cơ bản thì thuật toán QuickSort hoạt động bằng cách phân hoạch một dãy thành dãy con, và gọi thuật toán QuickSort để sắp xếp từng dãy con đó. Thuật toán gồm 3 bước cơ bản như sau.

1. Chọn khóa. Khóa được chọn thường là phần tử đầu của mảng, giữa mảng hoặc cuối mảng.
2. Phân hoạch dãy con thành nhóm bên trái (nhỏ hơn khóa) và nhóm bên phải ( lớn hơn khóa).
3. Gọi lại thuật toán để sắp xếp nhóm bên trái.
4. Gọi lại thuật toán để sắp xếp nhớm bên phải.

Sau khi phân hoạch, tất cả những phần tử phía bên trái nhỏ hơn những phần tử bên phải. Nêu như chúng ta sắp xếp phần dãy con bên trái và đến phần dãy con bên phải, toàn bộ dãy sẽ được sắp xếp.
Chương trình cài đặt:

#include<iostream>
#include<conio.h>
using namespace std;
int n = 11;
int arr[] = {5,9,4,12,10,444,345,958,2,4,3};
void quicksort(int* arr, int leftIndex, int rightIndex){
 int i = leftIndex;
 int j= rightIndex;
 int pivot = arr[(leftIndex + rightIndex)/2];
 while(i<=j){
  while(arr[i] < pivot) i++;
  while(arr[j]> pivot) j--;
  if(i<=j){
   int temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
   i++;j--;
  }
  if(i<rightIndex) quicksort(arr,i,rightIndex);
  if(j>leftIndex) quicksort(arr,leftIndex,j);
 }
}
int main(){
 quicksort(arr,0,10);
 freopen("QUICKSORT.OUT","w",stdout);
 for(int i=0;i<11;i++){
  cout<<arr[i]<<" ";
 }
 return 0;
}

Nếu bạn có câu hỏi hay góp ý xin hãy để lại ý kiến trong phần comment của bài viết.

[Bài toán] Liệt kê tất cả các hoán vị của n phần tử.

Bài toán : Liệt kê các hoán vị của tập n phần tử. Cho X = { 1, 2,.., n }. Hãy liệt kê các hoán vị từ n phần tử của X.
Chương trình cài đặt bằng đệ quy quay lui.

//chương trình sẽ liệt kê tất cả các hoán vị của tập X={1,2,3,4} bằng phương pháp đệ quy quay lui.
//Kết quả của chương trình sẽ được ghi ra file HOANVI.OUT
#include<iostream>
using namespace std;
#define n 4 //Định nghĩa tập X gồm 4 phần tử X = {1,2,3,4}
int arr[n+1][2];//giá trị của arr[k][0] là mảng chứa các phần tử của mảng X  (1 <= k <= n+1)
    //giá trị của arr[k][1] là biến đánh dấu phần tử đó đã xuất hiện trong hoán vị hay chưa (1 <= k <= n+1)
int permute[n+1];// mảng 1 chiều ghi kết quả của các lần hoán vị.
void toPermute(int index){
 if(index > n){// nếu chỉ số trong bước lặp đệ quy lớn hơn n -> in ra kết quả hoán vị.
  for(int i=1;i<=n;i++){
   cout<<permute[i];
   if(i<n)cout<<",";
  }
  cout<<endl;
  return;
 }
 //Đệ quy để sinh ra hoán vị tiếp theo.
 for(int i=1;i<=n;i++){
  if(arr[i][1] == false){// kiểm tra phần tử i của tập X chưa xuất hiện trong hoán vị 
   permute[index] = arr[i][0];
   arr[i][1] = true;
   toPermute(index+1);
   arr[i][1] = false;
  }
 }
}
int main(){
 freopen("HOANVI.OUT","w",stdout);
 for(int i=1;i<=n;i++){
  arr[i][0] = i;
  arr[i][1] = false;
 }
 toPermute(1);
 return 0;
}

Output của chương trình

1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,2,3
1,4,3,2
2,1,3,4
2,1,4,3
2,3,1,4
2,3,4,1
2,4,1,3
2,4,3,1
3,1,2,4
3,1,4,2
3,2,1,4
3,2,4,1
3,4,1,2
3,4,2,1
4,1,2,3
4,1,3,2
4,2,1,3
4,2,3,1
4,3,1,2
4,3,2,1

[Bài toán] Liệt kê tập con của tập n phần tử.

Bài toán: Cho X = {1, 2,3,.., n}. Hãy liệt kê tất cả các tập con k phần tử của X (k<=n).
Giải: Mỗi tập con của tập hợp X có thể biểu diễn bằng bộ có thứ tự gồm k thành phần a = (a1a2..ak) thoả mãn 1 ≤a1 ≤a2 ≤..≤ak ≤n.
Trên tập các tập con k phần tử của X có thể xác định nhiều thứ tự khác nhau. Thứ tự dễ nhìn thấy nhất là thứ tự từ điển được định nghĩa như sau:
Ta nói tập con a = a1a2... ak đi trước tập con a’ = a1’a2’...ak’ trong thứ tự từ điển và ký hiệu là a<a’, nếu tìm được chỉ số j ( 1 ≤j ≤k ) sao cho: a1= a1’, a2 = a2’,..., aj-1= a’j-1, aj< a’j.
Chẳng hạn X = { 1, 2, 3, 4, 5 }, k = 3. Các tập con 3 phần tử của X được liệt kê theo thứ tự từ điển như sau:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Như vậy, tập con đầu tiên  trong thứ tự từ điển là (1, 2,.., k) và tập con cuối cùng là (n-k+1,n-k+2,.., n). Giả sử a = (a1, a2,.., ak) là tập con hiện tại và chưa phải là cuối cùng, khi đó có thể chứng minh được rằng tập con kế tiếp trong thứ tự từ điển có thể được xây dựng bằng cách thực hiện các qui tắc biến đổi sau đối với tập con đang có.

1. Tìm từ bên phải dãy a1, a2,.., ak phần tử ai≠n – k + i
2. Thay ai bởi ai+1,
3. Thay aj bởi ai+ j – i, với j:= i+1, i + 2,...,k

Chẳng hạn với n = 6, k =4. Giả sử ta đang có tập con (1, 2, 5, 6), cần xây dựng tập con kế tiếp nó trong thứ tự từ điển. Duyệt từ bên phải ta nhận được i =2, thay a2 bởi a2+ 1 = 2 + 1 =3.
Duyệt j từ i + 1 = 3 cho đến k, ta thay thế a3= a2+ 3 – 2 = 3 + 3 - 2 = 4, a4= a2 + 4 - 2 = 3 + 4 – 2 = 5 ta nhận được tập con kế tiếp là ( 1, 3, 4, 5).
Với qui tắc sinh như trên, chúng ta có thể mô tả bằng thuật toán sau:
Thuật toán liệt kê tập con kế tiếp m phần tử của tập n phần tử:  

#include <stdio.h> 
#include <conio.h> 
#define TRUE 1 
#define FALSE 0 
#define MAX 100 
int n, k, count, C[MAX], Stop;
void Init(void){
 int i;
 printf("\n Nhap n="); scanf("%d", &n);
 printf("\n Nhap k="); scanf("%d", &k);
 for (i = 1; i <= k; i++)
  C[i] = i;
}
void Result(void){
 int i; count++;
 printf("\n Tap con thu %d:", count);
 for (i = 1; i <= k; i++)
  printf("%3d", C[i]);
}
void Next_Combination(void){
 int i, j;
 i = k;
 while (i > 0 && C[i] == n - k + i)
  i--;
 if (i > 0) {
  C[i] = C[i] + 1;
  for (j = i + 1; j <= k; j++)
   C[j] = C[i] + j - i;
 }
 else Stop = TRUE;
}
void Combination(void){
 Stop = FALSE;
 while (!Stop){
  Result(); Next_Combination();
 }
}
void main(void){
 Init();
 Combination();
 getch();
}

[Bài toán] Tìm điểm căn bằng.

Ở một dải ngân hà X có n hành tinh. Tọa độ của mỗi hành tinh được đặc trưng bởi 3 tọa độ (x,y,z). Vào một thời điểm nào đó trong năm, các hành tinh được sắp xếp trên một đường thẳng x (y = z = 0). Đây là một hiện tượng khoa học thú vị, các nhà khoa học đã đặt ra  câu hỏi: Ở những vị trí nào trên đường thẳng x khi đặt một hành tinh M vào đó thì hành tinh đó dứng yên.

Được biết rằng giữa hai hành tinh luôn tồn tại lực hấp dẫn. Lực này được tính theo công thức : F = G *m1*m2/(d*d).

• Trong đó : G là hằng số vũ trụ.
• m1, m2 lần lượt là khối lượng của hai hành tinh. 
• d là khoảng cách giữa  chúng.

Hãy làm tròn vị trí tìm được đến 1/10^9.
*Note: Biết rằng khi có n hành tinh thì ta luôn tìm được n-1 vị trí cân bằng cho hành tinh M.
[Input]
Dữ liệu của 10 test case được chứa trong file POINTOFBALANCE.INP. Dòng đầu ghi số hành tinh N của dải ngân hà X.
Dòng sau ghi tọa độ của N hành tinh trên trục x, theo ngay sau là khối lượng của N hành tinh.
[Output]
Hãy ghi ra file POINTOFBALANCE.OUT tất cả các điểm cân bằng trên trục x. Mỗi test case được bắt đầu bằng #C và các vị trí được ngăn cách với nhau bởi dấu cách.

[I/O example]
2  :// số hành tinh của dải ngân hà.
1 2 1 1 :// vị trí của 2 hành tinh [1 2] và khối lượng của 2 hành tinh [1 1].
2
1 2 1 1000
2
457 468 333 321
3
1 2 3 1 2 1
4
2 3 5 7 3 2 7 5
5
3 11 12 19 29 542 661 450 521 366
6
42 75 88 94 113 144 669 551 355 344 294 155
7
62 86 279 323 363 516 579 810 749 736 297 136 107 52
8
10 34 64 73 93 97 101 122 466 463 441 373 315 292 225 83
10
9 14 38 39 48 73 179 190 207 302 560 497 640 722 437 259 449 470 709 520
[OUTPUT]
#1 1.5000000000
#2 1.0306534300
#3 462.5504629633
#4 1.4060952085 2.5939047915
#5 2.5328594461 3.7271944335 6.0999536409
#6 6.3428568767 11.5477377494 15.9641592998 24.9267991615
#7 57.8805685415 81.8651598883 91.0573691382 105.0835650491 133.2934094881
#8 74.2211477711 190.6837563313 305.8269181686 348.3304429927 470.2694219293 555.4943093854
#9 21.5171374463 47.9890597763 68.6536668433 82.9131954023 95.0052272762 99.1999097770 116.4978330953

#10 11.5573600056 24.0238341337 38.4847676134 44.6137453708 64.7500445424 126.9908128982 184.3221650927 197.9760596291 266.0574653677

[Giải thuật]

1. Với n ( H1,H2,H3,H3,...Hn) hành tinh thì có n - 1 vị trí căn bằng. Các vị trí này nằm ở khoảng giữa giữa 2 hành tinh (Xk, Xk+1). (1 <= k <=n-1)
2. Trong khoảng (Xk, Xk+1) ta lấy điểm chính giữa (điểm P1) và tính lực tác động của tất cả các hành tinh bên trái M và bên phải M lên hành tinh M. Nếu lực hút của các hành tinh bên trái lớn hơn bên phải thì điểm cân bằng sẽ nằm bên phải của điểm P1. Nếu lực hút của các hành tinh nằm bên phải lớn hơn bên trái thì điểm cân bằng sẽ nằm bên trái điểm P1.
3. Giả sử lực hút của các hành tinh nằm bên trái M lớn hơn bên phải thì điểm cân bằng sẽ nằm bên phải P1. Giờ xét điểm P2 nằm giữa P1 và Xk+1 và lặp lại bước 2. Cứ tiếp tục chia nhỏ như vậy cho đến khi khoảng cách của đoạn thẳng đủ nhỏ ( <= 1/10^9).
4. Ta được điểm Pn là điểm cần tìm.

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

 
#include<iostream>
#include<stdio.h>
using namespace std;
int n;
#define nMax 11
int material[nMax][2];
int main(){
 freopen("POINTOFBALANCE.INP","r", stdin);
 freopen("POINTOFBALANCE.OUT","w", stdout);
 for(int tc=1;tc<=10;tc++){
  cin>>n;
  for(int j=1;j<=n;j++){
   cin>>material[j][0];
  }
  for(int j=1;j<=n;j++){
   cin>>material[j][1];
  }
  cout<<"#"<<tc<<" ";
  double gravitationalLeft, gravitationalRight;
  for(int k=1;k<n;k++){
   double leftPoint = material[k][0];
   double rightPoint = material[k+1][0];
   double middle = rightPoint;
   while(rightPoint - leftPoint > 0.000000000001){
    middle = (rightPoint - leftPoint)/2 + leftPoint;
    gravitationalLeft = gravitationalRight =0;
    for(int i=1;i<n && material[i][0]<middle;i++){
     gravitationalLeft+=material[i][1]/((material[i][0] - middle) * (material[i][0] - middle));
    }
    for(int j=n;j>1 && material[j][0] > middle; j--){
     gravitationalRight+=material[j][1]/((material[j][0] - middle) * (material[j][0] - middle));
    }
    if(gravitationalLeft < gravitationalRight) rightPoint = middle;
    else if(gravitationalLeft > gravitationalRight)  leftPoint = middle;
    else { break;}
   }
   printf("%.10lf ",middle);
  }
  cout<<endl;

 }
 return 0;
}

[Bài toán] Đổi chỗ các phần tử trong mảng để được số lớn nhất.

Bài toán: Trong một chương trình truyền hình, người chơi có cơ hội nhận được một số tiền thưởng. Số tiền được ghi lên các card (bảng). Người chơi phải đổi chỗ 2 card bất kỳ theo một số lần quy định cho trước để được số tiền lớn nhất có thể.
Ví dụ: Có 5 card sau: 3, 2, 8, 8, 8 và người chơi phải đổi chỗ 2 lần cho mỗi card bất kỳ để được một số lớn hơn. Số tiền đó tương đương với số tiền thưởng mà người chơi có thể nhận được.
Người chơi có thể đổi chỗ như sau:

• Trước khi đổi: 3 2 8 8 8
• Đổi chỗ lần 1: Đổi chỗ card có giá trị 3 cho card có giá trị 8 ta được: 8 2 8 3 8.
• Đổi chỗ lần 2: Đổi chỗ card có giá trị 2 cho card có giá trị 8 ta được: 8 8 8 3 2.

Vậy sau 2 lần đổi chỗ số tiền thưởng tối đa mà người chơi có thể nhận được là : $88832.
Chú ý rằng: Người chơi phải thực hiện đổi chỗ các card theo số lần cho trước.
Ví dụ: Chương trình đưa ra 2 card : 9 4 , và người chơi phải đổi chỗ 1 lần.
Khi đó người chơi phải thực hiện đổi chỗ ít nhất 1 lần. Ta được 4 9.
Vậy số tiền mà người chơi có thể nhân được là $49.

Yêu cầu: Hãy tìm cách đổi chỗ các card để được số tiền thưởng lớn nhất.
[Input]
Dòng đầu ghi số lượng test case.
các dòng phía sau ghi danh sách card và số lần được phép đổi.
[Output]
Trên mỗi dòng in ra #C và số tiền lớn nhất mà người chơi có thể nhận được. Trong đó #C và số tiền được ngăn cách bởi một khoảng trắng.
[I/O Example]
Input.
10 // số lượng test case.
431159 7 // danh sách card (431159) và số lần đổi (3)
2737 1
757148 1
78466 2
32888 2
777770 5
436659 2
431159 7
112233 3
456789 10
Output
#1 954311
#2 7732
#3 857147
#4 87664
#5 88832
#6 777707
#7 966453
#8 954311
#9 332211
#10 987654
[Thuật toán]

1. Với một mảng các chữ số a1,a2,a3,....an (đại diện cho danh sách card). Nếu ta đổi chỗ ai với aj ( j > i và aj > ai) thì ta được một số lớn hơn. 
2. Từ trái qua phải tại vị trí i bất kỳ nếu tại vị trí k ( k > i) mà ak là số lớn nhất nằm bên phải của ai và ak >= ai thì ta sẽ đổi chỗ 2 số đó cho nhau.
3. Nếu đi từ trái qua phải mà không có vị trí nào thỏa mãn để đổi chỗ thì ta sẽ đổi chỗ 2 vị trí cuối.

Ví dụ: Với 2 lần đổi hãy đổi chỗ các card  3 2 8 8 8 để được số lớn nhất.

1. Đi từ trái qua phải, xét các vị trí từ 1 đến 5. Gặp số 3 (vị trí 1), trong các số bên phải 3 số lớn nhất tận tùng bên phải là số 8 (vị trí 5). Ta đổi chỗ số ở vị trí 1 với vị trí 5, ta được 8 2 8 8 3.
2. Lặp lại bước 1. Gặp số 2 (vị trí 2), trong các số bên phải số 2 số lớn nhất tận cùng bên phải là số 8 (vị trí 4). Ta đổi chỗ số ở vị trí 2 với vị trí 4, ta được 8 8 8 2 3.
3. Ta nhận thấy trong các các số được đổi sang bên phải số 2 (đổi sang vị trí 4) số 3 (đổi sang vị trí 5). Vì 2 số này có thể được đổi cho nhau mà không bị tính là mất thêm 1 bước đổi nên ta sắp xếp lại 2 số này theo thứ tự giảm dần được 3 > 2. Vậy vị trí 4 sẽ điền 3 và vị trí 5 sẽ điền 2.

• Vậy ta đã mất 2 lần đổi như sau : Đổi số 3 (vị trí 1) cho số 8 (vị trí 5) và đổi số 2 (vị trí 2) cho số 8 (vị trí 4) được số  8 8 8 3 2. đây là số lớn nhất sau 2 lân đổi.

Mình sẽ cung cấp chương trình cài đặt, nếu bạn nào muốn biết thêm về thuật toán hãy comment phía dưới mình sẽ trả lời nhé.
Chương trình cài đặt:

#include<iostream>
using namespace std;
int main(){
 freopen("BIGGESTPRIZE.INP", "r", stdin);
 freopen("BIGGESTPRIZE.OUT", "w", stdout);
 char cards[7];
 char swapsCards[7];
 int cardNo;
 int swapNum;
 int theGreatestNumberIndex;
 for (int t = 1; t <= 10; t++){
  for (int i = 0; i<6; i++){
   swapsCards[i] = '0';
  }
  cin >> cards >> swapNum;
  for (int i = 0; i <= 6; i++){
   if (cards[i] == '\0'){
    cardNo = i; break;
   }
  }
  while (swapNum > 0){
   bool isHas = false;
   int i;
   for (i = 0; i<cardNo - 1; i++){
    theGreatestNumberIndex = i + 1;
    for (int j = i + 1; j<cardNo; j++){
     if (cards[i]<cards[j] && cards[j] >= cards[theGreatestNumberIndex]){
      theGreatestNumberIndex = j;
      isHas = true;
     }
    }
    if (isHas){
     char temp = cards[i];
     cards[i] = cards[theGreatestNumberIndex];
     cards[theGreatestNumberIndex] = temp;
     swapsCards[theGreatestNumberIndex] = temp;
     break;
    }
   }
   if (!isHas){
    char temp = cards[cardNo - 1];
    cards[cardNo - 1] = cards[cardNo - 2];
    cards[cardNo - 2] = temp;
   }
   swapNum--;
  }

  for (int i = 0; i<cardNo; i++){
   for (int j = i + 1; j<cardNo; j++){
    if (swapsCards[i] != '0' && swapsCards[j] != '0' && swapsCards[i] < swapsCards[j]){
     char temp = swapsCards[i];
     swapsCards[i] = swapsCards[j];
     swapsCards[j] = temp;
    }
   }
  }
  for (int i = 0; i<cardNo; i++){
   if (swapsCards[i] != '0'){
    cards[i] = swapsCards[i];
   }
  }
  cout << "#" << t << " " << cards << endl;

 }
 return 0;

}

[Bài toán] Xếp hạng học sinh trong lớp.

Bài toán: Lớp học có n học sinh vừa trải qua kỳ thi cuối học kỳ I. Sau khi công bố điểm thi của các học sinh. Giáo viên chủ nhiệm muốn xem thứ tự xếp hạng của mỗi thí sinh.
Giới hạn thời gian : 1 sec.
[Input]
Dữ liệu đầu vào được lưu trong file INPUT.TXT. Dòng đầu chứa số lượng test case. Tiếp theo là danh sách test case.
Dòng đầu theo là số học sinh của hớp. N. ( 10 <= N <= 300000)
Dòng tiếp theo là điểm của các học sinh.Si ( 1 <= ST <= 32000)
[Output]
In ra kết quả ra file OUTPUT.TXT theo mỗi dòng thứ tự xếp hạng của mỗi thí sinh từ 1 cho đến N.
[I/O Example]
Input
2
10
1 2 3 4 5 6 7 8 9 9
10
27 22 15 30 29 12 20 13 6 10

Output
10 9 8 7 6 5 4 3 1 1
3 4 6 1 2 8 5 7 10 9

Chương trình giải:

 
#include <cstdio>
#include <iostream>
using namespace std;
int N;
int Si[300005];
int ranking[32001];
int repeat[32001];
int maxValue;
int minValue;
int main(int argc, char** argv)
{
 int tc, T, i;
 freopen("INPUT.TXT", "r", stdin);
 freopen("OUTPUT.TXT", "w", stdout);

 cin >> T;
 for (tc = 0; tc < T; tc++)
 {
  cin >> N;
  int rank = 1;
  fill_n(repeat, 32001, 0);
  maxValue = minValue = 0;
  for (i = 1; i <= N; i++) {
   cin >> Si[i];
   repeat[Si[i]]++;
   maxValue = maxValue < Si[i] ? Si[i] : maxValue;
   minValue = minValue < Si[i] ? minValue : Si[i];
  }
  while (maxValue >= minValue){
   if (repeat[maxValue] > 0){
    ranking[maxValue] = rank;
    rank += repeat[maxValue];
   }

   maxValue--;

  }
  for (int i = 1; i <= N; i++){
   cout << ranking[Si[i]] << " ";
  }
  cout << endl;
 }
 return 0;//Your program should return 0 on normal termination.
}