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

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

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

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

再帰

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

Q&A

1回答

771閲覧

再帰関数を使ったプログラムのランタイムエラーを解決したい

ttp111

総合スコア2

Java

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

再帰

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

0グッド

0クリップ

投稿2022/03/17 10:22

編集2022/03/17 15:55

1.実現したいこと
以下のように、入力された数値の和の組み合わせを全て昇順で出力するプログラムを組みたい。

入力例:
2⇦入力される個数
1
3
出力例:
4⇦出力される個数
0(何も足していない)
1(1のみ)
3(3のみ)
4(1+3)

2.発生している問題
入力によってはランタイムエラーが起きてしまう。

3.該当のソースコード

import java.util.*; public class Main { //答えを追加していくリスト static List<Integer> ans = new ArrayList<>(); //入力を受け取る配列 static int[] nums; //再起関数を使って全パターンを考える //patternという配列をnumsと比べ、patteran[i]が0のときにnums[i]をscoreに足し、 //足し終わったscoreをansに追加していく static void combination(int pattern[], int n, int num_decided){ if(num_decided==n){ int score = 0; for(int i=0; i<n; i++){ if(pattern[i] == 0){ score += nums[i]; } } ans.add(score); return; } //pattern[i]が0ならnums[i]をscoreに足す pattern[num_decided] = 0; combination(pattern,n,num_decided + 1); //pattern[i]が1ならnums[i]をscoreに足さない pattern[num_decided] = 1; combination(pattern,n,num_decided + 1); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); //入力の個数を受け取る int n = sc.nextInt(); nums = new int[n]; int[] pattern = new int[n]; int num_decided = 0; //入力を受け取る for(int i=0; i<n; i++){ nums[i] = sc.nextInt(); } combination(pattern,n,num_decided); //重複した数値を消去 List<Integer> ansDrop = new ArrayList<>(new HashSet<>(ans)); //昇順に並べる Collections.sort(ansDrop); //出力個数を出力 System.out.println(ansDrop.size()); //和の組み合わせを出力 for(int i=0; i<ansDrop.size(); i++){ System.out.println(ansDrop.get(i)); } } }

4.ソースコードの追加解説
再帰関数combinationの部分では入力例の場合、
pattern={0,0}
pattern={0,1}
pattern={1,0}
pattern={1,1}
とnums={1,3}を見比べ、pattern[i]が0の時はscoreにnums[i]を足し、1の時は足さないという作業をすることで、
score=0
score=3
score=1
score=4
をそれぞれ作り出し、ansというリストに追加している、ことを意図しています。

5.何を教えて欲しいのか
どのような入力の場合にランタイムエラーが起きてしまうのか、またそれはなぜ起きてしまうのかも出来れば教えていただきたいです。

6.補足
アルゴリズム的な間違いというよりも、入力が多い場合に、処理に時間がかかりランタイムエラーが起こっているのかもしれません(実行時間の制約があります)。

もし再帰を使わない等のよりシンプルな解法がわかる方がいれば、解答して頂ければ幸いです。

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

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

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

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

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

maisumakun

2022/03/17 10:26

> 入力によってはランタイムエラーが起きてしまう。 エラーメッセージなどはどのようなものでしょうか?
ttp111

2022/03/17 11:32

ランタイムエラーです。とだけ言われます。 ソースコード→コンパイル→実行(ここで起きてるエラーがランタイムエラー) 申し訳ありませんが、具体的なエラーメッセージやランタイムエラーを起こす入力はわかりません。 入力によっては恐らく無限ループなどにハマってしまっているものと思われます。
maisumakun

2022/03/17 11:35

実行環境はどのようなものですか?
ttp111

2022/03/17 11:39

web上で実行できるプログラミングサイトです
maisumakun

2022/03/17 11:41

別なサイトに乗り換えたほうがいいかもしれません。エラーを勝手に要約してしまうのは不親切です。
actorbug

2022/03/17 13:37

入力する数値の最小・最大はいくつでしょうか。 入力する数値の個数の最小・最大はいくつでしょうか。 以下のような入力は許されるのでしょうか。 1 2147483648
ttp111

2022/03/17 15:46

入力数値、個数の最大・最小は不明です。 そのような入力も許されます。
jimbe

2022/03/17 16:32

何が入力されたのかも、ランタイムエラーというものが何なのかも分からないのでは、推測も難しいように思われます。 プログラミングサイトとは具体的に何処なのでしょうか。
hoshi-takanori

2022/03/17 19:45

競プロならテストケースを考えることも問題に含まれます。
actorbug

2022/03/17 20:33 編集

ご提示のコードに、私が示した例を入力すると、以下のようなランタイムエラーになります。 Java における int の最大値(2147483647)を超えているためです。 Exception in thread "main" java.util.InputMismatchException: For input string: "2147483648" また、もっと単純に、入力数値の個数に -1 を指定しても、以下のようなランタイムエラーになります。 Exception in thread "main" java.lang.NegativeArraySizeException: -1 このように、入力数値や個数に制限がないと、問題として成り立たなくなるため、何らかの制限が明示されているのが普通です。
xebme

2022/03/17 21:17

↑つまり問題に、個数Nの範囲、数値の範囲などの制約が明示されているはず。 Nが大きい時、再帰がスタックオーバーフローするかが気になります。 (stackoverflowに質問するのもありです) 再帰をループに書き直すのはどうか。 ansをTreeSetにすれば重複排除、整列は不要。
xebme

2022/03/18 23:57 編集

N個の数字の冪集合の作り方は、もっと効率の良い方法がありそうです。調べてみましょう。 「ランタイムエラー」は調べてください。例外発生なのか、タイムアウトなのかなど、テストケースごとに結果が表示されていると思います。 この問題は、冪集合を作らず、和の集合に各数字を足した集合を加えることでも解けます。
guest

回答1

0

エラーになる状況

問題の制約は、入力値だけでなく、実行時の制約があり、実行条件はわかりかねます。結果のエラーレポートを読んで考えましょう。

改善コード

全ての数(正の値)を足した和がオーバーフローしないという仮定を設けます。メソッドは、入力値の配列を引数にとり、重複の排除にSetを利用します。戻り値のTreeSetを順にアクセスすれば、昇順に値が取り出せます。

Java

1static Set<Integer> uniqueSums(int[] nums) { 2 3 // 答えを追加していく集合 4 Set<Integer> ans = new TreeSet<>(); 5 ans.add(0); 6 7 // 和の集合を作成 8 Set<Integer> tmp = new HashSet<>(); 9 for (int n : nums) { 10 tmp.clear(); 11 for (int e : ans) { 12 tmp.add(e + n); 13 } 14 ans.addAll(tmp); 15 } 16 17 return ans; 18 19 }

これでも実行時エラーが起きるならTreeSetをやめるなどの方策が必要です。例えば、和の最大値がある数以下に決まっているなら配列を用意するなど。

コードにバグがあれば私の責任です。

追記(仕様について)

仕様の理解が正しいかどうか自信がありません。チェックプログラムを追記します。計算量はO(2^N)です。

Java

1import java.util.ArrayList; 2import java.util.Comparator; 3import java.util.List; 4import java.util.Map; 5import java.util.stream.Collectors; 6import java.util.stream.Stream; 7 8public class SumExpressions { 9 10 public static void main(String[] args) { 11 listAll(new int[] {1,2,3,5,7}); 12 } 13 14 static void listAll(int[] nums) { 15 16 // 答えを追加していく集合 17 List<String> ans = new ArrayList<>(); 18 ans.add("0"); 19 20 // 和の式を作成 21 List<String> tmp = new ArrayList<>(); 22 for (int n : nums) { 23 tmp.clear(); 24 for (String e : ans) { 25 String s = e + "+" + n; 26 tmp.add(s); 27 } 28 ans.addAll(tmp); 29 } 30 31 // 式の個数を出力 32 System.out.println("size : 2^" + nums.length + " : " + ans.size()); 33 // 和の組み合わせを出力 34 ans.stream().collect( 35 Collectors.groupingBy( 36 e -> Stream.of(e.split("\\+")) 37 .map(Integer::valueOf) 38 .collect(Collectors.summingInt(x -> x)) 39 ) 40 ).entrySet().stream() 41 .sorted(Comparator.comparing(Map.Entry::getKey)) 42 .map(e -> e.getKey() + " : " + e.getValue()) 43 .forEach(System.out::println); 44 } 45}

投稿2022/03/19 07:49

編集2022/03/21 22:52
xebme

総合スコア1090

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

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

xebme

2022/03/21 22:52

追記コードが分かりにくいので置き換えました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

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

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

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

ただいまの回答率
85.36%

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

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

質問する

関連した質問