Thứ Bảy, 21 tháng 11, 2015

NỘI DUNG TẬP HUẤN GIÁO VIÊN NGÀY 27/11/15

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 1Cấ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ảngkiểu xâukiểu mẫu tinkiể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 2Phươ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ữ liu 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ử:

       Chy thử và tìm li

  Xây dng các b test

Phần 3Cá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 6Kiể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 7Min- 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ầuTì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 8Giả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ầuCho 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 9Mã 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ầuCho 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


Bài 10: Sắp xếp.
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
---Hết---


               

2 nhận xét:

  1. Nhận xét này đã bị tác giả xóa.

    Trả lờiXóa
  2. a 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