千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2024年8月実施 専門 A5

标签：

• Two-Dimensional-Prefix-Sums

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

zeros(n) は全成分 $0$ の $n\times n$ 配列を返し、添字は $0$ 始まりとする。

def f(a, n):
    b = zeros(n)
    for i in range(n):
        sum = 0
        for j in range(n):
            sum = sum + a[i][j]
            if i == 0:
                b[i][j] = sum
            else:
                b[i][j] = b[i-1][j] + sum
    return b

(1) a=[[1,2,3],[4,5,6],[7,8,9]] のとき f(a,3) を求めよ。

(2) 正整数 $n$、整数配列 $a$、$b=f(a,n)$ に対し $b[k][\ell]$ を $a$ の成分で表せ。

(3) $0\le k<k'<n,0\le\ell<\ell'<n$ に対し、$\sum_{i=k+1}^{k'}\sum_{j=\ell+1}^{\ell'}a[i][j]$ を $b[k][\ell],b[k][\ell'],b[k'][\ell],b[k'][\ell']$ で表せ。

题目描述

对上述二维数组程序：(1) 计算所给 $3\times3$ 输入的输出。(2) 用输入元素表达一般的 $b[k][\ell]$。(3) 仅用指定四个输出元素表示对应矩形区域的元素总和。

Kai

(1)

[[1, 3, 6], [5, 12, 21], [12, 27, 45]]

(2)

内側のループの sum は $\sum_{j=0}^{\ell}a[k][j]$ であり、前の行の値を加えている。行に関する帰納法により

$$\boxed{b[k][\ell]=\sum_{i=0}^k\sum_{j=0}^{\ell}a[i][j]}.$$

(3)

不要な上側と左側を引き、二重に引いた共通部分を戻すと

$$\boxed{b[k'][\ell']-b[k][\ell']-b[k'][\ell]+b[k][\ell]}.$$