[S4L-JUN] ĐỀ THI SOLUTIONS FOR LIFE KỲ 08

Solutions for Life kỳ 08

DẪN NHẬP

Wascally Wabbits [1]

Vào năm 1202, Leonardo of Pisa (còn gọi là Fibonacci) xem xét một bài toán liên quan đến sự phát triển của số lượng thỏ trong quần thể. Ông đưa ra một số giả định đơn giản cho việc tính toán như sau:

  • Số lượng thỏ bắt đầu trong tháng đầu tiên với một cặp thỏ sơ sinh.
  • Thỏ đến tuổi sinh sản sau một tháng.
  • Trong bất kỳ tháng nào, mỗi con thỏ trong cặp thỏ ở độ tuổi sinh sản kết đôi với một con thỏ trong độ tuổi sinh sản khác.
  • Đúng một tháng sau khi đôi thỏ giao phối, chúng tạp ra một con thỏ đực và một con thỏ cái.
  • Những con thỏ thì không bao giờ chết hoặc ngừng sinh sản.

Vấn đề Fibonacci đưa ra cho biết số lượng cặp thỏ sau một năm. Chúng ta có thể thấy rằng trong tháng thứ hai, cặp thỏ đầu tiên sẽ đến tuổi sinh sản và qua tháng thứ ba, một cặp thỏ được sinh ra và chúng ta có hai cặp thỏ. Cặp thỏ đầu tiên của chúng ta giao phối một lần nữa. Trong tháng thứ tư, một cặp khác sẽ được sinh ra từ cặp ban đầu và cặp thứ hai sẽ đến độ tuổi trưởng thành và có thể giao phối (với tổng số ba cặp). Sự phát triển số lượng thỏ được minh họa trong hình Figure 1. Sau một năm, số lượng thỏ sẽ đạt đến 144 cặp.

capture

Figure 1. The growth of Fibonacci’s rabbit population for the first six months.

Mặt dù theo giả định của Fibonnaci về sự sống mãi của bầy thỏ có vẻ hơi cường điệu hóa, nhưng mô hình của ông có những ứng dụng thực tế cho việc ính sản trong môi trường tự do động vật ăn thịt. Thỏ châu Âu được du nhập vào châu Úc giữa thế kỷ 19 trong khi đó, châu Úc là nơi không có động vật săn mồi bản địa. Trong vòng 50 năm, những con thỏ này đã loại trừ nhiều loài thực vật đặc hữu trên khắp châu lục dẫn đến sự tuyệt chủng của nhiều loài thực vật và sự thay đổi không thể khôi phục của hệ sinh thái châu Úc, nhiều đồng cỏ bị xói mòn, có những nơi hẻo lánh hầu như không có người sinh sống. Trong vấn đề này, chúng ta sẽ sử dụng ý tưởng đơn giản đếm số lượng thỏ để cho ra một chủ đề tính toán mới mà có thể xây dựng các giải pháp lớn từ những phần nhỏ.

PROBLEM

  • Một trình tự là một tập các đối tượng có thứ tự (thường là số), mà cho phép lặp. Các trình tự này có thể hữu hạn hoặc vô hạn. Hai ví dụ về chuỗi hữu hạn (π2–√0π) và chuỗi vô hạn số lẻ (1, 3, 5, 7, …). Chúng ta sử dụng ký hiệu an để biểu diễn giới hạn thứ n của trình tự.
  • Một quan hệ lặp là một cách xác định giới hạn của trình tự mong muốn tới giá trị trước đó. Trong trường hợp về các chú thỏ Fibonacci giới thiệu bên trên, với bất kỳ tháng nào định trước sẽ chứa một số thỏ thuộc về tháng trước cộng thêm số thỏ mới được sinh ra. Một chú ý quan trọng là số thỏ được sinh ra trong bất kỳ tháng nào bằng với số thỏ sống ở hau tháng trước đó. Kết quả, nếu Fn biểu diễn số cặp thỏ sau n tháng, sau đó, chúng ta chứa một trình tự Fibonacci với giới hạn Fn được xác định trong mối quan hệ lặp F(n) = F(n-1) + F(n-2) với F1 = F2 = 1 để khởi tạo trình tự. Mặc dù, trình tự mang tên Fibonacci, nó đã được biết bởi các nhà toán học người Ấn Độ cách đây hai ngàn năm.
  • Chúng ta xác định giới hạn n của trình tự xác định bởi quan hệ lặp, chúng ta có thể sử dụng đơn giản quan hệ lặp để phát sinh giới hạn với giá trị lớn dần của n. Vấn đề này giới thiệu cho chúng ta kỹ thuật tính toán với lập trình động mà được xây dựng để giải quyết câu trả lời cho trường hợp số nhỏ.

CHO: Số nguyên dương  n ≤ và ≤ 5 .

KẾT QUẢ: Tổng số cặp thỏ có được sau n tháng, nếu chúng ta bắt đầu với một cặp thỏ và trong mỗi thế hệ, mỗi cặp thỏ sinh sản sẽ sản sinh ra k cặp thỏ (thay vì 1 cặp).

  • Hãy viết chương trình cho phép đọc tập tin văn bản có tên rosalind_fib.txt chứa hai số n và k.
  • Yêu cầu: Xuất ra số cặp thỏ sau n tháng. Sau đó ghi kết quả ra file có tên rosalind_fib_result.txt

DỮ LIỆU MẪU

5 3

KẾT QUẢ MẪU

19

CÁCH THỨC THAM GIA

Nén source-code là project chương trình kèm theo file hướng dẫn thành tập tin nén có tên theo định dạng sau:
[problem08]_<MSSV>_<HọTên>

Ví dụ: [problem08]_0912218_NguyenVanA.rar sau đó xoá phần mở rộng của tập tin thành [problem08]_0912218_NguyenVanA

CẤU TRÚC THƯ MỤC NÉN

  • Thư mục nộp chứa các thư mục con như sau:
  • Source: chứa project xây dựng chương trình (đảm bảo chạy được không báo lỗi).
  • Refs: chứa tài liệu tham khảo (nếu có).
  • Data: chứa bộ dữ liệu chạy chương trình và tập tin kết quả. ·
  • Problem: chứa file *.exe thực thi chương trình. ·
  • readme.docx: file hướng dẫn thực thi chương trình.

Gởi file về địa chỉ email theo cấu trúc sau: ·

    Get the best Vantin deals at our online store today! Take a look at our offers and buy your Vantin for only 2.32 USD!
  • Tiêu đề: [PROBLEM08_JUN] MSSV_Họ_Tên. Ví dụ: [PROBLEM08_JUN] 0912218_NguyenVanA
  • Nội dung: bắt buộc ghi rõ HỌ TÊN, SỐ ĐIỆN THOẠI để ban tổ chức liên hệ nhận thưởng. Ngoài ra, các bạn học sinh – sinh viên đang theo học trường CĐKT Cao Thắng vui lòng cung cấp thêm thông tin về LỚP, MÃ SỐ SINH VIÊN để có thể xét những quyền lợi liên quan. ·
  • File [problem08]_<MSSV>_<HọTên> đính kèm.

* Những bạn trường ngoài không có mã số sinh viên có thể bỏ trống thông tin MSSV.

Những phần quà may mắn sẽ dành cho các bạn tham gia khi có chương trình chạy đúng các bộ dữ liệu test mà Ban Tổ Chức đưa ra. Chương trình tham dự vui lòng gởi file về địa chỉ:

s4l.ckcit@gmail.com

Deadline: 23h55 – thứ 4, ngày 07/12/2016

[1] http://rosalind.info/problems/fib/

#rosalind #fibonacci #gene #ckcit #solutionsforlife #s4l #problem08

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>