Tìm vị trí phần tử có giá trị x xuất hiện cuối cùng trong mảng C
Bài tập này chúng ta sẽ sử dụng các kiến thức từ ngôn ngữ lập trình C như: cách nhập xuất cơ bản, cách sử dụng mảng một chiều, cách sử dụng hàm và sử dụng thuật toán tìm kiếm trong ngôn ngữ lập trình C. Show Yêu cầu của bài tập đưa ra cho chúng ta là tìm vị trí của x có trong mảng một chiều số nguyên bằng ngôn ngữ C. 2. Lời giảiĐầu tiên để thực hiện bài toán này chúng ta cần có kiến thức cơ bản về ngôn ngữ lập trình C, các cách nhập xuất cơ bản trong C, mảng một chiều trong C , cách sử dụng hàm trong ngôn ngữ lập trình C và các thuật toán tìm kiếm. Chúng ta có thể tham khảo và sử thuật toán tìm kiếm thông dụng như: tìm kiếm tuyến tính, tìm kiếm nhị phân, tìm kiếm nội suy,… đối với bài tập này tôi sẽ sử dụng thuật toán tìm kiếm tuyến tính để sử lí; bạn cũng có thể tìm hiểu các thuật toán tìm kiếm khác trong các trương trình học khác của chúng tôi. Thuật tìm kiếm tuyến tính (linear search) hay tìm kiếm tuần tự (sequential search) là thuật toán tìm kiếm bằng cách duyệt qua tất cả các phần tử của danh sách cho đến khi gặp phần tử cần tìm hoặc là đã hết danh sách. Các bước thực hiện yêu cầu của bài tập tìm vị trí của phần tử x trong mảng một chiều số nguyên bằng ngôn ngữ lập trình C như sau: Bước 1: Ta khai báo một mảng tĩnh số nguyên có 100 ô nhớ int a[100]. Bước 2: Ta khai báo số nguyên int n là số lượng phần tử có trong mảng với điều kiện n>1 hoặc n<100 nếu không thỏa mãn thì yêu cầu nhập lại n. Bước 3: Ta khỏi tạo hàm void Nhap(int a[], int n) dùng để nhập dữ liệu từ bàn phím cho mảng. Trong hàm ta sử dụng vòng for bắt đầu từ int i =0 và kết thúc khi i Bước 4: Ta khởi tạo hàm void Xuat(int a[], int n) dùng để hiển thị dữ liệu từ mảng ra màn hình. Trong hàm ta sử dụng vòng for bắt đầu từ int i =0 và kết thúc khi i Bước 5: Ta khởi tạo hàm int TimKiem(int a[], int n) dùng để tìm kiếm phần tử; ta khai báo biến int x là số cần tìm và nhập vào giá trị của x; tiếp theo sử dụng vòng lặp for bắt đầu từ int i =0 và kết thúc khi i Bước 6: Trong hàm main ta gọi hàm Nhap(a,n), Xuat(a,n) để hiển thị mảng gốc ta gọi thêm hàm TimKiem(a,n) rồi chạy chương trình. Chương trình giải bài tập tìm vị trí của phần tử x trong mảng một chiều số nguyên bằng ngôn ngữ lập trình C như sau: Ví dụ tôi nhập mảng có 5 phần tử: 1, 2, 3, 5, 2 và x = 2. Kết quả:
2 Vi tri cua x trong mang la: Sau khi làm bài tập này các bạn cần phải hiểu và nắm được những kiến thức sau: Tìm vị trí phần tử xuất hiện trong mảng là bài tập số 15 trong chuỗi các bài tập thực hành ngôn ngữ lập trình C/C++ do mình giới thiệu. Tìm kiếm vị trí phần tử trong mảng là một bài toán hay và đơn giản. Đây là một trong những bài toán giúp bạn hiều được phần nào về tìm kiếm. Đề bài: Viết hàm trả về vị trí đầu tiên của số x xuất hiện trong mảng một chiều a có n phần tử. Viết hàm trả về vị trí cuối cùng của số x xuất hiện trong mảng một chiều a có n phần tử. Hai bài toán nhưng mình gộp lại thành một, vì nội dung khá liên quan đến nhau. Cùng giải quyết thôi nào! Bài tập này ở mức vận dụng cơ bản, bạn chỉ cần nắm chắc các cú pháp, cách dùng của chủng là có thể làm được. Tìm kiếm có hai trường hợp: Vị trí xuất hiện đầu tiên và vị trí xuất hiện cuối cùng Ý tưởng: sử dụng vòng lặp duyệt mảng, gặp phần tử có giá trị bằng số x lập tức dừng vòng lặp và trả về kết quả. Ở đây mình sẽ viết hàm trả về vị trí nên dùng kiểu int. Hàm truyền vào 3 tham số là tên mảng, số phần tử của mảng và phần tử cần tìm. Code C/C++: int FindFirstX(int a[], int n, int x){
for(int i=0;i Cách đặt tên hàm thì tùy ý bạn nhé. Hàm tìm vị trí cuối cùng xuất hiện có khác thêm một chút. Khá giống với tư tưởng tìm vị trí đầu tiên. Điểm khác biệt ở đây là cần dùng một biến để lưu vị trí. Sau khi duyệt từ đầu đến cuối mảng ta sẽ có được vị trí cuối cùng mà phần tử cần tìm xuất hiện. Xem code tham khảo sau bạn sẽ hiểu hơn: int FindLastX(int a[], int n, int x){
int vitri;
for(int i=0;i Để thành chương trình hoàn thiện, bạn cần thêm một số cấu trúc mặc định của ngôn ngữ C/C++. Do làm việc với mảng nên chúng ta cũng cần thêm hàm nhập xuất mảng vào chương trình nhé! Code C và C++ không khác nhau nhiều lắm, nếu bạn đang cần tìm kiếm chương trình bằng code C thì chỉ cần sửa một chút câu lệnh in ra màn hình, nhập giá trị từ bàn phím là được. Code C++: #include Bài viết của mình đến đây là hết, cảm ơn bạn đã quan tâm bài viết. Đừng bỏ lỡ bài tập lập trình C/C++ tiếp theo nhé! Xem tiếp bài 16: Đếm số lần xuất hiện của phần tử trong mảng Xem lại bài 14: Xóa số nguyên tố trong mảng C/C++ Tải về đề cương 67 bài tập lập trình C/C++ Yêu cầu: Viết hàm tìm vị trí phần tử có giá trị x xuất hiện cuối cùng trong mảng. Thuật toán: Viết hàm có tham số đầu vào là mảng 1 chiều và giá trị x, giá trị trả về là vị trí phần tử có giá trị x xuất hiện cuối cùng trong mảng, nếu không có phần tử nào phù hợp thì trả về -1 Code:
/************************************************************
#include "stdio.h"
#include "conio.h"
#define LEN_MAX 100 // do dai toi da cua mang
int srchPos(int A[], int x, int len);
void main()
{
int arr[LEN_MAX];
int n, x;
int i;
int pos;
do
{
printf("\nNhap kich thuoc mang: ");
scanf("%d", &n);
}
while (n > LEN_MAX);
for (i = 0; i < n; i++)
{
printf("\nA[%d] = ", i);
scanf("%d", &arr[i]);
}
//Nhap phan tu x
printf("\nNhap x: ");
scanf("%d", &x);
pos = srchPos(arr, x, n);
if(pos != -1)
printf("\n%d xuat hien tai vi tri cuoi mang A la: %d", x, pos);
else
printf("\n%d khong xuat hien trong mang A", x);
getch();
}
int srchPos(int A[], int x, int len)
{
int i, pos = -1;
for (i = 0; i < len; i++)
if (x == A[i])
pos = i+1;
return pos;
}
Kết quả:
Nhap kich thuoc mang: 5 A[0] = 2 A[1] = 1 A[2] = 9 A[3] = 2 A[4] = 1 Nhap x: 1 1 xuat hien tai vi tri cuoi mang A la: 5
+ngoton |