Đề thi HSG Tin lớp 9 nè,ai vào giúp với

[quanghien95]

Nguyên đề:

ĐỀ THI HỌC SINH GIỎI TIN LỚP 9
Thời gian 90 phút kể cả thời gian phát đề
Ngày thi: 28/10/2007

Câu 1 : (8 Điểm)
Viết trương trình nhập từ bàn phím một mảng một chiều gồm n phần tử (5<n<30) là các số nguyên dương.Đưa ra màn hình các dãy sau:
- Dãy 1 là mảng vừa nhập
- Dãy 2 là các phần tử liên tiếp nhiều nhất không giảm lấy từ mảng.
- Dãy 3 là dãy các phần tử không tăng nhiều nhất lấy từ mảng mà không thay đổi vị trí các phần tử trong mảng.

Ví dụ : Nhập n=14 và các phần tử là:
31 3 6 7 9 18 22 10 21 24 27 13 7 4
Dãy 1 là: 31 3 6 7 9 18 22 10 21 24 27 13 7 4
Dãy 2 là: 3 6 7 9 18 22
Dãy 3 là: 31 22 21 13 7 4

Câu 2 : (8 điểm)
Nhập một số nguyên dương n (với 0<n<10 mũ 4) rồi phân tích số n ra thừa số nguyên tố và đưa kết quả ra màn hình.

Ví dụ : Nhập n=7560 thì kết quả in ra là 7560= 2.2.2.3.3.3.5.7

Câu 3 : (4 điểm)

Viết trương trình nhập từ bàn phím 2 số tự nhiên n,m (với 5<n<m<100) là hai kích thước của hình chữ nhật. Đưa ra màn hình phương án cắt hình chữ nhật trên thành các hình vuông sao cho số hình vuông là ít nhất có thể.

Ví dụ cho n=5, m=6 thì kết quả cắt thành 5 hình vuông và trên màn hình được biểu diễn nhu sau:
5 6
3 3 2 2 2

Ai giải được đề này thì giúp tui với

[tranvanho]

bài này của tỉnh nào zợ
bài này khá khó để suy nghĩ coi đã

[pippit2hn]

...khó nhằn quá...bài đầu tiên có vẻ dễ kiếm điểm nhất, bài 2 thì ko ra hướng thì bó tay...bài 3 thì khó nhăn răng...đúng là đề thi HSG có khác...

[amida]

Khó hơn đề năm ngoái của mình 1 chút nhưng dễ hơn đề 2,3 năm trước. Đề không khó, 90' vừa đủ

[cashier]

oé. lớp 9 mà ghê thế . ặc có 90 phút thui á
bài 1: ý b và c có dùng quy hoạch động ( bài toán đầu tiên trong phần quy hoạch động) nhưng mà có 90 phút mà n cũng có 30 thì chơi kiểu cùn vậy :
- xét tất cả các dãy bắt đầu từ mọi phần tử trong mảng
- tìm dãy có độ dài max
( đánh dấu các phần tử đã thuộc vào một dãy nào đó để đỡ mất công xét lại)
bài 2: làm rồi:

var u,d,m,m:longint;
BEGIN
      u:=2;{uoc so dau tien}
      Repeat
            m:=0;
            while n mod u <> 0 do inc(u);{tim uoc so tiep theo}
            while n mod u = 0 do
            begin
                inc(m);n:=n div u;
            end;
            write(u);
            if m>1 then write('^',m);{so mu}
            if n>1 then write(' * ');
      until n=1;
      readln;
END.

bài này ghi luôn cả số mũ ra, còn nếu như đề bài thì còn dễ hơn:

var u,d,n:longint;
BEGIN
      u:=2;{uoc so dau tien}
      Repeat
            while n mod u <> 0 do inc(u);{tim uoc so tiep theo}
            n:=n div u;
            write(u);
            if n>1 then write(' * ');
      until n=1;
      readln;
END.

bài 3: tạm thời chưa nghĩ ra (buồn ngủ )

[amida]

oé. lớp 9 mà ghê thế . ặc có 90 phút thui á
bài 1: ý b và c có dùng quy hoạch động ( bài toán đầu tiên trong phần quy hoạch động) nhưng mà có 90 phút mà n cũng có 30 thì chơi kiểu cùn vậy :
- xét tất cả các dãy bắt đầu từ mọi phần tử trong mảng
- tìm dãy có độ dài max
( đánh dấu các phần tử đã thuộc vào một dãy nào đó để đỡ mất công xét lại)

Bó tay. Bài này mà dùng QHĐ chả hiểu để làm gì, cho N <= 30 là khỏe lắm rồi.

[grenadier1991]

Bài 3 này tui thi vào vòng 1 đội tuyển cấp quận HBT cách đây 2 năm. Hồi đó ở đội tuyển không ai giải ra hết cách nào hiệu quả hết. May ra chỉ có đệ quy và quy hoạch động là được nhưng nếu độ dài cạnh quá lớn thì cũng khó khăn. Hồi đó tui dùng 1 cách giải ko chính xác, nhưng được cái là nhanh, kết quả tạm chấp nhận dc, tui dc cho 2/4 điểm của bài đó.
Hình chữ nhật (a,b)(coi a>b)
Dựng hình vuông cạnh b. Hình CN còn lại là (a:=a-b,b)
Tiếp tục lặp lại cho đến khi còn toàn là hình vuông(a=b)

[cashier]

Bó tay. Bài này mà dùng QHĐ chả hiểu để làm gì, cho N <= 30 là khỏe lắm rồi.

hơ thì mình đã nêu cách làm bên dưới không sử dụng quy hoạch động thây ( với n <=30 )
mà mình nêu ra cách dùng quy hoạch động để các bạn tham khảo dùng cho các bài toán có dữ liệu lớn hơn mà ... sao thích bắt bẻ dữ zậy??

[quanghien95]

có ai giải dc bài 1 ,bài 3 thì giúp tui
bài 2 quá dễ

[1+1=2]

So vo'i câ'p 2 thì đê` này là quá khó, còn vo'i câ'p 3 thì quá bình thuong,
Bài 1 cho du~ liêu <= 30 => có le~ đê quy cung~ ko sao
Bài 2 quá dê~ rô`i
Bài 3 qhđ, f[i,j] là sô' hình vuông ít nhât' khi căt hinh chu nhat kich thuoc (i x j) ra.
Các ban suy nghi thêm tí là ra ngay mà,...
chúc thành công...