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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
#1

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

31.07.2013, 15:39. Просмотров 376. Ответов 6
Метки нет (Все метки)

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

Быстрый подсчет количества бит - C++
Нужно подсчитать количество бит, равных единице в int32, использую статический массив, в котором заранее подсчитаны значения для 0x0000 -...

Быстрый алгоритм для подсчета количества делителей числа - C++
Быстрый алгоритм для подсчета количества делителей натурального числа 1 <= x <= 1018. Помогите реализовать такой. Дело в том, что должно...

Быстрый поиск - C++
Здравствуйте. Нужно выполнить поиск i-го вхождения заданного элемента в исходном наборе чисел. Написал такой поиск, но работает...

Быстрый поиск элемента - C++
Добрый день всем! Такой вопрос - есть у меня строка из 64-х чаров. Мне приходит новый чар и нужно найти какой индекс у такого же чара в...

Дерево отрезков. Поиск суммы чисел на отрезке массива. Изменение всех чисел на отрезке массива - 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
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
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     Подскажите быстрый поиск количества интервалов в отрезке
Еще ссылки по теме:

Быстрый поиск в векторе из pair - C++
Пытаюсь сделать вектор: vector&lt; pair&lt;string, string&gt; &gt; myVect; По идее, проще воспользоваться чем-то вроде map или unordered_map,...

Быстрый поиск супернатуральных чисел - C++
Натуральное число будем называть супернатуральным, если в своем десятичном виде оно не содержит единиц, а произведение всех его цифр равно...

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

Быстрый поиск ip адреса в текстовом файле - C++
Нужно найти конкретный ip-адрес в текстовом файле (он может попасться несколько раз). На каждой строчке по 1 ip-адресу. Всего строк ~300...

Быстрый поиск наиболее близких вершин графа - C++
Всем привет, у меня имеется некая задача и её суть состоит в том, что мне нужно найти расстояние между двумя наиболее близкими вершинами...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru