Bài tập phần Backtracking

Bài tập phần Backtracking: download.

Ôn tập Olympic 2015

Gửi các bạn tham dự ôn tập Olympic Tin học 2015:

Tài liệu tham khảo:

1. Tài liệu thuật toán của Lê Minh Hoàng: download.

2. Tài liệu “Art of Programming Contest”, 2nd Edition: download.

Bài học ngày 31-01-2015:

1. Bài tập trên lớp và về nhà: download.

2. Bài giải cho các bài tập trên lớp: download.

Sách hay mỗi tuần

Giới thiệu một số cuốn sách hay:

1. Discrete mathematics and its applications, 7th edition, 2012, Rosen, Kenneth H. Cuốn sách rất hay và đầy đủ, cập nhật về các chủ đề của Toán rời rạc. Download tại địa chỉ này.

2. Numerical recipes: the art of scientific computing, 3rd edition, 2007, William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Một tuyệt tác viết về các phương pháp số. Địa chỉ download.

3. Operating System Concepts, 9th Edition, 2012. Abraham Silberschatz, Peter B. Galvin, Greg Gagne. Một cuốn sách rất hay về nguyên lý của các hệ điều hành (Windows, Unix, Linux, Mac OS và cả các hệ thống di động như iOS, Android). Download tại đây.

4. Data Structures and Algorithm Analysis, Clifford A. Shaffer.  Một cuốn sách viết về cấu trúc dữ liêu, thiết kế và phân tích giải thuật khá hay và đầy đủ về nội dung. Các thuật toán trình bày trong sách có bản cài đặt bằng C++ và Java. Có thể download sách và source code tại đây.

5. Windows System Programming 4th Edition. Lập trình cho hệ điều hành Windows bằng cách sử dụng các hàm API (Win32). Download tại đây (xem link gốc tại đây).

6. Algorithms 4th Edition, cuốn sách hay viết về cấu trúc dữ liệu và giải thuật của hai tác giả Robert Sedgewick and Kevin Wayne, các ví dụ minh họa được cài đặt bằng Java. Địa chỉ Download

Bài giảng Phân tích, thiết kế và đánh giá thuật toán

Sắp xếp cơ bản – Basic sorting

Chương trình cài đặt các thuật toán sắp xếp cơ bản (sắp xếp nổi bọt (bubble sort), sắp xếp chọn (selection sort), sắp xếp chèn (insertion sort), sắp xếp nhanh (quick sort), sắp xếp trộn (merge sort), sắp xếp vun đống (heap sort)), so sánh thời gian thực hiện giữa các thuật toán và 1 hidden operation (can you find it out?).
Hình minh họa:
Vsort's image
Chương trình: download

Danh sách liên kết với ngôn ngữ C – Linked list in C programming language

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

// khai bao cau truc cho mot nut cua danh sach
typedef struct Node
{
// truong du lieu
int data;
struct Node * next;
} NodeType;

// khai bao kieu danh sach
typedef struct
{
NodeType * head;
NodeType * tail;
// so phan tu cua danh sach
int spt;
}LList;

// ham khoi tao danh sach
void init(LList * list);
// ham them 1 phan tu vao dau danh sach
void addFirst(LList *list, int d);
// ham them mot phan tu vao cuoi danh sach
void addLast(LList *list, int d);
// ham xoa phan tu o cuoi danh sach
int delLast(LList * list);
// ham xoa phan tu o dau danh sach
int delFirst(LList * list);
void insertAfter(LList * list, NodeType * p);
void insertBefore(LList * list, NodeType * p);
void removeAfter(LList * list, NodeType * p);
void removeBefore(LList * list, NodeType * p);
// ham in danh sach
void printList(LList list);
// ham sap xep danh sach
void sort(LList *list);
// ham tim kiem trong danh sach
NodeType * search(LList *, int d);
// giai phong toan bo danh sach
void freeAll(LList * list);

int main()
{
LList myList;
init(&myList);
addFirst(&myList, 10);
addFirst(&myList, 1);
addFirst(&myList, 12);
addLast(&myList, 20);
addLast(&myList, 23);
addLast(&myList, 25);
sort(&myList);
printList(myList);
freeAll(&myList);
printList(myList);
return 0;
}
void init(LList * list)
{
list->head = list->tail = NULL;
list->spt = 0;
}

void printList(LList list)
{
NodeType * tmp;
tmp = list.head;
while(tmp!=NULL)
{
printf(“%d “, tmp->data);
tmp = tmp->next;
}
printf(“\n”);
}

void addFirst(LList * list, int d)
{
NodeType * tmp = (NodeType *)malloc(sizeof(NodeType));
tmp->data = d;
if(list->spt==0)
{
tmp->next = NULL;
list->head = list->tail = tmp;
}
else
{
tmp->next = list->head;
list->head = tmp;
}
list->spt = list->spt+1;
}

void addLast(LList * list, int d)
{
NodeType * tmp = (NodeType *)malloc(sizeof(NodeType));
tmp->data = d;
tmp->next = NULL;
if(list->spt==0)
list->head = list->tail = tmp;
else
{
list->tail->next = tmp;
list->tail = tmp;
}
list->spt = list->spt+1;
}

NodeType * search(LList * list, int d)
{
NodeType * tmp = list->head;
while(tmp!=NULL)
{
if (tmp->data==d)
break;
tmp = tmp->next;
}
return tmp;
}

int delLast(LList * list)
{
NodeType * p, * q;
int ret = -1;

if(list->spt>0)
{
p = list->head;
q = NULL;
while(p->next!=NULL)
{
q = p;
p = p->next;
}
if(q!=NULL)
{
// danh sach chi co 1 phan tu
q->next = NULL;
list->tail = q;
}
else
list->head = list->tail = NULL;
ret = p->data;
free(p);
list->spt = list->spt-1;
}
return ret;
}

int delFirst(LList * list)
{
int ret=-1;
NodeType * tmp;
if(list->spt>0)
{
tmp = list->head;
if(list->spt==1)
{
// danh sach chi co 1 phan tu
ret = list->head->data;
list->head = list->tail = NULL;
}else
list->head = list->head->next;
free(tmp);
list->spt = list->spt – 1;
}
return ret;
}

// sap xep dung thuat toan doi cho truc tiep (interchange sort)
void sort(LList * list)
{
NodeType * p, * q;
int tmp;

p = list->head;
while(p!=NULL)
{
q = p->next;
while(q!=NULL)
{
if(q->data < p->data)
{
tmp = q->data;
q->data = p->data;
p->data = tmp;
}
q = q->next;
}
p = p->next;
}
}

void freeAll(LList * list)
{
NodeType * p, * q;
if(list->spt>0)
{
p = list->head;
list->head = list->tail = NULL;
list->spt = 0;
while(p)
{
q = p->next;
free(p);
p = q;
}
}
}

Danh sách liên kết với C++ – Linked list in C++


#include "iostream"
#include "ctime"
using namespace std;
class Element
{
// lop phan tu co ban
// truong du lieu quan ly
int data;
Element * next;
public:
Element(int d, Element * nxt);
friend class LList;
};

Element::Element(int d, Element * nxt):data(d), next(nxt)
{
}

class LList
{
protected:
Element * list; // con tro quan ly cac phan tu
int num; // so phan tu cua danh sach
public:
LList();
~LList();
void push_front(int d); // them vao dau
void push_back(int d); // them vao cuoi
void pop_back(); // xoa phan tu o cuoi danh sach
void pop_front(); // xoa phan tu o dau danh sach
int size()const; // kiem tra so phan tu cua danh sach
int empty()const;
int begin()const;
Element * find()const;
int end()const;
void sort();
void printList()const;
};

int LList::begin()const
{
if(num>0)
return list->data;
return INT_MAX;
}

int LList::end()const
{
Element * p = list;
if(num>0)
{
while(p->next)
p = p->next;
return p->data;
}
return INT_MAX;
}

LList::LList()
{
num = 0;
list = NULL;
cout << "LList constructor" <next!=NULL)
q = q->next;
q->next = p;
}
num ++;
}

void LList::printList()const
{
Element * p = list;
while(p)
{
cout <

data <next;
}
}

LList::~LList()
{
Element * p = list;
while(list)
{
list = list->next;
delete p;
p = list;
}
num = 0;
//cout << "LList destructor" <next;
delete p;
num --;
}
}

void LList::pop_back()
{
Element * q = list;
Element * p;
if(q)
{
p = q;
if(q->next==NULL)
list = NULL;
while(q->next!=NULL)
{
p = q;
q = q->next;
}
p->next = NULL;
delete q;
num --;
}
}

int LList::empty()const
{
return (num==0)?1:0;
}
void LList::sort()
{
Element * p, *q;
p = list;
while(p)
{
q = p->next;
while(q)
{
if(q->data

data)
{
int tam = q->data;
q->data = p->data;
p->data = tam;
}
q = q->next;
}
p = p->next;
}
}
class queue: public LList // lop hang doi ke thua tu danh sach lien ket
{
public:
queue()
{
//LList();
cout << "queue constructor" << endl;
}
};
class IntSet: public LList
{
public:
IntSet operator+(IntSet &);
IntSet operator*(IntSet &);
friend ostream & operator <data);
p = p->next;
}
p = r.list;
while(p)
{
if(!tam.find(p->data))
tam.push_front(p->data);
p = p->next;
}
return tam;
}
IntSet IntSet::operator*(IntSet & r)
{
IntSet tam;
Item * p = list;
while(p!=NULL)
{
if(r.find(p->data))
tam.push_front(p->data);
p = p->next;
}
return tam;
}
ostream & operator << (ostream &os, IntSet & r)
{
os << "{";
Item * p = r.list;
while(p)
{
os <

data <next;
}
os << "}";
return os;
}
int main()
{
queue mList;
int d; // Tested with d = 70000; 07/05/2007
time_t time = clock(); // tinh so xung nhip bat dau tu luc chuong trinh chay
// cho toi thoi diem goi ham
do
{
cout <> d;
if(d>0)
mList.push_back(d--);
}while(d>0);
mList.sort();
while(!mList.empty())
{
cout << mList.begin() << " ";
mList.pop_front();
}
time = clock() - time;
cout << (float)time/CLK_TCK;
system("pause");
return 0;
}