漸化式《DP》

DPメニュー

hogeちゃん

2022.09.14

DPメニュー【2項間漸化式・特殊な2項間漸化式・3項間漸化式各 1 〜 2】

問題【STEP: 1】2項間漸化式 1

Task

x, d, k が与えられます。a_n = a_{n-1} + d ( a_1 = x ) の a_k を求めてね。

【2項間漸化式 1】コード

reader.on('close', () => {
   const [x, d, k] = lines[0].split(' ').map(Number);
   const a = [x];  // 要素数 k 個の配列
   for (let i = 1; i < k; i++) {
      a[i] = a[i - 1] + d;  // 値が d ずつ増加
   }
   console.log(a[k - 1]);  // k 番目の値を出力
});

hogeちゃんの画像

a は値が d ずつ増加する要素数が k 個の配列ですね。

問題【STEP: 2】2項間漸化式 2

Task

x, d が与えられます。a_n = a_{n-1} + d ( a_1 = x ) の Q 個の a_k を求めてね。

【2項間漸化式 2】コード

reader.on('close', () => {
   const [x, d] = lines[0].split(' ').map(Number);
   const Q = Number(lines[1]);
   const a = [x];  // 要素数 1000個の配列
   for (let i = 1; i < 1000; i++) {
      a[i] = a[i - 1] + d;  // 値が d ずつ増加
   }
   for (let i = 2; i < Q + 2; i++) {
      const k = lines[i]-1;
      console.log(a[k]);  // k 番目の値を出力
   }
});

hogeちゃんの画像

要素数 1000 個の配列の値を漸化式で求めて a[k] の値を出力しています。

問題【STEP: 3】特殊な2項間漸化式 1

Task

添字の偶奇による場合分けを行い a_k を求めてね。

【特殊な2項間漸化式 1】コード

reader.on('close', () => {
   const [x, d1, d2, k] = lines[0].split(' ').map(Number);
   const a = [x];  // 要素数 1000個の配列
   for (let i = 1; i < k; i++) {
      i % 2 ? a[i] = a[i - 1] + d2 : a[i] = a[i - 1] + d1;  // a の要素の計算
   }
   console.log(a[k - 1]);  // k 番目の値を出力
});

hogeちゃんの画像

a は値が d1 または d2 ずつ増加する要素数が k 個の配列ですね。

問題【STEP: 4】特殊な2項間漸化式 2

Task

添字の偶奇による場合分けを行い Q 個の a_k を求めてね。

【特殊な2項間漸化式 2】コード

reader.on('close', () => {
   const [x, d1, d2] = lines[0].split(' ').map(Number);
   const Q = Number(lines[1]);
   const a = [x];  // 要素数 1000個の配列
   for (let i = 1; i < 1000; i++) {
      i % 2 ? a[i] = a[i - 1] + d2 : a[i] = a[i - 1] + d1;  // a の要素の計算
   }
   for (let i = 2; i < Q + 2; i++) {
      const k = lines[i]-1;
      console.log(a[k]);  // k 番目の値を出力
   }
});

hogeちゃんの画像

要素数 1000 個の配列の値を漸化式で求めて a[k] の値を出力しています。

問題【STEP: 5】3項間漸化式 1

Task

整数 k が与えられます。フィボナッチ数列の k 項目の値を出力してね。

【3項間漸化式 1】コード

reader.on('close', () => {
   const k = Number(lines[0]);
   const a = [1, 1];  // 要素数 1000個のフィボナッチ数列
   for (let i = 2; i < k; i++) {
      a[i] = a[i - 2] + a[i - 1];  // フィボナッチ数列の計算
   }
   console.log(a[k - 1]);  // k 番目の値を出力
});

hogeちゃんの画像

a[i] の値は a[i - 2] + a[i - 1]になっています。これはフィボナッチ数列と呼ばれる有名な数列だそうです。

問題【FINAL】3項間漸化式 2

Task

整数 k が与えられます。フィボナッチ数列の Q 個の k 項目の値を出力してね。

【3項間漸化式 2】コード

reader.on('close', () => {
   const Q = Number(lines[0]);
   const a = [1, 1];  // 要素数 1000個のフィボナッチ数列
   for (let i = 2; i < 40; i++) {
      a[i] = a[i - 2] + a[i - 1];  // フィボナッチ数列の計算
   }
   for (let i = 1; i <= Q; i++) {
      const k = lines[i] - 1;
      console.log(a[k]);  // k 番目の値を出力
   }
});

hogeちゃんの画像

要素数 40 個のフィボナッチ数列を漸化式で求めて a[k] の値を出力しています。

コメント