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 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

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---