Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование игр для компьютеров > C++

Ответ
 
Опции темы
Старый 18.09.2005, 18:51   #1
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Смущение

Интерполяционный поиск

Выполняется в уже отсортированном массиве ( за счёт чего, в общем-то, и можно написать ускоренный метод поиска). Базируется на примерном определинии места элемента и последующей корректировки теоритического индекса.

Программа запрашивает значение для поиска и диапозон индексов (нижний и верхний предлы - можно указать 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;
}
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
алгоритм поиска пути ии mifos JAVA Micro Edition 10 12.07.2011 17:34
А* - самый эффективный алгоритм поиска пути. Черный крыс Библиотеки 4 31.03.2008 14:47
Алгоритмы поведения противника WaReZ_MEN 2D-программирование 4 25.07.2007 01:50
Wave.dll - Волновой алгоритм поиска пути. Черный крыс Библиотеки 15 04.07.2007 21:08
Алгоритмы сортировки impersonalis C++ 10 07.11.2005 22:50


Часовой пояс GMT +4, время: 17:51.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com