Problem 20

问题描述：
n! means n  (n  1)  ...  3  2  1
For example, 10! = 10  9  ...  3  2  1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!


Java中可以使用BigDecimal
不过也可以使用自己实现的大数算法~

结果：
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  4  6  8  6  1  9  0  1  2  5  8  1  1  5  2  8  5  7  3  2  2  7  2  8  0  2  9  7  9  6  3  5  2  6  8  2  8  1  5  6  5  1  6  7  9  3  6  4  1  4  9  8  0  6  5  1  9  9  2  2  3  9  9  9  9  5  7  1  2  5  9  8  3  6  9  2  9  5  8  6  4  1  2  6  1  8  3  4  6  2  8  6  9  5  1  7  0  9  4  0  0  7  6  6  2  6  5  8  8  3  2  9  9  6  1  8  6  2  5  1  4  4  9  3  4  4  5  1  2  6  2  3  3  9  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
648
16
最后的16是执行的时间毫秒级别
因为每次都会产生无用的0，而且越来越多，导致进行无效的计算很多次
算法还可以改进~

具体的算法

public static Byte[] StringToByte(String number){
		int len = number.length();
		Byte[] result = new Byte[len];
		//从高位到低位依次转换,转换后字符串"1234"变为4321,这样方便以后计算
		for(int i=0; i<number.length(); i++){
			byte curByte =  Integer.valueOf(number.charAt(i)+"").byteValue();
			result[len-i-1] = curByte;
		}
		
		return result;
	}
	
	public static Byte[] Add(Byte[] number1, Byte[] number2){
		int len = (number1.length>number2.length) ? number1.length : number2.length;
		Byte[] result = new Byte[len+1];
		Integer sum = new Integer(0);
		Integer carry = new Integer(0);
		int i;
		if(number1.length>number2.length){
			for(i=0; i<number2.length; i++){
				sum = number1[i].intValue() + number2[i].intValue();				
				sum = sum +carry;
				carry = ((sum -10)>=0) ? 1:0;
				sum = ((sum -10)>=0) ? (sum-10):sum;
				result[i] = sum.byteValue();
				sum = 0;
			}
			for(;i<number1.length;i++){
				sum = number1[i] +carry;
				carry = ((sum -10)>=0) ? 1:0;
				sum = ((sum -10)>=0) ? (sum-10):sum;
				result[i] = sum.byteValue();
				sum = 0;
			}
			if(carry!=0){
				result[i] = carry.byteValue();
			}else{
				result[i] = 0;
			}
		}else{
			for(i=0; i<number1.length; i++){
				sum = number1[i].intValue() + number2[i].intValue();				
				sum = sum +carry;
				carry = ((sum -10)>=0) ? 1:0;
				sum = ((sum -10)>=0) ? (sum-10):sum;
				result[i] = sum.byteValue();
				sum = 0;
			}
			for(;i<number2.length;i++){
				sum = number2[i].intValue() + carry;
				carry = ((sum -10)>=0) ? 1:0;
				sum = ((sum -10)>=0) ? (sum-10):sum;
				result[i] = sum.byteValue();
				sum = 0;
			}
			if(carry!=0){
				result[i] = carry.byteValue();
			}else{
				result[i] = 0;
			}
		}
		
		return result;
	}
	//level表示左移次数
	public static Byte[] left_shift(Byte[] number, int level){
		Byte[] result = new Byte[number.length+level];
		Integer zero = 0;
		for(int i=0; i<level; i++){
			result[i] = zero.byteValue();
		}
		for(int i=0; i<number.length; i++){
			result[i+level] = number[i];
		}
		return result;
	}
	
	//乘法计算过程中被乘数总是与成数的一位相乘
	public static Byte[] MultiplyOne(Byte[] number1, Byte number2){
		Byte[] result = new Byte[number1.length+1];
		Integer cur = 0;
		Integer carry = 0;
		Integer zero = 0;
		int i;
		Arrays.fill(result, zero.byteValue());
		
		for(i=0; i<number1.length; i++){
			cur = number1[i].intValue()*number2.byteValue();
			cur = cur +carry;
			carry = cur/10;
			cur = cur%10;
			result[i] = cur.byteValue();
			cur = 0;
		}
		if(carry==0){
			result[i] = cur.byteValue();
		}else{
			result[i] = carry.byteValue();
		}
		
		return result;
	}

	public static Byte[] Multiply(Byte[] number1, Byte[] number2){
		Byte[] result = new Byte[number1.length+1];
		Byte[] before = new Byte[number1.length];
		Integer zero = 0;
		Arrays.fill(before, zero.byteValue());
		
		for(int i=0; i<number2.length; i++){
			result = MultiplyOne(number1, number2[i]);
			result = left_shift(result, i);
			result = Add(result, before);
			before = result;

		}
		
		return result ;
	}
	
	public static void print(Byte[] result){
		for(int i=0; i<result.length; i++){
			System.out.print(result[i]+"  ");
		}
		System.out.println();
	}

public static void main(String[] args){
		Integer one = 1;
		Byte[] result = new Byte[1];
		result[0] = one.byteValue();
		long t1 = System.currentTimeMillis();
		for(Integer i=2; i<=100; i++){
			Byte[] cur = BigNumber.BigNumber.StringToByte(i+"");
			result = BigNumber.BigNumber.Multiply(result, cur);
		}
		int sum = 0;
		for(int i=0; i<result.length; i++){
			sum += result[i].intValue();
		}
		long t2 = System.currentTimeMillis();
		BigNumber.BigNumber.print(result);
		System.out.println(sum);
		System.out.println((t2-t1));
	}