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 | 
 

 Dãy a và b đặc biệt

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 đề: Dãy a và b đặc biệt   Thu 18 Mar 2010, 13:25

Có hai dãy số: a và b rất đặc biệt. Dãy a là một hoán vị của 1;2;3;..;n và dãy b được tính theo dãy a như sau: phần tử b[i] bằng số lượng các phần tử đứng trước i trong a và lớn hơn i.

Ví dụ dãy a là 3 4 2 5 1 6 thì dãy b là 4 2 0 0 0 0 . Giải thích: xét với i=1, với quy luật trên đề bài thì phần tử b[i] bằng số lượng các phần tử đứng trước số 1 trong dãy a mà lớn hơn 1. Trong dãy a, có các số 3 4 2 5 đứng trước số 1, trong đó tất cả chúng đều lớn hơn 1. Vậy b[1]=4. Tương tự với các b[2],b[3]...

a) Cho dãy a, hãy tính và xuất ra dãy b.
b) Cho dãy b, hãy tính và xuất ra dãy a.
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: Dãy a và b đặc biệt   Thu 18 Mar 2010, 18:47

Bài này littlelee nên nói rõ giới hạn dữ liệu. Nếu n nhỏ thôi thì bài này không có gì để giải, còn nếu n >10^5 thì bài này trở nên khủng khiếp.
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: Dãy a và b đặc biệt   Fri 19 Mar 2010, 13:24

Hì hì. Thật ra đây chỉ là bài nho nhỏ thôi. Bài dành cho lớp 9 cơ mà.

Mình post bài này chủ yếu là để các bạn khác nghĩ ra những cách thú vị, nó nghiêng về sáng tạo. Nếu dùng dữ liệu >=10^5 thì khủng thật. Mà cũng chẳng qua là thuật toán thôi, chứ bê nguyên test 10^5 vô thì chưa chắc chi pascal đã chịu nổi.
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: Dãy a và b đặc biệt   Fri 19 Mar 2010, 13:26

À administrators ơi, bạn chỉ mình cách tính độ phức tạp và cách tính thời gian thực hiện đi. Đối với dữ liệu lớn thì mình chả biết tính ra là nó chạy trong bao lâu cả. Mình đã đọc tài liệu rồi, tuy nhiên nó phức tạp quá, với lại nó có một số kí tự toán học mihnf chưa học nữa. Mình chỉ cần dugnf sơ sơ thôi, nên nếu có cách hiểu nào đơn giản thì bạn giải thích cho mình nhé.


Được sửa bởi littlelee ngày Fri 19 Mar 2010, 13:33; 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: Dãy a và b đặc biệt   Fri 19 Mar 2010, 13:31

Theo cách hiểu hiện giờ của mình, nếu xét theo phép tính tích cực thì nếu nó thuộc 1 vòng lặp thì O(n) còn nếu 2 vòng thì là O(n^2). Thôi cứ tạm hiểu thế đã. Nếu với cách hiểu như thế thì bài này, câu a bỏ qua, câu b sẽ là O(n^2). Thật ra thì cách làm của mình cho bài b cũng không phức tạp lắm đâu. Nó chỉ là vận dụng một tí thôi, so với thời gian chạy câu a thì có lẽ bằng nhau. Mình dùng 2 vòng lặp lồng nhau, không dùng đệ quy gì cả.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Dãy a và b đặc biệt   Today at 18:46

Về Đầu Trang Go down
 
Dãy a và b đặc biệt
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