algorithm - 将一个整数范围的整数映射到另一个整数范围的数学算法?

  显示原文与译文双语对照的内容

一个时间效率和空间高效算法,用于线性映射整数( 假设间隔为 I1 [A..B]> =A )的离散范围,成为另一个整数( 假设间隔 I2 [C..D],其中D> =C ) 。

为了简单地演示,第二个范围的,的大小约限于或者等于第一个范围的x 。

因此,I1中的每个整数映射到一个或者多个包含在 I2 ( 因为I2的大小大于I1的大小) 中的。 相反,I2中的每个整数都返回到中对应的唯一对应整数。

因此,有两种需要的算法,它们在两个提供的整数间隔域中操作: 间隔 I1 [A..B] 和间隔 I2 [C..D] ( 其中B> =A和D> =C和D c> = B )

算法 A1: 给定了一个包含在ast中的整数X,计算了of中相应的线性映射集。 将这里表示为 A1(I1,I2,X) = [M..N],其中 [M..N] 是i的子间隔。

算法 A2: 给定区间1 中包含的整数Y,计算I1中的单个对应整数。 将这里表示为 A2(I1,I2,Y) = X 。

算法A2必须是A1的对称逆。 即,对于I1中的所有X: A1(I1,I2,X) = [M..N],然后为 [M..N] 中的所有Y: A2(I1,I2,Y) = X

显然,由于这个问题被约束为整数,映射可能不是完全线性的。 例如如果I1包含3 个整数,而I2包含4 个整数,那么2 中的2 个整数将有一个映射,1 中的第2 个整数将包含2 个映射。 包含两个映射的I1的特定整数不相关。 重要的是,算法A1选择的整型( X ) 有两个映射,然后算法A2必须将这些相同的两个Y 值映射回原来的X 。

算法A1和A2应该创建从I1到I2的最线性映射。 换句话说,如果间隔为J,区间为 I2,则I1的每个整数都具有TRUNC映射或者 TRUNC ( K/J ) +1映射到i 。

这些算法应该使用固定空间,因此由一组可能使用截断整数除法和模块运算的代数方程和其他基本数学函数组成。 换句话说,算法不能为需要空间存储每个映射的映射创建表,因为整数间隔的大小最多可以达 2 ^64.

编辑:假设间隔 I1 = [0..2] 和间隔 I2 = [0..4] 。 一个正确的解决方案可能是:


Algorithm A1 Algorithm A2


X=0, Y=[0..1] Y=0, X=0


X=1, Y=[2..3] Y=1, X=0


X=2, Y=[4] Y=2, X=1


 Y=3, X=1


 Y=4, X=2



另一个同样正确的解决方案是:


Algorithm A1 Algorithm A2


X=0, Y=0 Y=0, X=0


X=1, Y=[1..2] Y=1, X=1


X=2, Y=[3..4] Y=2, X=1


 Y=3, X=2


 Y=4, X=2



不正确的解决方案是:


Algorithm A1 Algorithm A2


X=0, Y=[0..1] Y=0, X=0


X=1, Y=[2..3] Y=1, X=1


X=2, Y=[4] Y=2, X=1


 Y=3, X=2


 Y=4, X=2



上述解决方案不正确。 虽然A1将 [0..2] 线性映射到 [0..4],而A2将 [0..4] 线性映射回 [0..2],问题是A2不是A1的逆。 例如,对于 X=0,A1(0)的一个值是 Y=1,但 A2(1) 给出 X=1 ( 而不是 0的原始值) 。

时间: 原作者:

你可以使用一个乘法和一个偏移来轻松地完成这个操作。 从减法开始,然后进行乘法逆计算,然后通过添加C 来翻译结果。

若要反转它,请减去D,执行乘法逆计算的逆,并添加。

这工作很好。我曾经用过它,效果不错。

原作者:
...