›
›
›

Kỳ thi chọn học sinh giỏi cấp tỉnh môn Tin học Lớp 9 - Năm học 2014-2015

Bài 1: Liên phân số (7,0 điểm):

            Số hữu tỉ dương a/b luôn được biểu diễn dưới dạng một liên phân số hữu hạn:

Liên phân số này ký hiệu là [q0,q1,q2,...,qn], trong đó q0³0; q1,q2,...,qn là những số nguyên dương; qn>1; n gọi là độ dài của liên phân số.

Hãy viết chương trình biến đổi một phân số a/b thành liên phân số hữu hạn.

Dữ liệu vào là hai số nguyên dương a, b nhập từ bàn phím để biểu diễn phân số a/b.

Dữ liệu ra là một dòng gồm các số q0,q1,q2,...,qn biểu diễn dạng liên phân số của phân số a/b. Các số viết cách nhau ít nhất một khoảng cách.

            Ví dụ:

Input   Output

a=7

b=5

   1 2 2

 

doc 6 trang mianlien 05/03/2023 3480
Download
Bạn đang xem tài liệu "Kỳ thi chọn học sinh giỏi cấp tỉnh môn Tin học Lớp 9 - Năm học 2014-2015", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • docky_thi_chon_hoc_sinh_gioi_cap_tinh_mon_tin_hoc_lop_9_nam_hoc.doc

Nội dung text: Kỳ thi chọn học sinh giỏi cấp tỉnh môn Tin học Lớp 9 - Năm học 2014-2015

  1. Bài 3: Tìm đường hái quả (6,0 điểm): Một khu vườn hình chữ nhật kích thước MxN được chia thành các ô vuông đơn vị để trồng một loại cây ăn quả. Trên mỗi ô thì số quả tương ứng có thể hái được là A[i,j] (1 i M; 1 j N). Một người khách dạo qua vườn và hái tất cả các quả trên những ô đi qua. Vị trí xuất phát từ ô [1,1] và kết thúc tại ô [M,N] với hành trình là sang ô chung cạnh theo hướng tăng của i hoặc j (sang phải hoặc đi xuống – như hình vẽ). Hãy viết chương trình tìm lộ trình đi của người đó để hái được nhiều quả nhất. 1 3 5 7 2 7 9 4 2 2 2 3 1 6 7 7 4 6 2 5 Dữ liệu vào là tệp HAIQUA.INP có cấu trúc như sau: - Dòng đầu tiên là hai số M, N nguyên dương cách nhau một khoảng cách (0<M,N<100). - M dòng tiếp theo, mỗi dòng gồm N số tương ứng là số quả có thể hái được ở các ô theo thứ tự tại hàng thứ i. Mỗi số cách nhau một khoảng cách. Dữ liệu ra là tệp HAIQUA.OUT cso cấu trúc như sau: - Dòng đầu là số quả lớn nhất có thể hái được theo một lộ trình thỏa mãn yêu cầu. - Dòng tiếp theo gồm M+N-1 số tương ứng là số quả hái ở từng ô theo đường đi để được số quả nhiều nhất. Mỗi số cách nhau ít nhất một khoảng cách. Ví dụ: HAIQUA.INP HAIQUA.OUT 4 5 41 1 3 5 7 2 1 7 9 4 2 6 7 5 7 9 4 2 2 2 3 1 6 7 7 4 6 2 5
  2. Write('Nhap a: '); Readln(a); Write('Nhap b: '); Readln(b); Until (a>0) and (b>0); Psrg; If a 0 do Begin r:=x mod y; x:=y; y:=r; End; If x=1 then Uc:=True Else Uc:=False; End; Function mUc(c:mmc;k:Byte;m:Word):Boolean; Var i:Byte; kt:Boolean; Begin Kt:=True; For i:=1 to k do Kt:=(Uc(m,c[i]) and Kt); mUc:=Kt; End; Function Max(c:mmc;k:Byte):Word; Var i:Byte; m:Word; Begin m:=a[1]; For i:=2 to k do If m<a[i] then m:=a[i]; Max:=m;
  3. Function vMax(i,j:Word):Word; Begin If i>j then vMax:=i Else vMax:=j; End; Procedure Optimize; Var i,j:Word; Begin For i:=1 to n-1 do Begin L[i,0]:=0; L[0,j]:=0; End; L[0,0]:=0; L[1,1]:=A[1,1]; For i:=1 to m do For j:=1 to n do L[i,j]:=vMax(L[i,j-1],L[i-1,j]) + A[i,j]; End; Procedure Trace(i,j:Word); Begin If (L[i,j]=L[i,j-1] + A[i,j]) then Dec (j) Else Dec(i); If (i>0) and (j>0) then Begin Trace(i,j); Write(f,A[i,j],' '); End; End; Procedure Result; Begin Assign(f,fo); Rewrite(f); Writeln(f,L[m,n]); Trace(m,n); Writeln(f,A[m,n]); End; Begin Time:=Times; Enter; Optimize; Result; Write(f,(Times-Time)/18.2:0:2); Close(f); End.