質問の三角形の個数の問題をJavaで解いてみた。(2)

　前回のプログラムを組合せを生成して条件に合うものをカウントして求める方法で作りなおしてみました。(^_^;
　PCは、Core2Duoですが、9段目ぐらいから遅くなってます。(^_^;

●NumOfEquTriAng02.java

/* 
 * NumOfEquTriAng02.java
 *  equilateral triangle: 正三角形 
 *           0
 * 0      /・          /  0
 * 1     /・・        /  1, 2
 * 2    /・・・      /  3, 4, 5
 * 3   /・・・・    /  6, 7, 8, 9
 * 4  /・・・・・  / 10,11,12,13,14
 * 5 /・・・・・・/ 15,16,17,18,19,20
 *    0 1 2 3 4 5
 */

class NumOfEquTriAng02 {
    static boolean next_perm(int[] p, int n, int r) {
        int i, j;
        int 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 isAscending(int[] p,int m) {
        for(int i=0; i< m-1; i++)
            if(p[i]> p[i+1]) return(false);
        return(true);
    }
    
    static boolean next_comb(int[] p, int n, int r) {
        do{
            if(!next_perm(p,n,r)) return(false);
        } while(!isAscending(p,r));
        return(true);
    }
    
    static int getY(int n) {
        int i;
        for(i=0; n>=i*(i+1)/2; i++);
        return --i;
    }
    
    static int getX(int n,int y) {
        return(n-y*(y+1)/2);
    }
    
    static int getNumOfEquTriAng(int m) {
        int n=(m+1)*(m+2)/2, count=0;
        int[] p = new int[n];
        int[] x = new int[3];
        int[] y = new int[3];
        
        for(int i=0; i< n; i++) p[i]=i;
        do{
            for(int i=0; i< 3; i++)
                x[i]=getX(p[i], y[i]=getY(p[i]));
            if(x[1]==x[2] && y[0]==y[1] && x[1]-x[0]==y[2]-y[1]) count++;
            if(x[0]==x[1] && y[1]==y[2] && x[2]-x[1]==y[1]-y[0]) count++;
        }while(next_comb(p,n,3));
        return count;
    }
    
    public static void main(String[] args) {
        long tm=System.nanoTime();      // Timer Start
        
        for(int x=1; x<=10; x++){
            int y=getNumOfEquTriAng(x) ;
            System.out.println(y);
        }
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

1
5
13
27
48
78
118
170
235
315
Runtime : 3.296 [sec]

明解Java 入門編

解きながら学ぶJava 入門編

明解Javaによるアルゴリズムとデータ構造