想象两个正整数A和b,我想把这两个组合成一个整数C。
不可能有其他整数D和E组合成C。 所以把它们和加法运算符结合是不行的。例:30 + 10 = 40 = 40 + 0 = 39 + 1 连接也不管用。例如“31”+“2”= 312 =“3”+“12”
这种组合操作也应该是确定的(总是用相同的输入产生相同的结果),并且应该总是在整数的正侧或负侧产生一个整数。
想象两个正整数A和b,我想把这两个组合成一个整数C。
不可能有其他整数D和E组合成C。 所以把它们和加法运算符结合是不行的。例:30 + 10 = 40 = 40 + 0 = 39 + 1 连接也不管用。例如“31”+“2”= 312 =“3”+“12”
这种组合操作也应该是确定的(总是用相同的输入产生相同的结果),并且应该总是在整数的正侧或负侧产生一个整数。
当前回答
我们可以在O(1)空间和O(N)时间内将两个数字编码为1。 假设您希望将0-9范围内的数字编码为1,例如。5和6。怎么做呢?简单,
5*10 + 6 = 56.
5 can be obtained by doing 56/10
6 can be obtained by doing 56%10.
即使是两位数的整数,比如56和45,56*100 + 45 = 5645。我们同样可以通过执行5645/100和5645%100来获得单个数字
但对于一个大小为n的数组,例如。A ={4,0,2,1,3},假设我们想对3和4进行编码,那么:
3 * 5 + 4 = 19 OR 3 + 5 * 4 = 23
3 :- 19 / 5 = 3 3 :- 23 % 5 = 3
4 :- 19 % 5 = 4 4 :- 23 / 5 = 4
通过推广,我们得到
x * n + y OR x + n * y
但我们还需要注意改变的值;所以结果是
(x%n)*n + y OR x + n*(y%n)
你可以通过除法和对结果取余来得到每个数字。
其他回答
构造一个映射并不难:
1 2 3 4 5 use this mapping if (a,b) != (b,a) 1 0 1 3 6 10 2 2 4 7 11 16 3 5 8 12 17 23 4 9 13 18 24 31 5 14 19 25 32 40 1 2 3 4 5 use this mapping if (a,b) == (b,a) (mirror) 1 0 1 2 4 6 2 1 3 5 7 10 3 2 5 8 11 14 4 4 8 11 15 19 5 6 10 14 19 24 0 1 -1 2 -2 use this if you need negative/positive 0 0 1 2 4 6 1 1 3 5 7 10 -1 2 5 8 11 14 2 4 8 11 15 19 -2 6 10 14 19 24
求任意a b的值有点难。
假设我们有两个数字B和C,把它们编码成一个数字A
A = b + c * n
在哪里
B= a % n = B
C= a / n = C
f(a, b) = s(a+b) + a,其中 s(n) = n*(n+1)/2
这是一个函数,它是确定的。 它也是单射的——f映射不同(a,b)对的不同值。你可以证明 它使用的事实是:s(a+b+1)-s(a+b) = a+b+1 <一个。 它返回非常小的值——如果你打算用它来做数组索引,那很好,因为数组不需要很大。 它是缓存友好的——如果两个(a, b)对彼此接近,那么f将彼此接近的数字映射到它们(与其他方法相比)。
我不明白您所说的:
应该总是产生一个整数 不管是积极的还是消极的 整数的边
我如何在这个论坛写(大于),(小于)字符?
给定正整数A和B,设D = A的位数,E= B的位数 结果可以是D, 0, E, 0, a和B的串联。
示例:A = 300, B = 12。D = 3, E=2 result = 302030012。 这利用了一个事实,即唯一以0开头的数字是0,
优点:易于编码,易于解码,人类可读,有效数字可以先比较,潜在的比较无需计算,简单的错误检查。
缺点:结果的大小是个问题。不过没关系,我们为什么要在电脑里存储无界整数呢。
正整数的标准数学方法是利用质因数分解的唯一性。
f( x, y ) -> 2^x * 3^y
缺点是,图像往往跨越相当大的整数范围,因此当涉及到在计算机算法中表示映射时,您可能会在为结果选择适当的类型时遇到问题。
你可以修改它来处理负x和负y,通过编码一个5和7次幂项的标志。
e.g.
f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)