Python 高级模运算算法
Python Advanced Modular Arithmetic Algorithm
我有这个程序：
#!/usr/bin/python3
def bounce(modulo: int, here: int, add: int) -> int:
# additive version
# modulo = 2n > 0, 0 <= here < n, add is any integer
# cycle {
# {0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...,
# 0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...},
# {0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...,
# 0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...},
# ...
# }
tmp = abs(here + add) % (2 * modulo)
if tmp <= modulo:
tmp *= -1
tmp -= 1
tmp %= modulo
return tmp
m = abs(int(input('Modulus: '))) + 1
i = abs(int(input('Iterate: '))) + 1
h: int = 0
m2: int = 3 * m
for x in range(1, 1 + i):
print(h, end = ('\n' if x % m2 == 0 else ', '))
h = bounce(m, h, 1)
input('Done.')
出于某种原因，bounce() 函数或其测试代码无法正常工作。我不知道为什么。例如，如果我为模数输入 6，为迭代变量 i 输入 4，程序应该打印 5 行 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0。相反，我会看到 2 行 6, 0, 6, 0, ...。答案可能很简单。我已经为这个 bounce() 函数绞尽脑汁了很多次，以至于我看不到它。 add 参数的标志让我感到困惑。
您可能不需要生成整个序列，以下是一个封闭形式的实现，它计算和 returns 您希望在 go- 中迭代的给定大小的序列中的索引来回循环时尚：
您可以从任何时间点开始，包括过去（负时间），并获取您在序列（索引）中的位置，而无需迭代或构建整个序列。
def bounce_back_and_forth(size: int, start_t: int=0)->int:
"""returns the index position in a sequence at time t=t, when the index starts
at position zero at time t=0, and walks the list from end to end, and and bounces
back and forth.
returns the index for all t in Z
@param size: int, the size of the sequence to iterate over
@param start_t: int, the starting indice (usually time), zero by default
:return: the index in the sequence corresponding to the start_t provided
closed form, no iteration necessary --> O(1) time & space complexity
size=5 size=5 size=5
start at t=0 start at t=6 start at t=-1 and decreases
0 [0, _, _, _, _] 6 [_, _, 2, _, _] -1 [_, _, _, _, 4]
1 [_, 1, _, _, _] 7 [_, 1, _, _, _] -2 [_, _, _, 3, _]
2 [_, _, 2, _, _] 8 [0, _, _, _, _] -3 [_, _, 2, _, _]
3 [_, _, _, 3, _] 9 [_, 1, _, _, _] -4 [_, 1, _, _, _]
4 [_, _, _, _, 4] 10 [_, _, 2, _, _] -5 [0, _, _, _, _]
5 [_, _, _, 3, _] 11 [_, _, _, 3, _] -6 [_, 1, _, _, _]
6 [_, _, 2, _, _] 12 [_, _, _, _, 4] -7 [_, _, 2, _, _]
7 [_, 1, _, _, _] 13 [_, _, _, 3, _] -8 [_, _, _, 3, _]
8 [0, _, _, _, _] 14 [_, _, 2, _, _] -9 [_, _, _, _, 4]
9 [_, 1, _, _, _] 15 [_, 1, _, _, _] -10 [_, _, _, 3, _]
10 [_, _, 2, _, _] 16 [0, _, _, _, _] -11 [_, _, 2, _, _]
"""
go_and_back = size * 2 - 2
if start_t < 0:
start_t = size - abs(start_t) % go_and_back
tdx_at_start_t = start_t % go_and_back
if tdx_at_start_t >= size:
tdx_at_start_t = go_and_back - tdx_at_start_t
return tdx_at_start_t
if __name__ == '__main__':
# tests
res = [0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1]
for idx in range(18):
actual, expected = bounce_back_and_forth(5, start_t=idx), res[idx]
assert actual == expected
stride = 0
for _ in range(5):
mod = 8 # the size of the sequence to iterate over
start = 0
stride += 1
print(f'size: {mod}, stride: {stride} -> ', end='')
for tdx in range(start, 20, stride): # <-- get indices for 20 time steps ahead
print(bounce_back_and_forth(mod, tdx), end=' ')
print()
输出：
size: 8, step: 1 -> 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0 1 2 3 4 5
size: 8, step: 2 -> 0 2 4 6 6 4 2 0 2 4
size: 8, step: 3 -> 0 3 6 5 2 1 4
size: 8, step: 4 -> 0 4 6 2 2
size: 8, step: 5 -> 0 5 4 1
测试：
class TestBounceBackAndForth(unittest.TestCase):
def test_size5_t0(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=0), 0)
def test_size5_t3(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=3), 3)
def test_size5_t4(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=4), 4)
def test_size5_t5(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=5), 3)
def test_size5_t6(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=6), 2)
def test_size5_t7(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=7), 1)
def test_size5_t8(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=8), 0)
def test_size5_t9(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=9), 1)
def test_size5_t10(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=10), 2)
def test_size5_t11(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=11), 3)
def test_size2_t0(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=0), 0)
def test_size2_t1(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=1), 1)
def test_size2_t2(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=2), 0)
def test_size2_t3(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=3), 1)
def test_size2_t4(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=4), 0)
def test_size15_t7(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=7), 7)
def test_size15_t8(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=97), 13)
# --- Negative Indices ------------
def test_size5_t_m1(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-1), 4)
def test_size5_t_m2(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-2), 3)
def test_size5_t_m3(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-3), 2)
def test_size5_t_m4(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-4), 1)
def test_size5_t_m5(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-5), 0)
def test_size5_t_m6(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-6), 1)
def test_size5_t_m7(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-7), 2)
def test_size5_t_m8(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-8), 3)
def test_size5_t_m9(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-9), 4)
def test_size5_t_m10(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-10), 3)
def test_size5_t_m11(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-11), 2)
def test_size2_t_m1(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=-1), 1)
def test_size2_t_m2(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=-2), 0)
def test_size2_t_m3(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=-3), 1)
def test_size2_t_m4(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=-4), 0)
def test_size15_t_m7(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=-7), 8)
def test_size15_t_m8(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=-8), 7)
def test_size15_t_m97(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=-97), 2)
if __name__ == '__main__':
unittest.main()
我有这个程序：
#!/usr/bin/python3
def bounce(modulo: int, here: int, add: int) -> int:
# additive version
# modulo = 2n > 0, 0 <= here < n, add is any integer
# cycle {
# {0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...,
# 0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...},
# {0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...,
# 0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...},
# ...
# }
tmp = abs(here + add) % (2 * modulo)
if tmp <= modulo:
tmp *= -1
tmp -= 1
tmp %= modulo
return tmp
m = abs(int(input('Modulus: '))) + 1
i = abs(int(input('Iterate: '))) + 1
h: int = 0
m2: int = 3 * m
for x in range(1, 1 + i):
print(h, end = ('\n' if x % m2 == 0 else ', '))
h = bounce(m, h, 1)
input('Done.')
出于某种原因，bounce() 函数或其测试代码无法正常工作。我不知道为什么。例如，如果我为模数输入 6，为迭代变量 i 输入 4，程序应该打印 5 行 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0。相反，我会看到 2 行 6, 0, 6, 0, ...。答案可能很简单。我已经为这个 bounce() 函数绞尽脑汁了很多次，以至于我看不到它。 add 参数的标志让我感到困惑。
您可能不需要生成整个序列，以下是一个封闭形式的实现，它计算和 returns 您希望在 go- 中迭代的给定大小的序列中的索引来回循环时尚：
您可以从任何时间点开始，包括过去（负时间），并获取您在序列（索引）中的位置，而无需迭代或构建整个序列。
def bounce_back_and_forth(size: int, start_t: int=0)->int:
"""returns the index position in a sequence at time t=t, when the index starts
at position zero at time t=0, and walks the list from end to end, and and bounces
back and forth.
returns the index for all t in Z
@param size: int, the size of the sequence to iterate over
@param start_t: int, the starting indice (usually time), zero by default
:return: the index in the sequence corresponding to the start_t provided
closed form, no iteration necessary --> O(1) time & space complexity
size=5 size=5 size=5
start at t=0 start at t=6 start at t=-1 and decreases
0 [0, _, _, _, _] 6 [_, _, 2, _, _] -1 [_, _, _, _, 4]
1 [_, 1, _, _, _] 7 [_, 1, _, _, _] -2 [_, _, _, 3, _]
2 [_, _, 2, _, _] 8 [0, _, _, _, _] -3 [_, _, 2, _, _]
3 [_, _, _, 3, _] 9 [_, 1, _, _, _] -4 [_, 1, _, _, _]
4 [_, _, _, _, 4] 10 [_, _, 2, _, _] -5 [0, _, _, _, _]
5 [_, _, _, 3, _] 11 [_, _, _, 3, _] -6 [_, 1, _, _, _]
6 [_, _, 2, _, _] 12 [_, _, _, _, 4] -7 [_, _, 2, _, _]
7 [_, 1, _, _, _] 13 [_, _, _, 3, _] -8 [_, _, _, 3, _]
8 [0, _, _, _, _] 14 [_, _, 2, _, _] -9 [_, _, _, _, 4]
9 [_, 1, _, _, _] 15 [_, 1, _, _, _] -10 [_, _, _, 3, _]
10 [_, _, 2, _, _] 16 [0, _, _, _, _] -11 [_, _, 2, _, _]
"""
go_and_back = size * 2 - 2
if start_t < 0:
start_t = size - abs(start_t) % go_and_back
tdx_at_start_t = start_t % go_and_back
if tdx_at_start_t >= size:
tdx_at_start_t = go_and_back - tdx_at_start_t
return tdx_at_start_t
if __name__ == '__main__':
# tests
res = [0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1]
for idx in range(18):
actual, expected = bounce_back_and_forth(5, start_t=idx), res[idx]
assert actual == expected
stride = 0
for _ in range(5):
mod = 8 # the size of the sequence to iterate over
start = 0
stride += 1
print(f'size: {mod}, stride: {stride} -> ', end='')
for tdx in range(start, 20, stride): # <-- get indices for 20 time steps ahead
print(bounce_back_and_forth(mod, tdx), end=' ')
print()
输出：
size: 8, step: 1 -> 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0 1 2 3 4 5
size: 8, step: 2 -> 0 2 4 6 6 4 2 0 2 4
size: 8, step: 3 -> 0 3 6 5 2 1 4
size: 8, step: 4 -> 0 4 6 2 2
size: 8, step: 5 -> 0 5 4 1
测试：
class TestBounceBackAndForth(unittest.TestCase):
def test_size5_t0(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=0), 0)
def test_size5_t3(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=3), 3)
def test_size5_t4(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=4), 4)
def test_size5_t5(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=5), 3)
def test_size5_t6(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=6), 2)
def test_size5_t7(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=7), 1)
def test_size5_t8(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=8), 0)
def test_size5_t9(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=9), 1)
def test_size5_t10(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=10), 2)
def test_size5_t11(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=11), 3)
def test_size2_t0(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=0), 0)
def test_size2_t1(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=1), 1)
def test_size2_t2(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=2), 0)
def test_size2_t3(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=3), 1)
def test_size2_t4(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=4), 0)
def test_size15_t7(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=7), 7)
def test_size15_t8(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=97), 13)
# --- Negative Indices ------------
def test_size5_t_m1(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-1), 4)
def test_size5_t_m2(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-2), 3)
def test_size5_t_m3(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-3), 2)
def test_size5_t_m4(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-4), 1)
def test_size5_t_m5(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-5), 0)
def test_size5_t_m6(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-6), 1)
def test_size5_t_m7(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-7), 2)
def test_size5_t_m8(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-8), 3)
def test_size5_t_m9(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-9), 4)
def test_size5_t_m10(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-10), 3)
def test_size5_t_m11(self):
self.assertEqual(bounce_back_and_forth(size=5, start_t=-11), 2)
def test_size2_t_m1(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=-1), 1)
def test_size2_t_m2(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=-2), 0)
def test_size2_t_m3(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=-3), 1)
def test_size2_t_m4(self):
self.assertEqual(bounce_back_and_forth(size=2, start_t=-4), 0)
def test_size15_t_m7(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=-7), 8)
def test_size15_t_m8(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=-8), 7)
def test_size15_t_m97(self):
self.assertEqual(bounce_back_and_forth(size=15, start_t=-97), 2)
if __name__ == '__main__':
unittest.main()