如何计算while循环的基本操作

Question

仅计数{+， - ，*，/，//，％，>，<，==，<=，> =}作为基本操作，确定将被执行的基本操作的确切数目时下面的代码段是为N和T的所述给定的值执行。

n = 5
t = 3
s = 0
i = 0
j = 0
x = n
while s < t:
    if x % 2 == 1:
        i = i + 1
    x = x // 2
    for k in xrange(n):
        s = s + 1
        j = j + i
print(j)

我知道答案是23，但我得到19这个6 * N + 1的算式

Answer 1

你可以写一个小包装类注册到相关的方法调用（对应于+，-，...）：

class Integer(int):
    n_ops = 0

def new_patch(name):
    def patch(self, other):
        Integer.n_ops += 1
        value = getattr(int, name)(self, other)
        if isinstance(value, int) and not (value is True or value is False):
            value = Integer(value)
        print(f'{repr(self)} {methods[name]} {repr(other)} -> {repr(value)}')
        return value
    patch.__name__ = name
    return patch

methods = {
    '__le__': '\u2264',
    '__lt__': '<',
    '__ge__': '\u2265',
    '__gt__': '>',
    '__eq__': '==',
    '__add__': '+',
    '__sub__': '-',
    '__mul__': '*',
    '__floordiv__': '//',
    '__mod__': '%',
}
for name in methods:
    setattr(Integer, name, new_patch(name))

然后使用该包装类来代替内置的整数，我们可以指望的操作：

n = 5
t = Integer(3)
s = Integer(0)
i = Integer(0)
j = Integer(0)
x = Integer(n)
while s < t:
    if x % 2 == 1:
        i = i + 1
    x = x // 2
    for k in range(n):
        s = s + 1
        j = j + i
print(f'j = {j}')
print(f'Number of operations: {Integer.n_ops}')

它计算16个操作：

0 < 3 -> True
5 % 2 -> 1
1 == 1 -> True
0 + 1 -> 1
5 // 2 -> 2
0 + 1 -> 1
0 + 1 -> 1
1 + 1 -> 2
1 + 1 -> 2
2 + 1 -> 3
2 + 1 -> 3
3 + 1 -> 4
3 + 1 -> 4
4 + 1 -> 5
4 + 1 -> 5
5 < 3 -> False
j = 5
Number of operations: 16

---

更一般

包括更多的方法：

class Integer(int):
    n_ops = 0

def new_patch(name):
    def patch(self, *args):
        Integer.n_ops += 1
        value = getattr(int, name)(self, *args)
        if isinstance(value, int) and not (value is True or value is False):
            value = Integer(value)
        print(f'{name}({repr(self)}, {repr(args)}) -> {repr(value)}')
        return value
    patch.__name__ = name
    return patch

methods = [f'__{name}__' for name in ('le', 'lt', 'ge', 'gt', 'eq', 'ne', 'neg', 'pos', 'abs', 'invert')]
for name in ('add', 'sub', 'mul', 'truediv', 'floordiv', 'mod', 'divmod', 'pow', 'lshift', 'rshift', 'and', 'xor', 'or'):
    methods.extend((f'__{name}__', f'__r{name}__', f'__i{name}__'))

for name in methods:
    setattr(Integer, name, new_patch(name))

随着输出：

__lt__(0, (3,)) -> True
__mod__(5, (2,)) -> 1
__eq__(1, (1,)) -> True
__add__(0, (1,)) -> 1
__floordiv__(5, (2,)) -> 2
__add__(0, (1,)) -> 1
__add__(0, (1,)) -> 1
__add__(1, (1,)) -> 2
__add__(1, (1,)) -> 2
__add__(2, (1,)) -> 3
__add__(2, (1,)) -> 3
__add__(3, (1,)) -> 4
__add__(3, (1,)) -> 4
__add__(4, (1,)) -> 5
__add__(4, (1,)) -> 5
__lt__(5, (3,)) -> False
j = 5
Number of operations: 16