kết quả từ 1 tới 4 trên 4

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

  1. #1
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

    Post Đề 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.
    test Sntghep.out
    5 23
    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
    Quick reply to this message Trả lời       

  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    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.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. #3
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

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

    theo tớ bài 2 ko cần dùng sàng đâu. dùng sàng lâu hơn đó

  4. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Đú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.

Nhãn