/* Bai toan tam hoang hau */
#include <stdio.h>
int dong[8], cot[8], cheoxuoi[15], cheonguoc[15];
void print ()
{
int i;
printf("\n");
for (i=0; i<8; i++)
printf("%3d", dong);
}
void thu(int i)
{
int j;
for (j=0; j<8; j++)
{
if (cot[j] == 1 && cheoxuoi[i+j] ==1 && cheonguoc[i-j+7] == 1)
{
dong = j;
cot[j] = 0;
cheoxuoi[i+j] = 0;
cheonguoc[i-j+7] = 0;
if (i<7)
thu(i+1);
else
print();
cot[j] = 1;
cheoxuoi[i+j] = 1;
cheonguoc[i-j+7] = 1;
}
}
}

void tim()
{
int i, q;
for (i=0; i<8; i++)
{
cot = 1;
dong = -1;
}
for (i=0; i<15; i++)
{
cheoxuoi = 1;
cheonguoc = 1;
}
thu(0);
}
void main()
{
tim();
getch();
}
/* Bai tap 3_67 - Quan ly hai STACK chi dung 1 day */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
int stack[2*MAX];
int top1, top2;
void initstack()
{
top1 = -1;

top2 = 2*MAX;
}
void push(int value, int _stack)
{
if (_stack == 0)
{
if (top1<top2)
stack[++top1] = value;
}
else
{
if (top1<top2)
stack[--top2] = value;
}
}
int isempty(int _stack)
{
if (_stack == 0)
return top1 == -1;
else
return top2 == 2*MAX;
}
int pop(int _stack)
{
if (_stack == 0)
if (!isempty(_stack))
return(stack[top1--]);
if (!isempty(_stack))
return stack[top2++];
else

return -1;
}
void main()
{
int i, value, _stack;
initstack();
randomize();
for (i = 0; i<20; i++)
{
_stack = random(2);
value = random(10);
printf("\nPUSH %d vao stack %d", value, _stack);
push(value, _stack);
}
printf("\nLay nhung gia tri tu stack 0 : ");
while (!isempty(0))
printf("%3d", pop(0));
printf("\nLay nhung gia tri tu stack 1 : ");
while (!isempty(1))
printf("%3d", pop(1));
getch();
}
/* Bai tap 3_67 - Quan ly hai STACK chi dung 1 day */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
int stack[2*MAX];
int top1, top2;
void initstack()

{
top1 = -1;
top2 = 2*MAX;
}
void push(int value, int _stack)
{
if (_stack == 0)
{
if (top1<top2)
stack[++top1] = value;
}
else
{
if (top1<top2)
stack[--top2] = value;
}
}
int isempty(int _stack)
{
if (_stack == 0)
return top1 == -1;
else
return top2 == 2*MAX;
}
int pop(int _stack)
{
if (_stack == 0)
if (!isempty(_stack))
return(stack[top1--]);
if (!isempty(_stack))

return stack[top2++];
else
return -1;
}
void main()
{
int i, value, _stack;
initstack();
randomize();
for (i = 0; i<20; i++)
{
_stack = random(2);
value = random(10);
printf("\nPUSH %d vao stack %d", value, _stack);
push(value, _stack);
}
printf("\nLay nhung gia tri tu stack 0 : ");
while (!isempty(0))
printf("%3d", pop(0));
printf("\nLay nhung gia tri tu stack 1 : ");
while (!isempty(1))
printf("%3d", pop(1));
getch();
}
/*Hang doi Queue*/
#include <stdio.h>
#define MAX 100
int queue[MAX + 1];
int front, rear, queue_size;
void khoi_tao_queue()

{
front = rear = 0;
queue_size = 0;
}
int is_empty()
{
return (queue_size == 0);
}
int is_full()
{
return (queue_size == MAX);
}
int push(int value)
{
if (queue_size < MAX)
{
queue_size++;
queue[rear++] = value;
if (rear == MAX)
rear = 0;
}
return rear;
}
int pop(int *value)
{
if (queue_size > 0)
{
*value = queue[front++];
if (front > MAX)
front = 0;

queue_size--;
}
return front;
}
void main()
{
int k;
khoi_tao_queue();
printf("\nNhap cac phan tu vao queue (-1 de ket thuc) : ");
do {
scanf("%d", &k);
if (k != -1)
push(k);
} while (k != -1 && !is_full());
printf("\n\nLay cac phan tu tu queue ra : ");
while (!is_empty())
{
pop(&k);
printf("%d ", k);
}
getch();
}
#include <stdio.h>
#define MAX 100
int stack[MAX + 1];
int top;
void khoi_tao_stack()
{
top = -1;
}

int is_empty()
{
return (top == -1);
}
int is_full()
{
return (top == MAX);
}
int push(int value)
{
if (top < MAX)
stack[++top] = value;
return top;
}
int pop(int *value)
{
*value = stack[top--];
return top;
}
void main()
{
int k;
khoi_tao_stack();
printf("\nNhap cac phan tu vao stack (-1 de ket thuc) : ");
do {
scanf("%d", &k);
if (k != -1)
push(k);
} while (k != -1 && !is_full());
printf("\n\nLay cac phan tu tu stack ra : ");

while (!is_empty())
{
pop(&k);
printf("%d ", k);
}
getch();
}
/* Chen nhi phan */
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int mang[MAX];
void in_mang(int *mang)
{
int i;
for (i=0; i<MAX; i++)
printf("%d ", mang);
}
void binarysort()
{
int i, j, x, l, r, m;
for (i=1; i<MAX; i++)
{
x = mang;
l = 0;
r = i-1;
while (l <= r)
{
m = (l + r) / 2;
if (x < mang[m])

r = m - 1;
else
l = m + 1;
}
if (x < mang[l])
{
for (j=i-1; j>=l; j--)
mang[j+1] = mang[j];
mang[l] = x;
}
}
}
void main()
{
int i;
randomize();
for (i=0; i<MAX; i++)
mang = random(100);
printf("\nTruoc khi sap : ");
in_mang(mang);
binarysort();
printf("\nSau khi sap : ");
in_mang(mang);
getch();
}
/* Bai tap 3_70 - Tim chieu cao cay */
#include <stdio.h>
#include <alloc.h>
typedef int element_type;
typedef struct node {

element_type element;
struct node *left, *right;
} NODE;
NODE *root;
#define max(a,b) ((a) > (b)? (a) : (b))
void khoi_tao_cay(NODE ** root)
{
*root = NULL;
}
void insert(NODE *tmp, NODE **root)
{
if (tmp->element < (*root)->element)
if ((*root)->left)
insert(tmp, &(*root)->left);
else
(*root)->left = tmp;
else
if ((*root)->right)
insert(tmp, &(*root)->right);
else
(*root)->right = tmp;
}
void insert_node(element_type e, NODE **root)
{
NODE *tmp;
tmp = (NODE *)malloc(sizeof(NODE));
tmp->element = e;
tmp->left = NULL;
tmp->right = NULL;
if (*root == NULL)

*root = tmp;
else
insert(tmp, root);
}
void nhap_cay(NODE **root)
{
element_type e;
do {
printf("\nNhap element (-1 de ket thuc) : ");
scanf("%d", &e);
if (e != -1)
insert_node(e, root);
} while (e != -1);
}
int chieucao(NODE *root, int start)
{
if (root == NULL)
return 0;
else
return max(chieucao(root->left, start + 1),
chieucao(root->right, start + 1)) + 1;
}
void main()
{
khoi_tao_cay(&root);
nhap_cay(&root);
printf("\nChieu cao cua cay = %d", chieucao(root, 1));
getch();
}
/* Bai tap 3_2 - Minh hoa giai thuat Boyer - Moore */

#include <stdio.h>
#include <conio.h>
#include <string.h>
#define MAX 256
int BoyerMoore(char *source, char *find);
void main()
{
char source[MAX], find[MAX];
int f;
printf("\nNhap vao chuoi nguon : ");
gets(source);
printf("Nhap vao chuoi tim kiem : ");
gets(find);
if ((f = BoyerMoore(source, find)) > 0)
printf("chuoi tim thay tai chi so %d", f);