区間の和《累積和》

累積和メニュー

hogeちゃん

2022.08.29

累積和メニュー【区間の和 1 〜 4】

問題【STEP: 1】区間の和 1

Task

用意した数列 a の a_2 から a_7 までの和を累積和を使うことで求てね。

【区間の和 1】コード

const a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4];  // 10個の数値 a[0] ~ a[9]  
const s = [0];  // a の累積和を保存する配列
for (let i = 0; i < 10; i++) {
   s.push(s[i] + a[i]);  // s[i] + a[i] は a[0] ~ a[i] の累積和
}
// s = [ 0, 1, 6, 15, 22, 27, 30, 32, 37, 45, 49]
console.log(s[8] - s[2]);  // a[2] ~ a[7] までの総和

hogeちゃんの画像

s は配列 a の累積和を保存するための配列です。

問題【STEP: 2】区間の和 2

Task

数列 a の a_2 から a_7 までの和を累積和を使うことで求めてね。

【区間の和 2】コード

reader.on('close', () => {
   const a = lines[0].split(' ').map(Number);
   const s = [0];  // a の累積和を保存する配列
   for (let i = 0; i < 10; i++) {
      s.push(s[i] + a[i]);  // s[i] + a[i] は a[0] ~ a[i] の累積和
   }
   console.log(s[8] - s[2]);  // a[2] ~ a[7] までの総和
});

hogeちゃんの画像

a[2] から a[7] までの和。配列 a の値は入力から受け取っています。それ以外は【STEP: 1】と同じでした。

問題【STEP: 3】区間の和 3

Task

数列 a の a_X から a_Y までの和を累積和を使うことで求めてね。

【区間の和 3】コード

reader.on('close', () => {
   const [X, Y] = lines[0].split(' ').map(Number);
   const a = lines[1].split(' ').map(Number);
   const s = [0];  // a の累積和を保存する配列
   for (let i = 0; i < 10; i++) {
      s.push(s[i] + a[i]);  // s[i] + a[i] は a[0] ~ a[i] の累積和
   }
   console.log(s[Y + 1] - s[X]);  // a[X] ~ a[Y] までの総和
});

hogeちゃんの画像

a[X] から a[Y] までの和。

問題【FINAL】区間の和 4

Task

数列 a の a_X から a_Y までの和を累積和を使うことで求めてね。

【区間の和 4】コード

reader.on('close', () => {
   const [N, X, Y] = lines[0].split(' ').map(Number);
   const a = lines[1].split(' ').map(Number);
   const s = [0];  // a の累積和を保存する配列
   for (let i = 0; i < N; i++) {
      s.push(s[i] + a[i]);  // s[i] + a[i] は a[0] ~ a[i] の累積和
   }
   console.log(s[Y + 1] - s[X]);  // a[X] ~ a[Y] までの総和
});

hogeちゃんの画像

配列 a の要素数が N 個になりました。それ以外は【STEP: 3】と同じ。

コメント