Расширенный модульный арифметический алгоритм Python - PullRequest
Новая
       32

Расширенный модульный арифметический алгоритм Python

0 голосов
/ 04 сентября 2018

У меня есть эта программа: 

#!/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 для модуля и 4 для переменной итерации i, программа должна вывести 5 строк 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0. Вместо этого я бы увидел 2 строки 6, 0, 6, 0, .... Ответ, вероятно, прост. Я просто столько раз ломал голову над этой bounce() функцией, что не вижу ее. Обозначение параметра add сбивает меня с толку.

1 Ответ

0 голосов
/ 04 сентября 2018

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

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

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()
...