30/09/2018, 17:56
Thắc mắc về giải thuật LinearSearch trong C
Theo em nghĩ nếu như không có dòng a[n] = x; thì khi nhập X không nằm trong mảng thì vòng lặp while sẽ lặp vô hạn nhưng sao em chạy thì vẫn ra kết quả đúng. Mong các cao nhân giúp đỡ đa tạ
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
void NhapMang(int a[], int n);
void XuatMang(int a[], int n);
int LinearSearch(int a[], int n, int x);
//int LinearSearch1(int a[], int n, int x);
//int LinearSearch2(int a[], int n, int x);
int main()
{
int n, x;
printf("Nhap so phan tu cua mang: ");
scanf("%d", &n);
int a[n];
NhapMang(a,n);
XuatMang(a,n);
printf("
Nhap vao so X can tim kiem trong mang: ");
scanf("%d", &x);
int result1 = LinearSearch(a,n,x);
if(result1 == -1)
printf("khong thay X");
else
printf("Thay X o vi tri a[%d] khi duyet tu dau den cuoi mang", result1);
//LinearSearch1(a,n,x);
//LinearSearch2(a,n,x);
getch();
return 0;
}
void NhapMang(int a[], int n)
{
srand((int)time(NULL));
for(int i=0; i<n; i++)
a[i] = rand()%50;
}
void XuatMang(int a[], int n)
{
for(int i=0; i<n; i++)
{
if(i%10==0 && i!=0)
printf("
");
printf("%d ", a[i]);
}
}
int LinearSearch(int a[], int n, int x)
{
int i=0;
//a[n] = x; phương pháp lính canh
while (a[i] != x)
i++;
if(i<n) return i;
return -1;
}
Bài liên quan
Đó là vì trong mảng có giá trị
x
, nếu không có thì vô hạnbạn chạy thử đi nếu X không có trong mảng thì nó vẫn in ra "khong thay X " chứ đâu có lặp vô hạn đâu bạn
vòng lặp này ko bao giờ thoát được nếu x ko có trong mảng
Trong C, bạn có thể truy cập phần từ ngoài vùng cấp phát của mảng, ví dụ như a[n], a[n+1], những vị trí này chứa những giá trị “rác”. Vòng lặp không vô hạn vì có thể “đằng sau” mảng (tức là gia trị từ a[n] trở đi) có một giá trị rác nào đó trùng với số cần tìm nhưng lại không nằm trong kích thước mảng thì hàm LinearSearch trả về -1. Nếu không có giá trị nào trùng thì vòng lặp vẫn có thể lặp vô hạn. Bạn thử in ra giá trị của biến i khi chạy xong vòng lặp thì sẽ rõ.
bạn chạy thử đi sẽ biết kết quả
có khi nào xảy ra trường hợp này không nhỉ .
Mình chạy thử chục lần thì không thấy bị lặp vô hạn, chỉ có 2 khả năng: