0.3 Mảng  (Page 2/2)

Ý tưởng:

     Dùng thuật toán tìm kiếm tuần tự. So sánh x với từng phần tử của mảng A. Thuật toán dừng lại khi x=A[i] hoặc i>N.

     Nếu x=A[i] thì vị trí cần tìm là i, ngược lại thì kết quả tìm là 0 (không tìmthấy).

Uses Crt;

Type Mang = ARRAY[1..50] Of Integer;

Var  A:Mang;

        N,i,x:Integer;

Function TimKiem(x, N: Integer; A:Mang):Integer;

Var i:Integer;

    Begin

        I:=1;

        While (I<= N) and (X<>A[I]) do I:=I+1;

        If I<= N Then Timkiem:=I  Else Timkiem:=0;

    End;

Begin

    {Nhập mảng}

    Write(‘Nhap N=’); Readln(N);

    For i:=1 To N Do

        Begin

           Write(‘A[‘,i,’]=’); Readln(A[i]);

        End;

    Write(‘Nhap X=’); Readln(x);

    {Kết quả tìm kiếm}

    If TimKiem(X,N,A)<>0 Then

        Writeln(‘Vi tri cua X trong mang la:’, TimKiem(X,N,A))

    Else Writeln(‘X khong co trong mang.’);

    Readln;

End.

Bài tập 5: Giả sử mảng A đã được sắp xếp theo thứ tự tăng dần. Viết hàm để kiểm tra xem phần tử X có trong mảng A hay không?

Ý tưởng:

     So sánh x với phần tử ở giữa mảng A[giua]. Nếu x=A[giua]thì dừng (vị trí cần tìm là chỉ số của phần tử giữa của mảng). Ngược lại, nếu  x>A[giua] thì tìm ở đoạn sau của mảng [giua+1,cuoi], ngược lại thì tìm ở đoạn đầu của mảng [dau,giua-1].

Sau đây là hàm cài đặt cho thuật toán này:

Function TimKiemNhiPhan(X, N: Integer; A: Mang):Integer;

Var  dau,cuoi,giua:Integer;

        Found:Boolean;

Begin

    dau:=1; {điểm mút trái của khoảng tìm kiếm}

    cuoi:=N; {điểm mút phải của khoảng tìm kiếm}

    Found:=False; {chưa tìm thấy}

    While (dau<=cuoi) and (Not Found) Do

        Begin

           giua:=(dau + cuoi) Div 2;

           If  X = A[giua] Then Found:=True {đã tìm thấy}

           Else

               If X>A[giua] Then dau:=giua+1

               Else cuoi:=giua-1;

        End;

    If Found Then TimKiemNhiPhan:= giua Else TimKiemNhiPhan:=0;

End;

Bài tập 6: Cho một mảng 2 chiều A cấp mxn gồm các số nguyên và một số nguyên x. Viết chương trình thực hiện các công việc sau:

     a/ Đếm số lần xuất hiện của x trong A và vị trí của chúng.

     b/ Tính tổng các phần tử lớn nhất của mỗi dòng.

Uses Crt;

Type Mang = ARRAY[1..10,1..10] Of Integer;

Var  A:Mang;

        m,n,i,j,x,dem,S,max:Integer;

Begin

    {Nhập ma trận}

    Write(‘Nhap số dòng m=’); Readln(m);

    Write(‘Nhap số cột n=’); Readln(n);

    For i:=1 To m Do

        For j:=1 To n Do

           Begin

               Write(‘A[‘,i,j,’]=’); Readln(A[i,j]);

           End;

    {Nhập x}

    Write(‘Nhap x=’); Readln(x);

    {Đếm số lãn xuất hiện của x và vị trí của x}

    dem:=0;

    Writeln(‘Vi tri cua x trong mang A: ‘);

    For i:=1 To m Do

        For j:=1 To n Do  

           If x=A[i,j] Then

               Begin

                   Write(i,j,’ ; ‘);

                   dem:=dem+1;

               End;

    Writeln(‘So lan xuat hien cua x trong mang A la: ‘,dem);

    {Tính tổng các phần tử lớn nhất của mỗi dòng}

    S:=0;

    For i:=1 To m Do {duyệt qua từng dòng}

        Begin

           {Tìm phần tử lớn nhất của dòng thứ i}

           Max:=A[i,1];

           For j:=2 To n Do   {duyệt từng phần tử của dòng thứ i}

               If max<A[i,j] Then max:=A[i,j];

           {Cộng max vào biến S}

           S:=S+max;

        End;

    Writeln(‘Tong cac phan tu lon nhat cua moi dong la: ‘,S);

    Readln;

End.