Pull to refresh
11
0
Алексей @AlMag

User

Send message
нет, нам нужны частичные суммы хешей. К примеру, если нужно узнать сумму на подотрезке, Вы делаете массив частичных сумм и тогда за О(1) узнаете ответ, неважно какой длины запрашивается отрезок.
Так же и здесь — сделать массив частичных сумм хешей и для любого M конкретный хеш извлекается за O(1)
Вы сами строите хеш-функцию.
Скажем F(pos) = Spos * p0 + Spos+1 * p1 +… + Spos+M-1 * pM-1
для pos = 0..|S|-M
p — простое число. желательно первое после количества букв в алфавите, тоесть 29 или 31. Функцию можно взять по модулю большого числа. Преподсчитываем за линию еще до вычислений для обоих строк.

Теперь, когда мы берем подстроку строки S2 — это преподсчитанное значение нашей функции. O(1). Нужно определить, в каких позициях это число находится в строке S. Это тривиально, так как работаем мы уже с числами, а не со строками.
Можно искать проекции хешированием. Поскольку у нас фиксированная длинна M, можно преподсчитать все хеши подстрок S2 длины M, а потом при проверке высчитать хеш нужной для проекции строки и сразу узнать позиции. Итого — O(|S2|) на препроцесс и O(M+log|S2|)
Еще одним последствием приглушения эмоциональности является искажение восприятия внешнего мира. Без радости, любви, печали или злости — он превращается в техногенный, серо-зеленый мир Матрицы. Работа, сон, работа… Сдается мне что такая ситуация будет мало кого радовать.


мне кажется, здесь Вы перегнули. Эмоций меньше — это правда, но меньше эмоций от тех вещей, которые вызывают эмоции у других. Например, у меня фракталы и их связь с реальным миром вызывают бурю эмоций. Астрономия, космос, математика в реальной жизни, все это лично у меня провоцирует шторм внутри.
Просто акценты и приоритеты меняются
Ну, во-первых, как уже здесь писали, абсолютная погрешность чисел Стирлинга стемится к бесконечности.
Во-вторых, я как раз к этому и веду, что при ограничениях можно как-то выкрутиться. Даже для тысячи, пускай не Вашим методом. А при их отсутствии всякие константы на размерность чего-либо теряют смысл.
Превратить ненулевое 32-битное знаковое число в 1 можно предоставленым Вами способом
Да, я что-то думал, что сравнивать дробные числа сложнее, чем целые) а принцип остается тот же.
тогда позовите сюда Вашого знакомого, интересно будет его аргументы послушать)
нет, я думаю для факториала решение
есть
поэтому некоторые класс таких задач уже можно решать подобным образом
int Rec(int n)
{
int a = -isPos(n);
return a&(n*Rec(n-1))+1-isPos(n);
}

isPos можно без ифов реализовать.

а так условных операторов вообще нету
да, действительно. можно использовать тот факт, что если
return (a&b);
и a равно нулю, то b не вычисляется. рекурсия спасает
ну если автор копал вглубь реализации встроенных хеш-таблиц, то Ваш код не подходит, так как все равно будет проверятся, чему равен индекс
есть желающие отсортировать массив дробных чисел без условных операторов?
Нет. Это то же самое, что использовать конструкцию
printf("%s", isCake(s)?«Yummy»:«Lie!!»);
В основе все равно if
автор старается избежать использования условных операторов вообще, а не только в явном виде.
а у Вас их многовато)
практически в любой задаче есть ограничения. Скажем, вычыслить n!.. 0<=n<=1000
поэтому в теории получается фиксированное количество операций. А если ограничений в задаче нету — тогда действительно невозможно
поскольку в реализации циклов условные операторы должны использоваться — то любую задачу, где количество итераций не константно, невозможно решить без условных операторов? (например тот же факториал)
Ох, вот это промазал так промазал =) есть к чему стремиться
1

Information

Rating
Does not participate
Location
Украина
Registered
Activity