JavaScript、アルゴリズムにつきまして

Question

お世話になっております。

組み合わせをもとめる課題の模範解答のご解説をお願い申し上げます。

「引数を２つ（0の個数と1の個数)とり、それらの組み合わせの数を求める（ただし0が連続している場合は除く関数を作成せよ）」という問題です。
例を挙げますと、
第一引数、第二引数をともに2にした場合、戻り値は３になります(0011, 0101, 0110, 1001, 1010, 1100 のうち0011、1001、1100を除く三つ)

模範解答は

const withoutTwoZeros = (a, b) => {
  if (a > b + 1) {
    return 0;
  } else if (a === 0 || b === 0) {
    return 1;
  }

  return withoutTwoZeros(a, b - 1) + withoutTwoZeros(a - 1, b - 1);
};

となっていました。
挙動自体を追うことはできるのですが、なぜ組み合わせの数が求められるのかわかりません。

よろしくお願いいたします。

Answer 1

似たような質問繰り返してるけど、高校の数学ちゃんと勉強した？

そしてこの課題はちゃんと考えたの？
うせやろ…私が同じように模範解答みたら5分で理解したんだけど……

はっきり言ってサボってたようにしか思えない。
同じ聞くでも仮説や仮定くらいは出せるよね、質問文に出てこないって時点でそれを読んだ多くの回答者は「ああ、こいつサボってたんだな」って解釈するよ。

---

さて、プログラミングテクニック側は回答でサポート出来るので解説していこう。
こういった数学系の問題で、回答に再帰関数が出る時点で99%が数列が関係してくる。

数列の漸化式を実現する手法が再帰関数。
なので、もし数学に強い人間なら多少プログラミングが弱かったとしても
自分で数列作って、拙いながらでも再帰関数に変換しながら動かすことは出来る。

高校数学でもあったでしょ？
xが1の場合、答えは3になります。
xが2の場合、答えは5になります。
(x + 1)すると、答えは+2されます。
数学的帰納法により云々みたいなヤツ、やってれば慣れるから我慢して数をこなそう。

まぁ、わざわざ直接コードに出来るんだから式作って変換するのは効率悪いけど、
考え方としてはまずは「0が1個、1が0個」と「0が0個、1が1個」…という風に0や1からスタートして、
1つずつ値を増やしながら検証して法則を見つける必要がある。

そうしていくうちに色々と条件が見えてくる

• 0が1よりも2個以上多い: 00になるパターンは存在してはならないので条件を満たせない
• 0もしくは1が0個: 0か1111という風にバリエーションがないのでパターン1つしか条件を満たせない
• 0が1よりも1個多い: 01010...という風に0で始まり0で終わるパターン1つしか条件を満たせない
• 0が1と同数以下: 1は複数続いても良いのでパターン数は不明

4パターン目は一見コンピュータで計算できないように見える、
しかし、コンピュータは高速かつ強力な演算を行うことが出来るので、
実際に1文字目になにかを仮置きして計算してしまえばいい(検討した所下記の2つが該当するとわかった)

• 先頭1のケース: withoutTwoZeros(a, b - 1)
• 先頭01のケース: withoutTwoZeros(a - 1, b - 1)

上の特別条件に当てはまるなら1か0が返ってくるだろうし、
その条件以外はまた1か01を仮置きしてwithoutTwoZerosに投げてやればいつかは0か1かの答えが返ってくる。

Comments

[Behemoth]

ご回答ありがとうございます。
基礎を学び直したいと思います。
姿勢をただし、ほかのユーザーの方々にとって有益な質問をできるようにいたします。