Interval tree

Đề bài:

Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0.

Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị.

Cho q câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất thuộc đoạn [u, v]

Giới hạn

n, m, q <= 50000

k > 0

Giá trị của một phần tử luôn không vượt quá 231-1

Input

Dòng 1: n, m

m dòng tiếp theo, mỗi dòng chứa u, v, k cho biết một phép biến đổi

Dòng thứ m+2: p

p dòng tiếp theo, mỗi dòng chứa u, v cho biết một phép biến đổi

Output

Gồm p dòng chứa kết quả tương ứng cho từng câu hỏi.

Example

Input:

6 2

1 3 2

4 6 3

1

3 4

Output:

3

Gợi ý: Sử dụng interval tree

https://nguyenvanquan7826.wordpress.com/2013/11/09/spoj-qmax/

code:

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <fstream>

#include <algorithm>

#include <cmath>

//#define INP "QMAX.INP"

//#define OUT "QMAX.OUT"

using namespace std;

int ans = 0, *a, *T, n, m, q, u, v, k;

// trong do a la mang luu thong tin

// T la cay interval tree

// n la so phan tu

// m la so phep bien doi

// q la so cau hoi

// u la gia tri phan tu dau

// v la gia tri phan tu cuoi

// k gia tri trong khoang u v se duoc tang k don vi

void updateTree(int k, int l, int r){

    int c;

    if (l > r) return;

    if (l == r) {

        T[k] = a[l];

        return;

    }

    c = (l + r) / 2;

    updateTree(k*2, l, c);

    updateTree(k*2 + 1, c + 1, r);

    T[k] = max(T[k*2], T[k*2+1]);

    return;

}

void findMax(int k, int l, int r, int i, int j){

    int c;

    if (l > j || r < i) return;

    if (i <= l && j >= r){

        ans = max(ans, T[k]);

        return;

    }

    c = (l + r) / 2;

    findMax(k*2, l, c, i, j);

    findMax(k*2 + 1, c + 1, r, i, j);

    return;

}

int main(){

    //freopen(INP, "r", stdin);

    //freopen(OUT, "w", stdout);

    cout<<"Nhap hai gia tri n , m"<<endl;

    scanf("%d %d", &n, &m);//cin >> n >> m;

    a = new int[n+2];

    T = new int[4*n]; // interval tree su dung mang co so phan tu toi da la 4*n -5

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

        a[i] = 0;

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

        T[i] = 0;

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

        scanf("%d %d %d", &u, &v, &k); //cin >> u >> v >> k;

        a[u] += k;

        a[v+1] -= k;

    }

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

        a[i] = a[i] + a[i-1];

    updateTree(1, 1, n);

    scanf("%d", &q);//cin >> q;

    ans = 0;

    for (int i = 0; i < q; i++){

        scanf("%d %d", &u, &v);//cin >> u >> v;

        ans = 0;

        findMax(1, 1, n, u, v);

        cout << ans << endl;

    }

    return 0;

}

Read More

Thuật toán QuickSort trong danh sách liên kết đơn

#include<iostream>

using namespace std;

int n;

struct Node{

int data;

Node *next;// chua dia chi node ke tiep ma no tro toi

};

struct List{

Node *head;

Node *tail;

};

void Init(List &l){ // k tao List rong

l.head = l.tail = NULL;

}

Node *creatNode(int x ){ //tao thong tin cho node

Node *p = new Node;

if(p == NULL) return NULL;

p->next = NULL;

p->data = x;

return p;

}

bool isEmpty(List l ){ // k tr a xem lieu List co rong hay k.

if(l.head == NULL ) return true;

return false;

}

// chen vao dau List:

void addHead(List &l, int x ){

Node *p = creatNode(x);

if(isEmpty(l)) l.head = l.tail = p;

else{

p->next = l.head; // con tro next cua p tro toi dia chi cua node head(ban dau)

l.head = p; // cap nhat node head( luc sau )

}

}

// ham chen vao cuoi List

void addTail(List &l, int x ){

Node *p = creatNode(x);

if(isEmpty(l)) addHead(l,x);

else{

l.tail->next = p;

l.tail = p;

}

}

// tim kiem

Node *search(List l, int k ){

Node *p = l.head;

while(p!=NULL) {

if(p->data == k ) return p;

else p = p->next;

}

return NULL;

}

void addMid(List &l, int x, int k ){ // chen node co data = x vao sau node co data  = k;

Node *p = search(l,k);

if(p!=NULL){

Node *q= creatNode(x);

Node *r = p->next;

p->next = q;

q->next = r;

}

else cout<<"\nKhong tim thay node co data = k.";

}

void addAtK(List &l, int x, int k ){ // chen vi tri bat ki;

if(isEmpty(l) || k<= 1 ) addHead(l,x);

else if(k>= n) addTail(l,x);

else{

Node *p = creatNode(x);

Node *q = new Node, *w = new Node;

Node *r = l.head;

int dem = 0;

while(r!=NULL){

dem++;

q = r;

if(dem == k ) break;

else r = r->next;

}

w = l.head;

while(w->next!= q) w = w->next;

w->next = p;

p->next = r;

}

}

// nhap vao mot list bat ki

void nhap(List &l){

cout<<"\nnhap so ptu ban dau cua List: "; cin>> n;

for(int i = 1; i<= n; i++ ) addTail(l,i);

}

// xuat thong tin ra man hinh

void xuat(List l ){

Node *p = l.head;

while(p!=NULL){

cout<<" " << p->data;

p = p->next;

}

}

void delHead(List &l ){ // xoa node o dau List

if(!isEmpty(l)){

Node *p = l.head;

l.head = l.head->next; // cap nhat l.head

delete p; // xoa bo node head ban dau

}

}

void delTail(List &l ){

if(!isEmpty(l)){

Node *p = l.head;

Node *q = new Node;

while(p->next != l.tail ) p = p->next; // tim node ngay truoc tail

q = p; // gan node nay cho node q

p = p->next; // p chinh la node tail can xoa

l.tail = q; // cap nhat l.tail

l.tail->next = NULL; // cap nhat node next cho l.tail

delete p;

}

}

void delAtK(List &l, int k ){

if(k<= 1) delHead(l);

else if(k>=n) delTail(l);

else{

int dem = 0;

if(!isEmpty(l)){

Node *p = l.head;

Node *q = new Node;

while(p != NULL){ // tim node thu k.

dem++;

q = p;

if(dem == k ) break; // tim thay thi break

else p= p->next; // k thi tim tiep

}

Node *r = l.head;

while(r->next != q ) r = r->next; // tim node k-1

r->next = q->next; // cho node next cua node k-1 tro toi node k+1;

delete q;

}

}

}

void QuickSort(List &l ){

List l1, l2;

Node *tag, *p;

if(l.head == l.tail ) return;

Init(l1); Init(l2);

tag = l.head;

l.head = l.head->next; // cap nhat lai l.head

tag->next = NULL;// co lap tag

while( l.head!= NULL ){

p = l.head;

l.head = l.head->next;

p->next = NULL;

if(p->data <= tag->data ) addHead(l1,p->data);

else addHead(l2,p->data);

}

QuickSort(l1); // goi de qui sap xep l1, l2

QuickSort(l2);

if(l1.head != NULL ){ // l1 k rong

l.head = l1.head; // lay head cua l1 gan cho head cua l;

l1.tail->next = tag;

} // l1 rong

else l.head = tag;

tag->next = l2.head;

if(l2.head!= NULL ) l.tail = l2.tail;

else l.tail = tag;

}

void menu(){

List l;

Init(l);

nhap(l);

xuat(l);

int k, x, lc;

do{

cout<<"\n______MENU______\n1_Chen dau.\n2_chen cuoi."

<<"\n3_Chen sau vi tri node data = k.\n4_Chen vao vi tri bat ki."

<<"\n5_Xuat Thong tin List.\n6_Xoa phan tu dau List."

<<"\n7_Xoa phan tu o cuoi List.\n8_Xoa node o vi tri k."

<<"\n9_Sap xep QuickSort."

<<"\n0_Thoat.\n_Ban chon ? ";

cin>> lc;

switch(lc){

case 0: break;

case 1: cout<<"\nNhap x: "; cin>> x; addHead(l,x); n++; break;

case 2: cout<<"\nNhap x: "; cin>> x; addTail(l,x); n++; break;

case 3: cout<<"\nNhap x, k: "; cin>> x >> k; addMid(l,x, k);n++; break;

case 4: cout<<"\nNhap x, vi tri k: "; cin>> x >> k; addAtK(l,x,k); n++; break;

case 5: xuat(l); break;

case 6: delHead(l); n--; break;

case 7: delTail(l); n--; break;

case 8: cout<<"\nNhap vi tri k: "; cin>> k; delAtK(l,k); n--; break;

case 9: QuickSort(l); break;

}

}while(lc != 0 );

}

int main(){

menu();

return 0;

}

Read More

Lap trinh game tho va rua tren man hinh console

#include<iostream>
#include<ctime>
#include<cstdlib>
#include<string>

using namespace std;

void delay( float sec ){ // cho nay dung float or int deu dc.
 clock_t be, fin;
 be = clock();
 fin = be;
 while( fin - be <= sec )
  fin = clock();
}

void tho( int &t, int & n, int &toi_dich_t, string &str ){
 n= rand() %10 + 1;
 if( n == 4 ){
  str[t] = '.';
  t += 9;
  if( t >= 70 ) t = 70, toi_dich_t = 1;
  str[t] = 'T';
 }
 if( n == 5 ){
  str[t] = '.';
  t -= 12;
  if( t < 1 ) t = 1;
  str[t] ='T';
 }
 
 if( n == 6 || n == 7 || n == 8 ){
  str[t] = '.';
  t += 1;
  if( t >= 70 ) t = 70, toi_dich_t = 1;
  str[t] = 'T';
 }
 if( n == 9 || n == 10 ){
  str[t] = '.';
  t-= 2;
  if( t < 1 ) t = 1;
  str[t] = 'T';
 }
}

void rua( int &r, int & n, int &toi_dich_r, string &str ){
 n = rand() % 10 + 1;
 if( n <= 5 ){
  str[r] = '.';
  r+= 3;
  if( r >= 70 ) r = 70, toi_dich_r = 1;
  str[r] = 'R';
 }
 if( n == 6 || n == 7 ){
  str[r] = '.';
  r -= 6;
  if( r < 1 ) r= 1;
  str[r] ='R';
 }
 
 if( n == 8 || n == 9 || n == 10 ){
  str[r] = '.';
  r+= 1;
  if( r>= 70 ) r = 70, toi_dich_r = 1;
  str[r] = 'R';
 }
}

void tho_rua(){
 srand( time ( 0 ) );
 int t, r, toi_dich_t, toi_dich_r, n;
 t = r = 1; toi_dich_t = toi_dich_r = 0;
 string str= " "; str+= 'O';
 for( int i = 1; i < 70; i++ ) str += '.';
 cout<<"\t\t\t--------- Bang ----------"<< endl;
 cout<<"\t\t\t------- Ouch!!! -------";
 cout<< endl << str;
 while( toi_dich_t == 0 && toi_dich_r == 0 ){
  rua( r, n, toi_dich_r, str );
  tho( t, n, toi_dich_t, str );
  if( t == r ){
   cout<<"\t\t\t------- Ouch!!! -------";
   str[r] = 'O';
   cout<< endl << str; // in ra vi tri hai ae can nhau.
  }
  if( toi_dich_t == 0 && toi_dich_r == 0 && ( r != t ) ){
   str[t] = 'T'; str[r] = 'R'; // dat lai vi tri rua, tho.
   cout<< endl << str;
  }
  if( toi_dich_t == 1 && toi_dich_r == 1 ){
   cout<< endl << str;
   cout<<"\t\t\t------------ Tho & Rua Dong Hang! ------------";
  }
  if( toi_dich_t == 1 ){
   cout<< endl << str;
   cout<<"\t\t\t-----------Tho Thang! -----------";
  }
  if( toi_dich_r == 1 ){
   cout << endl <<str;
   cout<<"\t\t\t-----------Rua Thang! -----------";
  }
  delay( 100 );
 }
}

int main(){
 tho_rua();
 cout<< endl;
 return 0;
}

Read More

Danh sách liên kết vòng

// Danh sach lien ket don vong.

#include<iostream>
using namespace std;
int n;
struct Node{
int data;
Node *next;// chua dia chi node ke tiep ma no tro toi
};

struct List{
Node *head;
Node *tail;
};

void Init(List &l){ // k tao List rong
l.head = l.tail = NULL;
}

Node *creatNode(int x ){ //tao thong tin cho node
Node *p = new Node;
if(p == NULL) exit(1);
p->next = NULL;
p->data = x;
return p;
}

bool isEmpty(List l ){ // k tr a xem lieu List co rong hay k.
if(l.head == NULL ) return true;
return false;
}

// chen vao dau List:
void addHead(List &l, int x ){
Node *p = creatNode(x);
if(isEmpty(l)) l.head = l.tail = p;
else{
p->next = l.head; // con tro next cua p tro toi dia chi cua node head(ban dau)
l.head = p; // cap nhat node head( luc sau )
}
l.tail->next = l.head; // khep vong don.
}
// ham chen vao cuoi List
void addTail(List &l, int x ){
Node *p = creatNode(x);
if(isEmpty(l)) addHead(l,x);
else{
l.tail->next = p;
l.tail = p;
}
l.tail->next = l.head; // khep vong don
}
// tim kiem
Node *search(List l, int k ){
Node *p = l.head;
do {
if( p->data == k ) return p;
else p = p->next;
} while( p != l.head );
return NULL;
}

void addMid(List &l, int x, int k ){ // chen node co data = x vao sau node co data  = k;
Node *p = search(l,k);
if(p!=NULL){
Node *q= creatNode(x);
Node *r = p->next;
p->next = q;
q->next = r;
}
else cout<<"\nKhong tim thay node co data = k.";
}
/*
void addAtK(List &l, int x, int k ){ // chen vi tri bat ki;
if(isEmpty(l) || k<= 1 ) addHead(l,x);
else if(k>= n) addTail(l,x);
else{
Node *p = creatNode(x);
Node *q = new Node, *w = new Node;
Node *r = l.head;
int dem = 0;
while(r!=NULL){
dem++;
q = r;
if(dem == k ) break;
else r = r->next;
}
w = l.head;
while(w->next!= q) w = w->next;
w->next = p;
p->next = r;
}
} */
// nhap vao mot list bat ki
void nhap(List &l){
cout<<"\nnhap so ptu ban dau cua List: "; cin>> n;
for(int i = 1; i<= n; i++ ) addTail(l,i);
}
// xuat thong tin ra man hinh
void xuat(List l ){
if(l.head){
cout<< "\nDanh sach cac phan tu: \n";
Node *p = l.head;
do{
cout<<" " << p->data;
p = p->next;
}while( p != l.head );
}
else cout<< "\nDanh Sach Rong";
cout<< endl;
}

void delHead(List &l ){ // xoa node o dau List
if(!isEmpty(l)){
if(l.head != l.tail ){
Node *p = l.head;
l.head = l.head->next; // cap nhat l.head
delete p; // xoa bo node head ban dau
l.tail->next = l.head;
}
else l.head = NULL;
}
else return;
}

void delTail(List &l ){
if(!isEmpty(l)){
if(l.head != l.tail ){
Node *p = l.head;
Node *q = new Node;
while(p->next != l.tail ) p = p->next; // tim node ngay truoc tail
q = p; // gan node nay cho node q
p = p->next; // p chinh la node tail can xoa
l.tail = q; // cap nhat l.tail
l.tail->next = l.head;
delete p;
} else l.head = NULL;
}
else return;
}

void delAtK(List &l, int k ){
if( k <= 1) delHead(l);
else if( k >= n ) delTail(l);
else{
int dem = 0;
if(!isEmpty(l)){
Node *p = l.head;
Node *q = new Node;
while(p != NULL){ // tim node thu k.
dem++;
q = p;
if(dem == k ) break; // tim thay thi break
else p= p->next; // k thi tim tiep
}
Node *r = l.head;
while(r->next != q ) r = r->next; // tim node k-1
r->next = q->next; // cho node next cua node k-1 tro toi node k+1;
delete q;
}
}
}

void menu(){
List l;
Init(l);
nhap(l);
xuat(l);
int k, x, lc;
do{
cout<<"\n______MENU______\n1_Chen dau.\n2_chen cuoi."
<<"\n3_Chen sau vi tri node data = k.\n4_Chen vao vi tri bat ki."
<<"\n5_Xuat Thong tin List.\n6_Xoa phan tu dau List."
<<"\n7_Xoa phan tu o cuoi List.\n8_Xoa node o vi tri k."
// <<"\n9_Sap xep QuickSort."
<<"\n0_Thoat.\n_Ban chon ? ";
cin>> lc;
switch(lc){
case 0: break;
case 1: cout<<"\nNhap x: "; cin>> x; addHead(l,x); n++; break;
case 2: cout<<"\nNhap x: "; cin>> x; addTail(l,x); n++; break;
case 3: cout<<"\nNhap x, k: "; cin>> x >> k; addMid(l,x, k);n++; break;
// case 4: cout<<"\nNhap x, vi tri k: "; cin>> x >> k; addAtK(l,x,k); n++; break;
case 5: xuat(l); break;
case 6: delHead(l); n--; break;
case 7: delTail(l); n--; break;
case 8: cout<<"\nNhap vi tri k: "; cin>> k; delAtK(l,k); n--; break;
// case 9: QuickSort(l); break;
}
}while(lc != 0 );
}

int main(){
menu();
return 0;
}

Read More

Tạo queue bằng danh sách liên kết đơn

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   main.cpp
 * Author: KHOA
 *
 * Created on August 26, 2016, 9:10 AM
 */

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

struct Node {
    int data;
    Node *next;
};

struct List {
    Node *head;
    Node *tail;
};

// khoi tao queue

void Init(List &q) {
    q.head = q.tail = NULL; // gan con tro head va tail cua queue bang NULL
}

// tao Node trong queue

Node *creat_Node(int x) {
    Node *p = new Node;
    if (p != NULL) {
        p->data = x; // dua gia tri cua x vao trong data
        p->next = NULL; // gan phan tu ke tiep bang NULL
        return p; // tra ve con tro p trong queue
    } else {
        return NULL; // neu cap phat khong thanh cong thi tra ve NULL
    }

}

// kiem tra xem queue co rong khong

bool isEmpty(List &q) {
    Node *p = q.head;
    if (p == NULL) return true; // neu phan tu dau bang NULL thi queue rong
    else return false; // neu khong thi khong phai rong
}

// push Node vao trong queue

void push(List &q, int x) {
    Node *r = creat_Node(x);
    if (isEmpty(q)) q.head = q.tail = r;
    else {
        r->next = q.head; // đưa phần tử mới vào trỏ tới next là phần tử đầu
        q.head = r; // cập nhật phần tử mới đưa vào đó là phần tử đầu
    }
}

// pop Node ra khoi queue

void pop(List &q) {
    Node *p = q.head;
    while (p->next->next != NULL) { // tim vi tri phan tu thu 2 tu duoi len
        p = p->next;
    }
    // p la phan tu o vi tri 2 tu duoi len
    Node *r = p->next; // r la phan tu cuoi cung cua queue
    p->next = NULL;
    delete r; // xoa phan tu r
}

// nhap phan tu vao trong queue

void nhap(List &q) {
    int n;
    cout << "Nhap so luong Node trong queue: ";
    cin>>n;
    for (int i = 1; i <= n; i++) {
        int x;
        cout << "Phan tu thu " << i << ": ";
        cin>>x;
        push(q, x); // dua phan tu vao trong queue
    }
}

// xuat cac phan tu ra man hinh

void xuat(List &q) {
    Node *p = q.head;
    while (p != NULL) {
        cout << " " << p->data;
        p = p->next;
    }
}

// tim Node trong queue

Node *search_Node(List &q, int x) {
    Node *p = q.head;
    while (!isEmpty(q)) {
        if (p->data == x) return p; // tra ve con tro p khi tim thay phan tu trong queue
        else p = p->next; // khong thi tim tiep
    }
    return NULL; // neu khong tim duoc tra ve NULL
}

int main() {
    List q;
    Init(q);
    nhap(q);
    xuat(q);
    int lc, x;

    do {
        cout << "\n _ _ _CHUONG TRINH QUEUE_ _ _"
                << "\n 1. Push queue "
                << "\n 2. Pop queue "
                << "\n 3. Tim phan tu trong queue "
                << "\n 0. Thoat ";
        cout << endl;
        cout << "Nhap lua chon: ";
        cin>>lc;
        switch (lc) {
            case 1:
            {
                cout << "Nhap phan tu can push: ";
                cin>>x;
                push(q, x);
                break;
            }
            case 2:
            {
                cout << "Ban da dua 1 phan tu ra khoi queue! ";
                pop(q);
                break;
            }
            case 3:
            {
                cout << "Nhap phan tu can tim kiem: ";
                cin>>x;
                if (search_Node(q, x) != NULL) cout << "Tim thay phan tu trong queue! ";
                else cout << "Khong tim thay phan tu do trong queue! ";
            }
            case 0: break;
        }
        xuat(q);
        cout << "\n";
    } while (lc != 0);

    return 0;
}

Read More

Tạo Stack bằng danh sách liên kết đơn

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   khoa.cpp
 * Author: KHOA
 *
 * Created on August 26, 2016, 9:16 AM
 */

#include <iostream>
#include<stdio.h>
#include<stdio.h>
using namespace std;

struct Node {
    int data;
    Node *next;
};

struct List {
    Node *head;
    Node *tail;
};

// khoi tao stack

void Init(List &s) {
    s.head = s.tail = NULL;
}

// kiem tra stack co rong khong

bool isEmpty(List &s) {
    if (s.head == NULL) return true;
    else return false;
}

// tao Node

Node *creat_Node(int x) {
    Node *p = new Node;
    if (p != NULL) {
        p->data = x;
        p->next = NULL;
    } else return NULL;
}

// Push vao stack

void push(List &s, int x) {
    Node *p = creat_Node(x);
    if (isEmpty(s)) {
        s.head = s.tail = p; // neu stack rong thi ta gan p la phan tu dau va cuoi
    } else {
        p->next = s.head; // cho phan tu ke tiep bang phan tu dau
        s.head = p; // cap nhat phan tu dau la phan tu moi them vao
    }
}

// Pop phan tu ra khoi stack

void pop(List &s) {
    Node *p = s.head;
    if (!isEmpty(s)) {
        s.head = p->next;
        delete p;
    } else {
        cout << "\nDanh sach da rong! ";
    }
}

// tim kiem phan tu trong stack

Node *search_Node(List &s, int x) {
    Node *q = s.head;
    while (q != NULL) {
        if (q->data == x) {
            return q;
        } else {
            q = q->next;
        }
    }
    return NULL;
}
// Nhap du lieu cho Stack

void nhap(List &s) {
    int n;
    cout << "nhap so luong phan tu cho stack: ";
    cin>>n;
    for (int i = 1; i <= n; i++) {
        int x;
        cout << "Phan tu " << i << ": ";
        cin>>x;
        push(s, x);
    }
}

// xuat cac phan tu trong stack

void xuat(List &s) {
    Node *p = s.head;
    while (p != NULL) {
        cout << " " << p->data;
        p = p->next;
    }
}

int main() {
    List s;
    Init(s);
    nhap(s);
    xuat(s);
    int x;
    int lc;
    do {
        cout << "\n_ _ _CHUONG TRINH STACK_ _ _";
        cout << endl;
        cout << " 1.Push Stack"
                << "\n 2.Pop Stack"
                << "\n 3.Tim phan tu"
                << "\n 4.Thoat";
        cout << "\nNhap thong tin can kiem tra: ";

        cin>>lc;
        switch (lc) {
            case 1: cout << "Nhap phan tu can Push: ";
                cin>>x;
                push(s, x);
                break;
            case 2: cout << "Pop phan tu trong Stack ";
                pop(s);
                cout << "\n";
                break;
            case 3: cout << "Nhap phan tu can tim kiem: ";
                cin>>x;
                if (search_Node(s, x) != NULL) cout << "Tim thay phan tu!\n";
                else cout << "khong tim thay!\n";
                break;
            case 4: break;
            default: cout << "Ban nhap sai ";
        }
        xuat(s);
        cout << "\n";
    } while (lc != 4);
    return 0;
}

Read More

Video tuyệt đẹp về Việt Nam do Bộ Ngoại giao Việt Nam thực hiện

Video tuyệt đẹp về Việt Nma do Bộ Ngoại giao thực hiện

Read More

Đếm số lần lặp

Cho trước n số nguyên không âm a1, a2, …, an. Mỗi lần lặp, bạn thay đổi dãy này thành một dãy mới theo cách: phần tử thứ k trong dãy mới bằng trị tuyệt đối của ak –  ak+1. Phần tử cuối cùng sẽ là an – a1. Quá trình lặp sẽ dừng lại khi được một dãy bằng nhau.

Ví dụ với n=4 và bắt đầu với dãy 0  2  5  11 ta sẽ có các lần lặp là:

2  3  6  11

1  3  5  9

2  2  4  8

0  2  4  6

2  2  2  6

0  0  4  4

0  4  0  4

4  4  4  4

Như vậy trong ví dụ này ta sẽ có 8 lần lặp. Hãy viết chương trình các định số lần lặp của một dãy ban đầu

Input

Gồm nhiều bộ test, mỗi bộ test gồm 2 dòng:

• Dòng 1 ghi số n (2<=n<=20)
• Dòng 2 ghi n số của dãy ban đầu

Input kết thúc khi n=0

Output

Với mỗi bộ test ghi trên một dòng là số lần lặp theo mẫu dưới đây. Nếu dãy không bằng nhau được sau 1000 lần lặp thì ghi ra dòng “not attained”

#include <iostream>
#include<stdio.h>
using namespace std;

// khai bao ham thuc hien lap
int x1(int n){
    int i, j;
    bool ok;
    long *a=new long[n+5];
    for(i=1; i<=n; i++) cin>>a[i];
    for(j=1; j<=1001; j++){
        ok=true;
        a[n+1] = a[1];
        for(i=1;i<=n;i++){
            a[i] = a[i+1]-a[i];
            if(a[i]<0) a[i] = -a[i];
            if(a[i]!=0) ok = false;
        }
        if(ok) return j-1;
    }
    return 1001;
}
int main()
{
    int T=0;
    int A[30005];
    int n;
    do{
        cout<<"Nhap gia tri cua n: ";
        cin>>n;
        if(n==0) break;
        T++;
        A[T] = x1(n);
    }while(1);
    for(int i=1;i<=T;i++){
        if(A[i]==1001) cout<<"Case "<<i<<" not attained"<<endl;
        else cout<<"Case "<<i<<": "<<A[i]<<" iterations "<<endl;
    }
    return 0;
}

Read More

Binary Search Tree

#include <iostream>
#include<cctype>
#include <stdlib.h>
#include <conio.h>

using namespace std;

struct node
{
 int element;
 node *left;
 node *right;
 int height;
};
typedef struct node *nodeptr;
class bstree
{
 public:
  void insert(int,nodeptr &);
  void del(int, nodeptr &);
  int deletemin(nodeptr &);
  void find(int,nodeptr &);
  nodeptr findmin(nodeptr);
  nodeptr findmax(nodeptr);
  void makeempty(nodeptr &);
  void copy(nodeptr &,nodeptr &);
  nodeptr nodecopy(nodeptr &);
  void preorder(nodeptr);
  void inorder(nodeptr);
  void postorder(nodeptr);
  int bsheight(nodeptr);
  nodeptr srl(nodeptr &);
  nodeptr drl(nodeptr &);
  nodeptr srr(nodeptr &);
  nodeptr drr(nodeptr &);
  int max(int,int);
  int nonodes(nodeptr);
};
// Inserting a node
void bstree::insert(int x,nodeptr &p)
{
 if (p == NULL)
 {
  p = new node;
  p->element = x;
  p->left=NULL;
  p->right = NULL;
  p->height=0;
  if (p==NULL)
  {
   cout<<"Out of Space\n"<<endl;
  }
 }
 else
 {
  if (x<p->element)
  {
   insert(x,p->left);
   if ((bsheight(p->left) - bsheight(p->right))==2)
   {
    if (x < p->left->element)
    {
     p=srl(p);
    }
    else
    {
     p = drl(p);
    }
   }
  }
  else if (x>p->element)
  {
   insert(x,p->right);
   if ((bsheight(p->right) - bsheight(p->left))==2)
   {
    if (x > p->right->element)
    {
     p=srr(p);
    }
    else
    {
     p = drr(p);
    }
   }
  }
  else
  {
   cout<<"Element Exists\n"<<endl;
  }
}
int m,n,d;
m=bsheight(p->left);
n=bsheight(p->right);
d=max(m,n);
p->height = d + 1;
}
// Finding the Smallest
nodeptr bstree::findmin(nodeptr p)
{
 if (p==NULL)
 {
  cout<<"The tree is empty\n"<<endl;
  return p;
 }
 else
 {
  while(p->left !=NULL)
  {
   p=p->left;
   //return p;
  }
  return p;
 }
}
// Finding the Largest node
nodeptr bstree::findmax(nodeptr p)
{
 if (p==NULL)
 {
  cout<<"The tree is empty\n"<<endl;
  return p;
 }
 else
 {
  while(p->right !=NULL)
  {
   p=p->right;
   //return p;
  }
  return p;
 }
}
// Finding an element
void bstree::find(int x,nodeptr &p)
{
 if (p==NULL)
 {
  cout<<"Sorry! element not found\n"<<endl;
 }
 else
 {
  if (x < p->element)
  {
   find(x,p->left);
  }
  else
  {
   if (x>p->element)
   {
    find(x,p->right);
   }
   else
   {
    cout<<"Element found!\n"<<endl;
   }
  }
 }
}
// Copy a tree
void bstree::copy(nodeptr &p,nodeptr &p1)
{
 makeempty(p1);
 p1 = nodecopy(p);
}
// Make a tree empty
void bstree::makeempty(nodeptr &p)
{
 nodeptr d;
 if (p != NULL)
 {
  makeempty(p->left);
  makeempty(p->right);
  d=p;
  free(d);
  p=NULL;
 }
}
// Copy the nodes
nodeptr bstree::nodecopy(nodeptr &p)
{
 nodeptr temp;
 if (p==NULL)
 {
  return p;
 }
 else
 {
  temp = new node;
  temp->element = p->element;
  temp->left = nodecopy(p->left);
  temp->right = nodecopy(p->right);
  return temp;
 }
}

// Deleting a node
void bstree::del(int x,nodeptr &p)
{
 nodeptr d;
 if (p==NULL)
 {
  cout<<"Sorry! element not found\n"<<endl;
 }
 else if ( x < p->element)
 {
  del(x,p->left);
 }
 else if (x > p->element)
 {
  del(x,p->right);
 }
 else if ((p->left == NULL) && (p->right == NULL))
 {
  d=p;
  free(d);
  p=NULL;
  cout<<"Element deleted successfully\n"<<endl;
 }
 else if (p->left == NULL)
 {
  d=p;
  free(d);
  p=p->right;
  cout<<"Element deleted successfully\n"<<endl;
 }
 else if (p->right == NULL)
 {
  d=p;
  p=p->left;
  free(d);
  cout<<"Element deleted successfully\n"<<endl;
 }
 else
 {
  p->element = deletemin(p->right);
 }
}

int bstree::deletemin(nodeptr &p)
{
 int c;
 cout<<"inside deltemin\n"<<endl;
 if (p->left == NULL)
 {
  c=p->element;
  p=p->right;
  return c;
 }
 else
 {
  c=deletemin(p->left);
  return c;
 }
}
void bstree::preorder(nodeptr p)
{
 if (p!=NULL)
 {
  cout<<p->element<<"\t";
  preorder(p->left);
  preorder(p->right);
 }
}

// Inorder Printing
void bstree::inorder(nodeptr p)
{
 if (p!=NULL)
 {
  inorder(p->left);
  cout<<p->element<<"\t";
  inorder(p->right);
 }
}

// PostOrder Printing
void bstree::postorder(nodeptr p)
{
 if (p!=NULL)
 {
  postorder(p->left);
  postorder(p->right);
  cout<<p->element<<"\t";
 }
}

int bstree::max(int value1, int value2)
{
 return ((value1 > value2) ? value1 : value2);
}
int bstree::bsheight(nodeptr p)
{
 int t;
 if (p == NULL)
 {
  return -1;
 }
 else
 {
  t = p->height;
  return t;
 }
}

nodeptr bstree:: srl(nodeptr &p1)
{
 nodeptr p2;
 p2 = p1->left;
 p1->left = p2->right;
 p2->right = p1;
 p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
 p2->height = max(bsheight(p2->left),p1->height) + 1;
 return p2;
}
nodeptr bstree:: srr(nodeptr &p1)
{
 nodeptr p2;
 p2 = p1->right;
 p1->right = p2->left;
 p2->left = p1;
 p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
 p2->height = max(p1->height,bsheight(p2->right)) + 1;
 return p2;
}
nodeptr bstree:: drl(nodeptr &p1)
{
 p1->left=srr(p1->left);
 return srl(p1);
}
nodeptr bstree::drr(nodeptr &p1)
{
 p1->right = srl(p1->right);
 return srr(p1);
}

int bstree::nonodes(nodeptr p)
{
 int count=0;
 if (p!=NULL)
 {
  nonodes(p->left);
  nonodes(p->right);
  count++;
 }
 return count;
}

int main()
{
 //clrscr();
 nodeptr root,root1,min,max;//,flag;
 int a,choice,findele,delele;
 char ch='y';
 bstree bst;

 //system("clear");
 root = NULL;
 root1=NULL;
 cout<<"\n\t\t\t\tWELCOME TO AVL TREE"<<endl;
 cout<<"\t\t\t\t:::::::::::::::::::\n"<<endl;

 do
 {
  cout<<"\t\t::::::::::::::::::::::::::::::::::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 1 to insert a new node::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 2 to find the minimum value:::::::::::"<<endl;
  cout<<"\t\t::::Enter 3 to find the max value:::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 4 to search a value:::::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 5 to delete a value:::::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 6 to display Preorder:::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 7 to display Inorder::::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 8 to display Postorder::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 9 to display the height of the tree:::"<<endl;
  cout<<"\t\t::::Enter 0 to exit:::::::::::::::::::::::::::::"<<endl;
  cout<<"\t\t::::::::::::::::::::::::::::::::::::::::::::::::\n"<<endl;

  cout<<"\nEnter the choice: ";
  cin>>choice;

  switch(choice)
  {
   case 1:
    cout<<"\n\t\tADDING NEW NODE"<<endl;
    cout<<"\t\t:::::::::::::\n"<<endl;
    cout<<"Enter a new value: ";
    cin>>a;
    bst.insert(a,root);
    cout<<"\nThe new value have been added to your tree successfully\n"<<endl;
    break;
   case 2:
    if (root !=NULL)
    {
     min=bst.findmin(root);
     cout<<"\nThe minimum element in the tree is: "<<min->element<<endl;
    }
    break;
   case 3:
    if (root !=NULL)
    {
     max=bst.findmax(root);
     cout<<"\nThe maximum element in the tree is: "<<max->element<<endl;
    }
    break;
   case 4:
    cout<<"\nEnter node to search: ";
    cin>>findele;
    if (root != NULL)
    {
     bst.find(findele,root);
    }
    break;
   case 5:
    cout<<"\nEnter node to delete: ";
    cin>>delele;
    bst.del(delele,root);
    bst.inorder(root);
    cout<<endl;
    break;
   case 6:
    cout<<"\n\t\tPRE-ORDER TRAVERSAL"<<endl;
    bst.preorder(root);
    cout<<endl;
    break;
   case 7:
    cout<<"\n\t\tIN-ORDER TRAVERSAL"<<endl;
    bst.inorder(root);
    cout<<endl;
    break;
   case 8:
    cout<<"\n\t\tPOST ORDER TRAVERSAL"<<endl;
    bst.postorder(root);
    cout<<endl;
    break;
   case 9:
    cout<<"\n\t\tHEIGHT\n"<<endl;
    cout<<"The height of the tree is: "<<bst.bsheight(root)<<endl;

    break;
   case 0:
    cout<<"\n\tThank your for using AVL tree program\n"<<endl;
    break;
   default:
    cout<<"Sorry! wrong input\n"<<endl;
    break;
  }
  //system("pause");
  //system("cls");
 }while(choice != 0);
 return 0;
}

Read More

How to make install graphic in ubuntu

Hello friends , here we are with a video "Graphics Programming in C++ on Ubuntu" , how to setup graphics.h in Linux environment / Ubuntu.

Download link: http://download.savannah.gnu.org/rele...

commands used in the tutorial:

= sudo apt-get update
= sudo apt-get upgrade
= sudo apt-get install build-essential
= sudo apt-get install libsdl-image1.2 libsdl-image1.2-dev guile-1.8 guile-1.8-dev libsdl1.2debian libart-2.0-dev libaudiofile-dev libesd0-dev libdirectfb-dev libdirectfb-extra libfreetype6-dev libxext-dev x11proto-xext-dev libfreetype6 libaa1 libaa1-dev libslang2-dev libasound2 libasound2-dev

= cd libgraph-1.0.2
= ./configure
= sudo make
= sudo make install
= sudo cp /usr/local/lib/libgraph.* /usr/lib


after you code graphics you will buile programs by command: 
g++ name.cpp -o name -lgraph

Read More

Tôi đã học tin học như thế nào? Bắt đầu từ đâu

Tôi đã học tin học như thế nào? Bắt đầu từ đâu

Trong bài viết này mình sẽ cố gắng trả lời ngắn gọn và đơn giản những câu hỏi mà mình nghĩ rằng sẽ có ích đối với các bạn đặc biệt có đam mê đối với Tin học, nhưng mới tiếp xúc và không biết phải bắt đầu từ đâu. Trọng tâm của mình sẽ là việc học thuật toán để tham gia các kì thi quốc gia, tuy nhiên mình cũng sẽ cố gắng gợi mở thêm nhiều hướng khác trong phạm trù kinh nghiệm của mình.

Lưu ý: Xuất xứ của mình là một người học Tin để thi quốc gia, sau đó chuyển dần sang nghiên cứu khoa học về Machine Learning. Vì thế, những gì được viết dưới đây xuất phát từ kinh nghiệm của riêng bản thân mình, và chỉ thể hiện góc nhìn từ con đường mình đã đi. Mình khuyên các bạn nên chừa ra một khoảng trống trong tâm hồn để thu nhặt các ý kiến từ các góc nhìn khác.

Sau đây là các câu hỏi…

Tại sao phải học Tin học?

Về cơ duyên đến với Tin học của mình, bạn có thể tham khảo bài viết trước. Hy vọng các bạn sẽ tìm thấy điểm chung nào đó. Một điều mình muốn nói thêm là Tin học hiện nay giống như một môn Toán thứ hai vậy. Nếu sau cuộc cách mạng công nghiệp, nhân loại bắt đầu gắn động cơ vào bất cứ mọi thứ xung quanh, thì đến cuộc cách mạng máy tính hiện tại, con người bắt đầu dùng máy tính vào mọi việc có thể. Một công việc trong thế giới hiện đại khó mà có thể vận hành hiệu quả mà không cần dùng đến máy tính. Vì thế, một con người trong thế giới hiện đại khó mà có thể thành công mà không có kỹ năng sử dụng công cụ này. Bạn bè của mình làm nhiều ngành khác nhau, từ toán học, hoá học, vật lý, đến kiểm toán. Họ đều phải chí ít phải có kỹ năng lập trình để phục vụ cho công việc của mình.

Học Tin học như thế nào cho đúng?

Rất khó để đưa được một câu trả lời trọn vẹn. Thay vì đó mình sẽ nói về một cách học mình cho là chưa đúng. Đó là quan niệm học Tin học tức là học một ngôn ngữ lập trình. Các cách nói dân gian như “học Pascal” không thể hiện được hết tinh thần của việc học Tin. Đối với phạm trù Tin học cấp 3, điều quan trọng nhất bạn rút ra được sau 3 năm học phải một tư duy thuật toán. Bạn cần làm cho bộ não quen thuộc với lối suy nghĩ theo các cấu trúc điều kiện, cấu trúc lặp lại, cách chia chương trình ra thành các chương trình nhỏ hơn rồi tập trung giải quyết từng phần một. Vì đa phần các ngôn ngữ lập trình đều được xây dựng dựa trên các yếu tố cơ bản trên, việc bạn thành thạo về tư duy lập trình sẽ giúp bạn học một ngôn ngữ lập trình rất nhanh. Hãy làm chủ ngôn ngữ lập trình chứ đừng bị phụ thuộc vào chúng.

Mình không phản đối việc thành thục một ngôn ngữ lập trình. Thậm chí việc thành thạo một ngôn ngữ lập trình là quan trọng sống còn sau này khi bạn muốn làm ra những sản phẩm thực thụ. Nhưng hãy để việc đó sau khi bạn đã có một nền tảng tư duy vững chắc.

Nhưng vẫn phải chọn một ngôn ngữ để bắt đầu học chứ?

Chính xác. Câu trả lời này mình xin chia ra dành cho hai đối tượng:

1. Các bạn luyện thi tin học quốc gia: theo mình biết thì hai lựa chọn chính dành cho các bạn là Pascal và C++. Việc đưa C++ vào danh sách là một thay đổi lớn vì 6 năm trước khi mình học Tin, Pascal là sự lựa chọn duy nhất cho các vòng thi trong nước. Trong tương lai mình dự đoán C++ sẽ thay thế hẳn cho Pascal. Mình không rành về Pascal bằng C++ nên sẽ không so sánh tính năng của chúng chi tiết. Tuy nhiên, C++ đưa ra ưu thế rõ rệt về tốc độ, bao gồm cả tốc độ chạy của chương trình và tốc độ lập trình ra chương trình đó. Nói đơn giản là code C++ chạy nhanh và tương đối ngắn gọn (không quá ngắn gọn đến mức khó hiểu). Đặc biệt, khi học C++ bạn có thể tham gia được rất nhiều kỳ thi lập trình thuật toán trực tuyến trên mạng. Đây là mấu chốt trong việc thành công trong kỳ thi quốc gia. Một lợi thế khác khi học C++ là nó được sử dụng rộng rãi trong công nghiệp. Vì sớm muộn gì bạn cũng phải học đến nó chi bằng học sớm từ đầu.

2. Các bạn học tin với mục đích chung khác: ngoài C++ ra, theo mình ngôn ngữ Python là một sự khởi đầu tuyệt vời. Cú pháp của Python cực kỳ đơn giản, giống như là đang viết những phép toán trong sách giáo khoa vậy. Dù đơn giản, Python lại rất đa năng và được hỗ trợ mạnh mẽ từ cộng đồng người sử dụng. Java là một sự lựa chọn tốt cho những bạn muốn học về lập trình hướng đối tượng một cách bài bản. Dù cả Python và C++ đèu hỗ trợ lập trình hướng đối tượng, Java theo mình là ngôn ngữ biểu hiện điều này rõ rệt nhất. Bạn không thể viết một chương trình hoàn chỉnh trong Java mà không đặt nó vào trong một đối tượng (class), trong khi nếu sử dụng Python và C++ ta có thể quên bẵng đi khái niệm này. Ngôn ngữ Java chặt chẽ và dạy cho bạn những thói quen tốt về cách thiết kế chương trình.

Học ngôn ngữ lập trình như thế nào?

Mình sẽ giả sử là các bạn muốn học C++. Theo mình thì việc chạy ra nhà sách và mua ngay một cuốn sách giáo khoa dày cộm về C++ không giúp ích gì mấy (vì mình đã từng làm điều này). Hồi mình mới học C++, mình thường lên các trang giải bài trực tuyến hoặc cách trang kỳ thi và xem code C++ của các cao thủ khác để học theo cách code của học. Điều này có hai lợi ích. Thứ nhất, vì mình đã biết trước lời giải, nên mình có thể đoán được từng phần chương trình sẽ làm nhiệm vụ gì, sau đó đi sau vào xem cụ thể nhiệm vụ đó được thực hiện thế nào. Thứ hai, vì là cao thủ nên code của họ sẽ rất tối ưu, có thể học được nhiều mẹo vặt mà sách giáo khoa không dạy. Một cách khác là bạn có thể google từ khoá “C++ interactive tutorial” để tìm kiếm cách trang dạy ngôn ngữ lập trình một cách tương tác. Các trang này thường sẽ đưa bạn đi qua các khái niệm từ dễ đến khó. Bạn vừa học vừa thực hành ngay nên sẽ bớt nhàm chám hơn là ngồi cày sách. Tuy nhiên, về lâu về dài bạn vẫn phải đọc sách hoặc tài liệu chính thống để hiểu biết các khái niệm cốt lõi của một ngôn ngữ. Ví dụ như là trong C++ bạn có thể truyền tham số bằng cả reference hoặc value, trong khi đó Java chỉ cho phép truyền tham số bằng value mà thôi. Những điều “behind-the-scenes” như vậy không thể học được nếu chỉ nhìn vào code của người khác.

StackOverflow – The definitive C++ book guide and list

Nên dùng công cụ gì để lập trình?

Trên Windows, Free Pascal là sự lựa chọn tốt cho Pascal. Ngoài ra còn có một số công cụ khác như Lazarus, Codeblocks, Delphi,… Đối C++ thì hồi trước mình hay dùng nhất là Dev-C++.

Tuy nhiên, mình khuyên là các bạn nên từ bỏ Windows và chuyển sang một hệ điều khác dựa trên nền tảng Unix như là Ubuntu. Hiện tại thì màn hình lập trình của mình trông giống như thế này (bấm vào để phóng to):

Ở cửa sổ trái mình sử dụng vim, chỉ đơn thuần là một chương trình soạn thảo văn bản (text editor) của Ubuntu. Ở cửa sổ phải mình sử dụng terminal, nói nôm na là nơi bạn có thể điều khiển máy tính bằng các câu lệnh thay vì dùng chuột (giống như là MS-DOS thời xa xưa). Lưu ý là hai công cụ này đều có sẵn trong Ubuntu, bạn không cần phải cài đặt gì cả. Trong hình, mình có cài thêm một số Plugins cho vim để thêm màu mè, màn hình đen, hiển thị dòng cột (cảm ơn bạn mình là RR!). Mình cũng cài thêm theme Macbook cho máy nên màn hình trông giống MacOS mặc dù thật ra nó vẫn là Ubuntu.

Khi lập trình, mình viết code vào vim rồi sử dụng câu lệnh này để biên dịch (compile) chương trình.

1	g++ test.cpp -o a -O2 -Wall

Lựa chọn “-o a” sẽ biên dịch file test.cpp thành một file excutable tương tự như file .exe của Windows có tên là a trong cùng thư mục của file test.cpp. Vì thế, muốn chạy chương trình, mình chỉ cần chạy file a bằng câu lệnh sau:

1

./a

Nếu bạn không thích vim, có thể xài gedit hoặc là emacs hoặc bất cứ trình soạn thảo văn bản nào khác đều được. Bộ đôi (text editor + terminal) rất đa năng vì bạn có thể sử dụng nó cho nhiều ngôn ngữ khác nhau. Hơn nữa, trong một sản phẩm lập trình thật sự, bạn không phải compile một lúc một file nữa mà có thể là cả ngàn files. Lúc đó, bạn sẽ cần đến các công cụ chạy từ terminal. Cho nên, làm quen với terminal sớm là một lợi thế. Ngoài ra, trong tương lai gần, nếu thi tin học quốc tế (IOI), các bạn sẽ thi trên hệ điều hành Ubuntu.

Tìm thầy nơi đâu? 

Muốn học giỏi cần phải có thầy giỏi. Cho dù có tố chất đến mấy mà không biết cách khai phá thì cũng sẽ không thể đạt đỉnh cao. Nếu ai đó bảo bạn rằng chỉ có tự học mới giỏi được, thì người đó nói đúng. Nhưng nếu bạn chỉ ngồi trong giếng nhà tự mày mò tất cả thì theo mình đó không phải là tự học, mà chỉ là học một mình. Tự học bao gồm cả việc tự tìm thầy để mà học.

Khi mình đặt chân vào trường Phổ Thông Năng Khiếu, nơi có đội tuyển tin thuộc hàng top của đất nước thời bấy giờ, mình cứ ngỡ sẽ được dạy dỗ bởi những sư tổ tu luyện lâu năm, là những giáo sư tiến sĩ đầu tóc bạc phơ. Tuy nhiên, Năng Khiếu xây dựng cho mình một hình tượng khác về người thầy. Người “thầy” của mình ở Năng Khiếu ngoài thầy chủ nhiệm, còn là các anh khóa trên đi trước và các bạn trong cùng đội tuyển. Ngoài ra, mình cũng chủ động làm quen các anh học giỏi trong cả nước thời ấy như Khúc Anh Tuấn hoặc Phạm Quang Vũ để hỏi bài. Khi hỏi mình cũng thấy hơi ngại nhưng mà thông qua đó mình học được cách suy nghĩ rất hay của các anh. Có những bài tập đòi hỏi những kỹ thuật mà mình thật sự không thể nào biết được nếu chỉ ngồi học trong giếng nhà. Sau này, diễn đàn VNOI được các đàn anh lập ra cũng vì mục đích để mọi người tìm được những người thầy như vậy.

Tuy nhiên, mình khuyến cáo các bạn không nên quá lạm dụng các “thầy”, không nên coi các thầy như là một cỗ máy trả lời. Các “thầy” thường sẽ tân tình đỡ các bạn hơn nếu các bạn thể hiện được mình là người chịu khó tư duy và tìm tòi hơn là chỉ biết vòi vĩnh câu trả lời. Các bạn coi phim chắc cũng biết là cao nhân chỉ truyền bí kíp cho kẻ có tố chất. Một mẹo nhỏ là nhớ lịch sự nói “cảm ơn” sau mỗi lần hỏi.

Tìm bài nơi đâu?

Khi học Tin học bạn có một lợi thế đó là bài tập dường như là vô biên (SPOJ, Timus, POJ). Nhưng bạn không cần thiết làm hết tất cả chúng để giỏi. Vì thế ta thay vì hỏi tìm bài ở đâu, thì nên hỏi:

Nên làm những bài gì?

Mình gợi ý một số cách làm bài cơ bản như sau:

1. Làm hết những bài cơ bản: vào trang SPOJ hoặc VOJ, mở list đề bài ra. Ở tiêu đề của cột “Users” khi bạn bấm vào đó một lần, thì các bài tập sẽ được sắp xếp theo thứ tự giảm dần số lượng người làm được. Bài ở những trang đầu tiêu là những bài cơ bản nhất, hầu như ai cũng làm được. Bạn nên làm khoảng vài trang đầu để luyện các kỹ thuật cơ bản.
2. Làm theo chủ đề: khi bạn đang làm những bài cơ bản sẽ gặp những bài bạn nghĩ mãi vẫn không ra. Không phải là bạn kém thông minh gì mà vì những thuật toán đó quá xa lạ với bạn. Vậy thì bạn nên tìm tòi làm những dạng bài tương tự để biết cách áp dụng các thuật toán mới học. Sau khi google mình tìm thấy trang này Problem classifier có lẽ khá hữu dụng.

Mình muốn dừng ở đây một chút để lưu ý là cách 1 và cách 2 phải nên được áp dụng bổ trợ cho nhau bởi vì một phương pháp chú trọng vào mở rộng kiến thức theo chiều rộng, còn phương pháp còn lại mở rộng theo chiều sâu. Chỉ làm theo kiểu gặp bài nào làm bài đó thì khó thể đúc kết được những kinh nghiệm sâu sắc. Ngược lại, làm theo chủ đề cho các bạn thời gian để tập trung suy nghĩ về một vấn đề, nhưng cẩn thận tránh đam mê quá một dạng bài mà trở nên không thoải mái khi làm những dạng bài khác.

3. Tham gia các kì thi trực tuyến: nếu hai phương pháp trên sẽ cho bạn nền tảng tốt thì phương pháp này sẽ đưa bạn đến đỉnh cao. Vì mục đích cuối của bạn là tham gia các kì thi quốc gia quốc tế, nên việc ngồi cả ngày trời để làm một bài tập trên các trang Online Judge một lúc nào đó sẽ trở thành một thói quen vô cùng nguy hại. Lúc đó, bạn nên chuyển qua làm bài theo thời gian thực. Có cảm nhận về áp lực thời gian, đầu óc bạn sẽ trở nên nhanh nhẹn hơn nhiều. Hơn nữa, khi thật sự thi đấu với những con người khác, bạn cũng sẽ có cảm xúc luyện tập hơn là chỉ ngồi cày Online Judge một mình. Hiện nay, các kì thi trực tuyến mọc lên như nấm (Codeforces, TopCoder, Hackerrank, USACO, COCI). Các bạn cũng có thể lấy bài từ các cuộc thi khác vào tạo ra cuộc thi của riêng rồi mời bạn bè tham gia (HUSTOJ).

Làm sao để làm bài ít mà vẫn giỏi?

Không có cách nào cả. Phải làm bài nhiều mới giỏi được. Nghiên cứu về các kiện tướng ở nhiều bộ môn cho thấy họ đều luyện tập ít nhất 10 ngàn giờ để đạt được trình độ đó.

Làm sao để không cần làm quá nhiều bài mà vẫn giỏi?

Điều này thì có thể. Thậm chí mình cảm thấy làm quá nhiều sẽ dẫn đến hoặc là quá tải hoặc là sẽ trở một cỗ máy giải bài, giải bài xong thì bỏ qua ngay mà không suy nghĩ thêm gì nữa. Nên nhớ là thời gian luyện tập của các bạn có hạn, nên các bạn phải khai thác hết giá trị của từng bài tập bạn giải. Giải một bài tập xong rồi quăng sang một bên là vô cùng phí phạm. Việc các bạn giải được nhiều bài trước kì thi chẳng có nghĩa lý gì nếu bạn không rút ra được nhiều giá trị từ chúng.

Suy cho cùng, thì nguyên lý “muốn giỏi phải làm nhiều bài tập” vẫn không đổi. Tuy nhiên, thay vì làm các bài tập một cách tuần tự, các bạn có thể cùng một lúc giải nhiều bài tập bằng cách suy nghĩ về những biến thể của một bài tập vừa giải được. Hãy xem xem trong bài toán có những điều kiện nào thể thay đổi được, có thể tổng quát hóa lên được. Bài toán này có tính chất gì đặc biệt mà thuật toán của bạn lại giải được? Tính chất đó có thể xuất hiện dưới dạng khác hay không? Chỉ cần bỏ một ít thời gian đặt ra những câu hỏi dạng này và đào sâu khám phá, giá trị thu được khi giải một bài tập sẽ được nhân lên nhiều lần. Giải một bài mà như giải 10 bài là như vậy.

Một ví dụ đơn giản là trong lúc làm bài tập, mình nhận ra rằng thuật toán chia nhị phân được sử dụng để chuyên trị những bài tập đòi hỏi “cực tiểu hóa một giá trị cực đại” (hoặc ngược lại, ví dụ như là tìm tập hợp sao cho số lớn nhất trong tập nhỏ nhất trong tất cả các cách chọn). Trong một ví dụ khác, với bài QBDIVSEQ, nhận xét mấu chốt là “độ dài dãy con tăng dài nhất là số lượng ít nhất các dãy con giảm mà ta có thể phân chia dãy ban đầu thành”. Khi chứng minh nhận xét này, mình nhận thấy một tính chất đặc biệt của mối quan hệ “lớn bé” giúp cho chứng minh trở nên khả thi. Đó là tính chất bắc cầu: “a < b, b < c suy ra a < c”. Từ đó, mình suy nghĩ ra rằng thay vì sử dụng mối quan hệ “lớn bé” thông thường khi so sánh các số, ta có hoàn toàn có thể áp dụng nhận xét của bài này cho một mối quan hệ “lớn bé” khác (ví dụ quan hệ chia hết), miễn là tính chất bắc cầu được thỏa mãn.

Cuối cùng nhưng quan trọng nhất… tiếng Anh!

Theo mình, có MỘT thứ tách biệt người học giỏi và người học không giỏi trong các kì thi Tin học quốc gia và quốc tế, đó là việc người học đó có thoải mái với tiếng Anh hay không. Việc thoải mái với tiếng Anh giúp cho bạn có thể vươn ra khỏi cộng đồng trong nước để tiếp cận với nhiều luồng tri thức của nhân loại. Hồi mình mới học Tin, tìm được một cuốn sách dạy thuật toán bằng tiếng Việt giống như là tìm cá mập trong vịnh Thái Lan vậy. Thực tế, chỉ có một cuốn sách về thuật toán được viết sát với nội dung thi quốc gia, do thầy Lê Minh Hoàng biên soạn. Nhưng chỉ luyện các thuật toán cơ bản trong sách thầy Hoàng thì không đủ để có thể cạnh tranh trên đấu trường quốc tế (em xin lỗi thầy ). Lúc ấy, muốn học thêm các kỹ thuật nâng cao về quy hoạch động hay cấu trúc dữ liệu, mình phải tìm đến trang dạy thuật toán của Topcoder hoặc đọc lời giải bằng tiếng Anh của các kì thi quốc tế. Hiện nay, các thành viên của Codeforces có viết nhiều trang blog mô tả đủ loại kỹ xảo lập trình tiên tiến nhất. Đó là một mỏ vàng cần được khai thác.

Thoái mái với tiếng Anh cũng giúp bạn hòa nhập với cộng đồng luyện thi lập trình trên thế giới thông qua việc tham gia các kì thi trực tuyến (đề tiếng Anh). Bạn từ một con cá nhỏ trong cái ao làng, vươn ra biển lớn. Bạn sẽ thấy rằng con cá lớn nhất trong cái ao của bạn chẳng to bằng một phần trăm con cá lớn của đại dương. Khi được tôi luyện với con những con cá đó, dù cố tình hay vô ý, khả năng sinh tồn của bạn rồi cũng sẽ được nâng cao.

Read More