Những tài liệu kinh điển về giải thuật lập trình cho dân IT
Sau nhiều năm nghiên cứu về mảng lập trình và kinh nghiệm thi thố Olympic tin học, mình tổng hợp được các tài liệu thuộc dạng kinh điển cho các bạn tham khảo
- Giải thuật lập trình – Lê minh Hoàng : Cuốn sách này rất kinh điển nhưng nó được viết dạng ngôn ngữ giả Pascal
- 150 bài toán lập trình chọn lọc – Lê Minh Hoàng. Kết hợp đọc quyển sách số 1 thì thực hành làm các bài tập này
- Tài liệu giáo khoa chuyên tin – Quyển 1
- Tài liệu giáo khoa chuyên tin – Quyển 2
- Tài liệu giáo khoa chuyên tin – Quyển 3 – phần 1
- Tài liệu giáo khoa chuyên tin – Quyển 3 – phần 2
- Tổng hợp một số đề Olympic tin học các năm và lời giải (Cái này các bạn chỉ tham khảo, có thể lời giải chưa tối ưu)
Ngoài ra, các bạn cũng nên thường xuyên ghé thăm blog này, sẽ có nhiều bài viết được cập nhật thường xuyên để các bạn tham khảo trên nhiều lĩnh vực
Chúc các bạn thành công
Một số hàm thuật toán hay thường dùng
Do nhu cầu lập trình giải các bài toán, chúng ta thường phải làm việc với các hàm sau:
1. Tìm số nguyên tố:
long nguyento(long n)
{
if (n<4) return n>1;
for (long i=2,temp=int(sqrt(double(n))); i<=temp; i++ )
if (n%i==0) return 0;
return 1;
}
2. Thuật toán tìm Ước số chung lớn nhất UCLN:
long UCLN(long a,long b)
{
if (a==b) return a;
else
if(a>b) return UCLN(a-b,b);
else return UCLN(a,b-a);
}
3. Tìm Bội chung nhỏ nhất:
sau khi tìm được UCLN, công thức tìm bội chung nhỏ nhất là:
BCNN=a*b/UCLN(a,b).
4.Kiểm tra số đối xứng:
bool doixung(long n)
{
long k = n,m=0;
while(k > 0)
{
m = 10*m + k%10;
k = k/10;
}
if(n == m) return true;
else return false;
}
5. Kiểm tra chuỗi đối xứng:
int chuoidoixung(char *st)
{
int i,j;
for(i=0,j=strlen(st)-1;i<strlen(st)/2;j--,i++)
if(st[i]!=st[j])
return 0;
return 1;
}
còn nữa…
Giải bài Prob C thi thử ACM
Tình hình là trong buổi tối sinh hoạt hướng nghiệp, tranh thủ giải quyết được bài này
Prob C: Short Phrase
Chẳng là lão nhà thơ Nhật Tanka and Haiku bịa ra cái luật Short Phrase này khiến anh em phải vất vả viết chương trình tìm ra chuỗi Short Phrase
Trong cái đề nó nói loằng ngoằng nhiều thứ nhưng đại loại yêu cầu của bài toán như sau:
Cho n dòng gồm nhiều từ (n<=40)
sẽ có một Short Phrase nằm trong n dòng này, nhiệm vụ của ta là phải tìm ra vị trí bắt đầu của Short Phrase trong n dòng này
Short Phrase là một số các dòng liên tiếp sao cho số lượng các ký tự lần lượt phải là 5:7:5:7:7
Để giải quyết bài toán này thì cứ việc duyệt cho tẹt ga thôi. Nhưng chú ý hàm kiểm tra ShortPhrase nhé.
Code như sau:
#include<bits/stdc++.h>
using namespace std;
int duyet5(int a[],int n,int i)
{
int j=i,kq=a[i];
while(kq<5)
{
j++; kq+=a[j];
}
if(kq==5) return j; else return -1;
}
int duyet7(int a[],int n,int i)
{
int j=i,kq=a[i];
while(kq<7)
{
j++; kq+=a[j];
}
if(kq==7) return j; else return -1;
}
int ShortPhrase(int a[],int n,int i)
{
if (duyet5(a,n,i) !=-1) //kiem tra nhom 5
{
int tam71 = duyet7(a,n,duyet5(a,n,i)+1);
if (tam71!=-1) //kiem tra nhom 7
{
int tam51=duyet5(a,n,tam71+1);
if(tam51!=-1) //kiem tra nhom 5
{
int tam72=duyet7(a,n,tam51+1);
if(tam72!=-1) //kiem tra nhom 7
{
int tam73=duyet7(a,n,tam72+1);
if(tam73!=-1) return i;
else return -1; //kiem tra nhom 7
}
else return -1;
}
else return -1;
}
else return -1;
}
else return -1;
}
int main()
{
int n,a[40],kq=-1;
string s;
ifstream infile("prob_C.inp");
ofstream outfile("prob_C.out");
while(!infile.eof())
{
infile>>n;
if(n>0) {
for(int i=0;i<n;i++)
{
infile>>s;
a[i]=s.length();
}
for(int i=0;i<n;i++)
{
kq=ShortPhrase(a,n,i);
if (kq!=-1) break;
}
outfile<<++kq<<endl;
}
}
infile.close();
outfile.close();
return 0;
}
Lập trình căn bản và nâng cao 