Tin học lập trình c++

Thảo luận trong 'Dòng họ c , c++ , c#' bắt đầu bởi ngô trang, 12 Tháng ba 2018.

Lượt xem: 370

?

tin

  1. 1

    1 vote(s)
    100.0%
  2. 2

    0 vote(s)
    0.0%
Multiple votes are allowed.

  1. ngô trang

    ngô trang Học sinh chăm học Thành viên

    Bài viết:
    12
    Điểm thành tích:
    71
    Nơi ở:
    Hà Nam
    Trường học/Cơ quan:
    trung học phổ thông chuyên biên hòa
    Sở hữu bí kíp ĐỖ ĐẠI HỌC ít nhất 24đ - Đặt chỗ ngay!

    Đọc sách & cùng chia sẻ cảm nhận về sách số 2


    Chào bạn mới. Bạn hãy đăng nhập và hỗ trợ thành viên môn học bạn học tốt. Cộng đồng sẽ hỗ trợ bạn CHÂN THÀNH khi bạn cần trợ giúp. Đừng chỉ nghĩ cho riêng mình. Hãy cho đi để cuộc sống này ý nghĩa hơn bạn nhé. Yêu thương!

    Đóng cửa sổ màn hình (c++)
    Khi làm việc trên máy tính người ta thường mở rất nhiều cửa sổ. Mỗi cửa sổ là một hình chữ nhật bao gồm một số ô vuông nhỏ kích thước 1 x 1. Một cửa sổ mới được mở, phụ thuộc vào vị trí và kích thước của nó, có thể che khuất một phần hoặc toàn bộ những cửa sổ mở trước nó. Chúng ta có thể đóng cửa sổ bằng cách nháy chuột vào ô vuông nhỏ ở góc phải trên của cửa sổ, nếu như tại thời điểm đó ta nhìn thấy ô vuông này. Một ô của một cửa số là nhìn thấy được nếu như mỗi cửa số che khuất nó đều đã được đóng.
    Yêu cầu: Hãy tính số lượng ít nhất lần nháy chuột để có thể đóng được cửa sổ được mở đầu tiên.
    Dữ liệu: vào từ file MCLICK.INP:
    - Dòng đầu tiên chứa số nguyên N (1 .. 100), là số cửa sổ.
    - Mỗi dòng trong số n dòng tiếp theo chứa 4 số nguyên R1, S1, R2, S2 (1 <= R1 <= R2 <= 10000, 1 <= S1 <= S2 <= 10000) trong đó (R1, S1) là toạ độ màn hình của đỉnh góc trái trên, còn (R2, S2) là toạ độ của đỉnh góc phải dưới của cửa sổ. Các cửa sổ được mở theo trình tự chúng xuất hiện trong file dữ liệu.
    Chú ý: hãy tưởng tượng màn hình bao gồm một lưới các ô vuông nhỏ. Các dòng của lưới được đánh số từ trên xuống dưới, các cột được đánh số từ trái qua phải bắt đầu từ 1. Ô ở góc trên trái của màn hình nằm ở dòng 1 cột 1.
    Kết quả: ghi ra file MCLICK.OUT: một số nguyên duy nhất là số lần nháy chuột ít nhất cần thực hiện để đóng được cửa sổ đầu tiên.
    Ví dụ:
    MLICK.INP MCLICK.OUT MCLICK.INP MCLICK.OUT
    3 3 3 1
    3 1 6 4 3 3 4 4
    1 2 4 6 1 1 2 2
    2 3 5 5 5 5 6 6
    Mọi người ơi giúp mình bài này với !!!
     
  2. Mark Urich

    Mark Urich Học sinh chăm học Thành viên

    Bài viết:
    133
    Điểm thành tích:
    59
    Nơi ở:
    Hà Nội
    Trường học/Cơ quan:
    NDC

    bạn chụp lại đề lên đi, viết ntn ko rõ ràng đâu, tôi nhìn input là biết ko chính xác rồi.
     
  3. Mark Urich

    Mark Urich Học sinh chăm học Thành viên

    Bài viết:
    133
    Điểm thành tích:
    59
    Nơi ở:
    Hà Nội
    Trường học/Cơ quan:
    NDC

    Gợi ý:
    Với 2 cửa sổ bất kì A và B, ta thấy chúng có mối quan hệ như sau:
    + Hoặc A và B ko che khuất nhau (nghĩa là điểm đóng ko bị che khuất), hoặc là chúng che khuất nhau.
    + Khi che khuất nhau, giả sử A bị B che khuất, thì để đóng đc A ta bắt buộc phải đóng B trước đã.
    + quan hệ che khuất là 1 chiều, nghĩa là ko thể có A che khuất B và B cũng che khuất A đc.
    + nếu A bị B che khuất thì chắc chắn B phải mở sau A.
    + nếu A1 bị che khuất bởi A2 bị che khuất bởi A3 ...... bị che khuất bởi An thì ko thể có chuyện An bị che khuất bởi A1 đc (ko thể che khuất vòng tròn xảy ra đc)
    Như vậy để đóng đc A, ta bắt buộc phải đóng đc tất cả các cửa sổ che khuất A trước, và để đóng đc các cửa sổ che khuất A này, ta lại phải xét đến các cửa sổ che khuất các cửa sổ này, để đóng chúng, cứ như thế.

    Trước hết ta phải biểu diễn đc mối quan hệ này khi cho N cửa sổ cho trước. Thông thường phù hợp nhất là sử dụng đồ thị, ở đây là đồ thị có hướng. B che khuất A thì có 1 cạnh có hướng từ B đến A.
    Trước hết, bạn đọc dữ liệu từ file vào, dữ liệu như trên thì lưu trữ = 1 mảng 100 x 4 là phù hợp. N là số phần tử của mảng, thứ tự trong mảng cũng chính là thứ tự cửa sổ như trong file.
    Sau đó bạn biểu diễn mối quan hệ giữa các cửa sổ với nhau = đồ thị, như trên thì dùng ma trận (mảng 2 chiều) 100 x 100 là đc trong đó a[i, j] = 0 nếu cửa sổ i và j ko che khuất nhau và = 1 nếu i che khuất j (1 chiều), chú ý là a[i, j] = 1 thì a[j, i] = 0 vì i che khuất j thì j ko che khuất i đc (do chỉ 1 chiều thôi). N x N là kích thước mảng này. (N <= 100). Để biểu diễn như này thì bạn xét lần lượt quan hệ giữa 2 phần tử trong mảng dữ liệu trên, rồi gán kết quả vào mảng đồ thị.
    Như vậy là xong phần biểu diễn dữ liệu. Đến phần thuật toán. Thuật toán tức là ta phải mô tả cách làm là ntn. có thể có nhiều cách làm, nhưng cách làm nào bao jờ cũng phụ thuộc vào đặc điểm của dữ liệu. Tôi mô tả 1 cách làm như sau: Ta sẽ xét lần lượt từ cửa sổ lớn nhất đến nhỏ nhất, hay đỉnh lơn nhất N đến đỉnh nhỏ nhất 2 (1 là đỉnh đầu tiên, cửa sổ đầu tiên). Với mỗi đỉnh đc xét, ta tìm xem có tồn tại đường đi đến đỉnh 1 hay ko, nếu có thì ta xóa (gán lại = 0, cũng đồng nghĩa với đóng cửa sổ này hay là 1 lần click chuột) tất cả các cạnh từ đỉnh này, rồi ghi lại (tăng) số đếm lên 1 nữa. Để tìm đường đi đến đỉnh 1, bạn phải tìm đc đi đến tất cả các đỉnh kề với N trước, rồi lại tìm đường đi đến tất cả các đỉnh kề với đỉnh này, cứ như thế, như vậy phù hợp nhất là bạn dùng thuật toán kiểu đệ quy (quay lui chẳng hạn), khi tìm đc đỉnh 1 thì dừng lại, nếu ko tìm đc thì ta lại xét tiếp đỉnh N-1. cứ thế.
    Cuối cùng ghi ra file số đếm (cộng thêm với 1) là số click chuột ít nhất để đóng cửa sổ 1.
     
    ngô trang thích bài này.
  4. ngô trang

    ngô trang Học sinh chăm học Thành viên

    Bài viết:
    12
    Điểm thành tích:
    71
    Nơi ở:
    Hà Nam
    Trường học/Cơ quan:
    trung học phổ thông chuyên biên hòa

    cảm ơn anh nhiều ạ !!!
     
  5. ngô trang

    ngô trang Học sinh chăm học Thành viên

    Bài viết:
    12
    Điểm thành tích:
    71
    Nơi ở:
    Hà Nam
    Trường học/Cơ quan:
    trung học phổ thông chuyên biên hòa

     

    Các file đính kèm:

Chú ý: Trả lời bài viết tuân thủ NỘI QUY. Xin cảm ơn!

Draft saved Draft deleted

CHIA SẺ TRANG NÀY

-->