Diễn đàn Trung học Phổ Thông

CHÚ Ý : Các thành viên tham gia Diễn đàn Trung học Phổ Thông cần đọc kĩ cách đặt tiêu đề,cách gõ $\LaTeX$ đúng quy định.

You are not connected. Please login or register

 
 

Lát gạch ( Thuật toán tìm công thức truy hồi )

Thông điệp (Trang 1 trong tổng số 1 trang)

#1

Bờ|☼|Lâu

Bờ|☼|Lâu
 
Tổng Tư Lệnh
Tổng Tư Lệnh

Posted Wed Oct 07, 2015 10:47 am

 

Cho một hình chữ nhật kích thước 2xN (1<=N<=100). Hãy đếm số cách lát các viên gạch nhỏ kích thước 1x2 và 2x1 vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.

Input:
Gồm nhiều test, dòng đầu ghi số lượng test T ( T<=100 ).
T dòng sau mỗi dòng ghi một số N.

Output:
Ghi ra T dòng là số cách lát tương ứng.

Example:
Input:                       Output:
  3                                1
  1                                2
  2                                3
  3



   

#2

PháĐảoThếGiớiẢo

PháĐảoThếGiớiẢo
 
Thành viên mới
Thành viên mới

Posted Thu Oct 08, 2015 9:02 am

 

+ Bước 1 : Nếu $N=0\Rightarrow$ không có hình chữ nhật $\Rightarrow$ có 1 cách xếp là không cho viên gạch nào vào.
+ Bước 2 : Ta có công thức truy hồi sẽ có dạng : $F(n)=x.F(n-1)+y.F(n-2)$
                Dựa vào Output, thay $n$, ta có hệ :$\left\{\begin{matrix}2=x+y \\ 3=2x+y \end{matrix}\right.$
+ Bước 3 : Giải hệ $\Rightarrow$ $x=y=1$
$\Rightarrow$ Công thức truy hồi $F(n)=F(n-1)+F(n-2)$
+ Bước 4 : Viết chương trình :
Lệnh gán kết quả  F[0]:=1;
                           F[1]:=1;
                           F[2]:=2;
                           F[3]:=3;
                           For i:=4 to 100 do F[i]:=F[i-1]+F[i-2];
:?: :?: :?: :?: :?:

Thông điệp (Trang 1 trong tổng số 1 trang)


  • Total Posts:
  • Total Members:
  • Newest Member:
  • Most Online: Số người truy cập cùng lúc nhiều nhất là 61 người, vào ngày Sat Jul 29, 2017 12:27 pm

Hiện có 0 người đang truy cập Diễn Đàn, gồm: 0 Thành viên, 0 Thành viên ẩn danh và 0 Khách viếng thăm
Đang truy cập Diễn Đàn này: Không