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

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

ただいまの
回答率

90.61%

  • Java

    13522questions

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

再帰的なメソッドをスタックを使って非再帰的に書くには?

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 372

gyro16

score 77

前提・実現したいこと

IntStackはInt型のスタック、先入れ後出しのStackです。

static void recur3(int n){
if(n > 0){
recur3(n-1);
recur3(n-2);
System.out.println(n);
}
これをIntStackをつかって

static void recur3(int n){
IntStack s = new IntStack(100);
if(n > 0){
s.push(n);
n = n - 2;
}
continue;
if(s.isEmpty() != true){
n = s.pop();
System.out.println(n);
}
}

これだと
static void recur3(int n){
if(n > 0){
recur3(n-2);
System.out.println(n);
}
}
しかなりません

IntStackをつかって書くにはどうすれば良いでしょうか?
recur(n-1)まで含めて書くにはどうすれば良いでしょうか?

スタック 入り口 1, 2, 1, 3 底

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

static void recur3(int n){
 if(n > 0){
  recur3(n-1);
  recur3(n-2);
  System.out.println(n);
}

該当のソースコード

static void recur3(int n){
 IntStack s = new IntStack(100);
 if(n > 0){
  s.push(n);
  n = n - 2;
 }
 continue;
 if(s.isEmpty() != true){
  n = s.pop();
  System.out.println(n);
 }
}

static void recur3(int n){
    int nn = n;
    IntStack s = new IntStack(100);
    if(n > 0){
        s.push(n);
        n = n - 2;
    }
    continue;
    if(nn > 0)
        nn = nn - 1;
        s.push(nn);
    }
    continue;
    if(s.isEmpty() != true){
        n = s.pop();
        System.out.println(n);
    }
}

試したこと

recur3(1)→ recur3(0) recur3(-1) Sys.out.1 → Sys.out.1
recur3(2)→ recur3(1) recur3(0) Sys.out.2 → Sys.out.1 Sys.out.2
recur3(3)→ recur3(2) recur(1) Sys.out.3 → Sys.out.1 Sys.out.2 Sys.out.1 Sys.out.3

スタック 入り口 1, 2, 1, 3 底

補足情報(言語/FW/ツール等のバージョンなど)

より詳細な情報

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

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

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

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

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

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

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

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

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • anndonut

    2017/12/30 20:38

    ちなみに「該当のソースコード」にはrecur3メソッドが2つ書いてありますね。2つのコードを試したけど両方ダメだったという意味でしょうか?

    キャンセル

回答 3

checkベストアンサー

+1

Deque<Integer>を使った書き方です。「Forthの力を信じよ!」ってやつです。

import java.util.Deque;
import java.util.ArrayDeque;

public class Main {
    public static final int RECURSION = 0;
    public static final int PRINT = 1;

    public static void recur3(int n) {
        // Javaのドキュメントによると、Stackクラスの代わりに
        // Dequeインターフェースを使用することが推奨されています。
        Deque<Integer> stack = new ArrayDeque<Integer>();
        stack.push(n);
        stack.push(RECURSION);
        while (!stack.isEmpty()) {
            if (stack.pop() == RECURSION) {
                int num = stack.pop();
                if (num > 0) {
                    stack.push(num);
                    stack.push(PRINT);
                    stack.push(num - 2);
                    stack.push(RECURSION);
                    stack.push(num - 1);
                    stack.push(RECURSION);
                }
            } else { // stack.pop() == PRINT
                System.out.println(stack.pop());
            }
        }
    }

    public static void main(String[] args) {
        recur3(3);
    }
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

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

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

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/12/31 12:06

    このコードを解説するために、デバッグ用の出力を追加したものを用意しました。
    https://gist.github.com/haruo-wakakusa/db9ce844370f4359effa49f992fb810e
    まず、recur3(1)について出力してみましょう。

    [0, 1]
    [0, 0, 0, -1, 1, 1]
    [0, -1, 1, 1]
    [1, 1]
    1
    []

    こうなります。Dequeでpush, popを行うと、データの末尾ではなく先頭にデータが追加・削除されるようですね。これを、Forth風(ただしForthとは逆の書き方)に書くと、こうなります。

    R 1
    R 0 R -1 P 1
    R -1 P 1
    P 1
    1が出力
    スタックが空になり、終了。

    つまり、Rがrecur3メソッドで、PがSystem.out.printlnメソッドに対応する命令です。Forthでは命令と引数を同じ型で表現しても正しく動作するので、R=0, P=1としています。

    recur3(1)の開始時には、R 1という命令を置いています。これは分かりやすいですね。
    次の行では、R 1の引数である1が0より大きいので、R 0 R -1に展開されます。
    その次の行では、R 0が先頭に来ていますが、Rの引数が0なので、0より大きくなく、そのまま消費されます。
    その次の行では、R -1が先頭に来ていますが、Rの引数が-1なので、0より大きくなく、そのまま消費されます。
    その次の行では、P 1が先頭に来ていますが、Pはその引数を表示するので、1を表示します。
    この時点で、スタックが空になったので、プログラムを終了します。

    recur3(2)以降についても同様のことが言えます。分からなければさらに解説させて頂きます。

    キャンセル

  • 2017/12/31 12:36

    分かりました。分かりやすいです。
    Dequeでもpushやpopできるんですね。

    キャンセル

0

分かりづらいけどこんな感じです。もっと分かりやすい回答があったらそっちに習ったほうがいいかもしれませんね。IntStackは使ってないです。Stackクラスを使ってます。

import java.util.Stack;

public class Main {
    public class Recur3 {
        private int num = 0;
        private Stack<Recur3> s = null;

        public Recur3(int n, Stack<Recur3> stack) {
            num = n;
            s = stack;
        }

        public void run() {
            if (num > 0) {
                s.push(new Printer(num, s));
                s.push(new Recur3(num-2, s));
                s.push(new Recur3(num-1, s));
            }
        }
    }

    public class Printer extends Recur3 {
        private int num = 0;

        public Printer(int n, Stack<Recur3> stack) {
            super(n, stack);
            num = n;
        }

        public void run() {
            System.out.println(num);
        }
    }

    private Recur3 create(int n, Stack<Recur3> stack) {
        return new Recur3(n, stack);
    }

    public static void main(String[] args) {
        Stack<Recur3> s = new Stack<Recur3>();
        s.push((new Main()).create(4, s));
        while (!s.empty()) {
            s.pop().run();
        }
    }
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

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

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

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/12/30 18:42

    ロジック違いませんか?結果違うと思いますよ
    ただ並列で並べただけでは再帰的な結果とは違いますよ

    キャンセル

  • 2017/12/30 19:21

    Javaの内部クラスが分かって、しかもForthという言語が分かるなら僕のやってることが分かると思う。

    キャンセル

  • 2017/12/30 19:51

    recur3(3)は1 2 1 3ですから、答えが違いますよ。
    recur3(4)でもrecur3(3) recur3(2) Sys.out.4
    ですから1 2 1 3 1 2 4ですから結果が違いますよ。

    キャンセル

  • 2017/12/30 20:34

    gyro16さん、ご指摘ありがとうございます。ケアレスミスでした。コード直しておきます。

    キャンセル

  • 2017/12/30 21:17

    箱型に箱型を押し込む。それを再帰的に繰り返すスタックですか。

    キャンセル

  • 2017/12/30 21:50

    IntStackクラスは本の中に登場するものだと思いますが、一般的にはjava.util.Stackクラスを使います。ただ、Stackクラスは総称型(ジェネリクス)で、型引数を必要とします。型引数にはintなどのプリミティブ型を指定することはできません。ただ、int型のラッパーであるInteger型を型引数にとることができ、IntStackクラスと同様の使い方ができます。Forthはoperatorとargumentを逆順で並べる言語ですが、逆順で並べるとスタックの構造と相性がいいのでそうします。詳しくは私のもう一つのコードをご参照ください。

    キャンセル

  • 2017/12/30 23:40

    Stackは古いので、Dequeで宣言してLinkedListやArrayDequeを使うべき。

    キャンセル

  • 2017/12/31 08:43

    Stackは古いかもしれないけど、Stackを使わないとForthを実装してる感が出ないんじゃない?Dequeを使う場合は、「これはスタックとして使っています」と、コメントを添えるべき。あと、できることなら代替コードを示して、具体的に、速度的に優れているとか、サイズが大きくなるとオーダー的に優れているとか示してあげると親切だと思います。

    キャンセル

  • 2017/12/31 10:35

    速度などの問題ではなく、Stackのドキュメントに記載されている事です。
    https://docs.oracle.com/javase/jp/8/docs/api/java/util/Stack.html
    > より完全で一貫性のある一連のLIFOスタック・オペレーションが、Dequeインタフェースとその実装によって提供されています。このクラスよりもそれらを優先的に使用するようにしてください。

    キャンセル

  • 2017/12/31 10:44 編集

    それは判断が厳しいねー。そもそも質問者さんがDequeというものを理解しているかですよね。Stackが使用不推奨になっていなければ今回の場合はStackで実装でいいと思いますけどね。

    キャンセル

  • 2017/12/31 10:55

    ちょい直しで済んだので、もう一つの回答の方でStack<Integer>をDeque<Integer>に直しておきました。swordoneさん、ご指摘ありがとうございます。

    キャンセル

  • 2017/12/31 11:04

    if(num > 0)で並列でpushしていてなぜ0以下がpushされないのですか?
    num-2,num-1ではチェックしていませんよね?

    キャンセル

  • 2017/12/31 11:18

    そもそも質問者はIntStackというおそらくオリジナルのクラスを使っているのにあなたが勝手にStackを使いだしたんだから、
    「質問者がDequeを理解しているか」というのはお門違い。

    キャンセル

  • 2017/12/31 11:24

    numが減っていく機序はどうなってるのですか?
    デバッグでブレークポイントで見たのですがよく分かりません。

    キャンセル

  • 2017/12/31 11:40

    swordoneさん、おっしゃる通りです。というかIntStackというクラスを使っているからこそ他の回答者さんはなかなか手を出すことができずに、私とgyro16さんのほうで忖度して回答しているということなんだと思います。

    キャンセル

  • 2017/12/31 11:42

    gyro16さん、このコードは分かりづらいので、もう一つのコードの方で解説させて頂きます。

    キャンセル

0

import java.util.Scanner;
public class En5_5b{
    static void recur3(int n) throws IntStack.OverflowIntStackException, IntStack.EmptyIntStackException{
        int num = n;
        IntStack s = new IntStack(100);
        while(n > 0){
            try{
                s.push(n);
            }catch(IntStack.OverflowIntStackException e){
                System.out.println("スタックが満杯です。");
            }
            n -= 2;
        }
        while(num-1 > 0){
            try{
                s.push(num-1);
            }catch(IntStack.OverflowIntStackException e){
                System.out.println("スタックが満杯です。");
            }
            num--;
        }
        while(s.isEmpty() != true){
            try{
                n = s.pop();
            }catch(IntStack.EmptyIntStackException e){
                System.out.println("スタックが空です。");
            }
            System.out.println(n);
        }
    }
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        System.out.println("整数を入力せよ:");
        int n = stdIn.nextInt();
        recur3(n);
    }
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

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

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

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/12/30 21:00

    gyro16さんのコードはn=4のときに1 2 3 2 4と出力しませんか?貪欲法で解きに行ってこけてるように思われたので。

    キャンセル

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

  • ただいまの回答率 90.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    ループ化の方法

    public class Gohkaku {     public static void main(String[] args){         int math = ne

  • 解決済

    Javaのクラス同士のつながりについて

    こんにちは。Javaの質問です。 2つのクラスがあるんですけど、これらはどのようにつながっているのでしょうか。 (うまく説明できません、言い直すと) Mainを実行するとSt

  • 解決済

    100になる直前の加算結果出力

    javaで開始値と終了値を入力してその間の偶数を加算していき、合計が100を超えたら「数値が100を超えたため、処理を中止します。」とメッセージを出し、かつ合計が100になる前の加

  • 解決済

    会員情報システム(Java)での作り方

    javaで会員情報システムのようなものを作りたいです。 下記の実行結果(コマンドプロンプトで実行)になるような、登録プログラムを作成したいのですが、作成方法が分かりませんので、教

  • 受付中

    計算機の機能追加に関する質問

    javaで計算機のプログラムを作成しました。 単項マイナス演算(例、-10+5)を行う処理を追加したいのですが 修正方法がわかりません。 どのように修正したらよいでしょうか?

  • 解決済

    Java Hit&Blow

    Hit&Blowのコードです。 答えの4桁の数字が重複しないためのコードはどのように書けばいいのでしょうか? import java.util.Scanner; class

  • 受付中

    ジャンケンゲーム

    ジャンケンゲームを作ってます。 <ルール> コンピュータに3回負けたらゲーム終了! 負けるまでゲームは続く! 数字を入力するとループが止まりません。 あと、winlo

  • 解決済

    ループ文の終了について

    数当てゲームで正解した時にプログラムを終了させたいのですが終わることができません。 初歩的なことで申し訳ありませんがお力添えをおねがいします。 public class N

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

  • Java

    13522questions

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