найти уникальный выход, основанный на двух входах? [дубликат]

Question

найти уникальный выход, основанный на двух входах? [дубликат]

На этот вопрос уже есть ответ здесь:

отображение двух целых чисел в одно уникальным и детерминированным способом

15 ответов

Мне нужно найти способ, такой, что пользователь должен ввести 2 числа (int) и для каждого другого значения один выход (int предпочтительно!) возвращенный.
Скажем, пользователь вводит 6, 8 он возвращает k, когда пользователь вводит что-либо еще подобно 6,7 или 9,8 или любому другому входу m, n, за исключением 6, 8 (даже если изменяется только один вход), получается совершенно другой выход. Но дело в том, что он должен быть уникален только для этого m, n, поэтому я не могу использовать что-то вроде m*n, потому что 6 X 4 = 24 но также, 12 X 2 = 24, поэтому выход не уникален, поэтому мне нужно найти способ, при котором для каждого другого входа есть совершенно другой выход, который не повторяется для любого другого значения.

EDIT: в ответ на Nicolas: диапазон ввода может быть что угодно, но будет меньше, чем 1000 (но больше, чем 1, конечно!)

EDIT 2 : в ответ на Rawling я могу использовать long (Int64) , но не предпочтительно использовать float или doulbe, потому что этот выход будет использоваться в цикле for, а float и double ужасны для цикла for, вы можете проверить это здесь

651 5

c#math algorithm unique

5 ответов:

Comments

Ничего не найдено.

Chowlett · Accepted Answer · 2012-05-29 11:01:32

Поскольку ваши два числа меньше 1000, вы можете сделать k = (1000 * x1) + x2, чтобы получить уникальный ответ. Максимальное значение будет равно 999999, что находится в пределах 32-битного int.

amit · Accepted Answer · 2012-05-29 11:06:08

Вы всегда можете вернуть a long: из двух целых чисел a и b, return 2^|INT_SIZE|*a + b

Это легко увидеть из принцип голубятни, что, учитывая два int, нельзя возвращать уникальный int для каждого другого входного сигнала. Пояснение: Если у вас есть 2 числа, каждое из которых содержит биты n, то для каждого числа есть возможности 2^n, и, следовательно, есть возможные пары (2^n)^2, поэтому из принципа piegeonhole-вам нужно, по крайней мере, биты lg_2((2^n)^2) = 2n, чтобы представить их,

EDIT : ваш edit упоминает диапазон ваших чисел [1,1000] - таким образом, можно применить ту же идею: 1000*a + b создаст уникальный int для каждой пары. Обратите внимание, что по тем же причинам диапазон результирующего целого числа должен быть [1,1000000] - или вы получите столкновения.

awesomelemonade · Accepted Answer · 2015-12-31 18:48:43

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

Функции спаривания, такие как функция спаривания Кантора(показанная на предыдущей ссылке) и функция спаривания Шудзика, которая позволяет входам быть бесконечными и все еще быть в состоянии обеспечить уникальный и детерминированный выход.

Вот еще один аналогичный вопрос о stackoverflow. (Отлично, мне нужно 10 репутации, чтобы разместить более двух ссылок..)

(http://) stackoverflow.com/questions/919612/mapping-two-integers-to-one-in-a-unique-and-deterministic-way

Правка: я опаздываю.

Rawling · Accepted Answer · 2012-05-29 11:10:07

Если у вас нет жесткой верхней границы, вы можете сделать следующее:
int Unique (int x, int y)
{
    int n = x + y;
    int t = (n%2==0) ? ((n/2) * (n+1)) : (n * ((n+1)/2));
    return t + x;
}
Говоря математически, это вернет уникальное неотрицательное целое число для каждой (неотрицательной) пары целых чисел без верхней границы. Говоря программно, он столкнется с проблемами переполнения, которые можно преодолеть, используя long вместо int для всего, кроме входных переменных.

Joel in Gö · Accepted Answer · 2012-05-29 11:34:49

Каноническое математическое решение состоит в использовании простых степеней. Поскольку каждое число можно разложить однозначно на его простые множители, возвращая 2^n * 3^m, вы получите различные результаты для каждого n и m.

Это может быть расширено до 2^n * 3^m * 5^a * 7^b *11^c и так далее; вам нужно только проверить, что у вас не закончились 32-разрядные целые числа. Если есть риск переполнения, вы можете взять остаток после деления на простое число, большее, чем ваш входной диапазон, и у вас все равно будет уникальность.