zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Đề thi Olympic Tin học sinh viên lần thứ XV khối Cá nhân Cao đẳng (Năm 2006)

Chia sẻ: Tư Khấu Quân Tường | Ngày: | Loại File: PDF | Số trang:2

Báo xấu

7
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề thi Olympic Tin học sinh viên lần thứ XV khối Cá nhân Cao đẳng (Năm 2006) cung cấp cho thí sinh các bài tập giải quyết vấn đề lập trình gồm: siêu mã; ảnh tích hợp;... Mời các bạn cùng tham khảo chi tiết nội dung đề thi!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi Olympic Tin học sinh viên lần thứ XV khối Cá nhân Cao đẳng (Năm 2006)

OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XV, 2006 Khối thi: Cá nhân Cao đẳng Thời gian làm bài: 150 phút Ngày thi: 06-05-2006 Nơi thi: TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Tên bài Tên file chương Tên file dữ liệu Tên file kết quả Thời gian cho trình mỗi test Siêu mã HCODE.* HCODE.INP HCODE.OUT 1 giây Ảnh tích hợp IIMAGE.* IIMAGE.INP IIMAGE.OUT 1 giây Dấu * được thay thế bởi PAS, C, CPP hoặc java của ngôn ngữ được sử dụng tương ứng là Pascal, C, C++ hoặc Java. Hãy lập trình giải các bài sau đây: Bài 1. Siêu mã Siêu mã là một loại mã có nhiều ứng dụng quan trọng trong lĩnh vực mã hóa và truyền tin. Trong bài này, ta xét bài toán đơn giản sau đây về siêu mã. Cho u và v là hai xâu kí tự khác rỗng có độ dài hữu hạn. Xâu u được gọi là xâu con của xâu v nếu u có thể nhận được từ v bằng cách xóa bớt ít nhất một kí tự trong v. Một tập X các xâu khác rỗng có độ dài hữu hạn được gọi là siêu mã nếu mọi cặp u, v bất kỳ thuộc X, u không là xâu con của v và v không là xâu con của u. Cho trước một tập X = {x1, x2, ..., xN} gồm N xâu khác rỗng, mỗi kí tự trong xâu là 0 hoặc 1. Hãy kiểm tra xem X có là một siêu mã hay không? Dữ liệu: vào từ file văn bản HCODE.INP có định dạng như sau: • Dòng đầu tiên chứa số nguyên dương N (N ≤ 500); • Dòng thứ i trong N dòng tiếp theo ghi xâu xi của tập X, độ dài của xâu xi không quá 15, với i = 1, 2, ..., N. Kết quả: ghi ra file văn bản HCODE.OUT có định dạng như sau: • Nếu X là siêu mã thì ghi số 1; • Nếu X không là siêu mã thì dòng đầu tiên ghi số 0, dòng thứ hai ghi chỉ số i nhỏ nhất mà hoặc xi là xâu con của xj hoặc xj là xâu con của xi, với xi, xj thuộc X, 1 ≤ i < j ≤ N. Ví dụ: HCODE.INP HCODE.OUT HCODE.INP HCODE.OUT 5 0 3 1 1111 2 010 100101 1000 01011 11 000 0001000 1/2 pages
Bài 2. Ảnh tích hợp Việc trích lọc các đặc trưng phục vụ cho các ứng dụng trong khoa học Thị Giác Máy Tính đòi hỏi phải biết không chỉ giá trị của từng điểm ảnh mà cả mối tương quan giữa giá trị các điểm ảnh. Một ảnh mức xám A là một lưới hình chữ nhật gồm N hàng đánh số thứ tự từ trên xuống bắt đầu từ 1 và M cột đánh số thứ tự từ trái sang phải bắt đầu từ 1. Mỗi điểm (i, j) của lưới A (giao của dòng i với cột j) ghi một giá trị nguyên thể hiện mức xám của ảnh tại vị trí tương ứng. Để tăng tốc xử lý, các nhà nghiên cứu đề nghị một cách lưu trữ ảnh đặc biệt gọi là ảnh tích hợp. Với một ảnh gốc mức xám A, người ta xây dựng một ảnh tích hợp B cũng có cùng kích thước, trong đó giá trị ảnh B(i, j) được tính bằng tổng giá trị các điểm ảnh nằm trong vùng phía trên, bên trái vị trí (i, j) và cả tại (i, j) trong ảnh gốc A (xem hình vẽ). Như vậy, các giá trị tại từng vị trí trong ảnh tích hợp B được tính theo công thức: (i, j) B(i, j ) =  A(i' , j ' ) 1i 'i ,1 j ' j (1  i  N ,1  j  M ) trong đó B(i, j) là giá trị ảnh tích hợp tại vị trí (i, j) và Giá trị của ảnh tích hợp tại (i, j) A(i', j') là giá trị ảnh gốc tại vị trí (i', j'). Yêu cầu: xây dựng ảnh tích hợp B từ ảnh gốc A. Dữ liệu: cho trong file văn bản IIMAGE.INP gồm: • Dòng thứ nhất ghi 2 số nguyên dương N và M (1 ≤ N, M ≤ 250); • Mỗi dòng trong N dòng tiếp theo ghi M số nguyên là các giá trị của ảnh A. Các số này có giá trị trong đoạn [0, 255]. Kết quả: ghi ra file văn bản IIMAGE.OUT gồm N dòng, mỗi dòng ghi M số là các giá trị của ảnh B. Các số trên cùng một dòng trong các file được ghi cách nhau bởi một dấu cách. Ví dụ: IIMAGE.INP IIMAGE.OUT 3 3 1 3 6 1 2 3 7 14 21 6 5 4 14 21 31 7 0 3 ------------------------------------ Hết -------------------------------------- 2/2 pages

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.