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 50808 times

Gởi Ðề Tài Mới Trả lời
 
Ðiều Chỉnh Xếp Bài
Old 01-01-1970, 07:00 AM   #11
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

Cái topic này myhanh mở ra cho những mem nào là học sinh LQĐ hay không là học sinh LQĐ đang tham gia đội tuyển tin học chuẩn bị 1-2 hay 3 năm nữa thi học sinh giỏi tin học cùng nhau trao đổi kinh nghiệm. myhanh sẽ đem hết những gì mình còn nhớ lại hồi các thầy như thầy Nhàn, thầy Bùi Phú Yên, thầy Tân dạy để chia sẻ cùng các bạn.
__________________
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 01-01-1970, 07:00 AM   #12
Hồ sơ
trongbangpham
Senior Member
 
Tham gia ngày: Nov 2004
Tuổi: 49
Số bài viết: 414
Tiền: 25
Thanks: 234
Thanked 300 Times in 85 Posts
trongbangpham is an unknown quantity at this point
Default

Trích:
Originally posted by myhanh@Oct 24 2005, 01:05 PM
Cái topic này myhanh mở ra cho những mem nào là học sinh LQĐ hay không là học sinh LQĐ đang tham gia đội tuyển tin học chuẩn bị 1-2 hay 3 năm nữa thi học sinh giỏi tin học� cùng nhau trao đổi kinh nghiệm. myhanh sẽ đem hết những gì mình còn nhớ lại hồi các thầy như thầy Nhàn, thầy Bùi Phú Yên, thầy Tân dạy để chia sẻ cùng các bạn.

Hoan hô myhanh hai tay luôn

thay đổi nội dung bởi: myhanh, 03-06-2008 lúc 10:00 AM.
trongbangpham is offline   Trả Lời Với Trích Dẫn
Old 01-01-1970, 07:00 AM   #13
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

MÔ HÌNH QUAY LUI
Một phương pháp phổ biến để tìm các cấu hình là dùng giải thuật quay lui. Tư tưởng chính của giải thuật này là xây dựng dần các thành phần của cấu hình bằng cách thử lần lượt các khả năng có thể có. Nếu tồn tại một khả năng chấp nhận được thì tiến hành bước tiếp theo; trái lại cần lùi lại bước trước để thử lại các khả năng chưa được thử . Ta sẽ dùng cách diễn đạt qui nạp để mô tả một cách chi tiết giải thuật này. Trước tiên phải hình thức hoá việc biểu diễn một cấu hình. Thông thường ta trình bày một cấu hình cần xây dựng như một bộ có thứ tự (vector) gồm có n thành phần thỏa mãn một số ràng buộc nào đó. Giả sử đã xây dựng xong i-1 thành phần bây giờ là bước xây dựng thành phần xi. Ta lần lượt thử các khả năng có thể có của xi. Xảy ra các trường hợp:
-Tồn tại một khả năng j chấp nhận được. Khi đó xi sẽ được xác định theo khả năng này. Nếu xi là thành phần cuối (i=n) thì được một nghiệm. Trái lại, i<n thì tiến hành bước tiếp qui nạp.
-Tất cả các khả năng đề cử cho xi đều không chấp nhận được. Khi đó cần lùi lại bước xác định xi-1
Để đảm bảo việc vét cạn, các giá trị đề cử phải không được bỏ sót. Mặt khác để đảm bảo không trùng lặp khi quay lui để xác định xi-1 cần không được thử lại những giá trị thử rồi. Trong phần lớn các bài toán điều kiện chấp nhận j không những phụ thuộc j mà còn phụ thuộc vào việc đã xác định i-1 thành phần trước, do đó cần tổ chức một số biến trạng thái để cất giữ trạng thái của bài toán sau khi xây dựng xong một thành phần để chuẩn bị cho bước xây dựng tiếp. Trường hợp này cần hoàn nguyên lại trạng thái cũ khi quay lui để thử tiếp các khả năng trong lúc trước
Code:
 MÔ HÌNH
Procedure Try(i:integer);
(* Xác định thành phần bằng đệ qui *)
Var j:integer;
 Begin
 For (j thuộc tập các khả năng để thử) do
  If  then
    Begin
        ;
        ;
        If i=n then 
         else Try(i+1);
        
     end
end;
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog

thay đổi nội dung bởi: myhanh, 03-06-2008 lúc 10:01 AM.
myhanh is offline   Trả Lời Với Trích Dẫn
Old 01-01-1970, 07:00 AM   #14
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

HÀM NHẬN PHÍM
Chương trình sau đây mô tả cách xây dựng hàm INKEY tạo ra mã của phím vừa bấm. Nó nhận biết được hầu hết các phím. Ngoài ra chương trình chính cũng sẽ in ra mà hình mã quét lấy từ bộ đệm bàn phím.
Khi chương trình có dùng Unit CRT, phép gán CheckBreak:=TRUE cho phép người sử dụng bấm Ctrl-Break để ngắt chương trình khi chương trình đang chạy( Không phụ thuộc vào lệnh break=on trong config.sys)
Code:
Uses CRT;
VAR 
Key,Head:Word;
FUNCTION INKEY:Word;
  VAR 
      ch:char;
   Begin
      ch:=ReadKey;
       INKEY:=byte(ch);
        If ch=#0 then
            Begin
             ch:=ReadKey;
              INKEY:=256+byte(ch);
             end;
     end;
      Begin
      CheckBreak:=TRUE;
       Clrscr;
       Write(' Bam phim bat ki.');
        Repeat
               If Keypressed then
                Begin
                Clrscr;
                 Head:=Word((ptr(0,$41A)^)-30;
                 Write(#32:7,'Ky tu:',char(ptr(0,$41E+Head)^),
                          #32:4,'Ma Ascii:', byte(Ptr(0,$41E+Head)^),
                          #32:4,'Ma quet:',byte(Ptr(0,$41E+Head+1)^),
                          #32:4);
                   Key:=INKEY;
                  Write('INKEY:',key);
                   Writeln;
                   Writeln;
                   Write(#32:24,'Bam Ctrl-Break de tro ve DOS.');
                  end;
           Until false;
      End.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog

thay đổi nội dung bởi: myhanh, 03-06-2008 lúc 09:59 AM.
myhanh is offline   Trả Lời Với Trích Dẫn
Old 01-01-1970, 07:00 AM   #15
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

CHỒNG (STACK) VÀ HÀNG ĐỢI (QUEUE)
Trong các thuật toán trên đồ thị ta thường tổ chức các dữ liệu thành các danh sách và xử lý các phần tử của danh sách theo một cách nào đó:
Danh sách FIFO(Queue):
Danh sách này được tổ chức theo kiểu phần tử nào vào trước được xử lý trước. Khi đó một cách đơn giản nhất là dùng một mảng một chiều A với kích thước có thể chứa mọi phần tử có thể có và hai biến first và last để ghinhận chỉ số của phần tử đầu tiên và chỉ số của phần tử cuối cùng. Các thao tác trên danh sách FIFO như sau
[code]
+Bước khởi tạo: Đầu tiên A rỗng nên first=last=0
+Kết nạp một phần tử v vào A: A[first]=v; first=last=1;
+Kết nạp một phần tử v vào cuối danh sách, kí hiệu A<=v
A <= v <=>last:=last+1;A[last]:=u;
+Đưa một phần tử ra khỏi danh sách, kí hiệu u<=A
u<=A<=>first:=first+1;
Danh sách LIFO(Stack):

Danh sách này được tổ chức theo kiểu phần tử nào vào sau được xử lý trước. Khi đó một cách đơn giản nhất để xử lý danhsách này là dùng một mảng A với kích thước đủ để chứa mọi phần tử có thể có và biến last để ghi nhận phần tử cuối cùng.
Code:
+Bước khởi tạo: Đầu tiên A rỗng tức là last=0
+Kết nạp v vào A <=> last=1;A[last]=v;
+Kết nạp u vào danh sách, kí hiệu A<=u <=> last:=last+1;A[last]:=u;
+Đưa một phần tử ra khỏi danh sách, kí hiệu A=>u
u<=A<=>last:=last-1;
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog

thay đổi nội dung bởi: myhanh, 03-06-2008 lúc 09:54 AM.
myhanh is offline   Trả Lời Với Trích Dẫn
Đã có thành viên gửi lời cám ơn đến myhanh vì bạn đã đăng bài:
UrkrassFuct (22-09-2016)
Old 01-01-1970, 07:00 AM   #16
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

CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG
Tìm kiếm theo chiều rộng BFS(Bread First Search)
Ý tưởng:
Bắt đầu từ một đỉnh v0 nào đó của đồ thị. Quá trình tìm kiếm tại một đỉnh v nào đó diễn ra như sau: Ta đi từ đỉnh v -->w kề nó ( có trong danh sách kề ). Sau đó lập lại quá trình đi đó đến từng đỉnh trong danh sách kề và cứ tiếp tục cho đến khi không còn đi được nữa.
Code:
PROCEDURE BFS(v)
{ Tìm kiếm theo chiều rộng bắt đầu từ v, các biến chuaxet, ke là biến toàn cục }
BEGIN
   Queue:=0;
   Queue <= v;
  chuaxet[v]:=false;
  WHILE Queue <> 0 DO
   BEGIN
     p<=Queue;
     Thamdinh(p);
    FOR u in ke(p) DO
       IF chuaxet[u] THEN
         BEGIN
            Queue <=u;
            chuaxet[u]:=false;
        END;
    END;
 END;
 BEGIN
   FOR v in V DO chuaxet[v]:=true;
   FOR v in V DO
    IF chuaxet[v] THEN BFS(v);
END.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog

thay đổi nội dung bởi: myhanh, 03-06-2008 lúc 09:56 AM.
myhanh is offline   Trả Lời Với Trích Dẫn
Old 01-01-1970, 07:00 AM   #17
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

CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG
Tìm kiếm theo chiều sâu DFS(Depth First Search)
Ý tưởng:
Bắt đầu từ một đỉnh v0 nào đó của đồ thị.
Sau đó chọn đỉnh v là đỉnh nào đó kề với đỉnh v0 rồi lập lại quá trình sau đối với đỉnh v: Ở bước tổng quát giả sử đang xét v nếu như trong số các đỉnh kề với v tìm được đỉnh u là chưa xét thì ta sẽ xét đỉnh này (nó trở thành đỉnh đã xét) và bắt đầu từ nó ta sẽ tiếp tục quá trình tìm kiếm . Còn như nếu không còn đỉnh nào kề với v là chưa xét thì ta nói rằng ta đã duyệt xong đỉnh v và quay trở lại tìm kiếm từ đỉnh mà trước đó đến đỉnh v ( nếu v=v0 thì kết thúc tìm kiếm). Có thể nói nôm na là tìm kiếm theo chiều sâu bắt đầu từ đỉnh v được thực hiện trên cơ sở tìm kiếm từ tất cả các đỉnh chưa xét kề với v.
Code:
PROCEDURE DFS(v)
{ Giả sử đồ thị cho bởi danh sách kề. Tìm kiếm theo chiều sâu bắt nguồn từ v.
   Các biến chuaxet,ke là các biến toàn cục }
BEGIN
  thamdinh(v);
  chuaxet[v]:=false;
  FOR u in ke(v) DO
     IF chuaxet[u] THEN DFS(u);
 END;
 BEGIN
   FOR v in V DO chuaxet[v]:=true;
   FOR v in V DO
    IF chuaxet[v] THEN DFS(v);
END.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog

thay đổi nội dung bởi: myhanh, 03-06-2008 lúc 09:57 AM.
myhanh is offline   Trả Lời Với Trích Dẫn
Old 01-01-1970, 07:00 AM   #18
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

TÌM ĐƯỜNG ĐI VÀ KIỂM TRA TÍNH LIÊN THÔNG
A.Bài toán tìm đường đi giữa hai đỉnh:

Giả sử s và t là hai đỉnh nào đó của một đồ thị hãy tìm đường đi từ s đến t.
Nhận xét:
-DFS(v) và BFS(v) sẽ cho phép thăm tất cả các đỉnh cùng một thành phần liên thông với s . Vì vậy sau khi thực hiện xong thủ tục nếu chuaxet[t]=true thì có nghĩa là không có đường đi từ s đến t. Ngược lại thì t thuộc cùng một thành phần liên thông với s.
-Dùng biến truoc[v] để ghi nhận đỉnh đi trước v trong đường đi tìm kiếm từ s đến t. Vì vậy cần sữa lại câu lệnh IF như sau:
Code:
DFS(v) -> IF chuaxet[u] THEN
                   BEGIN
                        truoc[u]:=v;
                        DFS(u);
                   END;
BFS(v) -> IF chuaxet[u] THEN
                   BEGIN
                        Queue <=u;
                         chuaxet[u]:=false;
                       truoc[u]:=p;
                 END;
Đường đi cần tìm kiếm sẽ được hồi phục theo qui tắc sau:
t <-p1:=truoc[t] <-p2:=truoc[p1]...<-s
* Chú ý: Đường đi tìm được theo tuấn toán tìm kiếm theo chiều rộng là đường đi ngắn nhất hiểu theo số cạnh từ s->t.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog

thay đổi nội dung bởi: myhanh, 03-06-2008 lúc 09:58 AM.
myhanh is offline   Trả Lời Với Trích Dẫn
Old 01-01-1970, 07:00 AM   #19
Hồ sơ
LeGiang
Banned
 
Tham gia ngày: Jan 2005
Số bài viết: 473
Tiền: 25
Thanks: 41
Thanked 593 Times in 241 Posts
LeGiang is an unknown quantity at this point
Default

Trích:
Originally posted by thihonghanh@Nov 27 2005, 02:49 AM
doc nhung gi chi Hanh dua len, em cam thay rat vui, nhung cung buon!!ba giao vien Tin hoc cua truong minh hinh nhu chua co ai la len trang web nay ca!!!That la tiec qua phai khong chi!!!Em se noi voi nhung dua hoc tro thich Tin nhung bai viet cua chi va mong rang tui se thich trang web hon!!
[snapback]6115[/snapback]
Neu như thầy cô tin học lên trangweb thì chúng ta sẽ có được nguồn cổ vũ và động viên, nhất là được chia sẽ kinh nghiêm.
LeGiang is offline   Trả Lời Với Trích Dẫn
Đã có thành viên gửi lời cám ơn đến LeGiang vì bạn đã đăng bài:
RidgeSt (30-09-2018)
Old 04-06-2008, 03:10 PM   #20
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

sao MH ko viết topic này nữa nhỉ?Em đang học trong đội Tin,em sẽ ủng hộ 2 tay 2 chân luôn.
__________________
"hcmiu.edu.vn"
khanhan2006_2009 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à 02:24 AM.

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