python - 在 N*N 矩阵中查找总数据

Question

一个矩阵由N×N block 组成， block 数等于行数和列数之和。每个 block 由数据组成，数据等于 block 号的偶数和奇数之和的差。计算n*n个区 block 的总数据

输入/输出格式

lets n = 4
so
matrix will be
2 3 4 5
3 4 5 6
4 5 6 7
5 6 7 8

所以总数据 = 2+3+4+5+3+4+5+6+4+5+6+7+5+6+7+8=80

如果 block 数在任何情况下都是 4256 那么其中的数据将是 abs(diff(sum(even digits)- sum(odd digits))) 即 abs((4+2+6)-(5) )= 7

我天真的尝试

n = int(raw_input())
sum1=0
sum2=0
for i in range(1,n+1):
    for j in range(1,n+1):
        sum1 = i+j
        diffsum = diff(sum1)
        sum2 = sum2+diffsum
print sum2

再次优化尝试

def diff(sum1):
    sum1 = str(sum1)
    m = sum([int(i) for i in sum1 if int(i) % 2 == 0])
    f = sum([int(i) for i in sum1 if int(i) % 2 != 0])
    return abs(m - f)


n = int(raw_input())
sum1 = 0
k = 1
# t1 = time.time()
p = 2 * n
for i in range(2, n + 2):
    diffsum = diff(i)
    diffsum1 = diff(p)
    sum1 = sum1 + (diffsum * k)
    sum1 = sum1 + (diffsum1 * k)
    p = p - 1
    k = k + 1
sum1 = sum1 - (diff(n + 1) * n)
print sum1

diff 在这两种情况下都是常用函数。我需要使用以下算法进行更多优化

Answer 1

您的优化方法只为每个数字计算一次数字总和，因此乍一看，内存没有任何好处。

您可以通过将两个循环合并为一个循环并使用字典来查找是否添加或减去数字来提高 diff 函数的性能:

value = dict(zip("0123456789", (0, -1, 2, -3, 4,-5, 6,-7, 8,-9)))

def diff2(s):
    s = str(s)
    return abs(sum([value[i] for i in s]))

这将需要转换为字符串。通过手动计算数字，您可以更快(但不会太多):

dvalue = [0, -1, 2, -3, 4,-5, 6,-7, 8,-9]

def diff(s):
    t = 0

    while s:
        t += dvalue[s % 10]
        s //= 10

    return abs(t)

最后，您可以利用以下事实:您可以按顺序计算从 2 到 2·n 的所有数字和。将当前数字的数字存储在一个数组中，然后实现一个类似里程表的计数器。当您增加该计数器时，请跟踪奇数位和偶数位的总和。在 10 种情况中的 9 种情况下，您只需调整最后一位数字，方法是从各自的总和中删除它的值，然后将下一位数字添加到另一个总和中。

这是一个执行此操作的程序。函数 next 递增计数器并将偶数和奇数的数字和保存在 sums[0] 和 sums[1] 中。主程序与您的程序基本相同，只是循环被分成两部分:一个是 k 增加的部分，另一个是减少的部分。

even = set(range(0, 10, 2))

def next(num, sums):    
    o = num[0]
    if o in even:
        sums[0] -= o
        sums[1] += o + 1
    else:
        sums[0] += o + 1
        sums[1] -= o

    num[0] += 1

    i = 0
    while num[i] == 10:
        sums[0] -= 10
        num[i] = 0

        i += 1
        o = num[i]
        if o in even:
            sums[0] -= o
            sums[1] += o + 1
        else:
            sums[0] += o + 1
            sums[1] -= o

        num[i] += 1

n = int(raw_input())
total = 0

m = len(str(2 * n + 1))
num = [0] * m
num[0] = 2
sums = [2, 0]

k = 1
for i in range(2, n + 2):
    total += abs(sums[0] - sums[1]) * k
    k += 1
    next(num, sums)    

k = n        
for i in range(n + 2, 2*n + 1):
    k -= 1        
    total += abs(sums[0] - sums[1]) * k
    next(num, sums)

print total

我在上面说过，内存对这种方法没有用。这不是真的。您可以存储数字 i 的偶数和奇数和，并在计算数字 10 * i 到 10 * i + 9 时使用它>。当您按照 i 递增的顺序调用 diff 时，您将可以访问 i//10 的存储总和。

这并不比里程计方法快多少，但以额外内存为代价实现更清晰。 (对于大的 n，预分配数组比字典工作得更好。您不需要为 (2*n + 11)/10 以上的数字保留空间。)

def diff(s):
    d = s % 10

    e = ememo[s / 10]
    o = omemo[s / 10]

    if d in even:
        e += d
    else:
        o += d

    if s < smax:
        ememo[s] = e 
        omemo[s] = o    

    return e, o

n = int(raw_input())

total = 0

even = set(range(0, 10, 2))
smax = (2*n + 11) / 10
omemo = smax * [0]
ememo = smax * [0]
omemo[1] = 1

k = 1    
for i in range(2, n + 2):
    e, o = diff(i)
    total += abs(e - o) * k
    k += 1        

k = n        
for i in range(n + 2, 2*n + 1):
    k -= 1   
    e, o = diff(i)     
    total += abs(e - o) * k

print total

如果可以找到数字总和的闭合公式，这可以做得更快，但我认为绝对函数阻止了这样的解决方案。