İnterpolyasiya ilə axtarış

Vikipediya, azad ensiklopediya
Jump to navigation Jump to search

İnterpolyasiya ilə axtarış (ing. Interpolation search) — Artan və ya azalan sıra ilə düzülmüş massivdə verilmiş elementin tapılması alqoritmidir.

İşləmə prinsipi[redaktə | əsas redaktə]

Eyni ilə ikili axtarış alqoritminin sxemi üzrə qurulur. Yeganə fərq ondan ibarətdir ki, massiv hər addımda ikiyə tən ortadan deyil, cari intervalın uclarındakı qiymətlərdən asılı olaraq xətti interpolyasiya ilə tapılmış mövqedən bölünür. Hesablamaya sərf olunan vaxt baxımından intervalın ikiyə ortadan bölunməsi ilə interpolyasıyanın hesablanması arasında fərq ciddi olmadığı üçün, bu intervalın daha böyük sürətlə yığılmasına gətirir. Massivdəki elementlərin sayı N olarsa, bir elementin mövqeyinin tapılması üçün orta hesabla müqayisə sərf edilər. Ən pis halda (məsələn verilənlər eksponsional xarakter daşıdıqda) tələb edilən əməliyatların sayı -ə çata bilər.

C++ proqramlaşdırma dilində icrasına nümunə[redaktə | əsas redaktə]

 1 #include <iostream>
 2 #include <stdlib.h>		/*	srand(), rand(), RAND_MAX	*/
 3 #include <time.h>		/*	time()						*/
 4 #include <locale.h>		/*	setlocale()					*/
 5 
 6 using namespace std;
 7 
 8 const int n = 12;			/* Massivin ölçüsü */
 9 
10 /* Artan sıra ilə düzülmüş massivdə interpolyasiya ilə axtarış funksiyasına nümunə */
11 int InterpolyasiyaIleAkhtar(int massiv[], int say, int axtarilan)
12 {
13 	int sol = 0;
14 	int sag = say - 1;
15 
16 	while ((massiv[sag] != massiv[sol]) && (axtarilan >= massiv[sol]) && (axtarilan <= massiv[sag]))
17 	{
18 		int yeniMovqe = sol + ((axtarilan - massiv[sol]) * (sag - sol) / (massiv[sag] - massiv[sol]));
19 
20 		if (massiv[yeniMovqe] == axtarilan)
21 			return yeniMovqe;
22 
23 		if (massiv[yeniMovqe] < axtarilan)
24 			sol = yeniMovqe + 1;
25 		else
26 			sag = yeniMovqe - 1;
27 	}
28 
29 	if (axtarilan == massiv[sol])
30 		return sol;
31 
32 	return -1;
33 }
34 
35 /* Massivi sıralamaq üçün tələb olunan müqaisə funksiyası.	*/
36 /* Bu funksiya massivi artan sıra ilə düzür.				*/
37 int compare(const void* elem1, const void* elem2)
38 {
39 	if (*((int*)elem1) > *((int*)elem2))
40 		return 1;
41 
42 	if (*((int*)elem1) < *((int*)elem2))
43 		return -1;
44 
45 	return 0;
46 }
47 
48 /* Alqoritminin istifadəsinə nümunə */
49 int main()
50 {
51 	int massiv[n];
52 	int i;
53 
54 	setlocale(LC_ALL, ".utf8");
55 	srand((unsigned)time(NULL));
56 
57 	cout << "Massivdəki ədədlərin ilkin təsadüfi sırası:\t";
58 	for (i = 0; i < n; i++)
59 	{
60 		massiv[i] = 100.0 * rand() / (RAND_MAX + 1);
61 		cout << massiv[i] << " ";
62 	}
63 	cout << endl;
64 
65 	/* Alqoritm ancaq sıralanmış massivlərlə işləyir */
66 	qsort(massiv, n, sizeof(int), compare);
67 
68 	cout << "Massivdəki ədədlər sıralandıqdan sonra:\t\t";
69 	for (i = 0; i < n; i++)
70 		cout << massiv[i] << " ";
71 	cout << endl;
72 
73 	while (true)
74 	{
75 		int axtarilan;
76 
77 		cout << endl << "Proqramdan çıxmaq üçün mənfi, sırasının tapilması üçün isə hər hansı bir digər ədəd daxil edin: ";
78 		cin >> axtarilan;
79 
80 		if (axtarilan < 0)
81 			break;
82 
83 		int cavab = InterpolyasiyaIleAkhtar(massiv, n, axtarilan);
84 
85 		if (cavab < 0)
86 			cout << "Cavab tapilmadi." << endl;
87 		else
88 			cout << "Sıra N=: " << cavab + 1 << endl;
89 	}
90 }

Həmçinin bax[redaktə | əsas redaktə]