Trang 1 / 2 12 LastLast
Hiển thị kết quả từ 1 đến 10 / 12
  1. #1
    Tham gia
    16-06-2003
    Location
    Da Nang
    Bài viết
    47
    Like
    0
    Thanked 0 Times in 0 Posts

    tính chu vi của n hình chữ nhật

    cho n hình chữ nhật.Tính chu vi của các hình chữ nhật đó

    Đây vốn là bài thi olympic lớp11,nhưng đọc lời giải ko hiểu chi cả
    Quote Quote

  2. #2
    Tham gia
    12-08-2003
    Bài viết
    678
    Like
    0
    Thanked 1 Time in 1 Post
    Bạn cần tính chi vi ngoài và chu vi trong. Xin hỏi thêm kích thước dữ liệu của bào toán (quan trọng lắm đấy).

  3. #3
    Tham gia
    19-07-2003
    Location
    Biên Hòa
    Bài viết
    499
    Like
    0
    Thanked 1 Time in 1 Post
    Phải nói rõ ràng chứ, đề cho thiếu dữ liệu.
    Thi 30/4 hả?

  4. #4
    Tham gia
    12-08-2003
    Bài viết
    678
    Like
    0
    Thanked 1 Time in 1 Post
    Phải rồi. Nếu tôi đoán không lầm thì tọa độ mỗi hình chữ nhật là nguyên có giá trị tuyệt đối bé hơn 10 000. Các cạnh của hcn song song với các trục tọa độ phải không?

  5. #5
    Tham gia
    19-07-2003
    Location
    Biên Hòa
    Bài viết
    499
    Like
    0
    Thanked 1 Time in 1 Post
    Đề vậy được đó, nhưng còn gì thêm không? n là số bất kì, và tìm max hả?

  6. #6
    Tham gia
    16-06-2003
    Location
    Da Nang
    Bài viết
    47
    Like
    0
    Thanked 0 Times in 0 Posts
    input
    -n(số hình chữ nhật)
    -n+1 dòng tiếp theo ghi tọa độ 2 đỉnh chéo nhau
    output
    -chu vi đa giác tìm được

  7. #7
    Tham gia
    19-07-2003
    Location
    Biên Hòa
    Bài viết
    499
    Like
    0
    Thanked 1 Time in 1 Post
    Vậy mà lúc trước tui tưởng thi 30/4 môn Toán chứ.
    Bài đó tui nghĩ ra cách giải này, n cỡ vài ngàn chắc chạy tốt. Nhưng với điều kiện tọa độ nguyên. Nếu ko phải sửa một ít
    - Tìm tổng chu vi các hình chữ nhật
    - Xét từng đoạn của mỗi cạnh của từng hình:
    + nếu nó nằm trong một hình nào đó thì trừ đi
    + nếu nó trùng một cạnh khác, thì đánh dấu đoạn đó để sau này trừ đi
    + nếu bị đánh dấu đã tính, thì trừ đi
    + nếu không, thì tiếp tục

    Không biết còn trường hợp nào nữa ko?

  8. #8
    Tham gia
    16-06-2003
    Location
    Da Nang
    Bài viết
    47
    Like
    0
    Thanked 0 Times in 0 Posts
    nếu tính theo cách của bạn thì độ phức tạp của bài toán là
    4*n*(4*n+n)=20*n*n
    n khoảng vài ngàn chạy có vẻ ko tốt đâu!!!

  9. #9
    Tham gia
    19-07-2003
    Location
    Biên Hòa
    Bài viết
    499
    Like
    0
    Thanked 1 Time in 1 Post
    độ phức tạp đa thức, và các phép tính chỉ là cộng trừ số nguyên. Không tồi đâu. Điều quan trọng là ko biết đã hết trường hợp chưa.

  10. #10
    Tham gia
    12-08-2003
    Bài viết
    678
    Like
    0
    Thanked 1 Time in 1 Post
    Các bạn phải chú ý tới kích thước của bài toán chứ. Nếu chỉ có tọa độ nguyên dương và chỉ khoảng <=10000 thì dùng mảng dấu gồm 0..10000 phần tử để làm. Nhưng theo tôi nghĩ, bạn nên tập tính diện tích trước rồi hãy tính chu vi vì nó khó lắm. Thuật toán nghiên về kỹ thuật lập trình nhiều.

Trang 1 / 2 12 LastLast

Bookmarks

Quy định

  • Bạn không thể tạo chủ đề mới
  • Bạn không thể trả lời bài viết
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
  •