Ответ на программистскую задачу
Feb. 28th, 2008 02:39 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkПро три числа
Первоначальное, математичное, решение было у меня такое:
Выберем из трех чисел два (A и B) так, чтобы их четность различалась (это желательно, но если четность всех трех одинакова, то не беда), а у третьего (C) был какой-нибудь бит, однозначно отличающий его от двух остальных.
Без потери общности будем считать, что при x=A должно получаться B, а при x=B - C. Построим "линейную" функцию:
Y = x*(C-B)/(B-A) + (B2-AC)/(B-A)
Вместо целочисленного деления на (B-A) воспользуемся умножением на обратное по модулю 232. Два числа обратны друг другу, если их произведение равно 1 (у четных чисел обратных нет, но с этим мы разберемся чуть позже). Как же найти обратное к N?
Обратим внимание, что если нечетное число возвести в квадрат, то количество нулей между неизменной единицей в младшем бите и ближайшей старшей единицей увеличивается (действительно, (n*2k + 1)2 = n2*22k + n*2k+1 + 1). Поэтому будем возводить N в квадрат, пока результат не станет равен 1, т.е. пока все лишнее не уедет за пределы разрядной сетки, а потом перемножим все промежуточные результаты, включая первоначальное N. В результате окажется число, которое если [еще раз] умножить на N, то получится 1, т.е. как раз обратное к N.
Если B и A одной четности - будем искать функцию, которая при x = A>>n дает B, а при x=B>>n дает C, где n - такое, что младшие биты A>>n и B>>n различаются. Назначать соответствие между числами и A-B-C, естественно, нужно так, чтобы все уникальные биты C не были в младших n разрядах.
Пока у нас получилось выражение f(x) = (x>>n)*K + M, где f(A) = B, f(B) = C, n - число совпадающих младших бит в A и B.
Теперь осталось лишь скорректировать значение выражения для x=C, не трогая значения при x=A и x=B. Пусть p - номер уникального бита в C, а q - его значение.
Ответ: f(x) + (A - f(C))*((x>>p)&1^(1-q))
Более простое решение, которое мне кажется наиболее прямолинейным, вытекает из того, что найдется как минимум два числа, у которых есть хоть один уникальный бит, поэтому не нужно мучиться с обратным по модулю и с четностями, а всего лишь A+(B-A)*((x>>pA)&1^(1-qA)) + (C-A)*((x >> pB)&1^(1-qB))
Еще более короткое, но требующее приведения к беззнаковому типу решение дал![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
kcmamu: http://spamsink.livejournal.com/189838.html?thread=1171854#t1171854
Первоначальное, математичное, решение было у меня такое:
Выберем из трех чисел два (A и B) так, чтобы их четность различалась (это желательно, но если четность всех трех одинакова, то не беда), а у третьего (C) был какой-нибудь бит, однозначно отличающий его от двух остальных.
Без потери общности будем считать, что при x=A должно получаться B, а при x=B - C. Построим "линейную" функцию:
Y = x*(C-B)/(B-A) + (B2-AC)/(B-A)
Вместо целочисленного деления на (B-A) воспользуемся умножением на обратное по модулю 232. Два числа обратны друг другу, если их произведение равно 1 (у четных чисел обратных нет, но с этим мы разберемся чуть позже). Как же найти обратное к N?
Обратим внимание, что если нечетное число возвести в квадрат, то количество нулей между неизменной единицей в младшем бите и ближайшей старшей единицей увеличивается (действительно, (n*2k + 1)2 = n2*22k + n*2k+1 + 1). Поэтому будем возводить N в квадрат, пока результат не станет равен 1, т.е. пока все лишнее не уедет за пределы разрядной сетки, а потом перемножим все промежуточные результаты, включая первоначальное N. В результате окажется число, которое если [еще раз] умножить на N, то получится 1, т.е. как раз обратное к N.
Если B и A одной четности - будем искать функцию, которая при x = A>>n дает B, а при x=B>>n дает C, где n - такое, что младшие биты A>>n и B>>n различаются. Назначать соответствие между числами и A-B-C, естественно, нужно так, чтобы все уникальные биты C не были в младших n разрядах.
Пока у нас получилось выражение f(x) = (x>>n)*K + M, где f(A) = B, f(B) = C, n - число совпадающих младших бит в A и B.
Теперь осталось лишь скорректировать значение выражения для x=C, не трогая значения при x=A и x=B. Пусть p - номер уникального бита в C, а q - его значение.
Ответ: f(x) + (A - f(C))*((x>>p)&1^(1-q))
Более простое решение, которое мне кажется наиболее прямолинейным, вытекает из того, что найдется как минимум два числа, у которых есть хоть один уникальный бит, поэтому не нужно мучиться с обратным по модулю и с четностями, а всего лишь A+(B-A)*((x>>pA)&1^(1-qA)) + (C-A)*((x >> pB)&1^(1-qB))
Еще более короткое, но требующее приведения к беззнаковому типу решение дал
kcmamu: http://spamsink.livejournal.com/189838.html?thread=1171854#t1171854
