知恵袋の袋の中の玉を交換する確率の問題をJavaで解いてみた。

　知恵袋の袋の中の玉を交換する確率の問題をJavaで解いてみました。(^_^;

　袋Aには白玉4個と黒玉5個,袋Bには白玉3個黒玉２個が入っている。まずAから２個を取り出してBに入れ次にBから２個を取り出してAに戻す。このときAの中の白玉と黒玉の個数が初めと変わらない確率を求めて下さい。

　Danjo3.javaが雛形になりそうなので、Javaで作ってみました。countMatches()メソッドは、ColorHat1.javaから持って来ました。(^_^;

● ExchangeBalls.java

/*
 * ExchangeBalls.java
 */

import java.util.Arrays;

class ExchangeBalls {
    // 順列生成
    static boolean nextPerm(char[] p, int n, int r) {
        int i, j;
        char t;
        
        if(r <= 0 || n < r) return(false);
        for(i = r + 1; i <= n-1; i++)
            for(j = i; j >= r + 1 && p[j-1] < p[j]; j--){
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;    // swap(p,j,j-1);
            }
        for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
        if(i==0) return(false);
        for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
        t = p[j]; p[j] = p[i-1]; p[i-1] = t;            // swap(p,j,i-1);
        for(j=n-1; i< j; i++, j--){
            t = p[i]; p[i] = p[j]; p[j] = t;            // swap(p,i,j);
        }
        return(true);
    }
    // 組合せ生成
    static boolean nextComb(char[] p, int n, int r) {
        int i;
        do{
            if(!nextPerm(p,n,r)) return(false);
            for(i=0; i< r-1; i++)
                if(p[i]> p[i+1]) break;
        } while (i< r-1);
        return(true);
    }
    // 最大公約数
    static int gcd(int a, int b){ return( b == 0 ? a : gcd(b, a % b) ); }
    
    // 文字列 s の中で、文字 c が出現した数を取得
    static int countMatches(String s, char c) {
        int n = s.length();
        int count = 0;
        for(int i=0; i< n; i++)
            if(s.charAt(i)==c) count++;
        return(count);
    }
    
    public static void main(String[] args) {
        final String A = "ABCDabcde";       // 白玉を大文字、黒玉を小文字で表す
        final String B = "EFGfg";
        char[] p = A.toCharArray();         // 組合せ生成用
        int count = 0, total = 0;
        long tm = System.nanoTime();    // Timer Start
        
        do{
            String a = A.replace(""+p[0],"").replace(""+p[1],"");   
            String b = B+p[0]+p[1];         // まず袋Aから２個を取り出して袋Bに入れ
            char[] q = b.toCharArray();
            Arrays.sort(q);
            do{
                total++;                    // 全てをカウント
                String s = a+q[0]+q[1];     // 次に袋Bから２個を取り出して袋Aに戻す
                for(int i=0; i< 9; i++)     // 横に白黒表を作成
                    s+=(Character.isUpperCase(s.charAt(i)) ? "白" : "黒");
                if(countMatches(s,'白')==4) count++;
                //System.out.println(s);
            }while(nextComb(q,7,2));
        }while(nextComb(p,9,2));
        
        int g = gcd(total,count);
        System.out.printf("%d / %d = %d / %d\n", count, total, count/g, total/g);
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

360 / 756 = 10 / 21
Runtime : 0.032 [sec]

※参考URL
http://stackoverflow.com/questions/275944/how-do-i-count-the-number-of-occurrences-of-a-char-in-a-string

スッキリわかるJava入門 第2版 (スッキリシリーズ)

明解Java 入門編

新わかりやすいJava入門編