Mỗi ngày tôi đấu tranh với các câu hỏi về thuật toán và cố gắng hỏi tại đây mà tôi không thể trả lời. Xin lỗi, nếu tôi gây đau đầu. Dù sao,Bạn có thể tạo hình chữ nhật 3xn với hình chữ nhật 2x1 bằng cách nào?
Đây là số problem từ Cuộc thi lập trình ACM của Đại học Waterloo.
Bạn có thể tạo hình chữ nhật 3xn bằng hình chữ nhật 2x1 bằng cách nào?
Nirvana: mùi như đệ quy tinh thần
Bạn có thể giải quyết điều này bằng cách sử dụng quy hoạch động. Kiểm tra this để có giải pháp khả thi.
Chỉ cần một giải pháp rõ ràng để các phương trình trao ngầm trong câu trả lời của taskinoor:
Hoặc
f[n]=((1 + (-1)^n)*((2 - Sqrt[3])^(n/2)*(-1 + Sqrt[3]) +
(1 + Sqrt[3])* (2 + Sqrt[3])^(n/2)))/(4*Sqrt[3])
nếu có ai quan tâm.
Hãy hiển thị 10 giá trị (ví lẻ n không có giải pháp) {n, f [n]}:
{6, 41.},
{12, 2131.},
{18, 110771.},
{24, 5.75796*10^6},
{30, 2.99303*10^8},
{36, 1.5558*10^10},
{42, 8.08717*10^11},
{48, 4.20377*10^13},
{54, 2.18515*10^15},
{60, 1.13586*10^17}
Tôi thực sự không bao giờ cố gắng để tạo thành một hình thức rõ ràng. 1 cho điều này. – taskinoor
+1. thực sự bối rối chấp nhận câu trả lời đúng :). cảm ơn cả hai bạn –
@taskinoor Nó có sự tương đồng kỳ lạ về dạng Fibonacci rõ ràng http://upload.wikimedia.org/math/a/f/9/af9b6b5e3dea6654db4794bd066dd433.png –
Chỉ cần một lưu ý về cách để có được công thức giải pháp rõ ràng, các trick là viết nó xuống lặp lại như phép nhân ma trận, và sau đó sử dụng công thức eigenvalue cho n công suất thứ của ma trận. Đối với đệ quy trên, phương trình là
(không có)
Bạn có thể thấy bốn giá trị riêng hiển thị trong công thức rõ ràng những Belisarius
+1: Và nếu bạn chỉ đang tìm kiếm một thuật toán, chỉ cần tính toán các quyền hạn của ma trận trong thời gian O (logn), có lợi thế là chỉ sử dụng số nguyên số học. –
hình ảnh bị thiếu. – taskinoor
vào liên kết đề cập không hoạt động –
@hitesh_noty liên kết đã chết . Tôi đã viết câu trả lời này một thời gian dài trước đây khi tôi không hiểu vấn đề này với liên kết chỉ trả lời. Tôi đã tìm thấy một giải thích khác tại đây: http://cs.stackexchange.com/questions/42170/why-do-these-recurrences-determine-the-number-of-ways-of-tiling-a-3xn-rectangle nhưng trung thực , Tôi cần chỉnh sửa câu trả lời này để thêm giải thích tại đây để nó không phụ thuộc vào liên kết khác. – taskinoor