Những thuật toán hay thi HSG Tin học

[khanhan2006_2009]

Nhưng mà khi thi làm sao biết dc là test cái đồ thị có dày hay không?Nếu vậy thì phải xài Floyd cho tất cả các trường hợp=>mình thua rui DH ah.

[duyhung123abc]

roài, để tui suy nghĩ tìm ra cái cây nào lưu để chạy DIJK nhanh nhất. Nhưng thường thì trong các bài thi dữ liệu lớn, nếu cứ tổ chức kiểu FLOYD (tức là mảng 2 chiều) thì có thể chương trình ko chạy đâu.

[khanhan2006_2009]

KA thấy cách tổ chức dữ liệu trên mảng 1 chiều thì khá là phù hợp với những test lớn.Nhưng không thấy thuật toán nào để xử lí trên mảng 1 chiều cả(tất cả những thu6a5t toán KA biết đều làm trên mảng 2 chiều).

[myhanh]

Về mặt lưu trữ thì mảng hai chiều hay một chiều thì cũng vậy mà chỉ khác nhau về mặt logic thôi!

[duyhung123abc]

Còn thuật toán nào hay anh Myhanh giới thiệu cho tụi em đi. Chẳng hạng về CTDL á. Lo cá độ đá banh hoài

[khanhan2006_2009]

DH nói đúng đó anh,anh MH nhượng tài sản lại cho em ,em làm CEO cho,anh hãy tập trung chỉ dạy tụi em mấy thuật toán hay đi...hehe

[duyhung123abc]

KA làm CEO rùi, vậy em chịu khó làm chủ tịch HĐQT cũng đc. Nếu có tài liệu anh post lên rùi bàn luận.

[khanhan2006_2009]

KA xin giới thiệu 1 kĩ thuật trong lập trình ,đó là Qui hoạch động(QHD) hay còn gọi là qui hoạch tuýên tính.
Định nghĩa :QHD là phương pháp giải quyết một bài toán bằng cách qui về những bài toán con và giải quyết tất cả những bài toán con để tìm ra đáp án tối ưu.
Một ví dụ đơn giản:Cho 1 số tự nhiên n,hãy tính số cách có thể phân tích n thành tổng của các số nguyên dương bé hơn n.
Giải:Ta có thể dùnh phương pháp vét cạn để tìm tất cả các trướng hợp.Nhưng vì yêu cầu bài toán chỉ là tìm số cách phân tích nên vét cạn sẽ là 1 sự lãng phí đáng kể.
QHD:_gọi F[i,j] là số cách phân tích số j>0 thành tổng của các số nguyên dương <=i.
Xét 2 khả năng:
+ Nếu ta chọn số i vào cách phân tích,khi đó F[i,j]=F[i,j-i];
+ Nếu ta không chon i thì phép phân tích xem như chỉ chọn các số từ i-1 trở về 1,do đó F[i,j]=F[i-1,j];
Vì vậy,bài toán này sẽ có giải thuật như sau:
Cho i chạy từ 1 tới n
Cho j chạy từ 1 tới n
Nếu j<i thì gán F[i,j]=F[i-1,j]
Nếu >=i thì F[i,j]=F[i-1,j]+F[i,j-1]
Đáp số bài toán là F[n,n].Ta có thể làm tốt bài làm bằng cách sử dụng mảng 1 chiều thay vì mảng 2 chiều nhưng ở đây KA chỉ giới thiệu cách này cho dễ hiểu.

[myhanh]

Cái này anh MH gọi là chia để trị (divide and conquer)

[duyhung123abc]

anh MH ăn nhậu với Euro xong rùi bỏ lun cái topic này mà