Cựu Học Sinh Lê Quý Đôn - Long An
Trang 1/2 1 2 >
Hiển thị 40 bài trong cũng một trang

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

thihonghanh 01-01-1970 07:00 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!!

myhanh 01-01-1970 07:00 AM
Trích:
Originally posted by thihonghanh@Nov 27 2005, 09: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]
Chào cô Hạnh!
myhanh cũng có một chút giống cô Hạnh đó là cái nick myhanh. Cái nick này myhanh lấy khi làm thơ, viết báo riết rồi quen chứ myhanh là man 100% hì hì.
Đọc mấy dòng của cô Hạnh, myhanh cảm thấy mình có thêm sức mạnh. Thật ra kiến thức tin học rất mênh mông. myhanh cũng không biết các em cần gì nữa. myhanh chỉ nhớ lại những chủ đề mà Thầy Nhàn, Thầy Yên, Thầy Tân dạy myhanh khi myhanh tham gia đội tuyển Toán-Tin ngày trước.
Nhớ năm 1997 tại trường Đại học Bách Khoa Hà nội, khi ấy myhanh tham gia kỳ thi Tin học không chuyên toàn quốc lần thứ 3, đề thi cho hai câu hỏi thật đơn giản một bài dùng thuật giải Dijkstra và một bài nhân chia số lớn nhưng myhanh không làm được. Thật đáng buồn. Cuối cùng chỉ được giải khuyến khích. Một phần lúc đó do myhanh đang bệnh, một phần do mình thực hành quá ít nên khi lâm trận thì thiếu tự tin.
Từ ngày đó đến nay đã 8 năm rồi không biết việc thi cử có gì thay đổi không. Theo kinh nghiệm qua qua các lần thi cử hồi đó (4 lần thi học sinh giỏi, 3 lần thi tin học không chuyên) thì để làm được bài thi thì thí sinh phải nắm một số giải thuật, heuristic sau:
1. Mô hình quay lui, giải thuật vét cạn, nhánh cận.
2. Mô hình vết dầu loang, bài toán sinh.
3. Các giải thuật đồ thị như: Tô màu đồ thị, tìm đường đi ngắn nhất (Dijkstra, Loyd), cây phủ, cây phủ tối thiểu (Prism, Krusal),BFS,DFS, liên thông, chu trình Euler, chu trình Hamilton,...
4. Bài toán hình học: Đa giác lồi, diện tích đa giác lồi, cặp đoạn thẳng cắt nhau, tìm vùng nhìn,...
5. Bài toán cộng, trừ, nhân, chia số lớn.
6. Bài toán phân việc, giải thuật tham lam (greedy algorithm).
7. Giải hệ phương trình tuyến tính (phương pháp Gauss, Jaccobi).

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.

myhanh 01-01-1970 07:00 AM
CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
2.Cây khung của đồ thị:
Định nghĩa:
Giả sử G=(V,E) là đồ thị vô hướng liên thông. Cây T=(V,F), F là tập con của E được gọi là cây khung của đồ thị.
Áp dụng thuật toán tìm kiếm theo chiều rộng, chiều sâu để xây dựng cây khung của đồ thị vô hướng liên thông. Trong cả hai trường hợp mỗi khi ta đến được đỉnh mới u từ đỉnh v thì cạnh (v,u) sẽ được kết nạp vào cây khung
Code:
PROCEDURE STREE_DFS(v);
(* Tìm kiếm theo chiều sâu tìm cây khung T của đồ thị vô hướng liên thông G cho bởi danh sách kề, các biến chuaxet,ke,T là toàn cục*)
BEGIN
  chuaxet[v]:=false;
  FOR u in ke(v) DO
      IF chuaxet[u] THEN
          BEGIN
                T:=T U (v,u);
                  STREE_DFS(u);
          END;
END;
BEGIN
  FOR u in V DO chuaxet[u]:=true;
  T:=Ø;
  STREE_DFS(Root);
 END.

Bài tập:
Viết thủ tục STREE_BFS(v).

myhanh 01-01-1970 07:00 AM
CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
3.Bài toán cây khung nhỏ nhất:
Cho đồ thị G=(V,E) là đồ thị vô hướng , liên thông với
V={v1,v2,...,vn}, E= m cạnh với ∀e ∈ E, ∃C(e)>0: C(e) gọi là độ dài của nó.
H=(V,T) là cây khung của đồ thị G. Ta gọi độ dài C(H) của cây khung H là tổng độ dài các cạnh của nó
C(H) = ΣC(e), e ∈ H.
Tìm H sao cho C(H) nhỏ nhất.

quemoi 01-01-1970 07:00 AM
Ngoài các thuật toán ra, trong các kỳ thi Olympic các bạn đi thi cần một số chiến thuật và kinh nghiêm. Ví dụ:
1. Ban giám khảo chấm điểm tự đông bằng chương trình, không xem source code, cho nên đầu tiên là chương trình của các bạn cần phải chạy, cho kết quả được đầu vào đầu ra đúng. Trong một số trường hợp thì không tìm được thuật giải hoàn chỉnh với một khoảng thời gian cho phép, lúc đó bạn cứ bình tĩnh, cố gắng tìm ra được một thuật giải càng đúng nhiều test càng tốt.

2. Có một số vấn đề mà trong toán học có thể hơi khác với trong tin học, lúc các bạn làm bài nếu bị một tính "ì" trong toán học thì các bạn có thể dẫn đến KQ sai(không đúng với đầu ra của test). Chẳng hạn như là so sánh 2 số thực, trong toán học 2 số thực bằng nhau là a=b, nhưng trong một số bài toán của tin học thì các bạn phải thay a=b bởi 1 hàm số abs(a-B)<saiso vì số thực của Tin học không "chính xác" như là số thực của toán học. VD so sánh a*a=2*b*b, nếu như b=1, a=1.4142... thì dấu bằng cũng có thể không xảy ra. Các bạn phải chú ý sai số mà bài toán đưa ra.
Tuy những vấn đề này đơn giản nhưng có nhiều bạn làm rất tốt về thuật toán vẫn bị điểm thấp, nhất là các bạn thiếu "kinh nghiêm trận mạc".

Bữa khác tiếp tục nhé............

myhanh 01-01-1970 07:00 AM
Mấy ngày gần đây myhanh quá bận với thi cử nên không có ghé qua diễn đàn. Hôm nay thi xong myhanh xin tiếp tục chủ đề này.
Thứ nhất là ý kiến của quemoi rất hay. Văn ôn thì võ luyện. Cái kinh nghiệm trận mạc của quemoi chỉ là dùng để luyện gà chọi thôi. Ở đây myhanh muốn bàn về khía cạnh kiến thức. Cả hai mặt này bổ sung cho nhau, không thể xem nhẹ mặt nào đâu nha :lol: .

quemoi 01-01-1970 07:00 AM
Trích:
Originally posted by myhanh@Jan 9 2006, 12:27 PM
Mấy ngày gần đây myhanh quá bận với thi cử nên không có ghé qua diễn đàn. Hôm nay thi xong myhanh xin tiếp tục chủ đề này.
Thứ nhất là ý kiến của quemoi rất hay. Văn ôn thì võ luyện. Cái kinh nghiệm trận mạc của quemoi chỉ là dùng để luyện gà chọi thôi. Ở đây myhanh muốn bàn về khía cạnh kiến thức. Cả hai mặt này bổ sung cho nhau, không thể xem nhẹ mặt nào đâu nha :lol: .
Đúng là không được xem nhẹ mặt nào, trong các kỳ thi thì kiến thức thuật toán vẫn là quan trọng nhất, nhưng bên cạnh đó cần chú ý một số vấn đề mà minh đưa ra. Thực tế là đã có nhiều bạn HSSV ở các trường phổ thông và ĐH đã gặp phải những vấn đề này mặc dù rất giỏi. Mục tiêu của chúng ta là đem lại tiếng tăm cho HSSV Miền Nam chúng ta nói chung và quê hương Long An nói riêng, nên mình cũng tham gia đóng góp một vài ý kiến nho nhỏ cho đàn em của chúng ta.

3. Vấn đề thứ 3 trong các kỳ thi đó là thuật giải sắp xếp:
Có nhiều thuật giải sắp xếp khác nhau, nhưng ở các kỳ thi thì các bạn sẽ thường dùng đến 2 thuật giải là Bubble Sort và Quick Sort.
- Thuật giải Bubble sort cài đặt rất nhanh, dễ, dễ dàng kiểm tra tính đúng đắn, tuy nhiên lại chiếm thời gian lớn khi thực thi (0(n^2)).
- Thuật giải Quick sort thì thực thi nhanh nhưng lại đòi hỏi thời gian cài đặt lâu hơn 1 chút.
Vì vậy tuỳ vào yêu cầu của bài toán(số phần tử cực đại và thời gian cho 1 test) mà các bạn chọn 1 thuật giải thích hợp. Đã từng có bạn đi thi viết đúng thật giải hoàn toàn nhưng đề bài cho số phần tử lớn, và thời gian để thực thi 1 test ít, chương trình của bạn ấy không kịp ghi KQ ra file xuất cho nên đã không đạt điểm tuyệt đối do sai ở một số test, thật đáng tiếc!!!!!

myhanh 01-01-1970 07:00 AM
CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
4.Thuật toán Kruskal:
Xây dựng tập cạnh T của cây khung nhỏ nhất H=(V,T). Sắp xêp các cạnh của đồ thị G theo thứ tự không giảm của độ dài.
Bắt đầu T = Ø
Ở mỗi bước duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn để tìm ra cạnh mà việc bổ sung vào tập T không tạo thành chu trình trong tập này.
Thuật toán sẽ kết thúc khi ta thu được tập T gồm có n-1 cạnh.
Code:
PROCEDURE KRUSKAL;
  BEGIN
  Sắp xếp các cạnh theo chiều không giảm;
    T = Ø;
  WHILE ( |T| < n-1 ) AND ( E <> Ø) DO
      BEGIN
          Chọn e in E là cạnh có độ dài nhỏ nhất.
            E:= E - {e};
            IF (T + {e}) không chứa chu trình THEN
            T:=T+{e}
            END;
      END;

khanhan2006_2009 04-06-2008 02:10 PM
Ðề: 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.

myhanh 04-06-2008 02:53 PM
Ðề: Những thuật toán hay thi HSG Tin học
 
Còn nhiều lắm viết đến khi nào cho hết mà thời gian ko cho phép! Nếu như có gì cần hỏi em cứ post lên anh nói tiếp! Cái topic này do lần đổi host trước làm mất thời gian nên trình tự nó hơi lộn ngược. Em coi cái bài sau cùng trước nhé!

khanhan2006_2009 05-06-2008 10:04 AM
Ðề: Những thuật toán hay thi HSG Tin học
 
Trong mấy cái thuật toán về tìm kiếm đường đi ngắn nhất trên đồ thị thì cái nào là tối ưu nhất để chạy được các test lớn?Em thường dùng Dijkstra nhưng nghe nói cái đó khi chạy test lớn mất khá nhiều thời gian.

myhanh 05-06-2008 10:21 AM
Ðề: Những thuật toán hay thi HSG Tin học
 
Trích:
Nguyên văn bởi khanhan2006_2009 (Post 29681)
Trong mấy cái thuật toán về tìm kiếm đường đi ngắn nhất trên đồ thị thì cái nào là tối ưu nhất để chạy được các test lớn?Em thường dùng Dijkstra nhưng nghe nói cái đó khi chạy test lớn mất khá nhiều thời gian.

Đúng như em nói trong thực tế để giải quyết bài toán tìm kiếm người ta phải kết hợp giữa Local Search và Meta Search em à! Gỉai thuật Dijkstra là một trong những giải thuật Local search nó tìm kiếm ra một mẫu khi đã bỏ qua rất nhiều ràng buộc. Sau đó dùng mẫu này làm dữ liệu nhập cho các giải thuật meta search như Leo đồi, luyện kim, Tabu, gen ...
Do đó em cứ yên tâm dùng Dijkstra nhé vì khi cho Dijktra thì người ta cũng cho dữ liệu nhỏ thôi
Trong tìm kiếm đường đi ngắn nhất có hai giải thuật: Dijkstra (theo hướng tìn kiếm theo chiều rộng- cây tìm kiếm toả nhánh liên tục từ điểm gốc cho đến điểm đích và kết quả khi kết thúc giải thuật thì ta tìm được tất cả đường đi ngắn nhất từ điểm xuất phát đến các điểm còn lại của đồ thị) . Giải thuật Floyd (theo hướng tìm kiếm theo chiều sâu, cây tìm kiếm sinh ra không liên tục). Cả hai giải thuật có độ phức tạp thuật toán là . Tuy nhiên kinh nghiệm cho thấy Floyd đơn giản, dễ thực hiện và chạy nhanh hơn nhiều.
Đồ thị dày dùng Floyd
Đồ thị không dày () dùng Dijkstra.

khanhan2006_2009 05-06-2008 03:28 PM
Ðề: Những thuật toán hay thi HSG Tin học
 
Theo em biết thì Dijkstra chỉ là n^2 thôi.
Đồ thị dày là sao anh?
Nếu như Floyd đơn giản, dễ thực hiện và chạy nhanh hơn thì sao ko dùng Floyd cho tất cả các dạng đồ thị.?

myhanh 05-06-2008 05:17 PM
Ðề: Những thuật toán hay thi HSG Tin học
 
Trích:
Nguyên văn bởi khanhan2006_2009 (Post 29711)
Theo em biết thì Dijkstra chỉ là n^2 thôi.
Đồ thị dày là sao anh?
Nếu như Floyd đơn giản, dễ thực hiện và chạy nhanh hơn thì sao ko dùng Floyd cho tất cả các dạng đồ thị.?
Đúng là n^2 nhưng để so sánh với F thì phải chạy D n lần cơ!
Đồ thị dày tức là trái với độ thị không dày đã định nghĩa rùi đó.

khanhan2006_2009 05-06-2008 09:01 PM
Ðề: Những thuật toán hay thi HSG Tin học
 
???????????????????????

khanhan2006_2009 05-06-2008 09:02 PM
Ðề: Những thuật toán hay thi HSG Tin học
 
ah!Em hiểu rồi,ý anh là tìm đường đi ngắn nhất giữa mọi cặp đỉnh?
Nếu như vậy thì Dijkstra là n^3.
"Nếu như Floyd đơn giản, dễ thực hiện và chạy nhanh hơn thì sao ko dùng Floyd cho tất cả các dạng đồ thị mà phân ra dày hay không dày?"

duyhung123abc 05-06-2008 09:11 PM
Ðề: Những thuật toán hay thi HSG Tin học
 
Nếu sử dụng Dijkstra trên cấu trúc HEAP có lẽ sẽ chạy nhanh hơn FLOYD, đúng hem ta?

myhanh 06-06-2008 08:53 AM
Ðề: Những thuật toán hay thi HSG Tin học
 
Trích:
Nguyên văn bởi duyhung123abc (Post 29735)
Nếu sử dụng Dijkstra trên cấu trúc HEAP có lẽ sẽ chạy nhanh hơn FLOYD, đúng hem ta?
Khi D dùng Heap với ma trận kề thì độ phức tạp thuật toán là => Nhanh hơn Floyd. Nhưng nếu đồ thị đầy tức là thì Floyd lại nhanh hơn nên dùng Floyd ở đây!

duyhung123abc 06-06-2008 10:37 AM
Ðề: Những thuật toán hay thi HSG Tin học
 
Vậy nghĩa là chỉ trường hợp đó FLOYD mới nhanh hơn DIJKSTRA, haha, KA ui, tụi mình thắng kiện roài

khanhan2006_2009 06-06-2008 10:53 AM
Ðề: 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.

duyhung123abc 06-06-2008 10:58 AM
Ðề: 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.

khanhan2006_2009 06-06-2008 09:06 PM
Ðề: 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).

myhanh 07-06-2008 09:17 AM
Ðề: 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!

duyhung123abc 11-06-2008 10:50 AM
Ðề: 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 :))

khanhan2006_2009 11-06-2008 11:04 AM
Ðề: 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:biggrin::biggrin:

duyhung123abc 11-06-2008 11:08 AM
Ðề: 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.

khanhan2006_2009 29-06-2008 09:16 PM
Ðề: 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.:smile::smile:

myhanh 29-06-2008 10:56 PM
Ðề: 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)

duyhung123abc 07-07-2008 09:34 PM
Ðề: 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à :))


Múi giờ GMT +7. Hiện tại là 06:52 AM.
Trang 1/2 1 2 >
Hiển thị 40 bài trong cũng một trang

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