Help us understand the problem. What is going on with this article?

トリボナッチ数列のn番目を求める関数をメモ化してみた!(JavaScript)

はじめに

最近、Udemyでアルゴリズムの講座とかをやってたりするのですが、JavaScriptでフィボナッチ数列のプログラムを書いて、それをメモ化するのが面白かったので、トリボナッチ数列でも少し変えてやってみました。

Stephen Grider先生の講座はどれも分かりやすいです。
参考:The Coding Interview Bootcamp: Algorithms + Data Structures

トリボナッチ数列とは

トリボナッチ数列は 0、0、1 で始まり、以後の項がその前の3つの項の和となる数列です。

引用:フィボナッチ数列(9): トリボナッチ数列とテトラナッチ数列の計算

確認用のテスト

少し冗長かもですが、こんな感じに書いてみました↓

src/test.js
const tri = require("./index");

test("関数が定義されているか", () => {
  expect(typeof tri).toEqual("function");
});

test("n=1の時", () => {
  expect(tri(1)).toEqual(0);
});

test("n=2の時", () => {
  expect(tri(2)).toEqual(1);
});

test("n=3の時", () => {
  expect(tri(3)).toEqual(1);
});

test("n=4の時", () => {
  expect(tri(4)).toEqual(2);
});

test("n=5の時", () => {
  expect(tri(5)).toEqual(4);
});

test("n=50の時", () => {
  expect(tri(50)).toEqual(3122171529233);
});

for文を使ったやり方

一番最初に思い付いたのはfor文を使った基本的なやり方でした。

src/index.js
function tri(n) {
  const arr = [0, 0, 1];
  for (let i = 3; i <= n; i++) {
    arr[i] = arr[i - 3] + arr[i - 2] + arr[i - 1];
  }
  return arr[n];
}

module.exports = tri;

次のコマンドでテストを実行!

jest src/test.js

image.png
うまくいきました!

再帰関数を使ったやり方

再起的なやり方を使って、コードを短くできました!

function tri(n) {
  if (n < 3) return n === 2 ? 1 : 0;
  return tri(n - 3) + tri(n - 2) + tri(n - 1);
}

module.exports = tri;

しかし、このやり方だと、どんどん枝分かれしていって、nが50の時には何回も同じ呼び出しをテストがなかなか終わりません。
なので、以下のようにメモ化をしてみます。

function memorize(fn) {
  const cache = [];
  return function (args) {
    if (cache[args]) return cache[args];
    const result = fn.call(this, args);
    cache[args] = result;
    return result;
  };
}

function slowTri(n) {
  if (n < 3) return n === 2 ? 1 : 0;
  return tri(n - 3) + tri(n - 2) + tri(n - 1);
}

const tri = memorize(slowTri);

module.exports = tri;

少し複雑で分かりにくいかもしれません。一応説明↓

  • triの宣言のところから見ていくと、memorizeはfunction(args){...}を返すので、argsにはnが入る。
  • memorizeの中の関数では、配列cacheにnの時の値があればそれを返して、なければfnの引数nにargsに入っていたnが入って呼び出せれます。その後に求められた値がcacheに格納されます。
  • fnはmemorizeの引数なので、slowTriです。
  • slowTriのなかでnが3以上なら、枝分かれしてtriが呼び出されます。枝分かれしていきnが3より小さくなるまで繰り返されます。

image.png

テストがうまくいきました!

終わりに

ここまで読んでいただきありがとうございました!私の説明が下手で少し分かりにくかったらごめんなさい!
結果的にfor文のやり方より長くなってしまいましたが、素のJavaScriptを使って、関数のメモカを書いたの初めてなので勉強になりました。アルゴリズムの問題は人によって時方が結構違って、毎回何かしら学べるので楽しいです。
感想やご要望などお待ちしております!

NozomuTsuruta
大学3年生/プログラミングにどハマり中。 現在アルバイトエンジニアとして、Webアプリの開発に携わっています。Javascript(React+Typescript)やPHPで勉強したことや気づきをアウトプットしたり、最新技術などをまとめたりしながら自分自身も成長していきたいと思っています。リクエストや感想などお待ちしております!
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away