нечестное решение
Nov. 21st, 2014 01:14 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ile_eliДочка загадала загадку:
имеется массив длины n с целыми числами от 1 до n-1. Разумеется, хотя бы одно число появляется дважды (а может, вообще все одинаковые - это уж как повезет). Нужно найти хотя бы одно повторяющееся число за время порядка n, используя память порядка 1.
Решение (некрасивое и нечестное): суммируем 2^A(i). На каждом шаге перед тем, как возвести 2 в степень следующего числа и прибавить к результату, смотрим, какой остаток суммы при делении на 2^(A(i)+1). Если он больше или равен 2^A(i), значит оно уже было.
Жульничество в том, что вместо того чтоб добавлять ячейки памяти, мы одну раздуваем сколько вздумается.
А морали никакой, никакой, никакой, (с)
имеется массив длины n с целыми числами от 1 до n-1. Разумеется, хотя бы одно число появляется дважды (а может, вообще все одинаковые - это уж как повезет). Нужно найти хотя бы одно повторяющееся число за время порядка n, используя память порядка 1.
Решение (некрасивое и нечестное): суммируем 2^A(i). На каждом шаге перед тем, как возвести 2 в степень следующего числа и прибавить к результату, смотрим, какой остаток суммы при делении на 2^(A(i)+1). Если он больше или равен 2^A(i), значит оно уже было.
Жульничество в том, что вместо того чтоб добавлять ячейки памяти, мы одну раздуваем сколько вздумается.
А морали никакой, никакой, никакой, (с)
