Имеется 2 уникальных числа, скажем 145 и 1, идентифицируюшие пользователей. Между пользователями создается диалог. Задача сформировать уникальный ID диалога из двух ID пользователей, так, чтобы была симметрия вычисления этого уникального ID с двух сторон. Т-е id(unique) = (145+1) и это равно id(unique) = (1+145) Извините за не столько ясное объяснение - трудность в программировании - решил обратится к математике задан 2 Фев '14 3:47 Jony |
Насколько я понял, рассматриваются неупорядоченные пары, состоящие из двух различных натуральных чисел. Будем их записывать в таком виде, когда меньшее число идёт первым. Тогда эти пары можно перечислить в естественном порядке: (1;2), (1;3), (2;3), (1;4), (2,4), (3;4), ... . Сформулированная задача будет решена, если задать следующие функции: $%f(x;y)$% от двух переменных, вычисляющая номер пары $%(x;y)$% в списке (здесь $%x < y$% -- произвольные натуральные числа); $%g(n)$% и $%h(n)$%, каждая от одной переменной, где по номеру $%n$% пары $%(x;y)$% в списке вычисляются её первый элемент $%x=g(n)$% и второй элемент $%y=h(n)$%. Формулы при этом получаются следующие. Положим $$k=k(n)=\left\lceil{\frac{\sqrt{8n+1}-1}2}\right\rceil,$$ где скобки означают округление до ближайшего целого в сторону увеличения. Тогда $$h(n)=k(n)+1=\left\lceil{\frac{\sqrt{8n+1}+1}2}\right\rceil;\qquad g(n)=n-(k-1)k/2.$$ Функция $%f$% задаётся такой формулой: $$f(x;y)=(y-1)(y-2)/2+x.$$ Например: $%f(10;23)=21\cdot22/2+10=241$%; $%8\cdot241+1=1929$%; $%\sqrt{1929}=43,9...$%; $%k(241)=\lceil42,9.../2\rceil=22$%; $%h(241)=23$%; $%g(241)=241-21\cdot22/2=10$%. Доказательство формул несложное -- при желании, его можно привести. отвечен 2 Фев '14 4:21 falcao Большое спасибо за ответ! Но думаю это довольно "сложно", я решил остановиться на концепции меньшее число первым. Т-е на входе в функцию у меня два уникальных числа, они сравниваются и меньшее записывается первым, затем через тире, второе. в итоге. 1_145. это и будет уникальный ключ для пользователей с id = 1 и id = 145. Даже если на входе будет 145,1 или 1,145 все равно ключ преобразуется к 1_145
(2 Фев '14 4:32)
Jony
Если разрешено числа кодировать текстом, да ещё и использовать дополнительные символы, то тогда, конечно, проблемы нет вообще никакой. Запись 10,23 с запятой при этом ничем не отличается от записи 10_23 с "чёрточкой".
(2 Фев '14 4:35)
falcao
Да-верно. Большое спасибо. Сейчас до конца понять вашу формулу не удается) уже середина ночи и мозг спит) завтра обязательно перечитаю все.
(2 Фев '14 4:39)
Jony
@falcao, подскажите как появилась эта формула или покажите, пожалуйста, ее доказательство?
(7 Фев '14 22:40)
lemonc
Давайте я на примере покажу, как это получается. Рассмотрим пару (10;23). Перед ней идёт одна пара (1;2) со вторым элементом 2, две пары (1;3), (2;3) со вторым элементом 3, ..., 21 пара со вторым элементом 22. Итого 1+2+...+21=21*22/2=231 пара. А в списке пар вида (x;23) наша пара идёт 10-й, то есть она оказывается 241-я в списке. Это даёт формулы для нахождения g и h. А в обратную сторону нужно найти k, для чего решается несложное квадратное уравнение.
(7 Фев '14 22:47)
falcao
спасибо большое, то есть я правильно понял n- номер пары x, y - пара чисел где x<y результат n=f(x;y)=(y−1)(y−2)/2+x а h(n) и g(n) обратные функции, чтобы по номеру пары и одному из чисел получить другое число? или не правильно формулы понял?
(7 Фев '14 23:02)
lemonc
По номеру пары мы должны уметь получать оба числа. Поэтому "обратных" функций здесь две: x=g(n) и y=h(n). Обе они выражаются через k(n).
(7 Фев '14 23:20)
falcao
спасибо за ответ
(7 Фев '14 23:26)
lemonc
показано 5 из 8
показать еще 3
|