LoginSignup
4
4

More than 5 years have passed since last update.

幅優先探索

Posted at

 ここ最近、チーター本が詰まってからAOJに訪れて再帰の練習問題を探したりしていたのですが、幅優先探索の問題を見つけたので試しにコーディングしてみました。ですが、無限ループに入ってしまい(何回目だ・・・)うまくいきません。よろしければ、どこがおかしいかご指摘頂ければ嬉しいです。
問題:AOJ0202(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202)

コード:


import java.util.*;
public class Main {
    int limit;
    int[] dish;
    int ans = Integer.MIN_VALUE;

    boolean isPrime(int num) {
        if(num < 2) return(false);
        for(int r = 2; r * r <= num; r++) {
            if(num % r == 0) return(false);
        }
        return(true);
    }

    int solve() {
        Queue<Integer> sum = new LinkedList<Integer>();

        sum.add(0);

        int ans = 0;
        while(!sum.isEmpty()) {
            int now = sum.poll();
            for(int r = 0; r < dish.length; r++) {
                int next = now + dish[r];
                if(next < limit) {
                    if(isPrime(next)) ans = Math.max(ans, next);
                    sum.add(next);
                }
                System.out.println(ans);
            }
        }
        return(ans);
    }

    void doIt() {
        Scanner stdIn =new Scanner(System.in);

        while(true) {
            int kind = stdIn.nextInt();
            limit = stdIn.nextInt();
            if(kind + limit == 0) break;
            dish = new int[kind];
            for(int r = 0; r < kind; r++) {
                dish[r] = stdIn.nextInt();
            }
            System.out.println(solve());
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        new Main().doIt();
    }

}

 この再帰とか、幅優先とかのアルゴリズムが、自分の中でしっかりしてくれないと次に進めない・・・(泣)

4
4
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
4