| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск в массиве
selesasha © (2012-03-15 14:26:00)Дано:
1) Неубывающий массив повторяющихся данных, длинной ~15000 возможно имеющий nil среди значений, и почти наверняка имеющий хвост из nil в конце
2) Массив находится на удаленном сервере, каждый запрос одного элемента это post через http с последующим парсингом ответа. Т.е. Чтобы сравнить 2 элемента массива нужно сделать 2 запроса.
3) Функция позволяющая для пары данных однозначно определить какой из аргументов больше, или их равенство, если ни одно из них не nil
Задача:
Найти границы окна, внутри котрого находится значение заданное пользователем, за наименьшее число обращений к серверу. Найти не обязательно точно, возможна погрешность, максимальнывй размер которой задается пользователем, при этом пользователь может указать погрешность 0.
Поделитесь пожалуйста своими соображениями. Код никакой не прошу, только идеи и Ваши умные мысли.
app (2012-07-12 11:29:00) [1]Обсуждать можно идеи, а не носителя.
Можно сказать, что идея дурацкая, но не дядя Петя ты дурад
Sergey (2012-07-12 10:40:00) [2]Нет конечно, мой комментарий тоже из той же серии, так что не говорю, что я сильно от него отличаюсь )
критиковать конечно легко.. по теме писать - нужны мозги
Sergey (2012-07-12 10:31:00) [3]Удалено модератором
Sergey (2012-07-12 10:30:00) [4]Удалено модератором
Sergey (2012-07-12 10:26:00) [5]Удалено модератором
Sergey (2012-07-12 10:25:00) [6]Удалено модератором
Примечание: Ты получил разрешение на обсуждение личности?
Sergey (2012-07-12 10:24:00) [7]Всем здравствуйте!
Почитал, конечно, человек принимает близко к сердцу всякие слова со стороны jeer, но мало кто может спокойно относиться к подобному, тем более радоваться..
jeer за всё время в этой теме не написал ничего полезного, ядовитые слова человека характеризуют фигово, зачем нужны такие комментарии?
selesasha - пытаетесь разобраться, студент, угодить супруге преподавателя (нормальным способом), чтобы учиться бесплатно - всё это вполне понятно и критиковать тут нечего. Удачи..
Конечно у Вас есть слабость, к такой тупой критике, как у jeer, но ничего : )) у меня тоже есть, у большенства есть, у jeer тоже есть : )) хотя он это тщательно скрывает )) и плюёт на тех кто его критикует, но это его характеризует ещё фиговей.
просто вам стоило игнорировать его посты, да и всё, и можно ещё попытаться понять почему он так себя ведёт - это тоже интересно, потом можно научиться жалеть таких людей, у них проблемм гораздо больше из-за дурного характера.
selesasha (2012-03-16 12:34:00) [8]
> Тебе дается число, и задача - найти диапазон, в который
> оно будет входить.
Мне задача - найти все вхождения этого числа
> Ты, конечно, извини, но программист - это человек, который
> должен уметь строить алгоритм.
Агоритм я уже построил в [38], теперь прошу его поругать
Cobalt (2012-03-16 12:19:00) [9]> selesasha (15.03.12 17:34) [3]
> бинарный поиск тут не подходит - по крайней мере в лоб:
> 1) Какой поддиапазон выбирать если середина отрезка - nil?
>
> 2) Как находить границы окна, если середина отрезка попала в искомое значение?
Ты, конечно, извини, но программист - это человек, который должен уметь строить алгоритм.
Представь, что перед тобой лежит на полу сотня бумажек подряд. На оборотной стороне бумажек написаны числа в убывающей последовательности.
Тебе дается число, и задача - найти диапазон, в который оно будет входить.
Если у тебя бедное воображение - возьми хотя бы 20 бумажек, напиши на некоторых из них числа, отсортируй, переверни, и приступай, записывая каждый шаг в тетрадочку.
Anatoly Podgoretsky (2012-03-16 12:07:00) [10]> selesasha (16.03.2012 12:03:35) [35]
Раз ты можешь определить, что это центр, то несложно повторить это несколько
раз, называется метод постепенного приближения
selesasha (2012-03-16 12:03:00) [11]
> Таблица, как я понял за исключением 0 упорядоченная
Да.
> P.S. Уточним задачу: при запросе к таблице мы можем:
> a) найти элемент, удовлетворяющий условию
> б) узнать значение элемента по индексу
б.
> если б - количество обращений = индексу нижней границы.
> То есть ПОЧТИ ПОЛНЫЙ перебор.
Если использовать тот алгоритм, который я привел в [32], то в самом худшем случае мы можем сократить границы перебора вдвое. В среднестатистическом, процедура бинарного поиска повторится 2-3 раза. А это уже совсем не ПОЧТИ ПОЛНЫЙперебор, даже если пункт 2 заменить на "Если центр - искомое значение, то начинаем искать левую и правую границу перебором"
Собственно это решение пока что самое лучшее из того, что я смог придумать. Может Вам с высоты вашего полета сразу видны какие-то изъяны?
oldman (2012-03-16 09:55:00) [12]
> > Задача: найти границы вхождения числа 4, используя минимальное
> > число обращений к массиву. Нули границы вхождения не ограничивают.
> имхо - перебором, возможно оптимизированным, но ПОЛНЫМ перебором.
Ну зачем же ПОЛНЫМ?
Сначала ищем 0<Nmin<4 - верхняя граница
Потом ищем 0<Nmax>4 - верхняя граница
Таблица, как я понял за исключением 0 упорядоченная
P.S. Уточним задачу: при запросе к таблице мы можем:
a) найти элемент, удовлетворяющий условию
б) узнать значение элемента по индексу
???
если а - два обращения
если б - количество обращений = индексу нижней границы. То есть ПОЧТИ ПОЛНЫЙ перебор.
selesasha (2012-03-16 07:56:00) [13]в 1 формула вот так выглядит: cnt:=cnt+IntPower(-1,count)*count
se (2012-03-16 07:41:00) [14]
> > А по теме сказать нечего?
> > > давай начнем с показа ее реализации...
> > Давайте не будем. Функция протестирована и работает.
Если Вы мне бестолковому понятно объясните каким образом реализация полностью рабочей функции сравнения двух величин влияет на алгоритм поиска нужного значения с использованием этой функции, я эту функцию тут дам Вам посмотреть.
Ну это Вы загнули.
Вот что на данный момент оформилось у меня:
поиск идет в условно-бесконечном цикле, стандартным методом дихотомии. С каждой интерацией увеличиваем значение счетчика (count) на единицу.
На каждой интерации проверяем стандартые условия плюс:
1. Если центр - 0, то смещаем центр по принципу cnt:=cnt+IntPower(-1,count)
2. Если центр - искомое значение, то начинаем искать левую и правую границу по тому же алгоритму.
3. если ни одно из этих условий не выполнилось, то вычисляем новые границы диапазона поиска, и новый центр.
Попинайте пожалуста
brother (2012-03-16 06:55:00) [15]> А по теме сказать нечего?
> > давай начнем с показа ее реализации...
>
> Давайте не будем. Функция протестирована и работает.
> Есть массив целых одноразрядных чисел (а), такой что: а[n]<=a[n+1]
> при a[n]<>0 и a[n+1]<>0. Можно представить себе массив из
> нулей, заполненный на 3/4 случайными числами от 1 до 9,
> потом эти 3/4 отсортировали по возрастанию (получился неубывающий
> массив с хвостом из нулей), и заменили некоторые из чисел
> в этих 3/4 на нули.
> Задача: найти границы вхождения числа 4, используя минимальное
> число обращений к массиву. Нули границы вхождения не ограничивают.
имхо - перебором, возможно оптимизированным, но ПОЛНЫМ перебором...
brother (2012-03-16 06:51:00) [16]> угодить<>удовлетворить сексуальное желание
а я об этом и не говорил...
selesasha (2012-03-16 06:20:00) [17]угодить<>удовлетворить сексуальное желание
А по теме сказать нечего?
Вот у меня вопрос возник:
При применении Монте-Карло, я могу найти стохастическую ширину нужного диапазона, а вот как при применении этого метода мне найти границы этого диапазона?
brother (2012-03-16 04:29:00) [18]> пытающийся угодитьжене преподавателя
> на этом самом месте закончим шутки по этому поводу
тогда меняй формулировку...
selesasha (2012-03-15 20:31:00) [19]
> Это твое мнение, но всеж...
Если Вы можете помочь в приведении, скажите что еще рассказать чтобы задача была описана полно.
> В твоем случае классики нет
Это значит... что? Что нужно искать неклассические алгоритмы решения или что?
> ... начни с цветов и вина)
Давайте пожалуста вот на этом самом месте закончим шутки по этому поводу. Неуместно
brother (2012-03-15 20:22:00) [20]> Я задачу описал довольно полно,
Это твое мнение, но всеж...
> показать как она будет выглядеть сведенная к классической
В твоем случае классики нет, хотя, начни с цветов и вина)
| |
Страницы: 