| impersonalis |
18.09.2005 18:51 |
Интерполяционный поиск
Выполняется в уже отсортированном массиве ( за счёт чего, в общем-то, и можно написать ускоренный метод поиска). Базируется на примерном определинии места элемента и последующей корректировки теоритического индекса.
Программа запрашивает значение для поиска и диапозон индексов (нижний и верхний предлы - можно указать 0 и максимальный индекс)
Код:
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<iomanip.h>
long interp_f(int a[],long N,int x,int ALeft,int ARight);
void input(int a[],long N);
void output(int a[],long N);
void main(){
long N;
cout<<"N?\n";
cin>>N;
int *b=new int[N];
input(b,N);
output(b,N);
cout<<"x, left, right?\n";
int x;
long left,right;
cin>>x>>left>>right;
int m=interp_f(b,N,x,left,right);
if(m!=-1)cout<<"return "<<m<<endl;
cout<<"Press any key\a";
cout<<endl;
getch();
}
long interp_f(int a[],long N,int x,int Left,int Right){
cout<<"interp_f RUN\n";
while (Right>Left){
*int m=Left+(Right-Left)*(x-a[Left])/float(a[Right]-a[Left]);
*cout<<"["<<setw(4)<<Left<<setw(4)<<m<<setw(4)<<Right<<"]"<<endl;
*if(a[m]==x){return m;}
*else if(a[m]>x){Right=m-Left;}
*else if(a[m]<x){Left=m+Left;}
}
cout<<"error 404"<<endl;
return -1;
}
void input( int a[],long N){
int x=rand()%50;
for(int i=0;i<N;i++){
*a[i]=x;
*x=x+rand()%12;
}
}
void output(int a[],long N){
cout<<"output ===\n";
for(int i=0;i<N;i++)
*cout<<"a["<<i<<"]="<<a[i]<<endl;
}
|
