kết quả từ 1 tới 12 trên 12

Giúp với đề thi HSG nghệ an 2007-2008

  1. #1
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

    Question Giúp với đề thi HSG nghệ an 2007-2008

    Bài 1 (7 điểm)
    ĐƯỜNG HẦM
    Có N hòn đảo đánh số từ 1 đến N. Một số hòn đảo đã có đường hầm thông với nhau.
    Người ta muốn xây dựng thếm một số đường hầm sao cho có thể đi lại giữa 2 hòn đảo bất kỳ
    bằng đường hầm. Biết rằng đường hầm nối các đảo là đường đi 2 chiều, hãy lập trình tính số
    đường hầm ít nhất cần xây dựng thên.
    Dữ liệu: vào từ file văn bản HAM.INP gồm
    - Dòng đầu tiên la số N(1<=N<=100).
    -Các dòn tiếp theo mỗi dòng ghi hai số i và j cho biết có đường hầm nối giữa 2 hòn đảo u va j.
    Kết quả :ghi ra file văn bản HAM.OUT chỉ số suy nhất cho biết số đường hầm ít nhất cần xây dựng
    thêm.
    Ví dụ


    HAM.INP HAM.OUT
    9 2
    1 3
    1 5
    1 6
    2 7
    4 8
    8 9
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: giúp với đề thi HSG nghệ an 2007-2008

    Bạn xây dựng đồ thị với đỉnh là hòn đảo đc đánh số từ 1 tới N; 2 đỉnh u và v đc nối với nhau nếu có đg` hầm nối 2 hòn đảo. Đây là đồ thị vô hướng vì đg` hầm là 2 chiều. Sau đó, bạn duyệt đồ thị (dùng BFS hay DFS đều đc), tìm số lượng connected components của đồ thị. Số đg` hầm cần thêm vào chính là số connected components trừ đi 1.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. #3
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    t mới học lập trình cậu chỉ rõ hơn hoặc viết code cho t đc ko>

  4. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    Bài này thuộc về graph theory rồi, không thích hợp nếu bạn mới học lập trình đâu. Mình không thể viết toàn bộ lý thuyết đồ thị cơ bản lên đây đc chỉ có thể nói gọn thôi. Cách làm bài này là:
    1) Xây dựng đồ thị:
    - Dùng 1 mảng 2 chiều n x n để đánh dấu. a[i, j] = 1 nếu đã có đg` hầm từ đảo i tới đảo j (và a[j, i] = 1 vì đg` hầm là 2 chiều). Còn lại a[i, j] = 0.
    - Mình ghi code đơn giản như bên dưới để xây dựng đồ thị như trong ví dụ:
    Mã:
    procedure read_data;
    var i, j : integer;
    begin
        n := 9;
        for i := 1 to n do
            for j := 1 to n do
                a[i, j] := '0';
        a[1, 3] := '1'; a[3, 1] := '1';
        a[1, 5] := '1'; a[5, 1] := '1';
        a[1, 6] := '1'; a[6, 1] := '1';
        a[2, 7] := '1'; a[7, 2] := '1';
        a[4, 8] := '1'; a[8, 4] := '1';
        a[8, 9] := '1'; a[9, 8] := '1';
    end;

    Bạn cần đọc file và sửa lại a[i, j] = '1' tùy theo nhé.

    2) Xử lý:
    - Từ mỗi hòn đảo, đi theo các cung "đường hầm" để xem đến đc những đảo nào. Đảo nào đến đc thì đánh dấu lại và không đi trùng. Có 2 thuật toán cơ bản để duyệt là DFS (depth first search) và BFS (breadth first search). Trong code mình dùng DFS vì dễ viết. Nếu từ 1 hòn đảo có thể đi đc đến những hòn đảo nào khác thì nguyên cụm đó gọi là "connected component" của đồ thị (thành phần liên thông).
    - Bởi vì không cần xây dựng đg` hầm với những đảo nằm trong một thành phần liên thông nữa, nên chúng ta chỉ quan tâm tới giữa những thành phần liên thông với nhau. Ví dụ nếu có M điểm thì phải cần M - 1 đoạn thẳng nối nó lại. Như vậy, số đg` hầm chính là số thành phần liên thông trừ đi cho 1.
    Mã:
    procedure dfs(start : integer);
    var i : integer;
    begin
        color[start] := 'g';
        for i := 1 to n do
            if (color[i] = 'w') and (a[start, i] = '1') then
                dfs(i);
    end;
    
    function number_of_tunnels() : integer;
    var i, count : integer;
    begin
        // mảng dấu để đánh dấu những đỉnh đã đến rồi. Khởi tạo ban đầu là chưa đến đỉnh nào cả.
        for i := 1 to n do
            color[i] := 'w';
        // đếm thành phần liên thông
        count := 0;
        for i := 1 to n do
            if (color[i] = 'w') then
                begin
                    dfs(i);
                    count := count + 1;
                end;
        exit(count - 1);
    end;

    Biến khai báo là:
    Mã:
    const MAXN = 100;
    var a : array[1..MAXN, 1..MAXN] of char;
        color : array[1..MAXN] of char;
        n : integer;

    Bạn xem visualization về cách duyệt DFS trong link sau (chọn Undirected Graph), nhập vào đỉnh bắt đầu duyệt rồi nhấn "Run DFS": Bạn kéo slider bên dưới để giảm tốc độ lại khi xem.
    HTML Code:
    https://www.cs.usfca.edu/~galles/visualization/DFS.html

  5. #5
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    cảm ơn cậu nhiều nha! tớ mới học đc mấy tháng thui!!.
    nên mấy bài này hơi trìu tượng. tớ vẫn chưa hiểu rõ lắm c giải thích rõ hơn đc ko?

  6. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    Trích Nguyên văn bởi hoangtungok123 Xem bài viết
    cảm ơn cậu nhiều nha! tớ mới học đc mấy tháng thui!!.
    nên mấy bài này hơi trìu tượng. tớ vẫn chưa hiểu rõ lắm c giải thích rõ hơn đc ko?
    Bạn không rõ ở bước nào? Phần xây dựng đồ thị hay là phần xử lý chính? Đây là hình vẽ của ví dụ trong đề bài, mỗi một hòn đảo tượng trưng cho hình tròn đc đánh số từ 1 tới 9. Hai vòng tròn nối với nhau nếu có đg` hầm đi qua giữa 2 đảo. Nhìn vào hình bạn thấy rất rõ có 3 thành phần liên thông:
    Mã:
     {1, 3, 5, 6}, {2, 7}, {4, 8, 9}
    Rõ ràng, trong cùng 1 thành phần liên thông thì có thể tự do qua lại thoải mái giữa các đảo, và ta cần xây thêm nhiều nhất là 1 đg` hầm để đi sang thành phần liên thông khác. Như vậy có tổng cộng là 2 đg` hầm.

    Mảng 2 chiều tương ứng với hình vẽ trên là
    Mã:
       1  2  3  4  5  6  7  8  9
    1  0  0  1  0  1  1  0  0  0
    2  0  0  0  0  0  0  1  0  0
    3  1  0  0  0  0  0  0  0  0
    4  0  0  0  0  0  0  0  1  0
    5  1  0  0  0  0  0  0  0  0
    6  1  0  0  0  0  0  0  0  0
    7  0  1  0  0  0  0  0  0  0
    8  0  0  0  1  0  0  0  0  1
    9  0  0  0  0  0  0  0  1  0

  7. #7
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    bạn viết chương trinh đầy đủ dc ko?
    procedure dfs(start : integer);
    var i : integer;
    begin
    color[start] := 'g'; {chỗ này t ko hiểu sao lại là 'g'}
    for i := 1 to n do
    if (color[i] = 'w') and (a[start, i] = '1') then {cả 'w' nữa}
    dfs(i);
    end;

    function number_of_tunnels() : integer;
    var i, count : integer;
    begin
    // mảng dấu để đánh dấu những đỉnh đã đến rồi. Khởi tạo ban đầu là chưa đến đỉnh nào cả.
    for i := 1 to n do
    color[i] := 'w';
    // đếm thành phần liên thông
    count := 0;
    for i := 1 to n do
    if (color[i] = 'w') then
    begin
    dfs(i);
    count := count + 1;
    end;
    exit(count - 1);{ý nghĩa câu này là gì ? }
    end;

  8. #8
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    - Mình viết cho bạn đã 90% chương trình rồi. Bạn chỉ còn viết phần đọc file lấy từng cặp số i, j rồi gán a[i, j] = '1' và a[j, i] = '1'. Sau đó, gộp nó lại với phần xử lý là chạy được thôi.
    - Mảng 'color' dùng để đánh dấu đỉnh chưa đến ('w' = white, chưa đến), hay đến rồi ('g' = grey = đến rồi). Bạn dùng cặp character nào cũng được cả. Mình sử dụng nó là thói quen rồi, có thể '0' và '1' nữa.
    - exit(....) là để function trả ra giá trị đó ngay lập tức mà không chạy tiếp nữa.

  9. #9
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    ông viết cho rui code hoàn chỉnh đi giúp tui với. mai nộp rùi nhé làm ơn!
    tui đọc ko hiểu gì ý

  10. #10
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    Mình không dùng Pascal đã lâu rồi, nhất là khoảng nhập xuất file, nên chưa test kỹ:
    Mã:
    const MAXN = 100;
          FI = 'HAM.INP';
          FO = 'HAM.OUT';
    var a : array[1..MAXN, 1..MAXN] of char;
        color : array[1..MAXN] of char;
        n : integer;
        
    procedure dfs(start : integer);
    var i : integer;
    begin
        color[start] := 'g';
        for i := 1 to n do
            if (color[i] = 'w') and (a[start, i] = '1') then
                dfs(i);
    end;
    
    function number_of_tunnels() : integer;
    var i, count : integer;
    begin
        // mảng dấu để đánh dấu những đỉnh đã đến rồi. Khởi tạo ban đầu là chưa đến đỉnh nào cả.
        for i := 1 to n do
            color[i] := 'w';
        // đếm thành phần liên thông
        count := 0;
        for i := 1 to n do
            if (color[i] = 'w') then
                begin
                    dfs(i);
                    count := count + 1;
                end;
        exit(count - 1);
    end;
    
    procedure read_data;
    var f : text;
        i, j : integer;
    begin
        assign(f, FI);
        reset(f);
        readln(f, n);
        for i := 1 to n do
            for j := i to n do
                begin
                    a[i, j] := '0';
                    a[j, i] := '0';
                end;
        while not eof do
            begin
                readln(f, i, j);
                a[i, j] := '1';
                a[j, i] := '1';
            end;
        close(f);
    end;
    
    procedure write_data(k : integer);
    var f : text;
    begin
        assign(f, FO);
        rewrite(f);
        writeln(f, k);
        close(f);
    end;
    
    BEGIN
        read_data;
        write_data(number_of_tunnels());
    END.

  11. Đã cảm ơn tengiday:


  12. #11
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    Trích Nguyên văn bởi tengiday Xem bài viết
    Mình không dùng Pascal đã lâu rồi, nhất là khoảng nhập xuất file, nên chưa test kỹ:
    Mã:
    const MAXN = 100;
          FI = 'HAM.INP';
          FO = 'HAM.OUT';
    var a : array[1..MAXN, 1..MAXN] of char;
        color : array[1..MAXN] of char;
        n : integer;
        
    procedure dfs(start : integer);
    var i : integer;
    begin
        color[start] := 'g';
        for i := 1 to n do
            if (color[i] = 'w') and (a[start, i] = '1') then
                dfs(i);
    end;
    
    function number_of_tunnels() : integer;
    var i, count : integer;
    begin
        // mảng dấu để đánh dấu những đỉnh đã đến rồi. Khởi tạo ban đầu là chưa đến đỉnh nào cả.
        for i := 1 to n do
            color[i] := 'w';
        // đếm thành phần liên thông
        count := 0;
        for i := 1 to n do
            if (color[i] = 'w') then
                begin
                    dfs(i);
                    count := count + 1;
                end;
        exit(count - 1);
    end;
    
    procedure read_data;
    var f : text;
        i, j : integer;
    begin
        assign(f, FI);
        reset(f);
        readln(f, n);
        for i := 1 to n do
            for j := i to n do
                begin
                    a[i, j] := '0';
                    a[j, i] := '0';
                end;
        while not eof do
            begin
                readln(f, i, j);
                a[i, j] := '1';
                a[j, i] := '1';
            end;
        close(f);
    end;
    
    procedure write_data(k : integer);
    var f : text;
    begin
        assign(f, FO);
        rewrite(f);
        writeln(f, k);
        close(f);
    end;
    
    BEGIN
        read_data;
        write_data(number_of_tunnels());
    END.
    tớ chạy nó lỗi cậu xem lại hộ tớ đi !!

  13. Đã cảm ơn hoangtungok123:


  14. #12
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Giúp với đề thi HSG nghệ an 2007-2008

    Trích Nguyên văn bởi hoangtungok123 Xem bài viết
    tớ chạy nó lỗi cậu xem lại hộ tớ đi !!
    Bạn cho mình biết thông báo lỗi mới fix đc. Bạn kiểm tra lại xem mảng 'a' đã nhập chính xác hay chưa. Nếu lỗi nhập xuất file thì bạn có thể tự sửa đc. Mình không có Pascal nên chỉ có thể dùng online Pascal mà thôi, bởi vậy mình không làm phần đọc xuất file bao giờ cả.

Nhãn