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

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

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

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

再帰

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

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

417閲覧

再帰処理アルゴリズムを使った結果の取り出し方

DaikiMurata

総合スコア5

アルゴリズム

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

再帰

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

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

1クリップ

投稿2020/04/29 02:10

現在会津オンラインジャッジの全探索の問題に取り組んでいます。
会津オンラインジャッジ

与えられた数列の値のいくつかを足し合わせて次の数列の値を作れるか判定する問題です。

現在やりたいこととして、数の取り得る組み合わせ全て(2^n通り)を考えて一致するかどうかを判定しようと考えています。

まず全ての組み合わせを表現するにあたって再帰関数で2^n通りを表現しようと考えました。

python3

1def makeCombination(n, l): 2 if n == 0: 3 print(l) 4 5 l[n-1] = 0 6 makeCombination(A, n-1, l, ans) 7 l[n-1] = 1 8 makeCombination(A, n-1, l, ans)

ここでlはnこの数値を採用するかしないかを表した配列です。([0,0,1,0,0...])
この方法だとprintで全ての組み合わせを確認することはできるのですが、この結果をどのように取り出して次の処理につなげればいいのかがわからない状態です。

頭の中では

  1. 2^n通りの組み合わせを求める
  2. それぞれの和を求める
  3. 与えられた数列に該当するか判定する
  4. 出力

と言う手順を踏もうと思っています。
1から2へのデータの繋げ方が混乱しています。どのような処理を記述すればよいのでしょうか。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

その「頭」の中の手順は再帰的ではありませんね。その、再帰処理でないほうから。

手順を[1, 2, 3]という数列と5にあてはめると。

  1. すべての組み合わせを求める

[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
2. それぞれの和を求める。
[1, 2, 3, 3, 4, 5, 6]
3. 5に該当するものがあるかどうかチェック
ある
4. 答え
ある

のようになるでしょう。「1から2へのデータの繋げ方が混乱して」とのことですが、これならわかりますか?

再帰の部分。
あとは、すべての組み合わせを求めることができればよいので、ここで再帰ですね。

再帰を考えるにあたって必要なのは、

  1. 1つ簡単にする=1つ前の状態の解があったときに、今の解はそこからどうやって得られるか
  2. 簡単にしていって、一番簡単なときの解は何か

ということを考えることです。

数列からいくつか取った全ての組み合わせの場合、

  • 1つ簡単なのは、その数列から1つ取り除いたもの

先の例であれば、[1, 2]。 これの全ての組み合わせは、
[[], [1], [2], [1, 2]] (※ 空を入れておくのは秘訣です)

  • ここから、[1, 2, 3]の組み合せを作るにはどうしたらいいでしょう? その手順で、 [1, 2, 3, 4]の組み合わせも作れるでしょうか。
  • 一番簡単なものは何でしょう。そのときの組み合わせは?

というように考えてみてはいかがでしょう

投稿2020/04/29 06:16

TakaiY

総合スコア12657

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問