N * N行列の合計データを見つける

Question

行列は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（奇数）））になります。 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は、両方の場合に共通の関数です。私は次のアルゴリズムでより多くのoptmizationが必要です

Answer 1

あなたの最適化されたアプローチでは、数値ごとに桁の合計が1回だけ計算されるため、一見するとメモから得られるものはありません。

あなたは一つに二つのループをマージすることで、あなたのdiff機能のパフォーマンスを向上させ、追加または数字を引くかどうかをルックアップするために辞書を使用することができます。

value = dict(zip("", (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＆middotまでの2からすべての桁の合計を計算しているという事実を利用することができます;順次n個。現在の数値の桁を配列に格納し、オドメータのようなカウンタを実装します。そのカウンタをインクリメントするときは、奇数と偶数の合計を追跡します。 10件のうち9件では、それぞれの合計からその値を削除し、次の桁を他の合計に加算するだけで、最後の桁を調整する必要があります。

これはこれを行うプログラムです。関数nextは、カウンタをインクリメントし、偶数と奇数の桁の合計をsums[0]とsums[1]に保持します。メインプログラムは、ループが2つに分割されていることを除いて、基本的にあなたと同じです：1つは、kが増加し、1が減少する場所です。

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になります。

これはオドメーターのアプローチよりも格段に高速ではありませんが、実装がより多くのメモリを犠牲にしてより明確になります。 （事前に割り当てられた配列は、大きな文字の辞書よりも優れています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 

1の桁の合計のためのクローズド式を見つけることができる場合、これはより速く作ることができるが、私は絶対的な機能は、このような解決策を防止することを考えます。