interpolasi pemrograman c++

C ++ Program untuk Melaksanakan interpolasi Cari Algoritma

Program ++ C ini menerapkan interpolasi Cari Algoritma.

pencarian interpolasi adalah algoritma pencarian untuk nilai kunci yang diberikan dalam array diindeks yang telah diperintahkan oleh nilai-nilai kunci. Hal ini juga disebut sebagai pencari ekstrapolasi.

Hal ini didasarkan pada bagaimana manusia mencari melalui buku telepon untuk nama tertentu.

Rata-rata kompleksitas waktu pencarian interpolasi adalah O (log n (log n)) perbandingan, di mana n adalah jumlah elemen yang akan dicari. Dalam kasus terburuk dapat membuat hingga O (n) perbandingan yang setara dengan pencarian linear.

iklan

Program ini memiliki berbagai masukan dari ukuran 10 diinisialisasi dengan 10 nilai. Ini mengembalikan indeks dari elemen, jika ditemukan dan -1 jika tidak menggunakan interpolasi Cari Algoritma.

data[posisi] > data yg dicari, high = pos – 1
– Jika data[posisi] < data yg dicari, high = pos + 1
Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu yang
dilakukan dengan perkiraan letak data.

contoh program pencarian interpolasi :

Algoritma

a) awal = 0

b) akhir = banyak Data Array-1

c) pencarian data (input bilangan)

d) menggunakan rumus interpoasi posisi = ((cari_data – data[awal])*(akhir-awal)+awal)/(data[akhir]-data[awal])

e) cari_data == data[posisi]

f) Jika sesuai dengan yang dicari / sama , data yang dicari telah ditemukan maka program berhenti / selesai.

g) Jika tidak sesuai dengan yang dicari ,maka akan membandingkan  :

·         JIKA (data[posisi] < cari_data awal = posisi + 1;

h)     Melakukan langkah 4 dan 5

i)        Jika data[posisi] > cari_data, tampilkan data tidak ditemukan, program selesai

 

Code Pemrograman :

#include <iostream>

#include <conio.h>

#include <iomanip>

using namespace std;

int main()

{

int data[10] = {23,1,21,31,14

                 ,5,6,7,8,9};

int cari_data, posisi, awal, akhir, proses;

bool berhenti =

false;

cout<<"Data: ";

for(int z = 0; z<10; z++)

   

cout<<setw(3)<<data[z];

cout<<endl<<endl;

cout << “Data yang dicari : “;

cin >> cari_data;

awal = 0;

akhir = 10;

proses = 0;

while(berhenti != true)

    {

proses++;

posisi =(((cari_data-data[awal])*(akhir-awal))/(data[akhir]-

data[awal])+awal);

if(data[posisi] == cari_data) {

cout << “Data ” << cari_data << ” pada posisi indeks ke-” << posisi <<endl;

cout << “Proses pencarian sebanyak ” << proses <<endl;

berhenti = true;

} else if(data[posisi] < cari_data) {

awal = posisi + 1;

} else {

cout << “Data ” << cari_data << ” ora ono.\n”;

berhenti = true;

}

}

return 0;

}

folchart