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

矩阵由n×n个块组成，块数等于行数和列数之和。每个块由数据组成，数据等于块号的奇偶和之差计算n*n块的总数据
I/O格式

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
如果块的数目在任何情况下都是4256，那么块中的数据将是abs（diff（sum（偶数）-sum（奇数）），即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在这两种情况下都是常用函数我需要用下面的算法进行更多的操作

最佳答案

你的优化方法只为每个数字计算一次数字和，所以乍一看，没有任何东西可以从记忆中得到。
您可以通过将两个循环合并为一个循环并使用字典来查找是加还是减一个数字来提高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的数字时使用它当您按增加diff的顺序调用i时，您将可以访问存储的i // 10和。
这并没有比里程表方法快得多，但是以额外的内存为代价实现起来更清晰。（对于bign，预先分配的数组比字典工作得更好您不需要为(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

如果能找到一个闭式的数和公式，这可能会更快，但我认为绝对函数阻止了这样的解。