Diễn đàn tin học Nguyễn Văn Linh
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

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

The second house for every one
 
Trang ChínhLatest imagesTìm kiếmĐăng kýĐăng Nhập

 

 Xóa số để tạo thành số nhỏ nhất, lớn nhất.

Go down 
3 posters
Tác giảThông điệp
littlelee
Admin
Admin
littlelee


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

Xóa số để tạo thành số nhỏ nhất, lớn nhất. Empty
Bài gửiTiêu đề: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Xóa số để tạo thành số nhỏ nhất, lớn nhất. I_icon_minitimeFri 19 Mar 2010, 21:20

Cho một số tự nhiên n chữ số a= a1 a2 ... an (ai  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, i = 1, 2, ..., n; (n có thể đạt tới giá trị 1000000). Hãy tìm cách xoá bỏ m chữ số của a, sao cho số thu được sau khi xoá bỏ m chữ số đó là nhỏ nhất.

Dữ liệu: Vào từ file văn bản XOASO.INP có cấu trúc:
- Dòng đầu ghi giá trị m và n cách nhau ít nhất một dấu cách.
- n dòng tiếp theo ghi các chữ số của a theo thứ tự từ trái qua phải.

Kết quả: Ghi ra file XOASO.OUT gồm m dòng, mỗi dòng chứa chữ số bị xoá và chỉ số của nó trong dãy số gốc, được phân cách bởi ít nhất một dấu cách.

Ví dụ: với m=2, n=5, a= 41325 thì file XOASO.INP gồm 6 dòng sau:
2 5
4
1
3
2
5

và file XOASO.OUT gồm hai dòng sau:
4 1
3 3
Về Đầu Trang Go down
littlelee
Admin
Admin
littlelee


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

Xóa số để tạo thành số nhỏ nhất, lớn nhất. Empty
Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Xóa số để tạo thành số nhỏ nhất, lớn nhất. I_icon_minitimeSat 20 Mar 2010, 21:24

Chán quá, chả thấy ai trải lời
Về Đầu Trang Go down
administrators
Gà nhỏ
administrators


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

Xóa số để tạo thành số nhỏ nhất, lớn nhất. Empty
Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Xóa số để tạo thành số nhỏ nhất, lớn nhất. I_icon_minitimeSun 21 Mar 2010, 20:37

Bài cho khó vậy ai mà giải cho được, nên bạn thấy chán là chuyện bình thường.
Vì số liệu cho quá lớn nên muốn giải bài này chạy dưới 1 giây cần đến 2 kỹ thuật cao cấp
- Cơ sở suy luận toán cao cấp
- Cấu trúc cơ sở dữ liệu đặc biệt IT.

Cách làm như sau:

- Trong m+1 số đầu tiên chọn ra số nhỏ nhất. Xóa các số trước đó rồi làm tiếp...

* Ví dụ m=10:
* Ta xét 11 số thì số nhỏ nhất ở vị trí thứ 7. Thì ta sẽ xóa đi 6 số đầu tiên chừa số thứ bảy lại (làm số đứng đầu luôn đấy)
* Sau đó xét tiếp 4+1 (=5) số từ vị trí thứ 8 và chọn ra số nhỏ nhất. Giả sử số nhỏ nhất năm ở vị trí 11 thì ta xóa bỏ hết tất cả các số có vị trí lớn hơn 7 và nhỏ hơn 11. (hiển nhiên là được 3 số). Như vậy ta đã xóa hết 9 số rồi.
* Sau đó xét tiếp 1+1 (=2) số kế tiếp kể từ vị trí 12, số nào nhỏ thì xóa số đó là xong (bằng xóa đại cái nào cũng được)

- Rỏ ràng ta thấy việc tìm số nhỏ nhất trong 1 dãy số cứ liên tục lặp lại. Như vậy độ phức tạp của thuật toán này là O(m.n). Nếu m nhỏ thì không sao cả. Nhưng nếu m đủ lớn thì ta phải dùng đến cây IT để tìm max (cấu trúc này rất khó hiểu đối với độ tuổi các bạn). Chúc các bạn vui.


Được sửa bởi administrators ngày Sun 21 Mar 2010, 21:00; sửa lần 1. (Reason for editing : gõ nhằm m^2 và m.n)
Về Đầu Trang Go down
littlelee
Admin
Admin
littlelee


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

Xóa số để tạo thành số nhỏ nhất, lớn nhất. Empty
Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Xóa số để tạo thành số nhỏ nhất, lớn nhất. I_icon_minitimeSun 21 Mar 2010, 21:22

administrators đã viết:
Bài cho khó vậy ai mà giải cho được, nên bạn thấy chán là chuyện bình thường.
Vì số liệu cho quá lớn nên muốn giải bài này chạy dưới 1 giây cần đến 2 kỹ thuật cao cấp
- Cơ sở suy luận toán cao cấp
- Cấu trúc cơ sở dữ liệu đặc biệt IT.

Cách làm như sau:

- Trong m+1 số đầu tiên chọn ra số nhỏ nhất. Xóa các số trước đó rồi làm tiếp...

* Ví dụ m=10:
* Ta xét 11 số thì số nhỏ nhất ở vị trí thứ 7. Thì ta sẽ xóa đi 6 số đầu tiên chừa số thứ bảy lại (làm số đứng đầu luôn đấy)
* Sau đó xét tiếp 4+1 (=5) số từ vị trí thứ 8 và chọn ra số nhỏ nhất. Giả sử số nhỏ nhất năm ở vị trí 11 thì ta xóa bỏ hết tất cả các số có vị trí lớn hơn 7 và nhỏ hơn 11. (hiển nhiên là được 3 số). Như vậy ta đã xóa hết 9 số rồi.
* Sau đó xét tiếp 1+1 (=2) số kế tiếp kể từ vị trí 12, số nào nhỏ thì xóa số đó là xong (bằng xóa đại cái nào cũng được)

- Rỏ ràng ta thấy việc tìm số nhỏ nhất trong 1 dãy số cứ liên tục lặp lại. Như vậy độ phức tạp của thuật toán này là O(m.n). Nếu m nhỏ thì không sao cả. Nhưng nếu m đủ lớn thì ta phải dùng đến cây IT để tìm max (cấu trúc này rất khó hiểu đối với độ tuổi các bạn). Chúc các bạn vui.

Rất đúng với ý mình. Tuy nhiên chuyện m quá lớn thì mình vẫn để vậy. Bình thường mình làm với n=10 000 còn 1000 000 thì chưa thử bao giờ.
Về Đầu Trang Go down
hoangtin14
Mèo con
hoangtin14


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

Xóa số để tạo thành số nhỏ nhất, lớn nhất. Empty
Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Xóa số để tạo thành số nhỏ nhất, lớn nhất. I_icon_minitimeWed 24 Mar 2010, 21:05

Bó tay toàn tập cho lit luôn. Lúc đầu thì bảo cho bài dễ cho các bạn trong trường còn làm. Giờ cho những bài như thế này thì chắc chỉ có administrators mới giải dc thui
Về Đầu Trang Go down
littlelee
Admin
Admin
littlelee


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

Xóa số để tạo thành số nhỏ nhất, lớn nhất. Empty
Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Xóa số để tạo thành số nhỏ nhất, lớn nhất. I_icon_minitimeWed 24 Mar 2010, 21:07

Ừ thì bài này dễ mà confused
Về Đầu Trang Go down
Sponsored content





Xóa số để tạo thành số nhỏ nhất, lớn nhất. Empty
Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Xóa số để tạo thành số nhỏ nhất, lớn nhất. I_icon_minitime

Về Đầu Trang Go down
 
Xóa số để tạo thành số nhỏ nhất, lớn nhất.
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Dãy con tăng dài nhất
» Đề thi thánh phố Đà Nẵng 2009-2010
» Phân tích thành một dãy liên tiếp
» Dãy con dài nhất có tổng chia hết cho K
» nhập vào 2 số và tìm số nhỏ nhất ?

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