Jizzax filiali amaliy matematika fakulteti

Interpolatsiya qidiruvida joylashuvni tekshirish
Interpolatsiya qidiruvi prob o'rnini hisoblash orqali ma'lum bir elementni topadi. Dastlab, zond pozitsiyasi to'plamning o'rtadagi eng ko'p elementining pozitsiyasidir.


Agar mos keladigan bo'lsa, element indeksi qaytariladi.


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace Struktura_12_variant

{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
timer1.Enabled = true;
timer2.Enabled = true;
}

bool d=true;

int[] arr = { 1, 4, 8, 12, 20, 25, 27, 30, 36, 40, 41, 43, 45, 49, 52, 56, 58, 60, 63 };
int chap = 0, ong = 19;
private void timer1_Tick(object sender, EventArgs e)
{
/*int[] arr = new int[] {Convert.ToInt32(textBox1.Text), Convert.ToInt32(textBox2.Text), Convert.ToInt32(textBox3.Text),
Convert.ToInt32(textBox4.Text),Convert.ToInt32(textBox5.Text),Convert.ToInt32(textBox6.Text),
Convert.ToInt32(textBox7.Text),Convert.ToInt32(textBox8.Text),Convert.ToInt32(textBox9.Text),
Convert.ToInt32(textBox10.Text),Convert.ToInt32(textBox11.Text)};*/
int x = Convert.ToInt32(textBox13.Text);
int orta = chap + (ong - chap) / 2;
if (arr[orta] == x)
{
textBox13.BackColor = Color.Green;
textBox13.Location = new Point(26 + 35 * orta, textBox13.Location.Y);
timer1.Enabled = false;
}
if (arr[orta] < x)
{
textBox13.Location = new Point(26 + 35 * orta, textBox13.Location.Y);
chap = orta + 1;
}
else
{
textBox13.Location = new Point(26 + 35 * orta, textBox13.Location.Y);
ong = orta - 1;
}

}
int minIndex = 0, maxIndex = 18;

private void timer2_Tick(object sender, EventArgs e)

{
//Interpolation qidiruv algoritmi
int x = Convert.ToInt32(textBox26.Text);
int post = minIndex + Convert.ToInt32(((x - arr[minIndex]) * (maxIndex - minIndex)) / (arr[maxIndex] - arr[minIndex]));

if (arr[post] == x)

{
textBox26.BackColor = Color.Green;
textBox26.Location = new Point(33 + 35 * post, textBox26.Location.Y);
timer2.Enabled = false;
}
if (arr[post] > x)
{
textBox26.Location = new Point(33 + 35 * post, textBox26.Location.Y);
maxIndex = post - 1;
}
else
{
textBox26.Location = new Point(33 + 35 * post, textBox26.Location.Y);
minIndex = post + 1;
}

if (minIndex == maxIndex)

{
if (arr[minIndex] == x)
{
textBox26.BackColor = Color.Green;
textBox26.Location = new Point(33 + 35 * post, textBox26.Location.Y);
timer2.Enabled = false;
}
}
}

private void button2_Click(object sender, EventArgs e)

{
timer2.Enabled = false;
timer1.Enabled = false;
}
}
}

Xulosa
Yuqoridagi munozaradan xulosa qilamizki, xeshlashning maqsadi to'plamdagi buyumni tezda topish muammosini hal qilishdir. Misol uchun, agar bizda millionlab inglizcha so'zlar ro'yxati bo'lsa va biz ma'lum bir atamani topmoqchi bo'lsak, uni yanada samarali topish va topish uchun xeshlashdan foydalanamiz. Biz bir uchrashuvini topish qadar ro'yxatlar millionlab har bir elementni tekshirish uchun samarasiz bo'ladi. Xeshlash qidiruvni boshida kichikroq so'zlar to'plami bilan cheklash orqali qidiruv vaqtini qisqartiradi.