а есть ссылка?
https://www.codewars.com/kata/596d34df24a04ee1e3000a25
Maks
Vladislav
паучье чутьё подсказывает мне, что нужно решать методами т.н. "динамического программирования"
Vladislav
разбивая задачу на подзадачи и потом объединяя решения
Vladislav
скажем, сумма от 0 до 255 будет равна сумме от 0 до 127 + (127 * сумма от 0 до 127)
John
Например тебе дают 1 и 12, нужно от 1 до 12 переводить в двоичную и считать кол-во едениц и складывать
Эммм, единица же это степнь двойки, что если брать округление в большую сторону логарифм от числа по основанию 2?
Vladislav
и т.д.
John
Например тебе дают 1 и 12, нужно от 1 до 12 переводить в двоичную и считать кол-во едениц и складывать
Если от 14 до 6985256, то единиц там будет = (сколько единиц в двоичной 14) + сумма арифметической прогрессии n+1 , где n = 14, а последний элемент - 6985256
Maks
По моему там надо от 0 до 14 и от 0 до второго числа найти одной формулой
Maks
а потом взять разницу
Maks
но как формулу нахождения найти я пока не осилил
John
По моему там надо от 0 до 14 и от 0 до второго числа найти одной формулой
Если сумму единиц бинарного представления от N до M, то ты прав- сумма чисел от (кол-во единиц в минимуме) до (кол-во единиц в максимуме), т.е. сумма ряда или сумма арифметической прогрессии. Так даже лучше с твоей поправкой
Илья
так а по биту сдвигать?
Илья
и просто & 1
Илья
или это в таймаут уходит?
Maks
ты посчитаешь в конкретном числа а тебе надо в диапазоне
Илья
аа
Maks
слишком долго будет для миллиарда значений
Maks
Эммм, единица же это степнь двойки, что если брать округление в большую сторону логарифм от числа по основанию 2?
ля, вот оно, когда матана не хватает)
Maks
Я ваще не помню что такое логарифмы)
Maks
но это то что мне было нужно)
John
Если N - это 2^x, а M - это 2^y+1, то сумма единиц в диапазоне будет : 2^(y-x) +1
John
Илья
да чувачки на расте через строки решили и прошли по времени
Илья
не то что медленный го
Maks
так там не в строках медленность в основном а в кол-во итераций
John
Если N - это 2^x, а M - это 2^y+1, то сумма единиц в диапазоне будет : (2^(2*(y-x)) + (y-x)) + 1
Maks
for i := 0; i < 20000000000
John
John
А какая алгоритмическая сложность вычисления логарифма?
Maks
2 в степени (2 * (15) + 15)+1?
John
264
John
«+1» - это я для нечетного максимума
John
1 - это 2^0
John
Да, я ошибаюсь, но уверен что задачу можно решить математически. Если упираемся в итерации - лучше отказаться от итераций
Юра (Юрий Александрович)
Мне с вашей задачей все понятно.
Юра (Юрий Александрович)
Если диапазон наших чисел от 0 до 2^n, то количество единиц по всех этих числах посчитать можно по формуле (формула в разработке).
Если же диапазон наших чисел другой, то его надо выразить по-другому. так, чтобы в нем оказались только диапазоны вида 0..2^n
Maks
Не до 2^n а просто до любого числа
Юра (Юрий Александрович)
а любое число можно представить в виде 2^n1+2^n2+2^n3...
Maks
Задача находить между двумя любыми числами. Но проще от нуля (1) до любого числа и потом дифф брать
Юра (Юрий Александрович)
С рекурсией получится задача.
John
Рекурсия упрется в глубину 255
Юра (Юрий Александрович)
во-первых, в Го рекурсия в 255 не упирается. Во-вторых, там не так много вложенностей будет.
John
почему?
Рекурсия формирует стек вложенных вызовов и имеет ограничение в го. При неосмотрительностей использование См.рекурсивный взрыв
Илья
Юра (Юрий Александрович)
итак, еще раз.
Допустим, надо найти в диапазоне от 0 до 13.
Это все равно, что в диапазоне от 0 до 15 минус то, что в диапазоне от 14 до 15.
Юра (Юрий Александрович)
в диапазоне от 0 до 15 - понятно сколько, т.к. это всевозможные комбинации из 4 двоичных разрядов, теперь надо понять, что надо отнять...
John
итак, еще раз.
Допустим, надо найти в диапазоне от 0 до 13.
Это все равно, что в диапазоне от 0 до 15 минус то, что в диапазоне от 14 до 15.
Классная идея уйти от конкретных чисел на показатели степени и свободный член
Юра (Юрий Александрович)
а дальше этот свобоный член нужно снова бить на диапазоны с показателем степени, пока он не превратится в одно число
Юра (Юрий Александрович)
В каждом диапазоне 0..2^n количество единиц следующее: 2^n*n/2
John
Логарифм от числа округлённый в большую сторону равен кол-ву единиц?
Юра (Юрий Александрович)
Yura
Есть же специальный метод для перевода числа в двоичное 🤡
Юра (Юрий Александрович)
Есть же специальный метод для перевода числа в двоичное 🤡
Там по условию задачи чисел может быть очень большое количество (миллиарды миллиардов)
Maks
Я эту же зависимость нашел но не смог ее в формулу выразить
Юра (Юрий Александрович)
Назовем величину "количество единиц в числах в диапазоне от 0 до 2^n" C(n) (а то писать неудобно)
так вот... по этой таблице видно, что C(n)=c(n-1)*2+2^(n-1)
Юра (Юрий Александрович)
(я, может быть, пока что напутал с +-1 в степенях, т.к. еще четко не подписал, где у меня какие n)
Yura
Вот эт инженеры, сразу видно не просто крудошлепы
Юра (Юрий Александрович)
Нашел ошибку.
Нам надо оперировать диапазонами 0...2^n-1
Юра (Юрий Александрович)
значит C(n) - это "количество единиц в числах от 0 до 2^n-1"
Юра (Юрий Александрович)
John
Получается сумма единиц бинарных представлений чисел от N до M можно вычислить по формуле
X=Math.Ceil(log2(N))
Y=Math.Ceil(log2(M))
((Y-X)*(Y-X+1))/2
John
Юра (Юрий Александрович)
C(1)=1
C(2)=C(2-1)*2+2^(2-1)=C(1)*2+2^1=1+1+2=4
Юра (Юрий Александрович)
Юра (Юрий Александрович)
C(3)=C(3-1)*2+2^(3-1)=C(2)*2+2^2=4*2+4=12
John
явно получаются нецелые числа
Четно умножение на нечётно всегда будет четным, при деление на 2 будет целым
Юра (Юрий Александрович)
x=Log2(N ) может быть нецелым, Y- тоже, их сумма или разность - тоже. И там уже ничего не исправить.