Форум программистов, компьютерный форум CyberForum.ru

Подскажите быстрый поиск количества интервалов в отрезке - C++

Восстановить пароль Регистрация
 
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
31.07.2013, 15:39     Подскажите быстрый поиск количества интервалов в отрезке #1
Есть массив H[N]
Есть отрезок x+dx.
Задача найти количество интервалов на которое делится отрезок x+dx массивом H[N].
Наверняка с такой задачей уже кучу раз сталкивались, и есть оптимальное по быстродействию решение. Подскажите его, а то у меня как то коряво получается.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.07.2013, 15:39     Подскажите быстрый поиск количества интервалов в отрезке
Посмотрите здесь:

C++ Быстрый поиск ip адреса в текстовом файле
Быстрый поиск совершенных чисел C++
Быстрый поиск супернатуральных чисел C++
Быстрый подсчет количества бит C++
Быстрый поиск элемента C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
31.07.2013, 15:54     Подскажите быстрый поиск количества интервалов в отрезке #2
1) пройтись по H[N], отобрать точки, попадающие в заданный отрезок. Время O(N).
2) отсортировать оторанные точки. Время O(NlogN).
3) удалить дубликаты в отсортированных точках. Время O(N).
4) число оставшихся отобранных точек + 1. Время O(1)
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
31.07.2013, 16:15  [ТС]     Подскажите быстрый поиск количества интервалов в отрезке #3
Небольшое уточнение H[N] уже отсортирован...

Ну у меня вот как то так получается...Проверею конец и начало отрезка на предмет попадания в массив, далее нахожу конец и начало фрагмента в массиве.Норм?
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template<class T>
int get_segment_in_arr(T x, const T *H, int N)
{
    int i0 = 0, i2 = N;
    for(; i2-i0>1; ) {
        const int i1 = (i0+i2)>>1;
        if( x<H[i1] )
            i2 = i1;
        else
            i0 = i1;
    }
    return i0;
}
 
template<class T>
int get_segment_count(T x,T dx, const T *H, int N)
{
    if((x+dx)>H[N])
    {
        count++
    }
    if(x<H[0])
    {
        count++
    }   
    int begin = get_segment_in_arr(x,H,N);
    int end = get_segment_in_arr((x+dx),H,N);
    count +=end - begin +1;
             return count;
 
}
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
31.07.2013, 16:25     Подскажите быстрый поиск количества интервалов в отрезке #4
Дубликаты, я так, понимаю, тоже не встречаются. Ну тогда ок.
Но ведь это C++, есть множество готовых алгоримов в STL, включая двоичный поиск в отсортированном массиве. Если же главная задача - реализовать такой поиск руками, то хоть название функциям давайте осмысленные и соответствующие их задачам.
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
01.08.2013, 10:47  [ТС]     Подскажите быстрый поиск количества интервалов в отрезке #5
Да, там все таки есть дубликаты.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.08.2013, 10:52     Подскажите быстрый поиск количества интервалов в отрезке #6
Цитата Сообщение от Maxak Посмотреть сообщение
Задача найти количество интервалов на которое делится отрезок x+dx массивом H[N].
приведите, пожалуйста, разумную формулировку задачи...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.08.2013, 13:11     Подскажите быстрый поиск количества интервалов в отрезке
Еще ссылки по теме:

C++ Как сделать быстрый поиск по массиву разнотипных данных?
Быстрый поиск C++
C++ Быстрый поиск минимального числа

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
01.08.2013, 13:11  [ТС]     Подскажите быстрый поиск количества интервалов в отрезке #7
Цитата Сообщение от salam Посмотреть сообщение
приведите, пожалуйста, разумную формулировку задачи...
выделил в отдельный топик.
Выделить из упорядоченного массива подмассив ограниченный точками x1, x2
Yandex
Объявления
01.08.2013, 13:11     Подскажите быстрый поиск количества интервалов в отрезке
Ответ Создать тему
Опции темы

Текущее время: 13:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru