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

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

新規登録して質問してみよう
ただいま回答率
86.02%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

再帰関数で組み合わせを選ぶアルゴリズムの意味が理解できないので教えてほしいです!

zeon.
zeon.

総合スコア15

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

1回答

0グッド

0クリップ

335閲覧

投稿2022/09/10 00:37

前提

再帰関数で以下の問題で模範コードの意味が知りたいです。
イメージ説明

実現したいこと

以下に記載のコードの以下の部分の意味がよくわからいので噛み砕いて教えて抱きたいです。(当サイトの解説が乏しいため)

c++

1func(n-1,l+1,r) + func(n,l+1,r);

該当のソースコード

c++

1#include <iostream> 2#include <vector> 3using namespace std; 4 5// 再帰関数 (N = n, L = l, R = r のときの問題の答え) 6int func(int n, int l, int r) { 7 // n = 0 のとき、答えは空配列のみ (1 つ) 8 if (n==0) return 1; 9 10 // l > r のとき、答えは存在しない 11 if (l>r) return 0; 12 13 // それ以外のとき 14 int ans = func(n-1,l+1,r) + func(n,l+1,r); 15 16 return ans; 17} 18 19int main() { 20 // 入力 21 int N, L, R; 22 cin >> N >> L >> R; 23 24 // 出力 25 int ans = func(N,L,R); 26 cout << ans << endl; 27}

input, output

  • input
2 1 3
  • output
3

以下のような質問にはグッドを送りましょう

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

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

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

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

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

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

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

適切な質問に修正を依頼しましょう。

回答1

1

ベストアンサー

funcが呼ばれたとき、
左再帰項のfunc(n-1,l+1,r)ってのは、Aiをlと定めたとき、残りのAi+1..An-1までのパターン数。だから引数には nー1(Aの決まってない数は減る)、l+1(このlは使ったから)。
右再帰項のfunc(n,l+1,r)ってのは、Aiにlを使わないときのパターン数。だからlだけ+1。
再帰なので、左で呼んだfuncでは「Ai+1をl+1と定める」か「L+1を使わない」かに分かれていくし、右で呼んだfuncでは「AiをL+1と定める」か「L+1を使わない」かに分かれていく。

具体的に書けばわかりやすいかも。
L=1, R=3, N=2のとき、こたえのパターンは1-2, 1-3, 2-3。再帰funcに呼び出し順で名前をつけておくと(func2は2回目に呼ばれたfunc、程度の意味)
func0左:a0=1を決定して、func1( N=1,L=2, R=3)を呼ぶ
+func1左:a1=2を決定して、func( N=0)でおしまい。#1-2
+func1右:2は使わず、func2( N=1, L=3, R=3)を呼ぶ
++ func2左:a2=3を決定して、func( N=0)でおしまい。#1-3
++ func2左:3を使わないと、func( N=1, L=4, R=3)で無効
func0右:1を使わずfunc3( N=2, L=2, L=3)を呼ぶ
+func3左:a0=2を決定して、func4( N=1,L=3,R=3)を呼ぶ
++func4左:a1=3を決定して、func( N=0)でおしまい。#2-3
(略)

投稿2022/09/10 02:20

matukeso

総合スコア1427

zeon.👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

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

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

このような回答には修正を依頼しましょう。

回答へのコメント

zeon.

2022/09/10 03:54

わー!ご丁寧に具体的な流れまで示して頂いてとても感激です! ようやく理解できました!

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

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。