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

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

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

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

再帰

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

Q&A

3回答

921閲覧

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

arch

総合スコア0

Java

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

再帰

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

0グッド

0クリップ

投稿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できれば、バックトラッキングを使って解きたいです。

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

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

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

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

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

mather

2021/08/10 07:46

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

2021/08/10 08:13

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

回答3

0

要素の和を 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

総合スコア8224

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

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

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

総合スコア1081

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

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

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引数なのは、アキュムレータ用の配列のインデックスかもしれないと思います。
guest

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

総合スコア12543

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

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

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

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問