Cựu Học Sinh Lê Quý Đôn - Long An

Cựu Học Sinh Lê Quý Đôn - Long An (http://www.lqdlongan.com/forum/index.php)
-   Học lập trình (http://www.lqdlongan.com/forum/forumdisplay.php?f=105)
-   -   Những thuật toán hay thi HSG Tin học (http://www.lqdlongan.com/forum/showthread.php?t=879)

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 :D

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.

myhanh 01-01-1970 07:00 AM

TÌM ĐƯỜNG ĐI VÀ KIỂM TRA TÍNH LIÊN THÔNG
B.Kiểm tra tính liên thông:

Dựa vào nhận xét đầu tiên mục A ta dễ dàng có thuật toán kiểm tra tính liên thông.

myhanh 01-01-1970 07:00 AM

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
1.Cây và tính chất cơ bản của cây:

Ta gọi cây là đồ thị vô hướng, liên thông và không có chu trình. Một đồ thị không có chu trình gọi là rừng. Như vậy thì rừng là đồ thị mà mỗi thành phần liên thông của nó là cây.
Code:

Định lí:
Giả sử G=(V,E) là đồ thị vô hướng n đỉnh. Khi đó các mệnh đề sau đây là tương đương nhau:
a. G là cây.
b. G không chứa chu trình và có n-1 cạnh.
c.G liên thông và có n-1 cạnh.
d.G liên thông và mỗi cạnh của nó đều là cầu.
e.Hai đỉnh bất kì của đồ thị được nối với nhau duy nhất bởi một đường đi đơn.
f.G không chứa chu trình, nhưng hễ cứ thêm vào nó một cạnh thì thì ta thu được đúng một chu trình



Múi giờ GMT +7. Hiện tại là 04:14 PM.

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.
Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này