Tài nguyên dạy học

Hỗ trợ trực tuyến

Điều tra ý kiến

Bạn thấy trang này như thế nào?
Đẹp
Bình thường
Đơn điệu
Ý kiến khác

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Ảnh ngẫu nhiên

    Lv_0_20211112112404.flv DF56A712CF3141DA80F70EF09DEB6F73.jpeg FF6F1482793A4824A1461269CCD7DB5B.jpeg 4109873E4DEA420C9AD131A157E54FB2.png 8318BBB6B9F148BDAE5F03B9DACE302D.png 000C173FA0A84E72A792F97CD36A9AED.png CD_2.jpg CD.jpg CD.jpg CD.jpg Anh_CD.jpg EE5384739BCD4978BB2C2C0592EB6687.jpeg 36F577F5999D4890BD47390569A36C80.jpeg C64B527F5BD84E2C904522C0C31306FC.jpeg 54644281610448DD9BEAD24D11446B3D.jpeg E337B6E0A50D4455BB2CC60035A74A7D.jpeg 6394A2F202D24718869F7782399EB741.jpeg B6DD37088CAD42B983EAB2A28E435BB2.jpeg 5EF2B7559DCB440388B8EDD69C57B32B.png C7A8BF39B8094D8B9FE17B3AC006A8A1.png

    Thành viên trực tuyến

    4 khách và 0 thành viên

    Rèn luyện kỹ năng lập trình cho HSG tin học

    Wait
    • Begin_button
    • Prev_button
    • Play_button
    • Stop_button
    • Next_button
    • End_button
    • 0 / 0
    • Loading_status
    Nhấn vào đây để tải về
    Báo tài liệu có sai sót
    Nhắn tin cho tác giả
    (Tài liệu chưa được thẩm định)
    Nguồn: Sở GD&ĐT Hà Nội
    Người gửi: Bùi Thị Kim Anh
    Ngày gửi: 09h:59' 08-02-2014
    Dung lượng: 818.0 KB
    Số lượt tải: 158
    Số lượt thích: 0 người
    1
    Chuyên đề:
    RÈN LUYỆN KỸ NĂNG LẬP TRÌNH
    Cho HSG tin THCS




    GV: Võ Văn Sửu.
    Nội dung chuyên đề
    I. Rèn luyện PP tìm tòi thuật toán
    II. Rèn luyện phong cách lập trình.
    III. Các dạng toán bồi dưỡng HSG THCS
    2
    I. Rèn luyện PP tìm tòi thuật toán

    1. Tại sao phải rèn luyện cho hs khả năng tìm tòi thuật toán.



    4

    5
    Thuật toán là phần quan trong bậc nhất để tạo nên một chương trình.
    Ở tiểu học, học sinh chưa được làm quen với khái niệm thuật toán. Do vậy khi học lập trình cái khó khăn ban đầu của học sinh chính là tìm thuật toán để giải bài toán đã cho.
    Một học sinh muốn tiến sâu, tiến xa trong tương lai phải có tư duy thuật toán tốt.

    6
    Làm quen và rèn luyện tư duy thuật toán cho học sinh mới bắt đầu học lập trình là một yêu cầu thiết yếu.

    Không nên vội vàng cho học sinh làm việc trên máy tính luôn khi mới bắt đầu học.

    7
    Xác định bài toán

    Xác định INPUT và OUTPUT của bài toán.
    Đặc tả mô hình toán học của bài toán.




    3. Tìm thuật toán
    8

    Ở THCS nên sử dụng cách trình bày thuật toán bằng SĐK.
    Khai thác ví dụ, hiểu ví dụ đã có và tìm các ví dụ khác.
    Trình bày thuật toán từ tổng thể đến chi tiết
    ( phương pháp min dần)
    Ví dụ: Kiểm tra số n có nguyên tố?
    Phương án thô:
    9
    Nhập n
    Có ước
    Thực sự
    n
    N không
    NT
    N là sô
    NT
    +
    -

    KT

    Phương án mịn bước 1.
    Đếm số ước của n
    10
    i:=0; d:=0
    i:=i+1
    n mod i=0
    d:=d+1
    I >=n
    D=2
    N khgnt
    N nt
    Nhập n
    -
    +
    +
    -
    +
    -
    Phương án mịn 2:
    Duyệt nếu có ước trong khoảng từ
    2 đến căn n thì n không phải NT
    P:=Trunc(Sqrt(n))
    OK: Biến Boolean;
    11
    N
    Ok:=N>1
    i:=1
    i:=i+1
    N modi=o
    Ok:=False
    I > p
    Ok=true
    N NT
    N kg NT
    +
    -
    +
    -
    +
    --
    4. Giải một bài, gợi ý nhiều bài.
    Có nhiều bài toán tuy phát biểu khác nhau nhưng cùng thuật toán, cùng cách giải.

    Khi ra và hướng dẫn HSG giải một bài tập, phải chỉ cho họ biết nhiều bài toán khác có các giải hoàn toàn tương tự
    12
    Ví dụ:
    Cho dãy các phần tử a1, a2,…, an
    Yêu cầu tìm số lớn nhất.
    TT: +max:=a1;
    + For i:=1 to n do
    if max< ai then max:=ai
    Nhận xét TT bài này có dạng:
    + Khởi tạo giá trị ban đầu
    + Duyệt, lưu lại giá trị tối ưu hơn.
    13
    Cho học sinh đề xuất các bài toán tương tự và cách giải: Cho dãy số nguyên ai
    + Tìm ai mà tổng chữ số của nó là lớn nhất.
    + Tìm số nguyên tố lớn nhất trong dãy.
    + Tìm số ai có nhiều chữ số nhất
    + Tìm 3 số liên tiếp có tổng lớn nhất…
    + Tìm 2 chỉ số i≠ j để ai+aj max
    + Tìm đoạn nhiều nhất các số liên tiếp bằng nhau
    + Tìm đoạn các số liên tiếp mà tổng max
    + Tìm số ai có tổng chữ số đầu và cuối max
    …..
    14
    II. Rèn luyện phong cách lập trình.
    .


    CHƯƠNG TRÌNH=TT+CTDL+NTLT
    15
    Tuân theo các quy chuẩn, các quy ước.
    Cách trình bày rõ ràng, sáng sủa nổi bật được cấu trúc logic của chương trình.
    Người dùng dễ đọc, dễ hiểu nó.
    16
    Lợi ích của việc trình bày cẩn thận:

    Thể hiện tốt cấu trúc lôgic của mã lệnh
    Cải thiện khả năng đọc
    Bảo đảm sự chính xác trong các thay đổi
    Các lợi ích hệ quả của các lợi ích trên
    + Chương trình ít mắc lỗi và dễ sửa
    chữa khi mắc lỗi.
    + Tăng khả năng làm việc theo nhóm,
    17
    1. Quy ước về cách đặt tên cho các
    định danh.
    a) Đặt tên cho biến.

    Tên biến nên thể hiện được ý nghĩa: thông thường các biến nguyên như i, j, k, n dùng làm biến lặp; x, y dùng làm biến tọa độ…
    Biến lưu trữ nên đặt tên gợi nhớ.
    18
    19

    b) Đặt tên hằng: Tất cả các ký tự nên viết hoa.

    Ví dụ: Const MAXN = 10000;
    INPUT = ‘Baitap.inp’;
    OUTPUT = ‘Baitap.out’;
    c) Đặt tên cho chương trình con:
    Tên chương trình con thường bắt đầu bằng chữ hoa. Vì chương trình con thường thực hiện một chức năng nào đó nên tên hay bắt đầu bằng động từ.
    Ví dụ: TimMax( ); GetNum( );
    2. Phong cách viết mã nguồn

    a) Trình bày tổng thể chương trình:
    Chương trình nên tách thành nhiều đơn thể, mỗi đơn thể thực hiện một công việc, (chương trình con).
    Nên sử dụng các tham số khi truyền thông tin cho các chương trình con. Tránh sử dụng các biến toàn cục để truyền thông tin giữa các chương trình con.
    20
    Cách trình bày chương trình phải nhất quán dễ đọc, dễ hiểu.
    Tính đơn giản, rõ ràng.
    Văn bản chương trình không trườn ra khỏi màn hình
    Thứ tự: khai báo đơn vị, khai báo
    hằng, khai báo kiểu, khai báo biến toàn
    cục, khai báo chương trình con.
    Không nên sử dụng Goto vì sẽ phá vỡ tính tuần tự khi thực hiện chương trình.
    21
    b) Quy tắc trình bày dòng lệnh

    Mỗi câu lệnh nên được đặt riêng trên một dòng để chương trình dễ đọc và dễ quan sát cách thực hiên khi dùng watch để tìm lỗi.
    Sử dụng tab để canh lề chương trình (các lệnh ngang cấp thì phải tab vào như nhau): Điều này sẽ giúp chương trình rõ ràng và dễ quản lý.
    22
    Ví dụ:
    Không nên
    For i := 1 to n do Begin Lệnh1;
    Lệnh2;
    End;
    Nên
    For i := 1 to n do
    Begin
    Lệnh1;
    Lệnh2;
    End;
    23
    c) Sử dụng khoảng trắng:
    Khó đọc
    If (aa:=b*c
    TimMax(a,b,c);
    Dễ đọc
    If ( a < c ) and ( c mod 2 = 0 ) then d := a + c;
    a := b * c;
    TimMax(a, b, c);
    24
    d) Nên định nghĩa hằng:
    Không nên
    ……………
    For i := 1 to 100 do A[i] := Random(100);
    While i<=100 do…
    Nên
    Const MAXN = 100;
    ……..
    For i :=1 to MAXN do
    A[i] :=Random(MAXN)
    While i <= MAXN do …..
    25
    Không nên:
    …..
    Assign(f, ‘Bai1.inp’);
    Reset(f);
    ….
    Assign(f,’Bai1.out’);
    …..
    Nên:
    Const fi=‘Bai1.inp’;
    fo=‘Bai1.out’;
    …..
    Assign(f, fi);
    Reset(f)
    ….
    Assign(f,fo);
    …..
    26
    e) Dùng biến, chú thích
    Biến chạy i, j…phải dùng biến địa phương
    Cách đặt tên biến phải gợi nhớ,
    Viết chú thích cho chương trình: Biến, hàm khi định nghĩa nên viết chú thích ý nghĩa. Chú thích ngắn gọn nhưng đầy đủ và dễ hiểu.
    Ví dụ: Var iCount : Integer; { đếm số cách thực hiện}
    Procedure Try( i: Integer); {Tìm từ I }
    27

    3. Tối ưu sự thực thi mã nguồn

    Không nên
    If b * b – 4 * a * c >0 then
    Begin
    x1 := (-b +sqrt( b * b – 4* a* c)) / (2 * a);
    x2 := (-b – sqrt(b * b – 4* a* c)) / (2* a);
    end;
     
    28
    Nên

    Delta := b * b – 4 * a * c
    If delta >0 then
    Begin
    Delta:=sqrt(delta);
    x1 := (-b + delta) / (2 * a);
    x2 := (-b – delta) / (2 * a);
    End;
    29

    Kết thúc vòng lặp sớm nhất có thể


    Không nên
    bkt := true; {n không có ước thực sự}
    For i := 2 to n-1 do
    If n mod i = 0 then
    bkt := False;

    Nên
    bkt := true;
    For i := 2 to n-1 do
    If n mod i = 0 then
    Begin
    bkt := False;
    Break;
    End;
    30
    Nhiều kết quả xử lý ngay khi nhập liệu

    Không nên

    For i := 1 to n do readln(f, a[i]);
    For i:=1 to n do s := s+a[i];


    Nên

    For i := 1 to n do
    Begin readln(f, a[i]);
    s := s+a[i];
    end;
    31
    Hạn chế lệnh rẽ nhánh
    Không nên

    If x > y then d:=True else d:= False;
    Nên
    d := x>y;
    32
    4. Kiểm nghiệm chương trình với các bộ test đầy đủ nhất.

    Test đầu bài,
    Các test đơn giản
    Test các trường hợp đặc biệt.
    Test lớn
    33

    II. Các dạng toán bồi dưỡng HSG THCS


    Nhóm các bài toán số học:
    Nhóm các bài toán thao tác trên mảng
    Nhóm các bài toán xử lý xâu .
    Các bài toán khác.
    34
    1. Các bài toán số học.

    Để giải các bài toán về số học giáo viên cần cho học sình ứng dụng nhuần nhuyễn các kiến thức số học ở THCS chủ yếu dựa vào 2 phép toán DIV, MOD
    35
    Thuật toán tìm UCLN
    Cho 2 số nguyên m, n>0 . UCLN(m,n)=?

    Thuật toán 1: Sử dụng phép trừ liên tục cho đến khi 2 số bằng nhau:
    + Nhập m, n
    + While m<>n do
    If m>n then m:=m-n
    Else n:=n-m;
    +UCNN:=n;
    36
    Thuật toán 2: (Đối với HSG nên hướng các em sử dụng thuật toán này)
    + Nhập m, n
    + While n <> 0 do
    Begin
    r:= m mod n
    m:=n;
    n:=r;
    End;
    +UCLN:=m
    37
    So sánh 2 thuật toán:
    Với m=1000000000, n=1.
    Thuật toán 1 thực hiện 1000000000 thao tác mới cho UCLN=1
    Thuật toán 2 chỉ thực hiện 3 thao tác đã cho UCLN=1.
    38
    Hàm kiểm tra số nguyên tố.
    FUNCTION Ngto(P:Integer): Boolean;
    Var NT: Boolean; I: integer;
    Begin
    NT:=P>1;
    For i:=2 to Trunc(Sqrt(P)) do
    If P mod i =0 then
    Begin NT:=False; Break End;
    Ngto:=NT;
    End;
    39
    Hàm tính tổng các chữ số
    Function TongCS(n: Integer): Integer;
    Var s, m:Integer;
    Begin
    m:=n; s:=0;
    While m<>0 do
    Begin
    s:=s+ m mod 10; m:=m div 10;
    End;
    TongCS:=s;
    40
    Một số bài tập.
    Bài 1. Phân tích ra thừa số nguyên tố
    Thuật toán:
    If Ngto(n) then writeln(n) Else
    Begin m:=n;
    For p:=2 to n div 2 do If Ngto(p) then
    Begin
    While m mod p = 0 do write(p,’.’);
    m:= m div p;
    End;
    End;
     

    41
    Bài 2. Rút gọn phân số.
    Đề bài: Cho phân số a/ b
    (a, b nguyên, b>0). Tìm c, d nguyên (d>0)
    sao cho c/ d tối giản và a/b=c/d
    + Thuật toán:
    Dau:=1; If a<0 then dau:=-1 ; a:=abs(a);
    c:=a div UCLN(a,b);
    d:=b div UCLN(a, b);
    Writeln(dau*c,’/ ‘, d);
    42
    Bài 3. Giai thừa.

    Cho số tự nhiên n. P=n!. Hỏi:
    a/ P có bao nhiêu chữ số không tận cùng.
    b/ Số khác 0 tận cùng của P là chứ số nào.
    43
    ?
    44


    a/ Số chữ số 0 cuối cùng chính là số ước bằng 10 của P! mà p!=a.10k=a.2k.5k.

    Do số ước 2 nhiều hơn ước 5, nên số 0 tận cùng là số ước 5 của P. Vậy ta cần tính số lượng ước 5 của P !

    45
    Gọi S5 là số lượng ước 5 của P. S5 ?
    ?
    ?
    46
    47
    Thuật toán a)
    Goi S5 là số ước 5 của P
    s5:=0;
    For m:=5 to n do
    Begin
    K:=m;
    While k mod 5 = 0 do
    Begin Inc(s5); k:=k div 5 End;
    End;
    In ra kết quả : S5.
    b) Câu này dễ mắc sai lầm vừa nhân vừa xóa 0 cuối và chỉ giữ lại chữ số khác 0 cuối cùng.
    + Thuật toán:
    - Xóa hết ước 2 (số lượng S2) và ước 5 (số lượng S5). Gọi k=S2-S5
    - Nhân các số còn lại được số p (các phép toán chỉ giữ chữ số cuối)
    Tính a=2k . a*p là đáp số
    48
    S2:=0; S5:=0; P:=1;
    For m:=2 to n do
    Begin
    K:=m;
    While K mod 2 = 0 do Begin inc(so2),
    k:= k div 2 End;
    While K mod 5 = 0 do Begin inc(so5),
    k:= k div 5 End;
    P:=P* K mod 10.
    End.
    For i:= 1 to so2-so5 do P*2 mod 10
    49
    Bài 4. Tính tổng chữ số.
    (Đề thi HSG thành phố Hà nội)

    Một quyển sách có n trang. Hỏi
    a/ Tổng tất các chữ số đã ghi trên các trang sách.
    b/ Mỗi chữ số xuất hiện bao nhiêu lần.

    50
    Thuật toán :
    + Lập hàm TongCS(K) để tính tổng các chữ số trong K
    + Dùng mảng a[0], a[1],…,a[9], trong đó a[i] số lần xuất hiện của chữ số i:
    + Khởi tạo
    Nhập n;
    Sum:=0; fillchar(a, sizeof(a),0);
    51
    For m:=1 to n do
    Begin
    K:=m;
    Sum:=Sum+TongCS(K);
    While K <> 0 do
    Begin
    Inc( a[ k mod 10])
    K:=K div 10
    End;
    In ra kết quả: Sum, a[0],…, a[9]
    52
    Anh / Chị hãy phát biểu một bài toán có cùng các giải.
    53

    Bài 5. Số siêu nguyên tố.


    Đề bài :Số P gọi lầ số siêu nguyên tố, nếu
    nó nguyên tố và khi ta lần lượt bỏ các chữ
    số ở hàng đơn vị từ tái qua phải thì số mới
    nhận được vẫn là một số nguyên tố.
    Ví dụ: 239 là số siêu nguyên tố vì 239 là số nguyên tố và 23, 2 cũng là các số nguyên tố , còn 431 không phải là số siêu nguyên tố. Cho một số n (054
    ???
    55
    Phương án 1: Duyệt toàn bộ:
    + Tìm số nhỏ nhất lớn nhất có n chữ số
    Chẳng hạn với n=3 thì số nhỏ nhất và lớn nhất có 3 chữ số là: n1=100 và n2=999
    + Dùng một biến chạy p:
    For p:= n1 to n2 do
    If p thỏa mãn then tăng biến đếm.
    + Thuật toán này cũng được 40 % số test
    56
    Suy nghĩ thêm về ví dụ:
    + Khi n=1 thì các số 2, 3 , 5, 7 là số nguyên tố => có 4 số siêu nguyên tố có 1 chữ số
    + Khi n=2 thì có các số siêu nguyên tố có 2 chữ số: 23, 29, 31, 37, 53, 59, 71, 73, 79
    Do đó xuất phát từ số siêu nguyên tố có 1 chữ số (2, 3, 5, 7) ta ghép với các số 1, 3, 7, 9 để tìm ra các số siêu NT có 2 cs (23,29, 31, 37, 53, 59, 71,73, 79).
    Lại xuất phát từ các số siêu NT có 2 cs rồi ghép với 1,3, 7 9 ta tính được số siêu NT có 3 chữ số…
    57
    58
    Thuật toán tốt.
    +If n=1 thì a[1]:=2;[2]:=3; a[3]:=5, a[4]:=7; slg:=4
    + If n>1 then
    Begin c[1]:=1; c[2]:=3; c[3]:=7; c[4]:=9;scs:=1;
    Repeat inc(scs); tg:=0; fillchar(b, sizeof(b),0)
    For k:=1 to slg do For g:=1 to 4 do
    Begin if NT(a[k]*10+c[g]) then
    Begin inc(tg); b[tg]:= NT(a[k]*10+c[g]) End
    End;
    a:=b;Slg:=tg; tg:=0;
    Until scs=n.
    End; {kết quả là Slg}
    59
    Anh/Chị hãy phát biểu một bài toán mà có thể áp dụng thuật toán vừa trình bày.
    60
    Ta có thể nêu các bài toán tương tự sau:
    Số n gọi là số SNT phải nếu n là NT và khi ta lần lượt bỏ đi các chữ số bên trái thì số còn lại vẫn là một số nguyên tố.
    Vd: n=317 là SNT phải vì 317 , 17 , 7 là các số NT
    Yêu cầu cho N đếm số lượng SNT phải có N chữ số.
    Gọi số SNT như trong bài 5 là số SNT trái, còn N gọi là SNT nếu nó vừa siêu NT trái vừa SNT phải. Tính số lượng các SNT có n cs.
    61
    2. Nhóm các bài toán mảng.
    Trong phần này gv cần cung cấp cho học sinh một số kỹ năng cơ bản khi thao tác trên mảng như:
    Tìm phần tử MAX, MIN.
    Sắp xếp dãy.
    Kiểm tra tinh đơn điệu của dãy.
    Tìm kiếm trên dãy…
    62
    Bài 1. Tìm tổng max


    Đề bài: Cho dãy n số nguyên dương a1, a2,…an. Hãy tìm 2 số ai, aj, sao cho i≠j và ai+aj đạt max.
    63
    ???
    64
    Thuật toán 1: Duyệt toàn bộ:
    + Max:=a1+a2;// Khởi tạo giá trị ban đầu
    + For i:=1 to n-1 do
    For j:=i+1 to n do
    If Max
    Thuật toán này có độ phức tạp O(n2)
    Khi n=10000, thuật toán không hiệu quả
    65
    Thuật toán 2 : Sắp xếp
    + Sắp xếp giảm dần a1, a2, a3,….
    +Max:=a1+a2.
    Độ phức tạp của TT này là O(n2). Tuy nhiên học sinh biết PP sắp xếp nhanh thì tốc độ xử lý tốt hơn (O(nlogn))
    66
    Tốt hơn được không?
    ???
    67

    Thuật toán 3. Tìm số lớn thứ nhất thứ nhì
    + maxi:=1; for I:=2 to n do if maxi+maxj:=1;
    for I:=2 to n do if maxjĐáp số : m+a[maxj]
    68
    ?
    69
    Thuật toán 4. (Xử lý luôn khi đọc dữ liệu)
    +Readl(f,n) {n >1}; Read (f, a,b);
    {gọi max1, max2 là số lớn và bé trong a,b}
    +If a>b then Begin max1:=a; max2:=b End
    Else Begin max1:=b; max2:=a End
    + For i:=3 to n do
    Begin
    Read(f, c);
    If c>= max1 then
    Begin max2:=max1; max1:=c End
    Else If c>= max2 then max2:=c;
    End; { Đáp số là max1+max2
    70

    Anh /Chị hãy phát biểu bài toán tương tự …và trình bày thuật toán giải nó.
    .
    71

    Bài toán cho tổng 3 số.
    Tìm tổng max của ai+ aj + ak (I, j, k khác nhau).
    Cho hs trình bày các thuật toán tương tự và đánh giá hiệu quả các thuật toán.
    72
    Bài 2. Dãy đối xứng
    Đề bài.
    Dãy a1, a2, …,an gọi là dãy đối xứng nếu a1=an, a2= an-1,….
    Cho dãy a1, a2, …,an . Hãy tìm các ghi tiếp vào dãy một số ít nhất câc phần tử để dãy nhận được là đối xứng.
    Ví dụ: Dãy 1 2 1 2 2 thì cần thêm 1 2 1
    73
    ?
    74
    Phân tích:
    Số phần tử thêm vào ít nhất nếu đoạn sau cùng tạo thành đoạn đối xứng là lớn nhất.
    Thuật toán:
    + Tìm I nhỏ nhất sao cho ai, ai+1,…, an đx
    + Thêm tiếp vào phía sau: ai-1. ai-2,…a1.
    75
    Cài đặt:
    +Lập hàm DX(l, r:integer): boolean;
    DX:=True; g:=(l+r) div 2;
    For i:=l to g do if a[i] <> a[l*r-i] then
    DX:=Fase;
    + Tìm h nhỏ nhất mà DX(h, n)
    for h:=1 to n do if DX( h, n) then Break;
    + Số phần tử cần thêm h-1;
    For i:=h-1 to 1 do write(a[i],’ ‘);

    76
    Bài 3. Bao nhiêu điểm
    Đề bài: .
    Trong một cuộc thi đấu thể thao n người tham gia . Người thứ I có điểm là ai . Biết rằng có đủ các giải nhất ,nhì, ba và những người có điểm ngang nhau có giải như nhau và ngược lại. An được giảI 3. Hỏi số điểm của An là bao nhiêu.
    Ví dụ: Input n=6, a: 10 9 1 7 3 10 7
    Output: 7


    77
    ?
    78
    Thuật toán:
    +sắp xếp giảm dần
    +i:=1;
    + While a[i+1]=a[i] do i:=i+1;
    + i:=i+1;
    +While a[i+1]=a[i] do i:=i+1;
    Đáp số : a[i+1]
    79
    Có thuật toán tốt hơn ?.

    + Tìm max1 (O(n))
    + Tìm max2< max1 (O(n))
    + Tìm max3< max2 (O(n))

    80

    Hãy phát biểu mở
    rộng bài toán!
    81
    Bài toán tổng quát:
    Cho dãy n các số nguyên dương. Biết rằng trong dãy tồn tại k giá trị khác nhau.
    Hỏi khi sắp theo thứ tự giảm dần thì phần tử lớn thứ k bằng bao nhiêu? (k=3 là trường hợp bài toán trên)
    82
    Bài 4. Dãy số Fibonacci
    Đề bài . Cho dãy sô Fibonacci 1, 1, 2, 3, 5….Ta thành lập dãy số mới bằng cách lần lượt thay mỗi số hạng bằng số dư của số hạng đó khi chia cho 100.
    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
    Dãy số mới nhận được sau khi thay là:
    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 44, 33
    Số hạng thứ n trong dãy mới là số nào?
    Có bao nhiêu giá trị khác nhau trong dãy số mới?
    83
    ???
    84
    Thuật toán (lùa bò vào chuồng)
    +Dùng mảng : a[0], a[1], a[2],…, a[99];
    A[i]=0 nếu I không xuất hiện trong dãy rút gọn), a[i]=1 nếu I xuất hiện trong dãy.
    + If (n=1) or (n=2) then writeln (1,’ ‘, 1);
    Else Begin a:=1; b:=1; d:=2;
    Repeat Inc(d);
    I c:=(a+b) mod 100; a:=b;b: =c;
    If a[c] =0 then a[c]:=1;
    Until d=n;
    End; {In ra C, a[0]+a[1]+…+a[99]}

    85
    5. Dãy tăng
    Cho một dãy các số nguyên a1, a2, …an.
    Yêu cầu: Hãy cho biết:
    a) Dãy có tăng hay giảm?
    b) Tìm một đoạn dài nhất các phần tử liên tục tăng.
    c) Tìm một đoạn dài nhất các phần tử liên tục giống nhau.
    86
    6. Tìm UCLN, BCNN của dãy
    Đề bài: Cho dãy số nguyên dương a1, a2, .., an. Hãy tìm UCLN, BCNN của dãy
    87
    3. Nhóm các bài toán xử lý xâu

    Để giải các bài toán về xâu cần cho học sinh nắm vững các hàm, thủ tục xử lý xâu như hàm COPY(), LENGTH(), INSERT(), STR() , VAL()…
    88
    Bài 1. Tìm số
    (Đề thi HSG Hà nội 2011)
    Đề bài:
    Cho một xâu S, trong đó có chứa một số cụm số. Không có quá 6 chữ số liên tuc trong S.
    Hãy tìm xâu con của S, biểu diễn một số nguyên tố lớn nhất.
    Ví dụ S = ‘tesst1234#password5426’. Số cần tìm là 23.
     
    89
    ???
    90
    Thuật toán 1: Giả sử xâu đã cho là S,
    + Tạo mảng so[1], so[2],,,lần lượt copy được từ các cụm số trong S
    +Với mỗi s[i] dùng 2 biến chạy l, r để tách ra một xâu con của so[i] từ vị trí l đến vị trí j và lưu lại số NT max trong so[i] rồi số sánh với các số nguyên tố trong so[j] khác.
    91
    Ví dụ S = ‘tesst1234#password5426’.
    So[1]=234; So[2]=5426;
    Số nguyên tố lớn nhất trong So[1] là 23.
    Số nguyên tố lớn nhất trong So[2] là 5
    Vậy đáp số là 23.
    92
    Thuật toán 2. (không lưu mảng các số)
    Khởi tạo: S:= ‘ ‘+S+ ‘ ‘; SoNgtmax:=-1
    For i:=2 to length(s) do if (S[i] in [0..9]) and
    S[i-1] not in [0..9] then begin j:=I; repeat
    inc(j) until not S[j] in [0..9] or (j> length(s));
    so:=copy(S, I, j-i)
    If SoNgtmax< max(so) then
    SoNgtmax:=max(so);
    End;
    { Function max(so: string[9]): integer, cho số NT max trong xâu so}
    93
    Có bài toán tương tự nào không?

    94
    Bài 2. Sắp xếp số
    Cho xâu S chỉ gồm các chữ cái tiếng anh thường và chữ số. Các chữ số kế tiếp nhau trong S tạo thành một số tự nhiên .
    Yêu cầu: Sắp xếp tăng dần các số trong xâu. Các kí tự khác giữ nguyên thứ tự. Giả thiết mỗi xâu con của S có không quá 6 chữ số liên tục.
    Ví dụ: Input: t994a0046ui00t148x
    Output:t0a46ui148t994x

     
    Thuật toán: S= t994a0046ui00t148x
    + Tách số và chèn dấu * vào vị trí số:
    so[1]=994, so[2]=0046, s0[3]=00, so[4]= 148
    S=t*a*ui*t*x
    + Chuẩn và sắp sếp tăng:
    so[1]=0, so[2]=46, so[3]=148, so[4]= 994
    + Lần lượt thay dấu * bởi so[1], so[2],…
    => S=t0a46ui148t994x
    96
    ?Anh / chi hãy phát biểu vài bài toán có cùng các giải.
    97
    3. Mật khẩu
    Cho trước một xâu S bao gồm chữ cái hoa, chữ cái thường và chữ số.
    Yêu cầu:
    Chọn một xâu con (gồm các ký tự liên tục) của S có độ dài ngắn nhất sao cho xâu con vừa chọn có thể dùng làm một mật khẩu an toàn
    ( nghĩa là trong xâu con đó có đủ 3 loại chữ cái in, chữ cái thường , chữ số và đô dài mk ≥ 6).
    Ví dụ: Input: Asdgcdh5rghvh4c
    Output: Asdgcdh5
    98
    Thuật toán
    Đây là bài toán đơn giản:
    Luui:=1; luuj:=length(s)
    For i:=1 to length(s)-5 do
    For j:=i+5 to length(s) do
    Begin x:=copy(s,I, j-i+1);
    If OK(x) then if j-i+1=6 then
    begin luui:=i; luuj:=j Break; End
    else Capnhat( luui, luuj)
    End;
    99
    ?Anh/ Chi hãy phát biểu bài toán mới!
    100
    4. Vòng xuyến.
    Đề bài: Một vòng xuyến có n (n<=100) hạt cườm. Mỗi hạt cườm có một trong 3 màu B (xanh) , R (đỏ), Y (vàng). Một số hạt maù trắng (W).
    Yêu cầu : Hãy tô một số hạt màu trắng thành màu B, R, hoặc Y để trên vòng xuyến có số hạt cùng màu là nhiều nhất.
    Ví dụ S=WRBBBWWYYRWRW. Ta tô W-> R
    khi đó S=RRBBRRYYRRRR. Đ/s 6
    101
    Thuật toán
    + Nhân đôi S:=S+S;
    + Bước1: Tô tất hạt W thành B. Tìm đoạn dài nhất các phần tử màu B liên tục (S1)
    + Bước 2: Tô tất cả các hạt W thành R và tìm đoạn dài nhất màu R (S2)
    + Bước 3 : Tô tất cả các hạt W thành Y và tìm đoạn dài nhất màu R. (S3)
    + Bước 4: So sánh S1 ,S2, S3  kết quả.
    102
    Tóm tắt:
    Khi bắt đầu giảng dạy môn thuật toán và lập trình cho học sinh THCS, GV cần :
    Rèn luyện tư duy thuật toán tốt cho HS
    Rèn luyện cách trình bày một chương trình.
    Rèn luyện tính sáng tạo, chặt chẽ, tối ưu.


    103
    Chúc anh/chị có nhiều sáng tạo trong giảng dạy môn lập trình.

    GV: VÕ VĂN SỬU
    104
     
    Gửi ý kiến