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

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

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.

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]

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

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.

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

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

#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 =)

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 =)

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

Ideone.com

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

Đá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.

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

g là hàm chứa tất cả các cách lát thì ta có:
g=f+1

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

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

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

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

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

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é

[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

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

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

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)

Bạn đọc sai đề rồi bạn.