Xin ý tưởng - Bài toán lát gạch

#1

Em có 1 bài toán mong mọi người đóng góp ý tưởng.
Cho 1 đường đi kích thước 2 x N.
Người ta dùng 2 loại gạch: 1x2 và 2x2.
Tính tất cả cách lát phù hợp.
Gạch 1x2 có thể xoay chiều.
Mong mọi người giúp đỡ

Xuất hiện trang web clone DNH
#2

Từ f(N) suy ra f(N+1) xem sao.

2 Likes
#3

Từ f(n-1) -> f(n): có thêm bao nhiêu cách xếp?
Từ f(n-2) -> f(n): có thêm bao nhiêu cách xếp?

Vẽ hình ra.

1 Like
#4

gọi f là hàm tính cách lát mà chứa ít nhất 1 hình 2x2 hoặc 2 hình 1x2 nằm ngang, g là hàm chứa tất cả các cách lát thì ta có:
g=f+1
f[0]=0;
f[1]=0;
f[2]=2;
Giờ xét với n>3, thì sẽ xét vị trí của ô 2x2 đầu tiên rồi cho chạy từ đầu đến cuối dãy, 1 ô2x2 lại tương đương với 2 ô 1x2 nên ta có:
f[n]=2(f[n-2]+1)+…+2(f[0]+1))
=2(f[n-2]+…+f[0]+n-1)
PS: cái f[n-2]+1 có thể thay là g[n-2]

#5

Công thức có vẻ không đúng lắm.

#6

Với mỗi đoạn 1x2 có 1 cách lát : 1 viên 1x2 nằm dọc.
Với mỗi đoạn 2x2 có 2 cách lát: 1 viên 2x2 hoặc 2 viên 1x2 nằm ngang (Lưu ý cách lát 2 viên 1x2 nằm dọc được tính là 2 đoạn 1x2 ở trên nên không tính ở đây)

Có bao nhiêu cách chia khối ban đầu thành các đoạn 2x2 và 1x2?
Với mỗi cách chia thành 2x2, sẽ có 2 cách lát đường, vậy có tất cả bao nhiêu cách lát đường?

Bài này chỉ là công thức, không cần lập trình.

1 Like
#7

công thức của mình ko đúng chỗ nào ?

#8

Bạn code đi rồi đưa ra kết quả f(n) với n = 1 -> 10.

#9 
#include <iostream>
using namespace std;

int main()
{
	int F[11];
	F[0]=0;
	F[1]=0;
	F[2]=2;
	for(int i=3;i<10;i++){
	int temp=0;
	for(int j=0;j<i-1;j++){
		temp+=2*F[j];
	}
	F[i]=temp+2*i-2;	
	}
	for(int i=0; i<10;i++){
		printf("\n%d %d",i,F[i]);
	}
}

mà quan trọng là nhìn thuật toán đúng hay ko, chứ code ra rồi thì cũng ai rảnh đi ngồi vẽ ra đếm lại để check đâu =)

#10

Vì mình biết đáp số nên mình mới bảo bạn check mà =)))

Đáp số của bạn đã sai. Chia buồn với bạn.

Ngay từ đầu bạn đã sai. F[1] = 1 mới đúng. Kể cả sửa lại F[1] thì kết quả vẫn sai.

#12

gọi f là hàm tính cách lát mà chứa ít nhất 1 hình 2x2 hoặc 2 hình 1x2 nằm ngang
g là hàm chứa tất cả các cách lát thì ta có:
g=f+1

#13

Không thể như vậy được. Bạn chứng minh đi.

#14

xét k=g-f thì k sẽ chứa những cách lát ko có ô 2x2 hoặc 1x2 nằm ngang nào, thế nên k chỉ chứa 1x2 nằm dọc=>k=1

#16

bạn nên đọc lại code để hiểu cách tính fn của mình

#17

Sai sai cả công thức truy hồi vẫn phần khởi tạo rồi. N bằng 1 có 1 cách lát là dùng 1 viên 1x2, với N bằng 2 thì có 3 cách. Ngay cả trường hợp N bằng 0 thì vẫn có 1 cách đó là không dùng viên nào :v hơi phi lý nhưng thực tế là vậy :v

#18

gọi f là hàm tính cách lát mà chứa ít nhất 1 hình 2x2 hoặc 2 hình 1x2 nằm ngang, g là hàm chứa tất cả các cách lát thì ta có:
g=f+1
đọc lại f của mình là gì đã nhé :wink:

#19

[spoiler]Số cách Nx2 = 2 * số cách của (N-2)x2 + (số cách của (N-1)x2 - số cách của (N-2)x2).[/spoiler]
Phải xét tới N-2 :slight_smile:

1 Like
#20

Chết, em xin lỗi :v :v

#21

Bạn có link bài này không bạn?

#22

nó là dãy fibonaci ấy, bắt đầu từ 1 2 3 5 …
với kích thước n*2 ta có thể thực hiện 2 cách
1.
lát 1 viên dọc, chiều dài còn lại là n-1 thì có f(n-1) cách lát
2.
lát 2 viên ngang, chiều dài còn lại là f(n-2)
như vậy với chiều dài là n thì sẽ có tổng số cách lát của 2 trường hợp trên
f(n) = f(n-1) + f(n-2)

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?