CÁCH LÀM ĐỀ THI TUYỂN SINH VÀO LỚP 10 TỈNH HÀ TĨNH | Nguyễn Xuân Hồng IT



CÁCH LÀM ĐỀ THI TUYỂN SINH VÀO LỚP 10 TỈNH HÀ TĨNH | Nguyễn Xuân Hồng IT
Tìm dãy con liên tiếp dài nhất có tổng dương
Câu 1: Diện tích hình vuông
Ý tưởng: Áp dụng định lý Pitago
– Nhập X(=10^9
– Gọi a là cạnh hình vuông
– X2= a2+a2=2 a2
– a=sqrt(X2/2)
– Shv= a*a; hay Shv=X2/2
Câu 2: Tổng dãy số
Ý tưởng
– Nhập a, b, N (N(=10^6) a=2,b=3, N=5
– X1=a;
– Ta có s= 2+5+8+11+14=40 (1)
Cách 1: qua được n(=10^6
S:=0;x:=a;
For i:=1 to N do
Begin
S:=s+x;
X:=x+b;
End;

Cách 2: qua được test n(=10^9
– Ta thấy tổng (1) trên tạo thành dãy cấp số cộng, công sai d=b; x1:=a;
– Ta có Xn=X1+(n-1)d=2+(4).3=14
– Sn=n(X1+Xn)/2=5(2+14)/2=5*8=40
– Từ cách phân tích trên in ra S=n(2a+(n-1)b)/2 =5(4+4.3)/2=40
Câu 3: Tìm dãy con liên tiếp dài nhất tổng dương
a- For i:=1 to N do // qua được n(=10^6; O(n)
Tìm A[i] mod 2#0 và A[i] mod 3=0 then inc(d)
– In ra d
b- Tính tổng hậu tố // tổng cộng dồn từ n về 1
For i:= N downto 1 do
F[i]:=F[i+1]+A[i] // sử dụng cho câu b và c
– In câu b: // qua được n(=10^6; O(n)
for i:=1 to N do ìf (A[i] lớn hơn F[1]/N) và A[i] nhỏ hơnmin then min:=A[i],Vt:=I;
– in ra VT

c. Câu C quá khó:
Cách 1: qua được test n(10^6
For d:=1 to N do //vị trí đầu dãy con
Begin
Tong:=0;
For c:=d to N do //vị trí cuối dãy con
begin
Tong:=tong+A[c]
If (tong ( 0) and(Max((vtc-vtd)) then begin vtd:=d; vtc:=c-1; end;
End;
Cách 2: // O(nlog(n))
– Sử dụng mảng tổng hậu tố câu b để làm
– Tạo bảng sau
+ Khởi tạo mảng Luu[1..N]:=0;
+ j:=0;
i 1 2 3 4 5
j 0 1 2 3 4 5
A[i] -9 -1 1 2 3
F[i] -4 5 6 5 3
Luu[j] -4 5 6
VTDau[] 1 2 3
ld 1 1 2 2
lc 1 1 3 5

For i=1 to n do
begin
– Lấy từng phần tử của F[i] so sánh với phần tử cuối của Luu[j]
Nếu F[i] )=luu[j] thì Luu]j]:=F[i]; j=j+1
– Tìm kiếm vị trí đầu dãy con: (Dùng tìm kiếm nhị phân)
+Lấy từng phần tử trong Luu[j] so sánh F[i+1]
Nếu Luu[j])=F[i+1] thì lưu vị trí đầu dãy = j
– Lưu vị trí đầu và cuối dãy con
End;
– In ra vị trí đầu và cuối dãy dài nhất dương

Nguồn: https://surprisedfarmer.com/

Xem thêm bài viết khác: https://surprisedfarmer.com/category/giao-duc

4 thoughts on “CÁCH LÀM ĐỀ THI TUYỂN SINH VÀO LỚP 10 TỈNH HÀ TĨNH | Nguyễn Xuân Hồng IT

Leave a Reply

Your email address will not be published. Required fields are marked *