Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Xây dựng giải thuật cho bài toán sắp xếp các Pentomino

  1. #1
    Ngày gia nhập
    02 2010
    Bài viết
    3

    Mặc định Xây dựng giải thuật cho bài toán sắp xếp các Pentomino

    Đề bài:
    Mỗi Pentomino được tạo thành từ 5 ô vuông bằng cách sắp xếp 5 ô vuông đó theo các cách khác nhau. Có tất cả 12 loại Pentomino (không tính các Pentomino đồng dạng nhờ phép quay và đối xứng từ các Pentomino có sẵn), như sau:

    Cho 1 hình chữ nhật kích thước 6x10. Sắp xếp 12 Pentomino kể trên vào trong hình chữ nhật này. Ví dụ:

    Hỏi có bao nhiêu cách sắp xếp các Pentomino vào hình chữ nhật đó.
    Các bạn góp ý cho mình về giải thuật bài này với. Mình nghĩ mãi ko ra.

  2. #2
    Ngày gia nhập
    02 2010
    Bài viết
    3

    Vẫn bó tay. Không có ai giúp à T_T

  3. #3
    Ngày gia nhập
    10 2008
    Bài viết
    54

    Có tất cả 12 loại Pentamino,nhưng do tính đ ối xứng của các h ình, khi xoay, lật... 12 hinh trên ta đư ợc tổng cộng
    63 hình khác nhau .Cách lưu trữ các hình này trên máy tính nh ư sau :
    Lấy ô ở trên cùng,bên trái làm chuẩn, 4 ô còn lại, mỗi ô là một struct gồm 2 giá trị dx,dy là số gia tọa độ so với ô đầu ti ên.
    Như vậy, mỗi pentamino là một struct gồm 4 ô,(ô đầu tiên không cần lưu) và một
    trường địa chỉ trỏ đến pentamono tiếp theo. Mỗi loại pentamino đ ược xem như một danh sách liên kết, gồm các hình cùng dạng nhung được xoay theo các hướng khác nhau. Tất cả những loại pentamino đ ược lưu trữ trong file penta.dat.Nội dung file nh ư sau :

    Code:
    8 P	
    0 1 1 0 1 1 2 0
    0 1 1 0 1 1 1 2
    1 -1 1 0 2 -1 2 0
    0 1 0 2 1 1 1 2
    0 1 1 0 1 1 2 1
    0 1 0 2 1 0 1 1
    1 0 1 1 2 0 2 1
    0 1 1 -1 1 0 1 1
    8 F
    0 1 1 -1 1 0 2 0
    1 0 1 1 1 2 2 1
    1 0 1 1 2 -1 2 0
    1 -1 1 0 1 1 2 1
    0 1 1 1 1 2 2 1
    1 -1 1 0 1 1 2 -1
    1 -1 1 0 2 0 2 1
    1 -2 1 -1 1 0 2 -1
    8 N
    0 1 1 1 1 2 1 3
    1 0 2 0 2 -1 3 -1
    0 1 0 2 1 2 1 3
    1 0 1 -1 2 -1 3 -1
    0 1 0 2 1 -1 1 0
    1 0 2 0 2 1 3 1
    0 1 1 0 1 -1 1 -2
    1 0 1 1 2 1 3 1
    8 L
    1 0 2 0 3 0 3 1
    1 -3 1 -2 1 -1 1 0
    0 1 1 1 2 1 3 1
    0 1 0 2 0 3 1 0
    1 0 2 0 3 0 3 -1
    0 1 0 2 0 3 1 3
    0 1 1 0 2 0 3 0
    1 0 1 1 1 2 1 3
    8 Y
    1 -1 1 0 1 1 1 2
    1 0 2 0 3 0 2 -1
    0 1 0 2 0 3 1 2
    1 0 1 1 2 0 3 0
    0 1 0 2 0 3 1 1
    1 0 2 0 3 0 2 1
    1 -2 1 -1 1 0 1 1
    1 -1 1 0 2 0 3 0
    4 W
    1 0 1 1 2 1 2 2
    1 -1 1 0 2 -2 2 -1
    0 1 1 1 1 2 2 2
    0 1 1 -1 1 0 2 -1
    4 Z
    0 1 1 1 2 1 2 2
    1 -2 1 -1 1 0 2 -2
    0 1 1 0 2 0 2 -1
    1 0 1 1 1 2 2 2
    4 T
    0 1 0 2 1 1 2 1
    1 0 1 1 1 2 2 0
    1 0 2 -1 2 0 2 1
    1 -2 1 -1 1 0 2 0
    4 V
    0 1 0 2 1 0 2 0
    1 0 2 0 2 1 2 2
    1 0 2 0 2 -1 2 -2
    0 1 0 2 1 2 2 2
    4 U
    1 0 1 1 1 2 0 2
    0 1 1 1 2 0 2 1
    0 1 0 2 1 0 1 2
    0 1 1 0 2 0 2 1
    2 I
    0 1 0 2 0 3 0 4
    1 0 2 0 3 0 4 0
    1 X
    1 -1 1 0 1 1 2 0
    Bạn tham khảo thêm link này nhé:
    http://diendan.congdongcviet.com/showthread.php?t=12105
    Đã được chỉnh sửa lần cuối bởi bachhaiduong : 28-09-2011 lúc 02:31 PM. Lý do: Bổ sung

  4. #4
    Ngày gia nhập
    02 2010
    Bài viết
    3

    Bài này mình đã xem từ lâu nhưng vẫn ko nghĩ ra cách giải quyết bài toán.

Các đề tài tương tự

  1. Giải thuật shaker sort. Giúp mình giải thuật với?
    Gửi bởi nguyenhai trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 29-01-2015, 10:53 PM
  2. Giải thuật Giải thuật Chia để trị, hướng đi với giải thuật này thế nào?
    Gửi bởi maivivan13 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 23-10-2012, 10:22 PM
  3. Bài tập C Cần giải giúp 3 câu trong đề thi kĩ thuật lập trình C và Cấu trúc dữ liệu và giải thuật
    Gửi bởi nguyenthi0602 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2012, 08:42 PM
  4. Giải thuật xắp xếp Quick sort, biểu diễn bằng hình ảnh giải thuật này?
    Gửi bởi yuklong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 9
    Bài viết cuối: 09-06-2012, 09:20 AM
  5. Tài liệu về giải thuật mã hóa. Mã hóa file theo giải thuật DES. Ai có giúp mình?
    Gửi bởi daolong83 trong diễn đàn Công cụ, ebooks C#, ASP.NET, và Windows Mobile
    Trả lời: 6
    Bài viết cuối: 17-07-2009, 11:28 PM

Quyền hạn của bạn

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