Описание тега ternary-search
Ternary search is an efficiency that can be used to find an element in a sorted array. Use this tag for question-related to ternary search only and not the ternary operator.
1
ответ
Как применить троичный поиск для вызова SPOJ - KOPC12A
Я пытался решить проблему KOPC12A в SPOJ. Ссылка на проблему: http://www.spoj.com/problems/KOPC12A/ Проблема вкратце: Для n зданий, каждая из которых имеет разную высоту (количество кирпичей), а каждое здание имеет стоимость добавления или удаления …
09 фев '15 в 16:55
2
ответа
Может ли пролог ответить неопределенно, а не просто да или нет?
Предположим, у меня есть база знаний likes(john,mary). person(mary). person(john). Если мы спросим пролог, |?- likes(mary,john) Он ответит " нет", потому что мы этого не утверждали. Есть ли способ сделать ответ пролога неизвестным, если мы прямо не …
07 мар '17 в 18:46
1
ответ
Как реализовать троичный поиск в C?
Возможный дубликат: Троичный поиск в т Напишите третичную [троичную] поисковую программу. Примечания: Третичный поиск похож на бинарный поиск. В бинарном поиске мы рассматриваем две части массива и выбираем одну часть в качестве следующего пространс…
28 авг '09 в 15:55
2
ответа
Является ли троичный поиск менее эффективным, чем этот связанный алгоритм?
Алгоритм троичного поиска - это быстрый алгоритм для нахождения минимума или максимума унимодальной функции , функции, которая либо увеличивается, а затем уменьшается или уменьшается, а затем увеличивается. Предположим, что мы имеем дело с функцией,…
14 дек '11 в 06:05
1
ответ
Solving ACM TJU 2886 - Рестораны
Я пытаюсь решить эту проблему: http://acm.tju.edu.cn/toj/showp2886.html Я попробовал несколько решений, я объясню 2 из них. Обратите внимание, что оба предполагают, что стоимость (позиция) является выпуклой функцией, что означает, что она уменьшаетс…
15 апр '15 в 08:36
2
ответа
Тройной Поиск, чтобы найти точку в массиве, где разница минимальна
Пусть A массив из n натуральных чисел. Как я могу найти некоторый индекс k А, такой что: left = A[0] + A[1] + ... + A[k] right = A[k+1] + A[k+2] + ... + A[n] иметь минимальную абсолютную разницу (то есть abs(left - right) это минимум)? Поскольку абс…
19 июн '16 в 20:29
1
ответ
Почему среднее число сравнений k-арного поиска составляет k* ln(N) / ln(k)?
Я знаю, что функция выполняется ln(N)/ln(K) раз, но в среднем она делает K операций? Вопросы: есть ли доказательства того, что k*ln(N)/ln(K) - это среднее число казней? Если эта формула верна, то троичный поиск будет самым быстрым поиском, так как k…
13 фев '12 в 11:16
2
ответа
Троичный поиск, как бинарный поиск, но деление элементов на 3
Ниже приведена функция с именем "test". Моя программа не может пройти тестовую функцию. Это мой код для троичного поиска. Тройной поиск похож на бинарный поиск, но вместо того, чтобы делить все элементы на два, вы делите их на три. Чтобы использоват…
12 мар '13 в 02:26
1
ответ
Двойное использование scanf() зависит от порядка вызовов
Я написал программу на C, которая принимает в качестве входных данных значение и упорядоченный массив целых чисел и выполняет троичный поиск, чтобы найти значение (если оно существует) внутри массива. Я видел все возможные проблемы с использованием …
19 мар '17 в 21:38
1
ответ
Рекуррентное соотношение для троичного поиска
Отношение рекуррентности троичного поиска имеет вид T(n)= T(n/3) + 4. Как 4 находится в отношении рекуррентности, так как в троичном поиске это лог для базы 3 N, поэтому там должно быть только 3 раздела?
25 дек '18 в 21:51
2
ответа
Бинарный поиск против троичного поиска
С точки зрения сложности времени и пространства, лучше ли двоичный поиск, чем троичный?
14 сен '15 в 19:22
0
ответов
Переполнение сегмента при тройном поиске
Я пытался реализовать тройной поиск. Потом я нашел ссылку на geeksforgeeks со ссылкой https://www.google.com/amp/s/www.geeksforgeeks.org/ternary-search/amp/ Я реализую точный код. Затем в основном я сначала объявляю массив из 100 элементов с элемент…
07 окт '19 в 21:28
1
ответ
Тернарный поиск не вернет ответ
Я написал следующий код для рекурсивной тернарной функции: def ternary_search(start,stop,x,arr): pos1 = start + (stop-start)//3 pos2 = stop - (stop - start)//3 if (pos1<=pos2): val1 = arr[pos1] val2 = arr[pos2] if val1 == x: print(pos1) return po…
03 авг '20 в 07:39
1
ответ
Найдите Minimun Vertext-Cover с помощью тернарного дерева
Я нашел несколько алгоритмов для поиска минимального Vertex-Cover, как при использовании двоичного дерева поиска, но я читал, что использование троичного дерева еще лучше. Но я не могу найти никакой информации об этом или придумать алгоритм для этог…
01 ноя '20 в 21:08
2
ответа
Почему троичный поиск используется для нахождения максимума / минимума унимодальной функции?
Я узнал, что найти минимум / максимум унимодальной функции можно с помощью троичного поиска, алгоритма, который работает в O(logN) время (где N размер заданного диапазона поиска). Однако недавно у меня возникла мысль, что, возможно, мы сможем найти …
14 ноя '20 в 05:15
0
ответов
Корень «пилообразной» функции
Скажем, у нас есть f(t) = v * t + A * sin(w * t). Я называю такие функции «пилообразными»: я хочу решить saw(t) = C, то есть найти корень saw(t) - C(еще "пилоподобный"). Я попытался записать троичный поиск функции abs(saw(t) - C)найти его минимумы. …
09 янв '21 в 16:11
1
ответ
установить несколько условий в тернарном операторе
Я хочу установить условие, что оно не должно быть больше 10 или меньше 0, но я не понимаю, как установить тернарный оператор var count = 0; var res = flag == "1" ? ++count : flag == "0" ? --count;
17 янв '23 в 04:16
1
ответ
Разница между количеством сравнений и ростом числа сравнений алгоритма
В чем разница между количеством сравнений и ростом числа сравнений алгоритма? Например, для бинарного поиска и троичного поиска. Я понимаю, что количество сравнений — фиксированное число для конкретного случая, но прирост учитывает наихудший сценари…
02 дек '22 в 22:46