【アルゴリズム】JavaScriptでステップ/ピラミッド問題を解く

はじめに

Qiitaの競技プログラミング研究月間ということで、アルゴリズムの記事を書いています。
今回はステップ問題とピラミッド問題をまとめました。

JavaScriptでアルゴリズムの勉強をされている方の参考になれば幸いです。
記事を順次まとめていきますので、その他の記事についてはマイページからご覧ください。

ステップ

引数に整数Nを与えたときに、N段の階段状になるように'#'を出力してください。
右側の'#'が入っていない部分にはスペースをいれてください。

   steps(2)
       '# '
       '##'
   steps(3)
       '#  '
       '## '
       '###'

解答

Row方向とColumn方向の二重ループで一行ずつ'#'を入れていく方針を考えます。

まずは空の文字列stairを用意し、Rowの値と同じ個数分'#'を入れていきます。
'#'の右側にはスペースを入れていき、Columnのループが終わったらconsole.log(stair)でその段の文字列を出力します。
console.log(stair)の出力後にrowを1つ増やし、以上と同じ処理をrow = n-1まで繰り返します。

index.js

function steps(n) {
  for (row = 0; row < n; row++) {
    let stair = '';

    for (column = 0; column < n; column++) {
      if (column <= row) {
        stair += '#';
      } else {
        stair += ' ';
      }
    }
    console.log(stair);
  }
}

再帰関数を使って解く方法も考えます。

関数の中に3つの分岐を作成します。
stairを更新しているときはif (stair.length <= row)の分岐に入り、stairに'#'かスペースを挿入したあとにsteps(n, row, stair)の再帰呼び出しを行います。
一行分のstairが完成したらif (n === stair.length)の分岐に入り、rowを1増やして再帰呼び出しsteps(n, row + 1)を行います。
rowが全て埋まったらif (n === row)の分岐に入り、再帰呼び出しを終えてreturnを返します。

index.js

function steps(n, row = 0, stair = '') {
  // 全部の行ができたらreturnを返す
  if (n === row) {
    return;
  }
  // 1行分のstairが完成したらここに入る
  if (n === stair.length) {
    console.log(stair);
    return steps(n, row + 1);
  }
  // 最初は必ずここに入る
  if (stair.length <= row) {
    stair += '#';
  } else {
    stair += ' ';
  }
  steps(n, row, stair);
}

ピラミッド

引数に整数Nを与えたときに、N段のピラミッド状になるように'#'を出力してください。
両側の'#'が入っていない部分にはスペースをいれてください。

   pyramid(1)
       '#'
   pyramid(2)
       ' # '
       '###'

解答

ステップのときと同様に、まずはRowとColumnの二重ループで考えます。

各行には(2 * n - 1)個の'#'が入るため、中央の'#'の位置をconst midpoint = Math.floor((2 * n - 1) / 2)として出すことができます。
空の文字列levelを用意し、(midpoint - row <= column && midpoint + row >= column)の範囲に'#'、それ以外の部分にスペースを入れていきます。

各行に入る'#'の個数と'#'が入る位置に気をつければ、ステップのときとほとんど同じ流れで解くことができます。

index.js

function pyramid(n) {
  // #を付与する位置を算出する
  const midpoint = Math.floor((2 * n - 1) / 2);

  for (let row = 0; row < n; row++) {
    let level = '';

    for (let column = 0; column < 2 * (n - 1) + 1; column++) {
      if (midpoint - row <= column && midpoint + row >= column) {
        level += '#';
      } else {
        level += ' ';
      }
    }
    console.log(level);
  }
}

以下が再帰関数を使う場合です。

index.js

function pyramid(n, row = 0, level = '') {
  if (row === n) {
    return;
  }

  if (level.length === 2 * n - 1) {
    console.log(level);
    return pyramid(n, row + 1);
  }

  const midpoint = Math.floor((2 * n - 1) / 2);
  let add;
  if (midpoint - row <= level.length && midpoint + row >= level.length) {
    add = '#';
  } else {
    add = ' ';
  }

  pyramid(n, row, level + add);
}

参考資料