java 二項式 – JAVA編程語言程序開發技術文章

/**
 * 劉雲龍
 *
 * 2011-10-12
 * 下午03:31:31
 */ 
package com.long3.util; 
 
import java.util.Arrays; 
 
/**
 * @author 劉雲龍 www.aiwalls.com
 * 
 */ 
public class LeftMove { 
    public static void main(String args[]) { 
        try { 
            timer.begin(); 
            for(int i = 0; i < 100; i++) 
            Arrays.toString(yanghui3(20)); 
            timer.end(); 
            System.out.println(timer.getTime()); 
             
             
            timer.begin();for(int i = 0; i < 100; i++) 
            Arrays.toString(yanghui2(20)); 
            timer.end(); 
            System.out.println(timer.getTime()); 
             
             
            timer.begin();for(int i = 0; i < 100; i++) 
            Arrays.toString(yanghui(20)); 
            timer.end(); 
            System.out.println(timer.getTime()); 
             
             
        } catch (IllegalAccessException e) { 
            e.printStackTrace(); 
        } 
    } 
 
    int[] createArray(int size) { 
        return new int[size]; 
    } 
 
    static int[][] yanghui(int level) throws IllegalAccessException { 
        if (level <= 0) { 
            throw new IllegalAccessException("參數不能為負值或為0 ： 現在的 level = " 
                    + level); 
        } 
        int[][] yanghui = new int[level][level]; 
 
        if (level >= 1) { 
            yanghui[0][0] = 1; 
        } 
        if (level >= 2) { 
            yanghui[1][0] = 1; 
            yanghui[1][1] = 1; 
        } 
 
        for (int row = 2; row < level; row++) { 
            yanghui[row][0] = 1; 
            for (int col = 1; col < level – 1; col++) { 
                yanghui[row][col] = yanghui[row – 1][col – 1] 
                        + yanghui[row – 1][col]; 
            } 
            yanghui[row][row] = 1; 
        } 
 
        return yanghui; 
    } 
 
    static int[] yanghui2(int level) throws IllegalAccessException { 
        if (level <= 0) { 
            throw new IllegalAccessException("參數不能為負值或為0 ： 現在的 level = " 
                    + level); 
        } 
        int[] yanghui = new int[level]; 
 
        if (level >= 1) { 
            yanghui[0] = 1; 
        } 
        if (level >= 2) { 
            yanghui[1] = 1; 
        } 
 
        for (int i = 2; i < level; i++) { 
            yanghui[i] = 1; 
            for (int j = i – 1; j >= 1; j–){ // 從左向右加，去掉  i 和 0 位置不參加計算 
                yanghui[j] = yanghui[j] + yanghui[j – 1]; 
            } 
        } 
 
        return yanghui; 
    } 
 
     
    static int[] yanghui3(int level) throws IllegalAccessException{ 
        if (level <= 0) { 
            throw new IllegalAccessException("參數不能為負值或為0 ： 現在的 level = " 
                    + level); 
        } 
        int[] yanghui = new int[level + 1]; 
         
        for(int i=0; i < level + 1; i++){ 
            yanghui[i] = combin(level, level-i); 
        } 
         
         
        return yanghui; 
    } 
     
    static int combin(int m, int n){ 
//      System.out.println( p(n) * p(m-n)  + "p(n) " + n + "p(m-n)" + (m-n)); 
//      System.out.println( p(n) * p(m-n)  + "p(n) " + p(n) + "p(m-n)" + p(m-n)); 
        return p(m) / ( p(n) * p(m-n) ); 
    } 
     
    static int p(int a){ 
        if(a == 0){ 
            return 1; 
        } 
         
        for(int i = a – 1; i >= 1; i–){ 
            a *= i; 
        } 
        return a; 
    } 
     
} 
 
class timer{ 
    static long beginTime ; 
    static long endTime;  
     
    static void begin(){ 
        beginTime = System.currentTimeMillis(); 
    } 
    static void end(){ 
        endTime = System.currentTimeMillis(); 
    } 
    static String getTime(){ 
        return (endTime-beginTime) + ""; 
    } 
} 

二項式 

摘自 longnihao的專欄