Đề Thi HSG Tin Học Đà Nẵng 2006-2007 Hay !! Mọi người cùng thảo luận nha.!!

Bài 1 Chuyển vị
Lập chương trình để chuyển đổi vik trí từ dòng thành cột của một bảng số nguyên có 4 hàng , 4 cột.
Đưa ra màn hình bảng số ban đầu và bảng số đã chuyển đổi vị trí.
{ dữ liệu lấy vào và xuất ra từ bàn phím}
Test
test
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

Bài2 Ghép số nguyên tố
Dãy A là dãy tăng dần các số nguyến tố: 2,3,5,7,11,13,...., ; lập dãy B bằng cách ghép từng cặp
số liền kề của dãy A với nhau, cụ thể 23,57,1113,...., Dãy C nhận được từ dãy B bằng cách loại đi các số
không âm là số nguyên tố.
Yêu cầu : Lập chương trình tìm j số hạng đầu tiên của dãy C.
Dữ liệu vào : Nhập j (j<=50) từ bàn phím.
Dữ liệu ra : Ghi ra tệp Sntghep.out, mỗi dòng một số hàng của dãy C.
testSntghep.out
523
3137
8389
157163
167173
Bài 3 Khoảng cách xâu

Với một xau ký tự, ta có thể tiến hành các phép biến đổi sau:
1. Thay một ký tự bất kỳ bở một kí tự khác, chẳng hạn: test thành text.
2.Xóa một ký tự bất kỳ,chẳng hạn : text thành ext hoặc text thành txt,
3.Thêm một ký tự vào một vị trí bất kỳ, chẳng hạn như SP thành SP2.
Với hai xâu S1 và S2, ta nói khoảng cách từ xâu S1 đễnâu S2 bằng số lượng ít nhát các phép
biến đổi thuộc 3 cách trên mà khi áp dụng liên tiếp vào S1, ta sẽ nhận được xâu S2.
Dữ liệu vào: Đọc từ file văn bản Kcxau.inp gồm 2 dòng, dòng 1 là xâu S1, dòng 2 là xâu S2
(Các xâu S1,S2 có độ dài không quá 100 ký tự);
Dữ liệu ra: Ghi ra file văn bản Kcxau.out như sau:
-Dòng đầu tiên ghi số N là khoảng cách từ S1 đến S2.
-các dòng tiếp theo, mỗi dòng ghi một phép biến đổi theo thư tự để từ xâu s1, có được xâu s2
 
  • Chủ đề
    de thi
  • tengiday

    Happy life
    Bài 1: Bạn chỉ cần đổi chỗ i và j lúc in ra là xong thôi.

    Bài 2: Bài này mình đang suy nghĩ xem có dùng thuật toán bên number theory nào tốt hay không, chứ mình dùng sieve of Eratosthenes phải cần 1 mảng 80 triệu phần tử (~80 MB) và chương trình mất khoảng 1.25 giây để chạy ra với j = 50. Nếu bài này mình gặp lúc đi thi thì mình sẽ chạy trên máy trước rồi ghi toàn bộ vào mảng hằng, sau đó chỉ việc in ra thôi, bảo đảm nhanh nhất.

    Bài 3: Bài này là quy hoạch động rồi. Gọi F[i, j] = số phép biến đổi tối thiểu để biến chuỗi S1[1..i] thành chuỗi S2[1..j]. Ta có công thức
    Mã:
    F[i, j] = F[i - 1, j - 1] if S1[i] = S2[j],
    F[i, j] = min(F[i - 1, j], F[i - 1, j -1], F[i, j - 1]) + 1 if S1[i] khác S2[j].
    Khởi tạo:
    Mã:
    F[0, j] = j và F[i, 0] = i.
     

    tengiday

    Happy life
    Đúng rồi, bài 2 không cần tới sàng vì chỉ cần tới số nguyên tố 7829 thôi.
     

    Thống kê

    Chủ đề
    100,657
    Bài viết
    467,424
    Thành viên
    339,832
    Thành viên mới nhất
    tiendungmobi
    Top