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

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

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

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

再帰

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

受付中

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

ttp111
ttp111

総合スコア2

Java

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

再帰

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

1回答

0評価

0クリップ

296閲覧

投稿2022/03/17 10:22

編集2022/03/22 07:52

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

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

良い質問の評価を上げる

以下のような質問は評価を上げましょう

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

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

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

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

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

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

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

まだ回答がついていません

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

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

ただいまの回答率
87.20%

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

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

質問する

関連した質問

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

Java

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

再帰

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