PHƯƠNG PHÁP BỒI DƯỠNG
HỌC SINH GIỎI MÔN TIN HỌC PHẦN 1
Chủ đề : CHƯƠNG TRÌNH = CẤU TRÚC DỮ LIỆU + GIẢI THUẬT
Phần 1: Cấu trúc dữ liệu và giải thuật:
+Các loại Cấu trúc dữ liệu: Bao gồm cơ bản và nâng cao.
-Cấu trúc dữ liệu cơ bản: Kiểu mảng, kiểu xâu, kiểu mẫu tin, kiểu tập tin, …
+Các loại giải thuật: Gồm giải thuật tìm kiếm đơn giản và nâng cao.
-Các giải thuật đơn giản: Sắp xếp, tìm kiếm.
-Các thuật toán nâng cao: Tham lam, phương pháp sinh, quay lui, nhánh cận, quy hoạch động, các giải thuật trên đồ thị, hình học, trò chơi.
+Các cấu trúc câu lệnh:
-Cấu trúc tuần tự, rẽ nhánh, lặp, điều khiển (halt, exit, break, continue).
Phần 2: Phương pháp giải một bài toán tin:
+Cấu trúc của một chương trình.
Program <Tên chuong trinh>;
<khai báo thư viện>;
<khai báo hằng>;
<khai báo kiểu>;
<khai báo biến>
<chương trình con>; {Nhập, xử lý, xuất, …}
BEGIN
<các câu lệnh trong CT chính>;
END.
+Các bước giải bài toán tin.
- Xác định bài toán
Input ® Process ® Output
(Dữ liệu vào ® Xử lý ® Kết quả ra)
- Chọn cấu trúc dữ liệu:
- Tìm thuật toán:
-Lập trình:
-Kiểm thử:
Chạy thử và tìm lỗi
Xây dựng các bộ test
Phần 3: Các bài toán đơn giản:
Bài 1: Tìm giá trị lớn nhất.
Cho một bảng số kích thước nxn, giá trị các phần tử của bảng là các số nguyên dương bất kỳ (n<=100) . Tìm giá trị lớn nhất trong bảng số trên.
Dữ liệu vào: cho trong file max.inp gồm:
Dòng 1 là số nguyên dương n.
N dòng tiếp theo mỗi dòng gồm n số nguyên dương.
Dữ liệu ra: ghi vào file max.out gồm:
-Bảng số n hàng, n cột.
-Dòng cuối cùng ghi số có giá trị lớn nhất tìm được (Nếu có nhiều hơn một số là giá trị lớn nhất thì chỉ lấy 1 trong các số đó) .
ví dụ:
max.inp
|
max.out
|
3
2 4 5
3 2 7
4 7 8
|
2 4 5
3 2 7
4 7 8
8
|
-Phân tích bài toán:
+Input: Là một số nguyên n và một bảng số nguyên dương n hàng, n cột.
+Output: Là một số có giá trị lớn nhất trong bảng số đã cho.
-Cấu trúc dữ liệu: Dùng mảng 2 chiều để lưu bảng số, và 2 file nhập, xuất.
-Giải thuật: Với bài này ta có 2 cách để giải quyết như sau:
Cách 1: Ta cho max bằng phần tử đầu tiên rồi so sánh max với các phần tử còn lại, nếu max<a[I,j] thì max=a[I,j].
Cách 2: Sắp xếp mảng tăng hoặc giảm, nếu tăng thì giá trị max chính là phần tử cuối cùng, nếu giảm thì max chính là phần tử đầu tiên.
-Chương trình tham khảo:
Program tim_max;
Const fi=’max.inp’;
fo=’max.out’;
Var n,max: word;
A:array[1..100,1..100] of byte;
Procedure nhap;
Var I,j: byte; f:text;
Begin
Assign(f, fi); reset(f);
Readln(f,n);
For i:= 1 to n do
begin
For j:=1 to n do
Read(f,a[I,j]);
Readln(f);
End;
Close(f);
End;
Procedure xuly;
Var I,j : byte;
Begin
Max:=a[1,1];
For i:=1 to n do
For j:=1 to n do
If max<a[I,j] then max:=a[I,j];
End;
Procedure xuat;
Var I,j: byte; f: text;
Begin
Assign(f,fo); rewrite(f);
For i:=1 to n do
begin
For j:=1 to n do
Write(f,a[I,j],’ ‘);
Writeln(f);
End;
Writeln(f,max);
Close(f);
End;
BEGIN
Nhap;
Xuly;
Xuat;
END.
Bài 2: Tìm giá trị nhỏ nhất.
Cho một bảng số kích thước nxn, giá trị các phần tử của bảng là các số nguyên dương bất kỳ (n<=100) . Tìm giá trị lớn nhất trong bảng số trên.
Dữ liệu vào: cho trong file min.inp gồm:
Dòng 1 là số nguyên dương n.
N dòng tiếp theo mỗi dòng gồm n số nguyên dương.
Dữ liệu ra: ghi vào file min.out gồm:
-Bảng số n hàng, n cột.
-Dòng cuối cùng ghi số có giá trị nhỏ nhất tìm được (Nếu có nhiều hơn một số là giá trị nhỏ nhất thì chỉ lấy 1 trong các số đó) .
ví dụ:
min.inp
|
min.out
|
3
2 4 5
3 2 7
4 7 8
|
2 4 5
3 2 7
4 7 8
2
|
Bài 3: Đếm số lượng.
Cho một bảng số kích thước nxn, giá trị các phần tử của bảng là các số nguyên bất kỳ (n<=100) . đếm số lượng phần tử có giá trị âm, số lượng phần tử có giá lớn hơn hoặc bằng 0.
Dữ liệu vào: cho trong file soluong.inp gồm:
Dòng 1 là số nguyên dương n.
N dòng tiếp theo mỗi dòng gồm n số nguyên dương.
Dữ liệu ra: ghi vào file soluong.out gồm:
-Bảng số n hàng, n cột.
-Dòng tiếp theo là một số chỉ số lượng các phần tử có giá trị âm.
-Dòng cuối cùng là một số chỉ số lượng các phần tử có giá trị lớn hơn hoặc bằng 0.
ví dụ:
soluong.inp
|
soluong.out
|
3
-2 4 5
1 2 -7
4 7 8
|
-2 4 5
1 2 -7 4 7 8 So luong so am=2
So luong so duong=7
|
Bài 4: Tính tổng.
Cho một bảng số kích thước nxn, giá trị các phần tử của bảng là các số nguyên dương bất kỳ (n<=100) . Tính tổng các số trong bảng trên.
Dữ liệu vào: cho trong file tong.inp gồm:
Dòng 1 là số nguyên dương n.
N dòng tiếp theo mỗi dòng gồm n số nguyên dương.
Dữ liệu ra: ghi vào file tong.out gồm:
-Bảng số n hàng, n cột.
-Dòng cuối cùng ghi số nguyên là tổng của các số trong bảng.
ví dụ:
tong.inp
|
tong.out
|
3
2 4 5
3 2 7
4 7 8
|
2 4 5
3 2 7
4 7 8
42
|
Bài 5: Số nguyên tố:
Cho một mảng 2 chiều kích thước nxn (n<=50). mà giá trị các phần tử của mảng là số nguyên dương m bất kỳ (m<=100) . Tìm tất cả các số nguyên tố trong mảng đã cho. Nếu không tồn tại số nguyên tố nào thì thông báo: ‘khong tim thay’.
Dữ liệu vào: cho trong file nguyento.inp gồm:
Dòng 1 là số nguyên dương n.
N dòng tiếp theo mỗi dòng gồm n số nguyên dương.
Dữ liệu ra: ghi vào file nguyento.out gồm:
Dòng 1 ghi số lượng các số nguyên tố tìm được.
Các dòng tiếp theo ghi các số nguyên tố tìm được.
ví dụ:
nguyento.inp
|
nguyento.out
|
3
2 4 5
3 2 7
4 7 8
|
6
2 5 3 2 7 7
|
Chương trình:
program so_nguyen_to;
const fi='nguyento.inp';
fo='nguyento.out';
var n,m,i,j:byte;
a:array[1..50,1..50]of byte;
procedure nhap;
var f:text;
begin
assign(f,fi);reset(f);
readln(f,n);
for i:=1 to n do
begin
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
close(f);
end;
function ok(i:byte):boolean;
var b:boolean; j:byte;
begin
b:=true;
for j:= 2 to i-1 do
if i mod j=0 then begin b:=false; break; end ;
ok:=b;
end;
procedure xuly;
var dem:byte; f:text;
begin
dem:=0;
assign(f,fo); rewrite(f);
for i:=1 to n do
for j:=1 to n do
if ok(a[i,j]) and (a[I,j]>1)then
dem:=dem+1;
if dem>0 then
writeln(f,dem);
for i:=1 to n do
for j:=1 to n do
if ok(a[i,j]) and (a[I,j]>1) then
write(f,a[i,j],' ');
if dem=0 then writeln(f,'khong tim thay');
close(f);
end;
begin
nhap;
xuly;
end.
Bài 6: Kiểm tra chuỗi.
Cho một tập tin văn bản có n dòng (3 ≤ n ≤ 30000), mỗi dòng là một chuỗi s có tối đa 255 ký tự, các ký tự s[i] Î [‘a’,…,’z’] với 1 ≤ i ≤ length(s). Trong đó chỉ có duy nhất một chuỗi s có số lần xuất hiện là một số lẻ, các chuỗi khác có số lần xuất hiện là một số chẵn. Hãy tìm chuỗi s (có số lần xuất hiện là một số lẻ) đó.
Dữ liệu vào: Từ file văn bản CHUOI.INP có cấu trúc như sau:
- Dòng đầu là một số nguyên n.
- n dòng tiếp theo mỗi dòng là một chuỗi ký tự.
Dữ liệu ra: Đưa vào file văn bản CHUOI.OUT chứa chuỗi ký tự tìm được.
Ví dụ:
CHUOI .INP
|
CHUOI .OUT
|
7
ha tien
phu quoc
rach gia
chau thanh
ha tien
chau thanh
phu quoc
|
rach gia
|
Program kiem_tra_chuoi;
const fi='chuoi.inp';
fo='chuoi.out';
max1=250;
max2=128;
var a:array[1..max1,1..max2]of byte;
n,i,j:longint;
s:string;
f,g:text;
procedure nhap;
Begin
fillchar(a,sizeof(a),0);
assign(f,fi); reset(f);
readln(f,n);
close(f);
end;
procedure xuat;
Begin
assign(g,fo); reset(g);
for i:=1 to max1 do
for j:=1 to max2 do
if a[i,j]=1 then write(g,chr(j));
close(g);
end;
procedure xuly;
begin
for i:=1 to n do
begin
readln(f,s);
for j:=1 to length(s) do
if a[j,ord(s[j])]=0 then a[j,ord(s[j])]:=1
else a[j,ord(s[j])]:=0;
end;
end;
begin
nhap;
xuly;
xuat;
end.
Một số bài toán trong đề thi năm trước:
Bài 7: Min- Max.
Cho một bảng số A có kích thước nxn (n ≤ 100).
Mỗi ô của bảng số chứa một số nguyên dương m bất kỳ.
Yêu cầu: Tìm số có giá trị nhỏ nhất và số có giá trị lớn nhất trong bảng số đã cho.
Dữ liệu vào: Từ file văn bản MINMAX.INP gồm:
- Dòng đầu là số nguyên dương n.
- n dòng tiếp theo, mỗi dòng n số nguyên dương (bảng số A).
(các số trên một dòng cách nhau ít nhất một khoảng trắng)
Dữ liệu ra: Đưa vào file văn bản MINMAX.OUT gồm:
- Dòng đầu là số có giá trị nhỏ nhất.
- Dòng thứ 2 là số có giá trị lớn nhất.
Ví dụ:
MINMAX.INP
|
MINMAX.OUT
|
3
2 4 5
3 2 7
4 7 8
|
2
8
|
Bài 8: Giải mã.
Để hiển thị trên màn hình các số hệ thập phân, máy tính có một bộ phận làm nhiệm vụ biến đổi dữ liệu từ hệ nhị phân về hệ thập phân.
Yêu cầu: Cho một dãy nhị phân có độ dài 1 byte (8 bit). Hãy biến đổi 7 bit đầu tiên của dãy nhị phân đó thành số thập phân tương ứng, bit thứ 8 (tận cùng bên trái) dùng để biểu diễn dấu nếu là 1 thì biểu diễn dấu âm, ngược lại thì biểu diễn dấu dương.
Dữ liệu vào: Từ file văn bản GIAIMA.INP gồm: một hoặc nhiều dòng, mỗi dòng là một dãy nhị phân có độ dài 1 byte.
Dữ liệu ra: Đưa vào file văn bản GIAIMA.OUT gồm: một hoặc nhiều dòng, mỗi dòng là một số thập phân tương ứng.
Ví dụ:
GIAIMA.INP
|
GIAIMA.OUT
|
10000111
00011111
|
-7
31
|
Bài 9: Mã hóa.
Để lưu trữ và xử lý các số hệ thập phân, máy tính có một bộ phận làm nhiệm vụ biến đổi dữ liệu từ hệ thập phân về hệ nhị phân.
Yêu cầu: Cho số thập phân n (-127 ≤ n ≤ 127). Hãy biến đổi số thập phân n thành dãy nhị phân tương ứng. Nếu n<0 thì bit thứ 8 (bit tận cùng bên trái) của dãy nhị phân là 1, ngược lại là 0.
Dữ liệu vào: Từ file văn bản MAHOA.INP gồm: một hoặc nhiều dòng, mỗi dòng là một số thập phân.
Dữ liệu ra: Đưa vào file văn bản MAHOA.OUT gồm: một hoặc nhiều dòng, mỗi dòng là một dãy nhị phân tương ứng.
Ví dụ:
MAHOA.INP
|
MAHOA.OUT
|
10
-7
|
00001010
10000111
|
Cho một bảng số A gồm n hàng và m cột (nxm), các phần tử của bảng số A là số nguyên.
Yêu cầu: Sắp xếp các phần tử của bảng số A đã cho theo thứ tự tăng dần từ trái qua phải và từ trên xuống dưới.
Dữ liệu vào: Từ file văn bản SAPXEP.INP gồm:
- Dòng đầu là 2 số nguyên n và m.
- n dòng tiếp theo, mỗi dòng m số nguyên (bảng số A).
Dữ liệu ra: Đưa vào file văn bản SAPXEP.OUT gồm n dòng mỗi dòng có m số nguyên (bảng số A sau khi sắp xếp).
Ví dụ:
SAPXEP.INP
|
SAPXEP.OUT
|
5 8
1 3 9 8 3 2 4 5
5 2 4 1 6 1 7 9
4 3 3 4 1 2 3 2
5 3 8 1 6 3 5 4
8 2 1 2 1 1 3 4
|
1 1 1 1 1 1 1 1
2 2 2 2 2 2 3 3
3 3 3 3 3 3 4 4
4 4 4 4 5 5 5 5
6 6 7 8 8 8 9 9
|
Nhận xét này đã bị tác giả xóa.
Trả lờiXóaa Dân ơi sao thấy thông báo thi học sinh giỏi khối 10-11 năm nay giới hạn nhiều quá. Biết ôn trọng tâm phần nào đây anh!
Trả lờiXóa