Алгоритм для нахождения количества пересечений отрезков в последовательности(списке)?

dollar, Обобщение это задачи (подсчитать сколько клеток покрыто отрезками на прямой) - это прямоугольники на плоскости. И там точно такой же трюк есть: в 4 угла поставить +1 и -1 (по диаганали знаки, правые/верхние сдвинуты на 1 наружу). Потом делаем 2 прохода по плоскости - сначала по строкам, потом по столбцам: и также накапливаем частичные суммы.

Если плоскость большая и надо, допустим, самую плотно покрытую точку найти - то можно двумерное дерево отрезков запилить. Или для экономии памяти - мою любимую структуру данных: дерево отрезков декартовых деревьев (в бинарном дереве точно также можно делать добавление на отрезке, как и в дереве отрезков).

Если же брать другое обобщение этой задачи - именно отрезки на плоскости, то там уже общих пересечений особо может и не быть вообще. Ибо два отрезка на плоскости пересекаются по точке. Что вы там хотите найти - все точки пересечения?

Но в таких задачах все-равно часто работает метод сканирующей прямой (решение, что я привел к вопросу - по сути и есть частный случай этого метода). Там можно, например, найти есть ли пересечение среди N отрезков за N log N.

Алгоритм для нахождения количества пересечений отрезков в последовательности(списке)?

Сергей Соколов, Почему? +1 ставится в позицию 1, -1 в позицию 2 (я же написал "в координату за правым концом").
При проходе сделаем +1 в позиции 1 и выведем 1. Потом в позиции 2 вычтем 1 и получим правильный 0.

Edit, слегка подправил формулировку в ответе, чтобы понятнее было.

Как понять цифры хэмминга на пальцах?

Alexandroppolus, Вообще, есть идея не хранить сами числа, а хранить только степени 2, 3 и 5 и вычислять большое число только в самом конце. Но тогда надо уметь 100% точно сравнивать 2 числа в таком виде. Если сравнивать ln2*i+ln3*j+ln5*k, то у дабла должно вполне хватить точности на много дольше, чем если бы в int64_t числа считать.

Как понять цифры хэмминга на пальцах?

Alexandroppolus, Это не так важно, потому что эти самые числа растут експоненциально (если до N их O((lnN)^3) - значит K-ое число порядка O(e^(k^(1/3))). Поэтому гораздо раньше придется беспокоится об длинной арифметике и размере самих чисел, преже чем о их количестве.

Теперь про размер списка. Ваш анализ не совсем точен. N - это само послледнее число. ln N - его длина. Растет оно примерно как количество чисел ^1/3. Таким образом, если вы генерируете первые K чисел, вам надо O(k^2/3) чисел. Не слишком большая экономия.

Как понять цифры хэмминга на пальцах?

TheSnegok, Это числа, которые могут делиться только на 2,3 и 5.

2 = 2^1*3^0*5^0

i=1 j=0 k=0

Как понять цифры хэмминга на пальцах?

Ну вот 2, 3, 4, 5, 6, 8, 9, 12, 15 - это числа хемминга, потому что они являются произведением сколько-то двоек, троек и пятерок. 7, 14 и 23 - не являются, потому что в разложении на простые множители содержат еще что-то кроме 2, 3 и 5.

Что за алгоритм вам надо описать-то?

Итерационное вычисление больших степеней числа по цифрам?

Rsa97, Опишите свой алгоритм на бумажке и попробуйте подсчитать, сколько там операций. Все те же самые O(L^2) вы и получите. Тот логарифм, который вы сюда впихиваете - он от числа X - и будет как раз длиной L.

Не зря умные дядьки 60 лет голову ломают над алгоритмами быстрого умножения длинных чисел.

Итерационное вычисление больших степеней числа по цифрам?

Оберните код в тег code (кнопка </> в редакторе). Иначе вопрос удалят.

Итерационное вычисление больших степеней числа по цифрам?

Важное замечание - этот алгоритм будет быстрее наивного, только если использовать быстрое преобразование фурье для собственно умножения чисел.

Ну, или если вам ответ только по модулю нужен.

Область видимости c Arduino. Как передать define в библиотеку?

red_crocodile, массив - указать и длина. Вам можно длину прередавать везде вместе с массивами. Создается массив через malloc (или new, если у вас, таки, C++)

Есть ряд 1/1+1/2+1/3+1/5+1/7+1/11+1/13+... В общем ряд состоит из единицы деленной на простое число. Вопрос в том сходится ли он и к какому числу?

ThunderCat,
Ваша логика вообще не работает. Например, сумма обратных для всех чисел, не содержащих цифру 7 в записи - сходится. А таких, кажется, нисколько не меньше, чем простых чисел. А сумма обратных простым - расходится.

Как посчитать БЖУ?

Alexandroppolus, Ну раз человек про рюкзак сказал, то я подумал, что нельзя съесть 0.66 яйца и 1.35 сала.

Если можно есть сколько угодно чего угодно - то да - задача тупо система линейных уравнений.

Как определить последовательность действий?

longclaps, Какая разница, что за пространство. Главное, что в нем метрика есть - количество шагов. Осталось только эвристику подобрать. Это может быть не тривиально, но, например, если все действия меняют ровно одно поле в зависимости от каких-то условий, то может быть эвристика - сколько полей не совпало с конечным состоянием. Эта эвристика допустима - она не переоценивает никакой путь. Она еще и консистентна. Отлично подходит для A*.

Как узнать, пересекутся векторы?

x1-0; y1-0;

- это же нулевой вектор?

Vx1=40; Vy1=0;

- Т.е. у вас какие-то параметрически заданные лучи? Начиная с точки {x1, y1} вдоль вектора {Vx1, Vy1}? И надо проверить, что два луча пересекутся? Это лучи или прямые - считается ли пересечением, если вектор Vx, Vy отложить назад, т.е. вычесть из начальной точки?

Имеет ли значение "время"?
Например вот эти два "вектора" пересекаются ли?
x1=0, y1=0 vx1=1 vy1 = 0
x2=1, y2 = -2, vy2=0 vy2=1

Тут на первом луче надо вектор направления отложить 1 раз, а на втором - 2 раза. Если это физические точки движущееся с заданными скоростями. Они пройдут через одну и ту же точку, но в разное время.

Как передать в функцию указатель если она принимает ссылку?

dominy, Этот вариант универсален. Просто переменная - это массив длинны 1:

uint8_t var;
readMyMemory<uint8_t>(0x12345, 1, &var);

Алгоритм поиска минимального количества ходов, требуемых для приведения всех элементов к одному числу (Python)?

AniArim, Вам уже ниже сказали - надо в качестве цели выбрать медиану всех чисел. Потому что при сдвиге цели на 1 вправо вы прибавляете столько, сколько числел слева и вычитаете столько, сколько чисел справа. Поэтому, если справа чисел больше, чем слева - то надо двигаться вправо и т.д. В итоге остановимся или на среднем числе (если их нечетно) или можно выбрать любое число из интервала между двумя средними (если чисел в массиве четное количество).

Ваши эвристики с выбором среднего не работают. Вам надо или отсортировать массив и брать среднее число или писать quickselect. Думаю в задаче достаточно будет отсортировать - вряд ли у вас там миллионы чисел в массиве.

Можно ли с помощью итератора для векторов(std::vector::iterator) создать вектор в куче?

> потом для того чтобы передать итератор на этот вектор я хотел бы присвоить итератору значение указателя на вектор

Итераторы по сути являются указателями на содержимое вектора. Поэтому если у вас функция принимает итераторы, то вы передавайте туда условынй vector->begin(). И этой функции должно быть глубоко пофигу - исходный вектор там в куче или в стеке.

Можно ли с помощью итератора для векторов(std::vector::iterator) создать вектор в куче?

IliaNeverov, опишите, что вы хотите сделать вообще. Вам куда-то дается итератор, вы хотите завести новый вектор? Или вы хотите итератор передать в какой-то конструктор? Пока вопрос звучит вроде "можно ли кастрюлей построить кухню?"

Кстати, содержимое векторов итак хранится на куче в большинстве случаев.

Как прочитать масив данных динамической длинны?

dominy, передавайте функции указатель на type, а не ссылку. Для чтения строки вам надо в щаблон передать wchar_t. Не указатель а просто тип.

Распишите для себя, что ваша функция делает. Она читает массив типа type длины length, и сохраняет его по заданному адресу.

Как прочитать масив данных динамической длинны?

dominy, Смотрите внимательно - ваша функция возвращает wchar_t. А вы присваиваете указателю на wchar_t. Но, если вы поменяете ее, чтобы возвращать указатель, то вам придется выделять память внутри функции.

Советую поменять фнукию так, чтобы она принимала указатель - куда положить данные и возвращала статус - получилось ли у нее прочитать.