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

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

新規登録して質問してみよう
ただいま回答率
86.02%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

再帰

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

Q&A

受付中

再帰関数 バックトラッキング 部分集合 java

arch
arch

総合スコア0

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

再帰

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

3回答

0グッド

0クリップ

740閲覧

投稿2021/08/10 06:48

前提・実現したいこと

三つの変数を用いて、要素の和が指定した値と同じになる部分集合を書き出すという問題になっているのですが、バックトラッキングを使って導けるのではないかというところまでは分かったのですが、集合の中身の要素の変動を全て把握し、書き出すことが難しくなかなか解けませんでした。
解答がないので、理解するために何かしら考え方のヒントだけでも貰いたいです。

出力例:3の場合、{3},{1,2},{1,1,1}
4の場合、{4},{1,3},{2,2},{1,1,2},{1,1,1,1}

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

java

1public static void main(String []args){ 2 bfDfs_demand(n,i,k); 3 } 4void btDfs_demand(int n, int i, int k) { 5 if () { 6 7 return ; 8 } 9 10 11 } 12int getChoice(int n,int i, int k){ 13 14} 15int write(int n,int i,int k){//この関数で出力 16} 17 18//これが考えた構造です。 19### 試したこと 20 21サイズが大きい順から考えていく。 22例:4の時、 23{1,1,1,1}  → 要素の1同士を足して、 {1,1,2} → 要素の1同士、また1と2を足して {1,3},{2,2}  →  {4} 24問題 集合が重複してしまう。 25 26 1を起点として考える。 27println(",1")というようにあらかじめ1が入るような設定をしておく。 28問題 6の時とかに{2,2,2}が入らない。 29 30### 補足情報(FW/ツールのバージョンなど) 31 32できれば、バックトラッキングを使って解きたいです。

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

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

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

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

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

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

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

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

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

mather

2021/08/10 07:46

ソースコードの記載がおかしくなっています。プレビューで確認し、ソースコードの記載の末尾に ``` を追加してソースコードの終了部分を明確にしないとマークダウンが正しく機能しません。 また、ソースコードがどう見ても空っぽで、考え方を記載したのみで何も実装されていないように見受けられます。 「試したこと」に記載した内容をまず実装してから質問に記載してください。 「バックトラッキング」という言葉についても、どういう意味で習ったのか自分の言葉で説明してみましょう。調べ直すことでヒントになるかもしれません。 最後に、もし学校の問題なら学校で質問してくださいね。
arch

2021/08/10 08:13

返答ありがとうございます。 もう一回自分で見直してみます。

回答3

1

要素の和を n とすると、全部 1 が一番長い部分集合になるので、
大きさ n の配列を用意して、大きい数から詰め込んで行くことにします。
まだ和に達していなければ、左側以下の値を大きいものから順に 1 になるまで
詰め込んで、次に行くというのを繰り返せばよいでしょう。

ヒントとして書くのが難しいので、コードで書きます。

Java

1import java.util.Scanner; 2 3class Main { 4 public static void main(String []args){ 5 Scanner sc = new Scanner(System.in); 6 for (;;) { 7 System.out.print(">> "); 8 if (!sc.hasNextInt()) break; 9 int n = sc.nextInt(); 10 new Sum(n).gen(0, n, n); 11 } 12 } 13} 14 15class Sum { 16 int a[]; 17 18 Sum(int n) { 19 a = new int[n]; 20 } 21 22 void gen(int i, int k, int r) { 23 if (r == 0) { // 和ができたので表示 24 for (int j = 0; j < i; j++) 25 System.out.print(" " + a[j]); 26 System.out.println(); 27 } 28 else if (r > 0) // まだ和に達していない 29 for (int j = k; j > 0; j--) { 30 a[i] = j; 31 gen(i+1, j, r - j); // 再帰呼出し 32 } 33 } 34}

追記
gen を static にして、Sumクラスを使わずに、
さらに、和を引数で与えるようにしてみました。

Java

1import java.util.Arrays; 2 3class Main { 4 public static void main(String []args){ 5 for (int i = 0; i < args.length; i++) { 6 int n = Integer.parseInt(args[i]); 7 if (i > 0) System.out.println(); 8 gen(new int[n], 0, n, n); 9 } 10 } 11 12 static void gen(int[] a, int i, int j, int r) { 13 if (r == 0) // 和ができたので表示 14 System.out.println(Arrays.toString(Arrays.copyOf(a, i))); 15 else if (r > 0) // まだ和に達していない 16 for (; j > 0; j--) { 17 a[i] = j; 18 gen(a, i + 1, j, r - j); // 再帰呼出し 19 } 20 } 21}

実行例

text

1$ java Main 3 4 2[3] 3[2, 1] 4[1, 1, 1] 5 6[4] 7[3, 1] 8[2, 2] 9[2, 1, 1] 10[1, 1, 1, 1]

追記2
Math.min を使うと、else if (r > 0)else で済みますね。

Java

1 static void gen(int[] a, int i, int j, int r) { 2 if (r == 0) // 和ができたので表示 3 System.out.println(Arrays.toString(Arrays.copyOf(a, i))); 4 else // まだ和に達していない 5 for (j = Math.min(j, r); j > 0; j--) { 6 a[i] = j; 7 gen(a, i + 1, j, r - j); // 再帰呼出し 8 } 9 }

gen の呼び出し回数も減ります。

追記3
xebme さんのコードに刺激されて、for文を再帰呼出しに変えてみました。

Java

1import java.util.Arrays; 2 3class Main { 4 public static void main(String []args){ 5 int n = 6; 6 gen(new int[n], 0, n, n); 7 } 8 9 static void gen(int[] a, int i, int j, int r) { 10 if (r == 0) // 和ができたので表示 11 System.out.println(Arrays.toString(Arrays.copyOf(a, i))); 12 else { // まだ和に達していない 13 a[i] = j = Math.min(j, r); 14 gen(a, i + 1, j, r - j); 15 if (--j > 0) gen(a, i, j, r); 16 } 17 } 18}

和の n は、ハードコーディングしました。
Scanner による標準入力や、args によるコマンドライン引数に
変えるのは簡単でしょう。

投稿2021/08/10 14:34

編集2021/08/11 11:30
kazuma-s

総合スコア8087

arch👍を押しています

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

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

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

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

0

仕様の不明点

引数(int n,int i, int k)の意味がわかりません。できれば追記をお願いします。

課題検討

与えられた数(n)が和になる、整数(1<=i<=n)の全ての組み合わせを求める課題だと思います。再帰で利用するため文字列をアキュムレータとして使っています。簡単すぎてかえって自信がありません。誤りがあれば指摘してください。繰り返し解くならメモ化してもよいかもしれません。

Java

1public class q353621 { 2 3 public static void main(String[] args) { 4 for (int i = 1; i < 10; ++i) { 5 checkRemainder(i, i, /* i, */ ""); 6 System.out.println(); 7 } 8 } 9 10 static void checkRemainder(int rem, int divisor, /* int v,*/ String accum) { 11 12 if (divisor == 0) return; 13 if (rem == divisor) { 14 // 余りがない -> 完了 15 System.out.println(accum + ((accum.length()==0)?"":",") + divisor); 16 } else if (rem > divisor){ 17 // 余りがある 18 checkRemainder(rem - divisor, divisor, /* v,*/ accum + ((accum.length()==0)?"":",") + divisor); 19 } 20 /* if (rem == v) accum = ""; */ 21 checkRemainder(rem, divisor - 1, /* v,*/ accum); 22 23 } 24 25}

結果も添付します。

bash

11 2 32 41,1 5 63 72,1 81,1,1 9 104 113,1 122,2 132,1,1 141,1,1,1 15 165 174,1 183,2 193,1,1 202,2,1 212,1,1,1 221,1,1,1,1 23 246 255,1 264,2 274,1,1 283,3 293,2,1 303,1,1,1 312,2,2 322,2,1,1 332,1,1,1,1 341,1,1,1,1,1 35 367 376,1 385,2 395,1,1 404,3 414,2,1 424,1,1,1 433,3,1 443,2,2 453,2,1,1 463,1,1,1,1 472,2,2,1 482,2,1,1,1 492,1,1,1,1,1 501,1,1,1,1,1,1 51 528 537,1 546,2 556,1,1 565,3 575,2,1 585,1,1,1 594,4 604,3,1 614,2,2 624,2,1,1 634,1,1,1,1 643,3,2 653,3,1,1 663,2,2,1 673,2,1,1,1 683,1,1,1,1,1 692,2,2,2 702,2,2,1,1 712,2,1,1,1,1 722,1,1,1,1,1,1 731,1,1,1,1,1,1,1 74 759 768,1 777,2 787,1,1 796,3 806,2,1 816,1,1,1 825,4 835,3,1 845,2,2 855,2,1,1 865,1,1,1,1 874,4,1 884,3,2 894,3,1,1 904,2,2,1 914,2,1,1,1 924,1,1,1,1,1 933,3,3 943,3,2,1 953,3,1,1,1 963,2,2,2 973,2,2,1,1 983,2,1,1,1,1 993,1,1,1,1,1,1 1002,2,2,2,1 1012,2,2,1,1,1 1022,2,1,1,1,1,1 1032,1,1,1,1,1,1,1 1041,1,1,1,1,1,1,1,1 105

投稿2021/08/11 08:25

編集2021/08/12 07:11
xebme

総合スコア976

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

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

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

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

回答へのコメント

kazuma-s

2021/08/11 11:23

if (rem == v) accum = ""; この行は要らないでしょう。 rem == v ということは再帰呼出しのトップレベルであり、 accum は元から "" です。
kazuma-s

2021/08/11 12:06

ということは、checkRemainder の引数 v は要らなくなるでしょう。
xebme

2021/08/12 07:18

kazuma-sさん、ありがとうございます。 引数vを削除しました。当初は2引数で作成していました。バグがあったため、vを追加しましたが、勘違いでした。 質問が3引数なのは、アキュムレータ用の配列のインデックスかもしれないと思います。

0

要件を満たしていないので答えにはなりませんが、ヒントになるか(ならないか)ということで、動作するモノを出してみます。
ハノイの塔のように '1' をあちこちに移動させている感じです。

java

1import java.util.Arrays; 2import java.util.HashSet; 3import java.util.Set; 4 5public class Q353621 { 6 public static void main(String[] args) { 7 int n = 6; //要素の和 8 9 int buf[] = new int[n]; 10 buf[0] = n+1; 11 Set<String> done = new HashSet<>(); 12 int i = 0; 13 do { 14 //パターン生成 15 if(i > 0) buf[i-1] ++; 16 for(int j=--buf[i--]; j > 0; j--) buf[++i] = 1; 17 //既存チェック・表示 18 String s = Arrays.toString(Arrays.stream(buf, 0, i+1).sorted().toArray()); 19 if(done.add(s)) System.out.println(s); 20 } while(i > 0); 21 } 22}

text

1[1, 1, 1, 1, 1, 1] 2[1, 1, 1, 1, 2] 3[1, 1, 1, 3] 4[1, 1, 2, 2] 5[1, 1, 4] 6[1, 2, 3] 7[1, 5] 8[2, 2, 2] 9[2, 4] 10[3, 3] 11[6]

投稿2021/08/10 17:00

編集2021/08/11 01:47
jimbe

総合スコア10819

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

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

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

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

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
86.02%

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

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

質問する

関連した質問

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

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

再帰

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