ヽ｜∵｜ゝ(Fantom) の 開発blog？

/**<h1>パスカルの三角形を作る</h1>
 * <p>パスカルの三角形を斜めに傾けた配列を作成。左上が(0,0)で右下に拡がる感じになる。</p>
 * @param w ： 横数 (1～33)
 * @param h ： 縦数 (1～33)
 * @return<b>long[][]</b> ： パスカルの三角形を配列化したもの
 */
public static final long[][] pascalsTriangle(final int w, final int h) {
    final long[][] arr = new long[h + 1][w + 1];
    arr[0][0] = 1;

    for (int i = 0; i <= h; i++) {
        for (int j = 0; j <= w; j++) {
            if (j > 0) {
                arr[i][j] += arr[i][j - 1];
            }
            if (i > 0) {
                arr[i][j] += arr[i - 1][j];
            }
        }
    }

    return arr;
}


//メインでは...
int w = 5;
int h = 4;
long[][] pascal = pascalsTriangle(w, h);    //パスカルの三角形

/**<h1>n 個のものから r 個取り出した組合せの数を求める</h1>
 * <p>nCr をパスカルの三角形から求める。
 * <br>n, r が 大きすぎるとオーバーフローするので注意。</p>
 * @param n ： すべての数 (1～66) (負の値はエラー)
 * @param r ： 取り出す数 (1～33) (負の値はエラー)
 * @return<b>long</b> ： 組合せの数
 */
public static final long combination(final int n, final int r) {
    if (n < 0 || r < 0 || n < r) {
        throw new ArithmeticException("n = " + n + ", r = " + r);
    }
    if (r == 0 || r == n) {
        return 1;
    }
    if (r == 1) {
        return n;
    }

    //パスカルの三角形
    final long[][] pascal = pascalsTriangle(r, n - r);
    return pascal[n - r][r];
}

//パスカルの三角形での解法
int n = 4;    //4人
long[][] pascal = pascalsTriangle(n, n); //大きさは適当(n x n あればカバーできる)
long sum = 0;    //勝敗がつく事象の合計
for (int i = 1; i < n; i++) {    //4C1～4C3 まで(4人のうち1～3人勝つ[=勝敗がつく]組合せ)
    sum += pascal[n - i][i];
}
sum *= 3;    //グー、チョキ、パーの３手でそれぞれ勝てるため、３倍する
double d = 1.0 - sum / Math.pow(3, n);    //あいこ = 全事象 - 勝敗がつく事象 [=余事象]
System.out.println(d);    //0.4814814814814815 (13/27)

//あいこになる確率を一般化したものでの解法
int n = 4;    //4人
double d = 1.0 - (Math.pow(2, n) - 2.0) / Math.pow(3, n - 1);    //あいこ = 全事象 - 勝敗がつく事象 [=余事象]
System.out.println(d);    //0.4814814814814815 (13/27)

//パスカルの三角形に通行止めフラグ(closed[][])を入れた
public static final long[][] pascalsTriangle(final int w, final int h, final boolean[][] closed) {
    final long[][] arr = new long[h + 1][w + 1];
    arr[0][0] = 1;

    for (int i = 0; i <= h; i++) {
        for (int j = 0; j <= w; j++) {
            if (closed[i][j]) {
                continue;
            }
            if (j > 0) {
                arr[i][j] += arr[i][j - 1];
            }
            if (i > 0) {
                arr[i][j] += arr[i - 1][j];
            }
        }
    }

    return arr;
}


//メインでは・・・
int w = 5;
int h = 4;
boolean[][] closed = new boolean[h + 1][w + 1];
closed[1][3] = true;    //通行止め
closed[2][1] = true;    //通行止め
closed[3][2] = true;    //通行止め
long[][] pascal = pascalsTriangle(w, h, closed);
System.out.println(pascal[h][w]);    //25 となる

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.HashSet;

public class FifteenPuzzleAstar {

    public static void main(String[] args) throws Exception {
        new FifteenPuzzleAstar();
    }

    //４方向探索用
    static final int[] dx = { 0, 1, 0, -1};
    static final int[] dy = {-1, 0, 1,  0};
    static final char[] dir = {'u', 'r', 'd', 'l'};

    static final int N = 4;          //盤サイズ
    static final int NN = N * N;     //パネル総数

    //各パネルのマンハッタン距離のテーブル
    static final int[][] MDTable = new int[NN][NN];
    static {
        for (int i = 0; i < NN; i++) {
            for (int j = 0; j < NN; j++) {
                MDTable[i][j] = getManhattanDistance(i % N, i / N, j % N, j / N);
            }
        }
    }

    //マンハッタン距離を求める
    static int getManhattanDistance(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    public FifteenPuzzleAstar() {

        int[][] board = new int[][]{    //初期の盤の状態
            { 1, 7, 2, 4},
            { 6, 0,14, 3},
            {13,10,11, 8},
            { 5, 9,15,12},
        };  //rrdllldruuurdllddrurrd 22(手)

        String ans = astar(board);
        System.out.println(ans);
        System.out.println(ans.length());
    }

    //A*(A-star)で15パズルを解く
    String astar(int[][] board) {
        Set<String> done = new HashSet<String>();    //既出パターンチェック用
        Queue<Puzzle> q = new PriorityQueue<Puzzle>();

        Puzzle p = new Puzzle();
        p.setBoard(board);        //初期の盤の状態をセットする
        p.estimate = p.md;        //推定値
        q.add(p);
        done.add(p.toString());

        while (!q.isEmpty()) {
            p = q.poll();
            if (p.md == 0) {      //全てのパネルが揃ったら０
                return p.path;    //空白の移動経路
            }

            done.add(p.toString());
            int sx = p.space % N;    //空白の位置
            int sy = p.space / N;

            for (int i = 0; i < dx.length; i++) {
                int nx = sx + dx[i];    //空白の移動位置
                int ny = sy + dy[i];
                if (nx < 0 || N <= nx || ny < 0 || N <= ny) {    //範囲外
                    continue;
                }

                Puzzle p2 = p.clone();
                p2.changeSpace(nx, ny);   //空白と数字パネルを入れ替える（スライドする）
                if (!done.contains(p2.toString())) {    //既出パターンチェック
                    p2.cost++;            //手数
                    p2.estimate = p2.md + p2.cost;    //推定値
                    //p2.estimate = p2.md;    //推定値（実行速度を優先したいときはこっちにする）
                    p2.path += dir[i];    //空白の移動経路(移動方向の記録)
                    q.add(p2);
                }
            }
        }

        return "unsolvable";    //完成できなかったとき
    }

    //パズルの状態を保存する構造体（クラス）
    class Puzzle implements Cloneable, Comparable<Puzzle> {
        int[] panel = new int[NN];    //各位置にあるパネル番号(番号は１ベース)
        int space;                    //空白のインデクス
        int md;                       //全パネルのマンハッタン距離の合計
        int cost;                     //手数
        int estimate;                 //推定値
        String path = "";             //空白の移動経路(移動方向の記録)

        //盤の並びをセットする
        void setBoard(int[][] board) {
            int p = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (board[i][j] == 0) {   //空白
                        panel[p] = NN;        //空白は最大値にする
                        space = p;            //空白のインデクス
                    } else {
                        panel[p] = board[i][j];
                    }
                    p++;
                }
            }

            calcMD();    //全パネルのマンハッタン距離の合計を求める
        }

        //全パネルのマンハッタン距離の合計を求める
        void calcMD() {
            md = 0;
            for (int i = 0; i < NN; i++) {
                if (panel[i] != NN) {        //空白は除外する
                    md += MDTable[i][panel[i] - 1];    //番号は１ベース
                }
            }
        }

        //空白と数字パネルを入れ替える（スライドする）
        void changeSpace(int x, int y) {
            int index = x + y * N;           //インデクスに変換
            md += MDTable[space][panel[index] - 1];    //全パネル距離合計から移動後の数字パネル距離を足す(差分計算)
            md -= MDTable[index][panel[index] - 1];    //全パネル距離合計から現在の数字パネル距離を引く
            panel[space] = panel[index];    //数字パネルを交換(スライド)
            panel[index] = NN;              //空白を交換
            space = index;                  //空白のインデクス更新
        }

        //比較関数
        @Override
        public int compareTo(Puzzle o) {
            return this.estimate - o.estimate;    //推定値で小さい順
        }

        //盤の状態を文字列にする（既出パターンのキーとしても利用）
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder(NN * 3);
            for (int i = 0; i < NN; i++) {
                if (i > 0) {
                    if (i % N == 0) {
                        sb.append("\n");
                    } else {
                        sb.append(" ");
                    }
                }
                sb.append(panel[i]);
            }
            return sb.toString();
        }

        //盤の状態を複製する
        @Override
        public Puzzle clone() {
            try {
                Puzzle obj = (Puzzle)super.clone();
                obj.panel = this.panel.clone();
                return obj;
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException();
            }
        }
    }
}

import java.util.PriorityQueue;
import java.util.Queue;

public class MazeShortestAstar {

    public static void main(String[] args) throws Exception {
        new MazeShortestAstar();
    }

    static final int INF = Integer.MAX_VALUE;    //INF値

    //４方向探索用
    static final int[] dx = { 0, 1, 0, -1};
    static final int[] dy = {-1, 0, 1,  0};
    static final char[] dir = {'u', 'r', 'd', 'l'};

    String path = "";    //移動経路(戻値用)

    //マンハッタン距離を求める
    static int getManhattanDistance(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }
    //チェビシェフ距離を求める
    static int getChevyshevDistance(int x1, int y1, int x2, int y2) {
        return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
    }

    public MazeShortestAstar() {

        int n = 10;    //↓方向
        int m = 10;    //→方向
        String[] maze = new String[]{
            "S..#...#..",
            ".#.#.#.#.#",
            "...#.#....",
            "##...#.##.",
            ".....#.#..",
            ".#####.#.#",
            ".......#..",
            "##.######.",
            "...#...#..",
            ".#...#...G",
        };

        int ans = astar(n, m, maze);
        System.out.println(ans);
        System.out.println(path);
    }

    //A*(A-star)探索アルゴリズム
    int astar(int n, int m, String[] maze) {
        int[][] grid = new int[n][m];    //移動コスト(距離)の記録
        int sx, sy, gx, gy;              //スタートとゴール位置
        sx = sy = gx = gy = 0;

        //迷路データのパース
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maze[i].charAt(j) == '#') {
                    grid[i][j] = -1;       //壁
                } else if (maze[i].charAt(j) == 'S') {
                    grid[i][j] = 0;        //スタートは距離０
                    sy = i;
                    sx = j;
                } else if (maze[i].charAt(j) == 'G') {
                    grid[i][j] = INF;
                    gy = i;
                    gx = j;
                } else {
                    grid[i][j] = INF;
                }
            }
        }

        //A*(A-star) 探索
        Queue<Position> q = new PriorityQueue<Position>();

        Position p = new Position(sx, sy);
        p.estimate = getManhattanDistance(sx, sy, gx, gy);    //推定値
        q.add(p);

        while (!q.isEmpty()) {
            p = q.poll();
            if (p.cost > grid[p.y][p.x]) {
                continue;
            }
            if (p.y == gy && p.x == gx) {    //ゴールに到達
                path = p.path;        //移動経路(戻値用)
                break;
            }

            for (int i = 0; i < dx.length; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx < 0 || m <= nx || ny < 0 || n <= ny) {    //範囲外
                    continue;
                }
                if (grid[ny][nx] > grid[p.y][p.x] + 1) {
                    grid[ny][nx] = grid[p.y][p.x] + 1;
                    
                    Position p2 = new Position(nx, ny);
                    p2.cost = grid[ny][nx];        //移動コスト(スタートからの移動量)
                    p2.estimate = getManhattanDistance(nx, ny, gx, gy) + p2.cost;    //推定値
                    p2.path = p.path + dir[i];     //移動経路(移動方向の記録)
                    q.add(p2);
                }
            }
        }

        return grid[gy][gx];    //見つからないときは INF 値になる
    }

    //位置情報の構造体
    class Position implements Comparable<Position>{
        int x;               //座標
        int y;
        int cost;            //移動コスト(スタートからの移動量)
        int estimate;        //推定値(ゴールまでのマンハッタン距離＋移動コスト)
        String path = "";    //移動経路(移動方向の記録)

        //コンストラクタ
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        //比較関数
        @Override
        public int compareTo(Position o) {
            return this.estimate - o.estimate;    //推定値で小さい順
        }
    }
}

public class WarshallFloyd {

    public static void main(String[] args) throws Exception {
        new WarshallFloyd();
    }

    public WarshallFloyd() {
        //図をデータにしたもの
        int n = 6;    //頂点数
        int[][] adj = new int[][]{
            //接続元ノード, 接続先ノード, 重み
            {0, 1, 1},
            {0, 3, 2},
            {0, 4, 3},
            {1, 2, 4},
            {1, 4, 1},
            {2, 4, 1},
            {2, 5, 3},
            {3, 4, 2},
            {4, 5, 3}
        };

        //辺の情報を無向グラフ用にする(有向グラフでも構わない)
        int[][] edges = new int[adj.length * 2][3];
        int len = adj.length;
        for (int i = 0; i < len; i++) {
            edges[i] = adj[i];    //そのままコピー(シャローコピー)
            //無向グラフにしたいので、逆方向も接続する
            edges[i + len][0] = adj[i][1];
            edges[i + len][1] = adj[i][0];
            edges[i + len][2] = adj[i][2];
        }

        int[][] ans = warshallFloyd(n, edges);    //各頂点間の最短コスト(表)

        //表を出力
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j > 0) {
                    System.out.print(" ");
                }
                if (ans[i][j] == INF) {
                    System.out.print("INF");
                } else {
                    System.out.print(ans[i][j]);
                }
            }
            System.out.println();
        }

        //負の閉路の判定
        System.out.println("Negative Cycle = " + isNegativeCycle(ans));
    }

    static final int INF = Integer.MAX_VALUE;    //INF 値((int)1e9, 1 << 30, Integer.MAX_VALUE / 2 などでも良い)

    //ワーシャル-フロイド法[全点対間最短経路(All Pairs Shortest Path)]
    int[][] warshallFloyd (int n, int[][] edges) {
        //初期化
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = (i == j) ? 0 : INF;    //i と j が同じ位置(d[i][i])は、負の閉路チェックに使う
            }
        }

        //隣接行列のように、重みを入れる
        for (int i = 0; i < edges.length; i++) {
            d[edges[i][0]][edges[i][1]] = edges[i][2];
        }

        //ワーシャル-フロイド法(全点対間最短経路)
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (d[i][k] == INF) {
                    continue;
                }
                for (int j = 0; j < n; j++) {
                    if (d[k][j] == INF) {
                        continue;
                    }
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }

        return d;
    }

    //負の閉路チェック
    boolean isNegativeCycle(int[][] d) {
        int n = d.length;
        for (int i = 0; i < n; i++) {
            if (d[i][i] < 0) {
                return true;    //負の閉路がある
            }
        }
        return false;
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BellmanFord {

    public static void main(String[] args) throws Exception {
        new BellmanFord();
    }

    public BellmanFord() {
        //Wikipedia の例(図)をデータにしたもの
        int n = 6;    //頂点数
        int s = 0;    //スタート頂点(頂点番号は -1 されている[元は 1])
        int g = 4;    //ゴール頂点(頂点番号は -1 されている[元は 5])
        int[][] adj = new int[][]{
            //接続元ノード, 接続先ノード, 重み
            {0, 1, 7},
            {0, 2, 9},
            {0, 5, 14},
            {1, 2, 10},
            {1, 3, 15},
            {2, 3, 11},
            {2, 5, 2},
            {3, 4, 6},
            {4, 5, 9}
        };    //s:0 → g:4 のとき、答えは 20

        //辺情報の配列を作る
        List<Edge> list = new ArrayList<Edge>();
        for (int i = 0; i < adj.length; i++) {
            list.add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
            list.add(new Edge(adj[i][1], adj[i][0], adj[i][2])); //無向グラフなので、逆方向も接続する
        }

        Edge[] edges = list.toArray(new Edge[0]);    //配列に変換

        int ans = bellmanford(n, edges, s, g);
        System.out.println(ans);    //s → g の最短距離
    }

    //ベルマン-フォード法[単一始点最短経路(Single Source Shortest Path)]
    int bellmanford(int n, Edge[] edges, int s, int g) {
        int[] distance = new int[n];        //始点からの最短距離
        int[] count = new int[n];           //更新カウント(負の閉路チェック用)

        Arrays.fill(distance, Integer.MAX_VALUE);    //各頂点までの距離を初期化(INF 値)
        distance[s] = 0;    //始点の距離は０

        boolean negative = false;     //負の閉路フラグ
        boolean update = true;        //更新フラグ

        while (update && !negative) {
            update = false;
            for (Edge e : edges) {
                //接続元＋接続先までの距離
                if (distance[e.source] != Integer.MAX_VALUE && distance[e.source] + e.cost < distance[e.target]) {
                    distance[e.target] = distance[e.source] + e.cost;    //現在記録されている距離より小さければ更新
                    update = true;

                    if (++count[e.target] >= n) {    //負の閉路チェック
                        negative = true;
                        break;
                    }
                }
            }
        }

        if (negative) {
            return Integer.MIN_VALUE;    //負の閉路があったときは、-INF(Integer.MIN_VALUE)を返す
        }
        return distance[g];    //到達できなかったときは、INF(Integer.MAX_VALUE)になる
    }

    //辺情報の構造体
    class Edge implements Comparable {
        public int source = 0;    //接続元ノード
        public int target = 0;    //接続先ノード
        public int cost = 0;      //重み

        public Edge(int source, int target, int cost) {
            this.source = source;
            this.target = target;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }

        @Override
        public String toString() {    //デバッグ用
            return "source = " + source + ", target = " + target + ", cost = " + cost;
        }
    }
}

・・・（略）・・・
import java.util.Collections;
import java.util.LinkedList;

public class BellmanFord {
    ・・・（略）・・・
    public BellmanFord() {
        ・・・（略）・・・
        List<Edge> paths = new LinkedList<Edge>();    //選択した辺(戻値用)

        int ans = bellmanford(n, edges, s, g, paths);
        System.out.println(ans);    //s → g の最短距離

        //選択した辺(確認)
        int len = paths.size();
        for (int i = 1; i < len; i++) {    //一番最初[0]は始点のためスキップ
            System.out.println(paths.get(i));
        }
    }

    //ベルマン-フォード法[単一始点最短経路(Single Source Shortest Path)]
    //選択した辺を返す。
    int bellmanford(int n, Edge[] edges, int s, int g, List<Edge> paths) {
        int[] distance = new int[n];        //始点からの最短距離
        int[] parent = new int[n];          //接続元ノード
        int[] count = new int[n];           //更新カウント(負の閉路チェック用)

        Arrays.fill(distance, Integer.MAX_VALUE);    //各頂点までの距離を初期化(INF 値)
        Arrays.fill(parent, -1);    //-1 は始点または未到達
        distance[s] = 0;    //始点の距離は０

        boolean negative = false;     //負の閉路フラグ
        boolean update = true;        //更新フラグ

        while (update && !negative) {
            update = false;
            for (Edge e : edges) {
                //接続元＋接続先までの距離
                if (distance[e.source] != Integer.MAX_VALUE && distance[e.source] + e.cost < distance[e.target]) {
                    distance[e.target] = distance[e.source] + e.cost;    //現在記録されている距離より小さければ更新
                    parent[e.target] = e.source;    //接続元を記録
                    update = true;

                    if (++count[e.target] >= n) {    //負の閉路チェック
                        negative = true;
                        break;
                    }
                }
            }
        }

        if (negative) {
            return Integer.MIN_VALUE;    //負の閉路があったときは、-INF(Integer.MIN_VALUE)を返す
        }

        //選択した辺(逆から辿る[到達点→始点])
        paths.clear();
        if (parent[g] > -1) {
            int p = g;
            while (p > -1) {
                paths.add(new Edge(parent[p], p, distance[p]));
                p = parent[p];
            }
            Collections.reverse(paths);    //反転する(始点→到達点)
        }

        return distance[g];    //到達できなかったときは、INF(Integer.MAX_VALUE)になる
    }
    ・・・（略）・・・
}