今アルゴリズムの勉強をしていてkupc(2012:practice)のサイトにあったアッカーマン関数の問題を見てプログラムを作りました。
下記が出来上がったものです。(m,n)=(2,3)であれば出力できましたが、入力例の2としてあった(3,45)はjava.lang.StackOverflowErrorとなりました。
bigintegerや例外処理できないか考えていますがここから進めないので何か方法があれば教えてほしいです。
import java.util.Scanner;
public class AckermannExec {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
System.out.print("[m]>");
long m=scan.nextInt();
System.out.print("[n]>");
long n=scan.nextInt();
long a=Ackermann(m,n);
System.out.println("A(m,n)="+a);
}
public static long Ackermann(long m,long n){
if(m>=1&&n>=1){
return Ackermann(m-1,Ackermann(m,n-1));
}else if(n==0){
return Ackermann(m-1,1);
}else{
return n+1;
}
}
}
よろしくお願いします。
No.2ベストアンサー
- 回答日時:
java.lang.StackOverFlowErrorは名前の通りスタックがオーバーフローした状態を表します。
変数の桁数は関係ないですから、
このエラーに関しては変数の型を変えても意味はありません。
関数を呼ぶと、引数の情報・関数から戻った後に実行する命令のアドレスが
スタックと呼ばれる領域に格納されます。
これらのデータは関数から戻るまで削除されないため、
再帰の階層が深くなりすぎるとスタックを使い切ってしまい、上述のエラーが発生します。
Java VMの設定でスタック領域を増やすといった対策も考えられますが、
アルゴリズムの勉強とのことですので、
再帰の階層が深くなりすぎないように工夫するのもおもしろいと思います。
No.3
- 回答日時:
深い再帰呼び出しでStackOverflowErrorが出る場合は、javaの-Xssオプションでスタックを増やしてあげればStackOverflowErrorを出さずに実行を継続できるようになる場合があります。
しかしこの場合は無意味でしょう。
Ackermann(3,45)の再帰呼び出しの深さは約2の48乗になります。呼び出し1段で仮にスタックを64バイト消費するとすれば、2の54乗バイト(16ペタバイト)のメモリが必要になります。そんな大量のメモリを積めるコンピュータはありません。
再帰が深くならないように書き換えられればいいのですが、アッカーマン関数は再帰を使わない書き方が不可能であることが証明されています。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Java java 入力 3 4 3 出力 ABC DEFG HIJ このようなプログラムの書き方を教えてくだ 2 2022/07/15 14:18
- Ruby 【JAVA】数字をひし形に出力するプログラムについて 2 2022/07/11 23:32
- Java javaでのプログラム(配列)について質問です. 2 2022/10/14 22:27
- Java Java 配列<選挙> 4 2023/07/31 15:07
- Java Java プログラム public class Main { public static void 3 2023/08/10 23:46
- Visual Basic(VBA) いつもお世話になっております、VBAで教えて頂きたいのですが 2 2022/05/05 22:20
- C言語・C++・C# C# DatagridviewにExcelシートを反映するとエラーが出る 2 2023/05/06 17:12
- Java JavaのSingletonパターンのprivateの持つ意味が分かりません。 5 2022/06/12 10:38
- Java java 引数 戻り値のあるメソッド 3 2023/02/12 06:23
- Visual Basic(VBA) batからexeを実行し戻り値を受け取る バッチからEXEの結果を受け取りたいのですが、 下記のバッ 1 2023/07/04 15:13
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
変数を動的に利用するには?
-
中カッコ{}だけの記述について
-
インタフェイス実装と抽象クラ...
-
Socketの接続のタイムアウトを...
-
randomで
-
プログラミングの問題です。大...
-
"try{}catch(){}"文で"close()"...
-
java 継承の問題で分からないと...
-
Javaでlog4jを使ってログ出力を...
-
Processing :指定フォルダ内の...
-
所持金の計算式とその表示の仕方
-
JSP/Servletのパラメータの受け...
-
現在時刻をYYYY-MM-DDThh:mm:ss...
-
privateなフィールドは継承され...
-
Javaで日本語の出力が文字化けする
-
コンストラクタの引数の中のnew?
-
【java】同ディレクトリ別ファ...
-
ArrayList でスタックを
-
複素数の計算するクラスを足せ...
-
javaで特定の文字列から特定の...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
プログラミングの問題です。大...
-
変数を動的に利用するには?
-
中カッコ{}だけの記述について
-
System.exit()の値を取得したい
-
Javaでlog4jを使ってログ出力を...
-
NoSuchMethodErrorが解決できま...
-
javaで特定の文字列から特定の...
-
Socketの接続のタイムアウトを...
-
Java プログラム public class ...
-
javaのプログラミングで作るRPG...
-
インタフェイス実装と抽象クラ...
-
コマンドライン引数の*(アフ...
-
【初心者です】javaで平均値を...
-
Javaで日本語の出力が文字化けする
-
(大至急)JavaでATMもどきを作成
-
コンストラクタの引数の中のnew?
-
Java 最大公約数 gcd
-
randomで
-
C# DatagridviewにExcelシート...
-
replaceAllが使えない場合の取...
おすすめ情報