Go Back   Cựu Học Sinh Lê Quý Đôn - Long An > :: Góc Học Tập :: > Tin học > Học lập trình

Học lập trình Pascal , C+ , C++ , VB

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

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

this thread has 48 replies and has been viewed 50800 times

Gởi Ðề Tài Mới Trả lời
 
Ðiều Chỉnh Xếp Bài
Old 06-06-2008, 11:53 AM   #31
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

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.
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 06-06-2008, 11:58 AM   #32
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

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.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 06-06-2008, 10:06 PM   #33
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

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).
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 07-06-2008, 10:17 AM   #34
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

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!
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Old 11-06-2008, 11:50 AM   #35
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

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
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 11-06-2008, 12:04 PM   #36
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

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
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 11-06-2008, 12:08 PM   #37
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

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.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 29-06-2008, 10:16 PM   #38
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

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.
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 29-06-2008, 11:56 PM   #39
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

Cái này anh MH gọi là chia để trị (divide and conquer)
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Old 07-07-2008, 10:34 PM   #40
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

anh MH ăn nhậu với Euro xong rùi bỏ lun cái topic này mà
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Trả lời


Ðiều Chỉnh
Xếp Bài

Quyền Sử Dụng Ở Diễn Ðàn
Bạn không được quyền gởi bài
Bạn không được quyền gởi trả lời
Bạn không được quyền gởi kèm file
Bạn không được quyền sửa bài

vB code đang Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt
Chuyển đến


Website sử dụng phần mềm vBulletin phiên bản 3.6.8
do Công ty TNHH Jelsoft giữ bản quyền từ 2000 - 2024.
Múi giờ GMT +7. Hiện tại là 07:00 PM.

Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này

Tự động[F9]TELEX VNI VIQR VIQR* TắtKiểm chính tảDấu cũ
phan mem quan ly ban hang | thuê vps