Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Tin học Tuyển tập các đề thi học sinh giỏi tin học qua các năm( có đáp án)...

Tài liệu Tuyển tập các đề thi học sinh giỏi tin học qua các năm( có đáp án)

.DOC
255
636
119

Mô tả:

Nhiều học sinh học tin rất giỏi nhưng kết quả không cao. lý do học sinh chưa hiểu được nội dung trong tâm của cấu trúc đề nên học lan man thiếu trọng tâm, chúng tôi biên tập bộ đề thi môn tin học có kèm theo đáp án để các bạn tiện theo dỏi, nếu các bạn thực sự nắm vững cách giải các bài tập này thì việc thi các đề thi HSG tin học không mấy khó khăn.
ĐỀ THI HỌC SINH GIỎI TRƯỜNG MÔN: TIN HỌC 9 ĐỀ SỐ 1 Thời gian: 120 phút Bài 1. Số bền Năm 1973, nhà Toán học Neil Sloan đưa ra khái niệm độ bền của một số nguyên không âm N như sau:  Nếu N có một chữ số thì độ bền của N bằng 0.  Nếu N có từ 2 chữ số trở lên thì độ bền của N bằng độ bền của số nguyên là tích các chữ số của N cộng 1. Cho N, tính độ bền của N. Dữ liệu vào từ file văn bản: persist.inp Dòng 1: Số nguyên N (0 ≤ N ≤ 2.000.000.000).  Kết quả ghi ra file văn bản: persist.out Dòng 1: Số nguyên là độ bền của N.  Ví dụ persist.inp 99 persist.out 2 Giải thích Doben(99)=Doben(81)+1=Doben(8)+1+1=0+1+1=2 Bài 2. Đổi giày Bờm là chủ một cửa hiệu bán giày. Một ngày nọ, Bờm kiểm tra kho và thấy trong kho còn lại 2*N chiếc giày, trong đó có N chiếc giày chân trái với kích thước lần lượt là a 1, a2, …, aN, N chiếc giày chân phải với kích thước lần lượt là b 1, b2, …, bN. Hai chiếc giày chỉ có thể hợp thành một đôi nếu chúng là một cặp trái - phải có cùng kích thước. Bờm quyết định mang một số giày đến nhà sản xuất để đổi. Hãy xác định giúp Bờm số ít nhất các chiếc giày cần đổi nếu cậu ta muốn cửa hiệu của mình có thể bán được N đôi giày. Dữ liệu vào từ file văn bản: shoes.inp 1 Dòng 1: Số nguyên N (1 ≤ N ≤ 100). Dòng 2: N số nguyên a1, a2, …, aN (1 ≤ ai ≤ 1000, i = 1, 2,…, N). Dòng 3: N số nguyên b1, b2, …, bN (1 ≤ bi ≤ 1000, i = 1, 2,…, N).    Kết quả ghi ra file văn bản: shoes.out Dòng 1: Số nguyên là số giày ít nhất cần đổi.  Ví dụ shoes.inp shoes.out 3 1 131 Giải thích Đổi 1 chiếc giày chân trái kích thước 1 thành giày chân trái kích thước 2 hoặc đổi 1 chiếc giày chân phải kích thước 2 thành giày chân phải kích thước 1. 321 Bài 3. Đối xứng Một số nguyên gọi là số đối xứng nếu viết dạng biểu diễn thập phân của số đó theo chiều ngược lại vẫn thu được chính số đó. Cho số nguyên dương N có không quá 100 chữ số. Hãy xác định số nguyên đối xứng nhỏ nhất lớn hơn N. Dữ liệu vào từ file văn bản: nextpal.inp  Dòng 1: Số nguyên N Kết quả ghi ra file văn bản: nextpal.out  Dòng 1: Số nguyên kết quả Ví dụ nextpal.inp Nextpal.out 99 101 Hướng dẫn giải Câu 1: Tư tưởng giải thuật: 2 - Xây dựng hàm tính tích các chữ số của N - Khi nào N>9 thì tăng d, đồng thời gán N:=tich(N); - Ra ngoài in ra d (chính là độ bền của N) Bài giải: Var f,g:text; d,n:longint; Function tich(x:longint):longint; Var s,a:longint; Begin s:=1; repeat a:=x mod 10; x:=x div 10; s:=s*a; until x=0; tich:=s; End; BEGIN Assign(f,'persist.inp'); Reset(f); Assign(g,'persist.out'); Rewrite(g); Read(f,n); d:=0; While n>9 do begin 3 inc(d); n:=tich(n); end; Write(g,d); Close(g); Close(f); END. Câu 2: Tư tưởng thuật giải: - Xét lần lượt từng chiếc dày bên trái. - Tìm chiếc dày đầu tiên bên phải trùng với chiếc dày bên trài đang xét, nếu có trùng thì đánh dầu chiếc dày đó, còn không có trùng thì xét chiéu tiếp theo. - Đếm số chiếc dày chưa đánh dấu bên phải chính là số dày phải đem đi đổi. Bài giải: Var f,g:text; n,j,i,d:longint; a,b:array [1..1000] of longint; 4 ĐỀ THI HỌC SINH GIỎI TỈNH MÔN: TIN HỌC 9 ĐỀ SỐ 3 Thời gian: 120 phút Bài 1: (6điểm). PHẦN TỬ YÊN NGỰA Cho mảng hai chiều có kích thước MxN số nguyên. Phần tử A[I,j] được gọi là phần tử yên ngựa nếu nó là phần tử nhỏ nhất trong hàng I đồng thời là phần tử lớn nhất trong cột j. Em hãy lập chương trình tìm phân tử yên ngựa của mảng A. Dữ liệu vào: Cho file PTYN.INP gồm - Dòng đầu tiên gồm hai số M,N ( 0 M; N  100) - M dòng tiếp theo, mỗi dòng gồm có N số nguyên của mảng A. (các giá trị cách nhau ít nhất 1 khoảng cách). Dữ liệu ra: Ghi file PTYN.OUT vị trí của các phân tử yên ngựa (nếu có) hoặc dòng thông báo “Không có phần tử yên ngựa”. Ví dụ: PTYN.INP PTYN.OUT 33 (2,2) 15 3 9 55 4 6 76 1 2 5 Hoặc PTYN.INP PTYN.OUT 33 Khong co phantu yen ngua 15 10 5 55 4 6 76 1 2 Bài 2: (7 điểm). TỔNG CÁC SỐ FIBONACI Dãy Fibonaci là dãy gồm các số: 1; 1; 2; 3; 5; 8; … được xác định bởi công thức sau: F1=1; F2=1; Fi=Fi-1+Fi-2 với i>2 Em hãy biểu diễn một số tự nhiên tành tổng ít nhất các số Fibonaci khác nhau. Dữ liệu vào: Cho file FIBO.INP chứa số N (N 2000000000) Dữ liệu ra: ghi vào file FIBO.OUT biễu diễn số N thành tổng ít nhất các số Fibonaci khác nhau. Ví dụ. FIBO.INP 129 FIBO.OUT 129=89+34+5+1 Hoặc FIBO.INP 8 FIBO.OUT 8=8 6 Bài 3. (7 điểm) CHỌN PHẦNTHƯỞNG Trong kỳ thi học sinh giỏi môn tin học, em là người đạt giải đặc biệt. Ban tổ chức cho phép em chọn các phần thưởng cho mình. Các phần thưởng xếp thành một dãy dược đánh dấu từ số 1 đấn số N (0 N 10000), phần thưởng thứ I có giáo trị là ai (1 ai 100). Em được phép chọn các phần thưởng cho mình theo nguyên tắc không chọn 3 phần thưởng liên tiếp nhau trong dãy. Viết chương trình để máy tính hướng dẫn em chọn các phần thưởng sao cho tổng giá trị các phần thưởng nhận được là lớn nhất. Dữ liệu vào: cho file PTHUONG.INP gồm các dòng: - Dòng đầu tiên là số phần thưởng N - N dòng tiếp theo là giá trị của các phần thương. Dữ liệu ra: ghi vào file PTHUONG.OUT gồm các dòng: - Dòng đầu tiên ghi tổng giá trị lớn nhất của phần thưởng đã chọn. - Dòng tiếp theo ghi vị trí của các phần thưởng đã chọn theo thứ tự tăng dần. Ví dụ: PTHUONG.INP PTHUONG.OUT 5 23 6 1245 9 1 3 7 5 Hoặc PTHUONG.INP PTHUONG.OUT 7 32 6 12467 9 1 3 5 10 4 8 Đáp án Bài 1: (6điểm). PHẦN TỬ YÊN NGỰA program yenngua; uses crt; type mang=array[1..100,1..100] of integer; var a:mang; n,i,j,d:integer; f:text; procedure nhap; var i,j:integer; begin assign(f,'PTYN.inp'); reset(f); readln(f,n); for i:=1 to n do begin 9 for j:=1 to n do read(f,a[i,j]); readln(f); end; end; function maxc(h:integer):integer; var max, i:integer; begin max:=a[1,h]; for i:=1 to n do if maxa[h,i] then min:=a[h,i]; minh:=min; end; begin clrscr; nhap; d:=0; 10 for i:=1 to n do for j:=1 to n do if ((a[i,j]=minh(i)) and (a[i,j]=maxc(j))) then d:=d+1; assign(f,'PTYN.out'); rewrite(f); for i:=1 to n do for j:=1 to n do if ((a[i,j]=minh(i)) and (a[i,j]=maxc(j))) then writeln(f,'(',i, ',',j,')'); if d=0 then write(f,'Khong co phan tu yen ngua'); close(f); end. Bài 2: (7 điểm). TỔNG CÁC SỐ FIBONACI Program TongFIBONACi; uses crt; var i,j,n,m:longint; f:text; function fi(h:integer):longint; var i:integer; x,y,tg:longint; begin 11 if (h=1) or (h=2) then fi:=1 else begin x:=1; y:=1; for i:=1 to h do begin tg:=x; x:=y; y:=y+tg; end; fi:=y; end; end; function vt(so:longint):integer; var i:integer; begin i:=1; while fi(i)< so do i:=i+1; if fi(i)= so then vt:=i else vt:=i-1; end; procedure doc; begin 12 assign(f,'FIBO.INP'); reset(f); read(f,n); close(f); end; begin doc; assign(f,'FIBO.OUT'); rewrite(f); write(f,n,'='); write(f,fi(vt(n))); n:=n-fi(vt(n)); while n<>0 do begin m:=fi(vt(n)); n:= n-fi(vt(n)); write(f,'+',m ); end; close(f); end. Bài 3. (7 điểm) CHỌN PHẦNTHƯỞNG program phan_thuong; uses crt; 13 type mang= array[0..10000 ] of byte; var a,d,m:mang; dd:array[1..20,1..400] of byte; b:array [1..10000] of boolean; r,dem, t,n,max,i,j:integer; f:text; procedure doc; var i:integer; begin assign(f,'pthuong.inp'); reset(f); readln(f,n); for i:=1 to n do readln(f,d[i]); close(f); end; function kt( c:mang):boolean; var i,j:longint; q:boolean; begin i:=1; q:=true; while (i<=r-2) and q do begin j:=1; 14 while c[i+j-1]+1=c[i+j] do j:=j+1; if j>=3 then q:=false else q:=true; i:=i+1; end; kt:=q; end; Procedure print; var i,tong: byte; begin if kt(a)=true then begin dem:=dem+1; tong:=0; for i:=1 to r do begin dd[dem,i]:= a[i]; tong:=tong+d[a[i]]; end; m[dem]:=tong; end; end; Procedure Find(k:byte); var j: byte; 15 begin if k>r then print else begin for j:=1 to n do if b[j] and (j>a[k-1]) then begin a[k]:=j; b[j]:=false; Find(k+1); b[j]:=true; end; end; end; begin clrscr; doc; dem:=0; r:= n-(n div 3); for t:=1 to n do b[t]:=true; a[0]:=0; Find(1); max:=m[1]; 16 for i:=1 to dem do if max< m[i] then max:=m[i]; assign(f,'PTHUONG.OUT'); rewrite(f); writeln(f,max); for i:=1 to dem do if max=m[i] then begin j:=1; while (dd[i,j] <>0) do begin write(f,dd[i,j]:2); j:=j+1; end; end; close(f); end. BEGIN Assign(f,'shoes.inp'); Reset(f); Assign(g,'shoes.out'); Rewrite(g); Readln(f,n); For i:=1 to n do read(f,a[i]); 17 Readln(f); For i:=1 to n do read(f,b[i]); d:=0; i:=1; repeat j:=0; repeat inc(j); until (a[i]=b[j]) or (j>n); if a[i]=b[j] then b[j]:=0; inc(i); until i>n; for i:=1 to n do if b[i]<>0 then inc(d); write(g,d); Close(g); Close(f); END. 18 ĐỀ THI HỌC SINH GIỎI HUYỆN ĐỀ SỐ 5 MÔN: TIN HỌC 9 Thời gian: 120 phút Câu 1: (4 điểm) Viết chương trình nhập vào tháng, năm và cho biết tháng đó có bao nhiêu ngày. Câu 2: (3 điểm) Viết chương trình nhập vào từ bàn phím ba số tự nhiên a, b, c và hiển thị kết quả thông báo ra màn hình bộ ba số đó có phải là bộ số Pitago hay không. Câu 3: (3 điểm) Cho abc là số có ba chữ số thỏa mãn điều kiện viết chương trình tìm các số thỏa mãn điều kiện đã cho. abc a 3  b 3  c 3 . Hãy Câu 4: (5 điểm) Một người gửi tiền tiết kiệm vào ngân hàng với số tiền ban đầu là x triệu đồng với lãi suất hàng tháng là k%. Biết rằng phương thức tính lãi suất là lũy kế theo thời hạn, nghĩa là số tiền lãi hàng tháng được cộng dồn vào số tiền gốc với chu kì (thời hạn) là c tháng và khi chưa đủ chu kì thì không được tính số tiền lãi. Sau thời gian t tháng, người đó rút tiền cả vốn và lãi được b triệu đồng. Tính b. 19 Hãy viết chương trình giải bài toán trên với x, k, c, t được nhập từ bàn phím và b được viết ra màn hình. Câu 5: (5 điểm) Dùng ba biến mảng lần lượt biểu diễn số tiền cước phí về điện thoại, điện và dịch vụ Internet của gia đình mình trong năm qua. Em hãy viết một chương trình thực hiện các nhiệm vụ sau: a. Nhập số tiền mà gia đình em đã chi cho ba dịch vụ từng tháng từ bàn phím. b. Tính và in ra màn hình: Tổng số tiền mà gia đình em phải trả cho các dịch vụ này trong năm qua; dịch vụ có tổng chi lớn nhất và số tiền trung bình mỗi tháng gia đình em phải trả cho các dịch vụ nói trên. 20
- Xem thêm -

Tài liệu liên quan