Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Chó soi và cừu non ^^

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Chó soi và cừu non ^^   Sun 21 Mar 2010, 20:43

Giống như cái đề vậy, bài này liên quan đến sói và cừu.

Ông chủ chăn cừu nọ có một cách đồng để nuôi cừu. Cách đồng gồm nhiều ô nhỏ (mô phỏng mảng hai chiều ^^), mỗi ô này có thể có một con cừu đứng ở đó, một đống gai (để xếp tạo thành hàng rào) hoặc không có gì cả. Một hôm, ông chủ đi vắng, một bầy sói nọ đã đột nhập vào cách đồng bằng một cách không rõ nào đó. Vì cánh đồng có hàng rào chắn nên có thể được chia thành nhiều miền khác nhau. Trong mỗi miền đều có thể bị sói đột nhập.

a) Hãy xác định xem sói đã đột nhập vào mấy miền. (dễ ^^)
b) Trong mỗi miền, nếu số cừu ít hơn hoặc bằng số sói thì toàn bộ cừu sẽ bị ăn thịt sạch, ngược lại, nếu số cưu nhiều hơn thì chúng sẽ không bị ăn thịt. Hãy đếm xem có bao nhiêu con cừu bị ăn thịt.
c) Thực ra "cách không rõ nào đó" đã giúp các con sói đã đột nhập vào cách đòng là do một người xấu đặt vào (giả sử thế đi laughing ). Người xấu này rất ghét ông chủ chăn cừu. Hãy tính xem số lượng cừu tối đa có thể bị giết chết bởi m con sói.

Dữ liệu vào của a và b:

File soivacuu.inp gồm một bản đồ dấu, dấu '.' tương trưng cho ko có gì cả, dấu '*' tượng trưng cho ô có rào gai, kí tự 'c' cho ô có cừu, kí tự 's' cho ô có sói. Lưu ý, mỗi ô trên cánh đồng chỉ được phép chứa một thứ duy nhất là rào gai, sói, cừu hoặc không có gì cả.

Dữ liệu ra đối với a và b là file soivacuu.out. Nếu câu a thì ghi 1 dòng duy nhất là số miền bị sói đột nhập. Nếu là câu b thì ghi 1 dòng duy nhất là một số biểu thị số cừu bị ăn thịt.

Dữ liệu vào của câu c là file batcuu.inp dồm một bản đồ dấu: dấu '.' nếu là ô trống, kí tự 'c' nếu chứa cừu, dấu '*' nếu chứa rào gai.

Dữ liệu ra của câu c là file batcuu.out ghi 1 dòng biểu thị số cừu tối đa có thể bị ăn thịt.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Chó soi và cừu non ^^   Sun 21 Mar 2010, 21:16

Ví dụ nhé, câu a và b thôi.

Ví dụ với bản đồ 10*15 sau:



Thì bản đồ sẽ có 8 miền.

có 5 miền bị sói đột nhập và trong đó có 9 con cừu bị ăn thịt.
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Chó soi và cừu non ^^   Mon 22 Mar 2010, 21:48

Bạn thường có một thói quen không giới hạn dữ liệu. Theo mình thì thói quen đó là không tốt. Vì một bài toán cái quan trọng nhất là giới hạn dữ liệu. Nó làm ảnh hưởng đến ý tưởng để giải 1 bài toán.

Ví dụ như thế này:
Đối với bài toán sắp xếp các số nguyên:
- Nếu số liệu nhỏ thôi (n< 10000) thì ta sẽ dùng 2 vòng for giải cho nó dễ
- Nếu số liệu lớn hơn một chút (10000< n < 10^7) ta phải dùng đến quick sort
- Nếu số liệu rất lớn ( 10^7 <n < 3*10^8) thì ta phải dùng đến phép thống kê.

Nói tóm lại bạn nên cho giới hạn dữ liệu ở mỗi bài toán.

Đối với bài ở trên nếu dữ liệu nhỏ thôi thì dùng 3 vòng for là đơn giản nhất. Ok
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Chó soi và cừu non ^^   Mon 22 Mar 2010, 21:57

mình và lit mới học lớp 9 nên cũng chưa rõ lắm về giới hạn dữ liệu và cách tính thời gian chạy chương trình. [You must be registered and logged in to see this link.] có thể chỉ cho em dc ko?


Được sửa bởi hoangtin14 ngày Tue 23 Mar 2010, 21:32; sửa lần 1.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Chó soi và cừu non ^^   Tue 23 Mar 2010, 11:48

Ad có thể chỉ littlelee về phép thống kê được ko. Littlelee chưa bao giờ nghe nói đến thuật toán này cả.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Chó soi và cừu non ^^   Today at 05:17

Về Đầu Trang Go down
 
Chó soi và cừu non ^^
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến