Bài toán Lát Gạch và Fibonanci và BigInteger

Bài toán gốc nằm ở đây: http://vn.spoj.com/problems/LATGACH/

Nguyên văn đầu bài như sau:

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.


Sau khi ngồi ngâm cứu cùng anh em,... mình phát hiện ra bài toán này có bộ input và output là vị trí và kết quả tương ứng của dãy fibonanci... 

kết quả test ban đầu như sau:

N:   1    2   3   4   6   7
KQ: 1   2   3   5   8   13

mấy anh em mình chỉ test đến 7 thôi chứ vẽ ra giấy nó hoa hết cả mắt,.. ( mà mình học xác suất ngu lắm,.. chứ không thì đã đi chơi xổ số kiểu mĩ rồi.. :v )

nhìn theo cái dãy kết quả thì nó khá tương đông với dãy fibonanci
1 1 2 3 5 8 13 21 ...

Ok,.. vậy ra nó là chơi với Fibo à.. :3 ( đoán thế,.. chưa accept thì chưa biết thế nào )
Thế là anh em ngồi code vài dòng đệ quy của fibo:


Ơ,.. nhưng để ý tiếp yêu cầu của bài,.... giới hạn về thời gian vậy nên chỉ fibo thôi chưa đủ,.. chứ tính trường hợp xấu nhất xem,.. số test case là 100 và test case là 100... vậy là một anh đề xuất,.. hay là ta khởi tạo một mảng fibo 100 phần tử ban đầu xem!! Ừm nhất chí,.. có xấu xa thế nào thì cũng chỉ phải đệ quy 100 lân đầu.. :v
Riêng mình thì sẽ gắn cờ và chơi lưu vết... là đi đến đâu mới cắm cờ đến đấy ý... như vậy sẽ không nhất thiết phải chạy hết 100 lần fibo..



Yeah..!! Sau khi cơ bản đã ổn thoả,.. Submit thôi,... oh no... báo Wrong các bạn ạ,... vậy là mình thử test trường hợp xấu nhất,... FIBO[100],.. theo trương trình c++ của mình là một số có 20 chứ số,.. tra google thì ra cái list fibo và ôi trời ơi,.. FIBO[101] có độ dài là 22 chữ số,.. vậy nên mình nghĩ ngay tới BigInt,..
Vì đề hiếu hơn về BigInt, mình có google và ra một số bài trên stackoverflow hay cộng đồng C Việt,.. cơ mà mình đọc méo hiểu gì,... nội dung của mấy cái đó đều xoay quanh việc làm sau để phân mảnh dữ liệu thành nhiều phần nhỏ để lưu trữ một biến lớn,... ( chắc tại mình ngu ý mà :3 ),.. cuối cùng mình nghĩ đến xử lí chuỗi,... theo quan điểm của mình thì làm kiểu phân mảnh như mấy bài kia chắc là đẹp nhất, tối ưu nhất và hiệu quả hơn các dùng chuỗi mà mình làm... nhưng đọc mấy cái đấy khó hiểu nên tự làm cái dễ dễ thôi....


Và như trên chính là cách mình áp dụng để làm phép được tính + của kiểu BigInt, sau đó thay long long FIBO thành BigInt FIBO thôi... hehe!!

Và Cuối dùng, sau khi mọi thứ đã hoàn thiện, đây là code mình đã Submit lên và Accept!!



Toàn bộ code: https://gist.github.com/DK189/d9b3682c5300c4a6093191c1c87c9b9f

Trịnh Trọng Trần Bá

Null..

2 nhận xét:

  1. mấy cái code này bạn tự nghĩ ra ạ ? tài thế !

    Trả lờiXóa
    Trả lời
    1. Cài fibonaci thì cũng đơn giản thôi mà!!

      Còn cái cộng 2 số lưu ở chuỗi thì mình mô phỏng theo cách tính tổng hồi cấp 1 ý!!

      Cứ dóng 2 số sao cho hàng đơn vị, hàng chục,... ngang nhau là được!!

      Cái dòng for mình viết chưa dược "đẹp mắt" cho lắm nên khá khó đọc!! mà code cũng không có comment nên nhiều chỗ còn khó hiểu,.. chắc lại phải sửa lại bài này vài lần nữa!! :D

      Xóa