# data[].attributes.body
- Đặng Thị Mỹ Hoà
+ STT - 10
- Hoàng Chung Nghĩa
+ STT - 24
- Lê Thế Phú
+ STT - 41
- Trần Hoàng Anh
+ STT - 63

# data[].attributes.body
Input : Chuỗi kí tự (chuoi[])

Output : Chuỗi đã được mã hoá

# data[].attributes.body
1.Chọn ký tự đầu tiên từ chuỗi nguồn.

2. Nối ký tự đã chọn vào chuỗi đích.

3. Đếm số lần xuất hiện tiếp theo của ký tự được chọn và thêm số đếm vào chuỗi đích.

4.Chọn ký tự tiếp theo và lặp lại các bước 2, 3 và 4 nếu KHÔNG đến cuối chuỗi

# data[].attributes.body
Input: Dãy số (a), số phần tử (n)
Output: Dãy số tăng dần

# data[].attributes.body
1.   Một mảng được chia thành các mảng con bằng cách chọn một phần tử trục ( thường thì người ta phần tử đầu tiên,phần tử cuối cùng hoặc phần tử trung tâm làm phần tử trục).

2.   Trong khi chia mảng, phần tử trục phải được định vị sao cho các phần tử nhỏ hơn trục được giữ ở phía bên trái và các phần tử lớn hơn trục nằm ở phía bên phải của trục

3.   Các mảng con bên trái và bên phải cũng được chia theo cách tiếp cận tương tự. Quá trình này tiếp tục cho đến khi mỗi mảng con chứa một phần tử duy nhất(Đệ Quy)

4.   Tại thời điểm này, các yếu tố đã được sắp xếp. Cuối cùng, các phần tử được kết hợp để tạo thành một mảng được sắp xếp

# data[].attributes.body
#include<stdio.h>
#include<stdlib.h>
int n;
//Sap xep
void NhapMang(int arr[], int n){
for(int i =1 ; i<=n ;i++){
printf("Nhap so thu %d : ",i);
scanf("%d",&arr[i]);
}
}

void Xuatmang(int arr[], int n){
for(int i = 1; i<= n; i++)
printf("%d ",arr[i]);
}

void Doicho(int &a ,int &b){
int tg = a;
a = b;
b = tg;
}

//QuickSort
void Quicksort(int arr[], int l, int r){
if(l < r){
int p = arr[(l+r)/2];
int i = l ,j = r;
while(i <= j ){
while(arr[i] < p )
i++;
while(arr[j] > p )
j--;
if(i <= j ){
if(i < j){
Doicho(arr[i],arr[j]);
Xuatmang(arr, n);
}
i++;
j--;
}
}
Quicksort(arr,i,r);
Quicksort(arr,l, j);
}
}

main(){
int dso[100];
printf("\n4. Quick Sort\n");
printf("Nhap bao nhieu phan tu: ");
scanf("%d", &n);
NhapMang(dso,n);
printf("Day so : \n");
Xuatmang(dso, n);
Quicksort(dso,1,n);
printf("\nDay so sau khi sap xep Quicksort: \n");
Xuatmang(dso, n);

}

# data[].attributes.body
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char *mahoa(char *a){
int i=0,dem,j=0,k;
char *tg = new char[2*strlen(a)+1];
char demdodai[100];

while(i < strlen(a)){
tg[j]= a[i];
j++;
dem=1;
while(i+1<strlen(a) && a[i]==a[i+1]){
dem++;
i++;
}
sprintf(demdodai, "%d", dem); //dung de tao chuoi tu cac kieu du lieu nguyen thuy nhu float,int,double
k = 0;
while(demdodai[k] != '\0') {
tg[j] = demdodai[k];
++j;
++k;
}
i++;
}
tg[j] = '\0';
return tg;
}
main()
{
char chuoi[100];
puts("Nhap chuoi ");
gets(chuoi);
char *dich = mahoa(chuoi);
puts("\tChuoi Dich: ");
printf("\t%s", dich);

}

# data[].attributes.body
Input: chuỗi cha (a), chuỗi cần tìm (b), mảng số (c), số phần tử (n)

Output: mảng gồm các vị trí bắt đầu của chuỗi (b) trong (a)

# data[].attributes.body
Lần lượt xét từng chữ cái trong chuỗi (a) với chữ cái đầu tiên của chuỗi (b)

Khi phát hiện chữ cái trong chuỗi (a) trùng với chữ cái đầu tiên của chuỗi (b), ta bắt đầu tiến trình so sánh, lần lượt so sánh từng chữ cái tiếp theo của chuỗi (a) với từng chữ cái tiếp theo của chuỗi (b):

Khi đang thực hiện tiến trình so sánh, lưu vị trí xuất hiện đầu tiên tiếp theo của chữ cái đầu (b) trong (a), gọi là ‘vị trí lưu’.

Nếu tất cả chữ cái trong (b) được phát hiện liên tiếp trong (a). lưu vị trí bắt đầu của chuỗi (b) trong (a) vào mảng (c) -> thoát tiến trình so sánh, thực hiện 'Tiếp tục'

Nếu phát hiện chữ cái của (a) không trùng với chữ cái trong (b) -> thoát tiến trình so sánh, thực hiện 'Tiếp tục'

'Tiếp tục': nếu có ‘vị trí lưu’ thì quay lại xét các chữ cái trong (a) từ vị trí lưu. Nếu không thì tiếp tục xét từ chữ cái tiếp theo

Thực hiện đến khi xét hết chữ cái trong chuỗi (a) thì dừng.

# data[].attributes.body
#include <stdio.h>
#include <string.h>
void search(char a[], char b[], int arr[], int *n)
{
int i = 0, j = 0, jump = 0, saveJump = 0, reset = 0;
int len_1 = strlen(a);
int len_2 = strlen(b);
while(i < len_1)
{
if(j > 0 && saveJump == 0 && a[i] == b[0])
{
jump = i;
saveJump = 1;
}
if(a[i] == b[j]) j++;
else if(j > 0)
reset = 1;
if(j == len_2)
{
arr[*n] = i-len_2+1;
(*n)++;
reset = 1;
}
i++;
if(i == len_1 || reset == 0) continue;
reset = 0;
j = 0;
if(saveJump != 0)
{
i = jump;
saveJump = 0;
continue;
}
}
}
void print(int indexs[], int n)
{
int i;
printf("Vi tri: ");
for(i = 0; i < n; i++)
printf("%d ", indexs[i]);
}
main()
{
char a[255], b[255];
int n = 0;
int arr[100];
fflush(stdin);
printf("Nhap chuoi a: ");
gets(a);
printf("Nhap chuoi b: ");
gets(b);
search(a, b, arr, &n);
print(arr, n);
}

# data[].attributes.body
-        Input: Chuỗi kí tự văn bản, Chuỗi kí tự mẫu (có chứa các kí tự ‘*’ và ‘?’ trong đó ‘?’ đại diện cho 1 kí tự bất kì, ‘*’ đại diện cho chuỗi kí tự bất kỳ kể cả chuỗi rỗng).

-        Output: Chuỗi mẫu có khớp với chuỗi văn bản hay không.

# data[].attributes.body
-        Xét từng kí tự trong chuỗi mẫu:

Trường hợp 1: kí tự đang xét là ‘*’. Ở đây ta có hai trường hợp:

a)    Chúng ta có thể bỏ qua kí tự ‘*’ và xét kí tự tiếp theo trong chuỗi mẫu.

b)   Kí tự ‘*’ khớp với 1 hoặc nhiều ki tự trong chuỗi văn bản. Lúc này chúng ta xét kí tự tiếp theo trong chuỗi.

Trường hợp 2: kí tự đang xét là ‘?’: chúng ta bỏ qua kí tự đang xét trong văn bản và xét tiếp kí tự tiếp theo trong chuỗi mẫu và văn bản.

Trường hợp 3: kí tự đang xét không phải kí tự đại diện: nếu hai kí tự đang xét trong chuỗi mẫu và chuỗi văn bản không khớp thì chuỗi mẫu và chuỗi văn bản không khớp, nếu có thì xét tiếp kí tự tiếp theo trong mẫu và văn bản.

-        Chúng ta dùng một mảng hai chiều để giải:

T[i][j] = 1 nếu và chỉ nếu i kí tự đầu tiên trong chuỗi văn bản khớp với j kí tự đầu tiên trong chuỗi mẫu.

Ngược lại T[i][j] = 0.

Với n là độ dài chuỗi văn bản, m là độ dài chuỗi mẫu.

+) Khởi tạo mảng hai chiều với T[i][j] = 0 (i chạy từ 0 đến n, j chạy từ 0 đến m)

+) Đầu tiên hai chuỗi rỗng thì luôn khớp nhau: T[0][0] = 1.

+) Tiếp theo đối sánh mẫu với chuỗi rỗng, ta chỉ xét các kí tự ‘*’ ở chuỗi rỗng (chỉ có ‘*’ mới khớp với chuỗi rỗng):

a.     T[0][j] = 1 khi kí tự thứ j trong mẫu là ‘*’ và j – 1 kí tự đầu tiên trong mẫu khớp với chuỗi rỗng.

b.    T[0][j] = 0 khi kí tự thứ j trong mẫu là ‘*’ và j – 1 kí tự đầu tiên trong mẫu không khớp với chuỗi rỗng.

=> T[0][j] = T[0][j – 1] khi kí tự thứ j trong mẫu là ‘*’.

+) Tiếp theo ta đối sánh lần lượt từng kí tự thứ i trong văn bản và thứ j trong mẫu:

·       Hai trường hợp nảy sinh nếu kí tự thứ j trong chuỗi mẫu là ‘*’:

a.     Kí tự ‘*’ khớp với chuỗi rỗng: bỏ qua kí tự j.

b.    Kí tự ‘*’ khớp với i kí tự đầu tiên của chuỗi văn bản

T[i][j] = T[i][j - 1] || T[i - 1][j]

·       Nếu kí tự thứ j trong mẫu đang xét là ‘?’ hoặc hai kí tự đang xét khớp nhau thì bỏ qua hai kí tự đó:

T[i][j] = T[i – 1][j – 1]

·       Nếu 2 kí tự đang xét không phải kí tự đại diện và không khớp nhau:

T[i][j] = 0

Kết quả: Nếu T[n][m] = 1 thì chuỗi văn bản khớp với chuỗi mẫu, ngược lại thì không.

# data[].attributes.body
#include<stdio.h>

#include<conio.h>

#include<string.h>

int isMatch(char pattern[], int m, char text[], int n){

// Khi chuoi mau rong:

// Neu chuoi van ban khong rong thi tra ve dung,

// neu khong thi nguoc lai

if (m == 0)

return (n == 0);

//Khai bao mang kiem tra:

int lookup[n + 1][m + 1];

//Khoi tao mang:

for(int i = 0; i <= n; i++)

for(int j = 0; j <= m; j++)

lookup[i][j] = 0;

lookup[0][0] = 1;//Hai chuoi rong thi khop nhau

//Chi co ki tu '*' khop voi chuoi rong:

for(int j = 1; j <= m; j++)

if(pattern[j - 1] == '*')

lookup[0][j] = lookup[0][j - 1];

//Thuc hien quy hoach dong de tinh tiep:

for(int i = 1; i <= n; i++){

for(int j = 1; j <= m; j++){

// Hai truong hop neu la ki tu '*'

// a) Bo qua ki tu '*' xet tiep

//    ki tu tiep theo cua chuoi mau,

//    Tuc la '*' khop voi chuoi rong.

// b) ki tu '*' khop voi i ki tu

//    dau tien trong chuoi van ban

if (pattern[j - 1] == '*')

lookup[i][j]

= lookup[i][j - 1] || lookup[i - 1][j];

// Ki tu dang xet khop o 2 truong hop:

// (a) ki tu o chuoi mau dang xet la '?'

// (b) hai ki tu dang xet khop nhau

else if (pattern[j - 1] == '?'

|| text[i - 1] == pattern[j - 1])

lookup[i][j] = lookup[i - 1][j - 1];

// Neu 2 ki tu dang xet khong khop

else

lookup[i][j] = 0;

}

}

return lookup[n][m];

}

main(){

char sm[1000], sn[1000];

printf("Nhap xau van ban: ");

gets(sn);

printf("Nhap xau mau: ");

gets(sm);

if(isMatch(sm, strlen(sm), sn, strlen(sn)))

printf("Khop!");

else

printf("Khong khop!");

}

# data[].attributes.body
Input: dãy số (a), số phần tử (n)

Output: dãy số tăng dần

# data[].attributes.body
Chọn phần tử chốt là phần tử cuối cùng của dãy.

Chọn phần tử trái lớn hơn phần tử chốt (duyệt từ đầu đến cuối danh sách, không tính phần tử chốt)

Chọn phần từ phải nhỏ hơn phần tử chốt (duyệt từ cuối đến đầu danh sách, không tính phần tử chốt)

Hoán vị phần tử trái và phần tử phải.

Tiếp tục cho đến khi vị trí của phần tử trái lớn hơn vị trí của phần tử phải thì dừng.

Sau khi dừng, hoán vị phần tử trái và phần tử chốt. Lúc này các phần tử nhỏ hơn chốt sẽ nằm bên trái, các phần tử lớn hơn chốt nằm bên phải. Trả về vị trí phần tử chốt.

Tiếp tục thực hiện các công việc trên với các mảng con được chia ra từ vị trí trả về.

# data[].attributes.body
int partition(int arr[], int min, int max) {
int pv = arr[max], left = min, right = max-1;
while(true) {
while(left <= right && arr[left] < pv)
left++;
while(left <= right && arr[right] >= pv)
right--;
if(left > right)
break;
swap(&arr[left], &arr[right]);
left++;
right--;
}
swap(&arr[left], &arr[max]);
return left;
}
void quick_sort(int arr[], int min, int max) {
if(min < max) {
int t = partition(arr, min, max);
quick_sort(arr, min, t-1);
quick_sort(arr, t+1, max);
}
}

# data[].attributes.body
Input: Dãy số (a), khóa(k)
Output: Dãy số đã mã hóa

# data[].attributes.body
- Ta có bảng ký tự 26 chữ cái A, B, C, …Z và các chữ số 0-9 được xếp thành một vòng tròn
- Sắp hai bảng chữ cái trên hai hàng song song với nhau
- Bảng chữ cái mật mã sẽ là bảng chữ cái thô đã được dịch sang trái hoặc sang phải một số vị trí.
- Đi từ đầu chuỗi đến cuối chuỗi:

Nếu a[i] là chữ số:

Nếu a[i] + k > '9' trong bảng mã ASCII thì a[i] sẽ dịch sang phải a[i]+k-10 vị trí

Nếu a[i] + k <= '9' trong bảng mã ASCII thì a[i] sẽ dịch sang phải a[i]+k vị trí

Nếu a[i] là chữ cái thường:

Nếu a[i] + k > 'z' trong bảng mã ASCII thì a[i] sẽ dịch sang phải a[i]+k-26 vị trí

Nếu a[i] + k <= 'z' trong bảng mã ASCII thì a[i] sẽ dịch sang phải a[i]+k vị trí

Nếu a[i] là chữ cái hoa:

Nếu a[i] + k > 'Z' trong bảng mã ASCII thì a[i] sẽ dịch sang phải a[i]+k-26 vị trí

Nếu a[i] + k <= 'Z' trong bảng mã ASCII thì a[i] sẽ dịch sang phải a[i]+k vị trí

# data[].attributes.body
#include <stdio.h>
#include <string.h>
int ktracThuong(char a)
{
if ((a>='a'&&a<='z'))
return 1;
return 0;
}
int ktracHoa(char a)
{
if ((a>='A'&&a<='Z'))
return 1;
return 0;
}
int ktraSo(char a)
{
if (a>='0'&&a<='9')
return 1;
return 0;
}
char* maHoa(char mm[], int n)
{
for (int i=0; i<strlen(mm);i++)
if(ktraSo(mm[i])==1)
if ((mm[i]+n) > '9')
mm[i] = mm[i]+n-10;
else
mm[i]=mm[i]+n;
else
if(ktracThuong(mm[i])==1)
if ((mm[i]+n) > 'z')
mm[i]=mm[i]+n-26;
else
mm[i]=mm[i]+n;
else
if(ktracHoa(mm[i])==1)
if ((mm[i]+n) > 'Z')
mm[i]=mm[i]+n-26;
else
mm[i]=mm[i]+n;
return mm;
}
main()
{
char matma[50];
int n;
printf("Nhap chuoi can ma hoa: ");
gets(matma);
printf("Nhap mat ma: ");
scanf("%d", &n);
printf("Chuoi sau khi ma hoa la: %s", maHoa(matma, n));
}

# data[].attributes.body
-        Input: Dãy số (a), số phần tử (n)

-        Output: dãy số tăng dần.

# data[].attributes.body
Ta coi các phần tử từ vị trí i = 1 đến [(n – 1) / 2] và từ j = [(n - 1) / 2] + 1 đến n đã được sắp xếp.

Lúc này ta dùng thuật toán trộn để trộn hai phần trên:

-        So sánh 2 khóa từ đầu dãy.

-        Chọn ra khóa nhỏ hơn đưa vào mảng tạm, sau khi chọn thì tăng biến vị trí của phần có khóa được chọn và mảng tạm lên 1.

-        Lần lượt làm cho đển khi một phần được chọn hết, đưa phần dư còn lại vào mảng tạm.

-        Sao chép mảng tạm vào dãy số.

# data[].attributes.body
#include<stdio.h>

void NhapMang(int arr[], int n){

for(int i =1 ; i<=n ;i++){

printf("Nhap so thu %d : ",i);

scanf("%d",&arr[i]);

}

}

void XuatMang(int arr[], int n){

for(int i = 1; i<= n; i++)

printf("%d ",arr[i]);

}

void MergeSort(int data[], int left, int right) {

if (right - left < 1)

return;

int mid = (left + right) / 2;

MergeSort(data, left, mid);

MergeSort(data, mid+1, right);

int i = left, j = mid + 1;

int cur = 0;

int a[right + 1];

while (i <= mid || j <= right)

if (i > mid)

a[cur++] = data[j++];

else if (j > right)

a[cur++] = data[i++];

else if (data[i] < data[j])

a[cur++] = data[i++];

else

a[cur++] = data[j++];

for (int i = 0; i < cur; i++)

data[left + i] = a[i];

}

main(){

int dso[1000], n;

printf("Nhap bao nhieu phan tu: ");

scanf("%d", &n);

NhapMang(dso, n);

printf("\nDay so : ");

XuatMang(dso, n);

MergeSort(dso, 1, n);

printf("\nDay so sau khi sap xep MergeSort: ");

XuatMang(dso, n);

}

# data[].attributes.body
-        Input: Dãy số (a), số phần tử (n)

-        Output: dãy số tăng dần.

# data[].attributes.body
Ta chọn một phần tử làm chốt (để dễ dàng thì chọn phần tử đầu)

Chuyển những phần tử bé hơn phần tử chốt sang trái phần tử chốt, những phần tử còn lại sang phải.

Sắp xếp 2 mảng con bên trái và bên phải của phần tử chốt

# data[].attributes.body
#include<stdio.h>

void NhapMang(int arr[], int n){

for(int i =1 ; i<=n ;i++){

printf("Nhap so thu %d : ",i);

scanf("%d",&arr[i]);

}

}

void XuatMang(int arr[], int n){

for(int i = 1; i<= n; i++)

printf("%d ",arr[i]);

}

void swap(int &x, int &y){

int tg = x;

x = y;

y = tg;

}

void quickSort(int a[], int left, int right) {

int i = left, j = right;

int prio = a[left];

while (i <= j) {

while (a[i] < prio) ++i;

while (a[j] > prio) --j;

if (i <= j) {

swap(a[i], a[j]);

++i;

--j;

}

}

if (left < j) quickSort(a, left, j);

if (i < right) quickSort(a, i, right);

}

main(){

int dso[1000], n;

printf("Nhap bao nhieu phan tu: ");

scanf("%d", &n);

NhapMang(dso, n);

printf("\nDay so : ");

XuatMang(dso, n);

quickSort(dso, 1, n);

printf("\nDay so sau khi sap xep quickSort: ");

XuatMang(dso, n);

}

# data[].attributes.body
- Input: Dãy số (a), số phần tử (n)

- Output: Dãy số tăng dần

# data[].attributes.body
-        Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng phần tử của mảng với một phần tử được gọi là phần tử chốt. Một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và một mảng gồm các phần tử lớn hơn phần tử chốt.

-        Quá trình phân chia này diễn ra cho đến khi độ dài của các mảng con đều bằng 1

# data[].attributes.body
#include <stdio.h>

void NhapMang(int arr[],int n)

{

for(int i=1;i<=n;i++)

{

printf("Nhap phan tu thu %d: ",i);

scanf("%d",&arr[i]);

}

}

void XuatMang(int arr[],int n)

{

for(int i=1;i<=n;i++)

printf("  %d  ",arr[i]);

}

void HoanVi(int &a,int &b)

{

int tg=a;

a=b;

b=tg;

}

void QuickSort(int a[], int tr, int ph)

{

if (tr>=ph)

return;

int chot = a[(tr+ph)/2];

int i=tr;

int j=ph;

do

{

while(a[i]<chot)

i++;

while(a[j]>chot)

j--;

if (i<=j)

{

HoanVi(a[i], a[j]);

i++;

j--;

}

}

while(i<j);

QuickSort(a, tr, j);

QuickSort(a, i, ph);

}

main()

{

int dso[100], ptu;

printf("Nhap bao nhieu phan tu: ");

scanf("%d",&ptu);

NhapMang(dso, ptu);

printf("Day so vua nhap la: ");

XuatMang(dso, ptu);

QuickSort(dso, 1, ptu);

printf("\nDay so sau khi sap xep la:\n");

XuatMang(dso, ptu);

}