2
8
2010
0

JAVA分数模板

贴SGU 382 Cantor Functions 用做JAVA分数模板

 

 

java code : Fraction
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.*;
import java.math.*;
import java.io.*;

class Fraction{
	BigInteger den, num;
	Fraction(){}
	Fraction(int a){
		den = BigInteger.ONE;
		num = BigInteger.valueOf(a);
	}
	Fraction(BigInteger a){
		den = BigInteger.ONE;
		num = a;
	}
	void simplify(){
		BigInteger gcd = den.gcd(num);
		den = den.divide(gcd);
		num = num.divide(gcd);
	}
	Fraction subtract( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.den );
		c.num = num.multiply( b.den ).subtract( b.num.multiply( den ) );
		c.simplify();
		return c;
	}
	Fraction add( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.den );
		c.num = num.multiply( b.den ).add( b.num.multiply( den ) );
		c.simplify();
		return c;
	}
	Fraction multiply( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.den );
		c.num = num.multiply( b.num );
		c.simplify();
		return c;
	}
	Fraction divide( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.num );
		c.num = num.multiply( b.den );
		c.simplify();
		return c;
	}
	void print(){
		System.out.println( num + "/" + den );
	}
}


public class Solution{
	static public void main( String argv[] ) throws IOException{
		Scanner scanner = new Scanner( System.in );
		int n = scanner.nextInt();
		// calc Cnk 
		Fraction C[][] = new Fraction[n+1][n+1];
		for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) C[i][j] = new Fraction(0);
		for(int i = 0; i <= n; ++i) C[i][0] = new Fraction(1);
	
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j<= i; ++j){
				C[i][j] = C[i-1][j].add( C[i-1][j-1] );
			}
		}

		Fraction F[] = new Fraction[n+1];
		F[0] = new Fraction(1);
		BigInteger three = BigInteger.valueOf(3);
		BigInteger two = BigInteger.valueOf(2);
		for(int i = 1; i <= n; ++i){
			Fraction sum = new Fraction(1);
			Fraction div = new Fraction(BigInteger.ONE.shiftLeft(i).multiply(three).subtract(two) );
			for(int j = 0; j < i; ++j){
				sum = sum.add( F[j].multiply( C[i][j] ) );
			}
			F[i] = sum.divide(div);
		}
		F[n].print();
	}
}
Category: 未分类 | Tags: | Read Count: 1047

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com