質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.50%

  • JavaScript

    16454questions

    JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 137

Behemoth

score 21

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

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

「引数を2つ(0の個数と1の個数)とり、それらの組み合わせの数を求める(ただし0が連続している場合は除く関数を作成せよ)」という問題です。
例を挙げますと、
第一引数、第二引数をともに2にした場合、戻り値は3になります(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);
};


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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+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個: 01111という風にバリエーションがないのでパターン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かの答えが返ってくる。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/07/28 20:03

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.50%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • JavaScript

    16454questions

    JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。