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

myhanh · 01-01-1970, 07:00 AM

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.

trongbangpham · 01-01-1970, 07:00 AM

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

myhanh · 01-01-1970, 07:00 AM

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;

myhanh · 01-01-1970, 07:00 AM

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.

myhanh · 01-01-1970, 07:00 AM

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;

myhanh · 01-01-1970, 07:00 AM

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.

myhanh · 01-01-1970, 07:00 AM

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.

myhanh · 01-01-1970, 07:00 AM

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.

LeGiang · 01-01-1970, 07:00 AM

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.

khanhan2006_2009 · 04-06-2008, 03:10 PM

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.