public int factorial(int x) { if (x < 0) { throw new IllegalArgumentException("x must be>=0"); } int fact = 1; for (int i = 2; i <= x; i++) { fact *= i; } return fact; }
第一题：数据结构（二叉树） 第二题：数论（模拟大数计算） package Helloworld;public class Hello { public static void main(String args[]) { int TheNumber = 1111;/*--- 要求阶乘的数字---*/ int mod = 10000; int[] ary = new int[TheNumber]; ary[0] = 1;
int i, j; int width; /*---表示结果的"宽度"---*/ int current_num; /*--- 当前数字 ---*/
第一题我以前做过:
//本程序只能计算正整数范围内的加减乘除运算。
import java.util.*;public class Expression{
//优先级数组，precede[i][j],表示第i个操作符与第j个操作符的优先级，0，1，2，3，4，5，6分别是'+', '-', '*', '/', '(', ')', '#'
//0表示，第i个操作符优先级小于第j个操作符。1表示大于，2表示相等，3是表示不可能的。
int precede[][]={{1 , 1 , 0 , 0 , 0 , 1 , 1},
{1 , 1 , 0 , 0 , 0 , 1 , 1},
{1 , 1 , 1 , 1 , 0 , 1 , 1},
{1 , 1 , 1 , 1 , 0 , 1 , 1},
{0 , 0 , 0 , 0 , 0 , 2 , 3},
{1 , 1 , 1 , 1 , 3 , 1 , 1},
{0 , 0 , 0 , 0 , 0 , 3 , 2}};
char[] operate={'+', '-', '*', '/', '(', ')', '#'};
String exp=null;
public Expression(String exp){
this.exp=exp;
}
int getValueInt(){
Stack<Integer> optr=new Stack<Integer>();
Stack<Integer> opnd=new Stack<Integer>();
String expression=exp+"#"; //给表达式加一个运算符，且是一个结束符
optr.push(6); //先把'#'操作符对应的序号入栈。
int index=0; //从0开始扫描表达式字符串。
//int sign=1; //符号，假设为正
int num=0;
char c=expression.charAt(index++);
while(c!='#'||optr.peek()!=6){
if(indexOperate(c)==-1){
/*if(c=='-'){
sign=-1;
c=expression.charAt(index++);
}else if(c=='+'){
c=expression.charAt(index++);
}*/
while(c>='0'&&c<='9'){
num=num*10+c-'0';
c=expression.charAt(index++);
}
opnd.push(num);
//sign=1;
num=0;
}
if(indexOperate(c)==-1){
System.out.println("Expression is Error!");
System.exit(0);
}
switch(precede[optr.peek()][indexOperate(c)]){
case 0 :
optr.push(indexOperate(c));
c=expression.charAt(index++);
break;
case 1 :
int num2=opnd.pop();
int opt=optr.pop();
int num1=opnd.pop();
opnd.push(binaryOperation(num1,opt,num2));
break;
case 2 :
optr.pop();
c=expression.charAt(index++);
break;
case 3 :
System.out.println("括号不配对Expression Error!");
System.exit(0);
}//switch
}//while
return opnd.peek();
}
int indexOperate(char c){
for(int i=0;i<operate.length;i++){
if(operate[i]==c) return i;
}
return -1;
}
int binaryOperation(int operand1,int opt,int operand2 ){
switch(opt){
case 0:
return operand1+operand2;
case 1:
return operand1-operand2;
case 2:
return operand1*operand2;
case 3:
return operand1/operand2;
}
return 0;
}
public static void main(String[] args){
Expression e=new Expression("((1+3)*3+(2+2)*5)/4");
//Expression e=new Expression("1+5");
System.out.println(e.getValueInt()); }
}
public int factorial(int x) { if (x < 0) { throw new IllegalArgumentException("x must be>=0"); } int fact = 1; for (int i = 2; i <= x; i++) { fact *= i; } return fact; }
BigDecimel 表示范围
不让用Math类,可以用java.math包中的BigInteger类.Math类是指java.lang.Math
public static BigInteger fac(BigInteger x) {
if (x.intValue()==1) {
return BigInteger.ONE;
} else {
BigInteger b = x.subtract(BigInteger.ONE);
return x.multiply(fac(b));
}
}
第二题：数论（模拟大数计算）
package Helloworld;public class Hello {
public static void main(String args[]) {
int TheNumber = 1111;/*--- 要求阶乘的数字---*/
int mod = 10000;
int[] ary = new int[TheNumber];
ary[0] = 1;
int i, j;
int width; /*---表示结果的"宽度"---*/
int current_num; /*--- 当前数字 ---*/
/*--- 从大到小进行阶乘计算 ---*/
for( width = 0 , current_num = TheNumber ; current_num > 1; current_num-- ){
/*--- 对每一个‘分段’进行运算 ---*/
for( i = j = 0; i <= width; i++ ){
/*--- 当前运算的‘有效数值’ ---*/
ary[i] = ( (j += ary[i] * current_num) ) % mod;
/*--- 当前运算的‘进位数值’ ---*/
j /= mod;
}
if ( (ary[i] = j ) != 0){ /*如果有进位，则索引向前推进*/
width++;
}
} /*--- 将求的数值输出 ---*/
System.out.printf("%d", ary[width] );
/*--- 将求的数值输出 ---*/
for( j = width - 1; j >= 0; j-- ){
System.out.printf( "%04d", ary[j] );/*--- 这里的4跟mod的位数有关 ---*/
}
}
}
public static uint[] CalculateLargeNumber(int n)
{
if (n < 0) { throw new ArgumentOutOfRangeException("n必须为非负数。"); } if (n == 0 || n == 1) { return new uint[] { 1 }; }
// 数组的最大长度
const int MaxLength = 100000;
uint[] array = new uint[MaxLength];
// 1! = 1
array[0] = 1;
int i = 0;
int j = 0;
// valid为当前阶乘值的位数（如5! = 120，此时valid = 3）
int valid = 1; for (i = 2; i <= n; i++)
{
long carry = 0;
for (j = 0; j < valid; j++)
{
long multipleResult = array[j] * i + carry;
// 计算当前位的数值
array[j] = (uint)(multipleResult % 10);
// 计算进到高位的数值
carry = multipleResult / 10;
}
// 为更高位赋值
while (carry != 0)
{
array[valid++] = (uint)(carry % 10);
carry /= 10;
}
}
// 截取有效元素
uint[] result = new uint[valid];
Array.Copy(array, result, valid);
return result;
}
用这个方法可以得出70!是101位（1.1979 × 10^100），450!是1001位，而1000!有2568位。需要注意的是，结果数的最高位存放在数组的索引最大的元素中，所以打印结果时要按正确的顺序。
{
if (n < 0) { throw new ArgumentOutOfRangeException("n必须为非负数。"); } if (n == 0 || n == 1) { return new uint[] { 1 }; }
// 数组的最大长度
const int MaxLength = 100000;
uint[] array = new uint[MaxLength];
// 1! = 1
array[0] = 1;
int i = 0;
int j = 0;
// valid为当前阶乘值的位数（如5! = 120，此时valid = 3）
int valid = 1; for (i = 2; i <= n; i++)
{
long carry = 0;
for (j = 0; j < valid; j++)
{
long multipleResult = array[j] * i + carry;
// 计算当前位的数值
array[j] = (uint)(multipleResult % 10);
// 计算进到高位的数值
carry = multipleResult / 10;
}
// 为更高位赋值
while (carry != 0)
{
array[valid++] = (uint)(carry % 10);
carry /= 10;
}
}
// 截取有效元素
uint[] result = new uint[valid];
Array.Copy(array, result, valid);
return result;
}
用这个方法可以得出70!是101位（1.1979 × 10^100），450!是1001位，而1000!有2568位。需要注意的是，结果数的最高位存放在数组的索引最大的元素中，所以打印结果时要按正确的顺序。
if(num == BigDecimal.ONE) {
return BigDecimal.ONE;
} else {
return num.multiply(hierarchy(num.subtract(BigDecimal.ONE)));
}
}
#include <iostream>
using namespace std;int a[10000];void Print( int nNum )
{
a[0]=1; if ( nNum == 1 )
{
return;
} for ( int j = 2;j <=nNum;j++ )
{
int b[2]; memset(b,0,sizeof(b)); for ( int i = 0 ;i < sizeof(a)/sizeof(int);i++ )
{
a[i] = a[i]*j + b[1];
b[1] = 0;//加了后立刻置0,很关键
if ( a[i] < 10 )
{
b[0] = a[i];
}
else
{
b[0] = a[i]%10;
b[1] = (a[i]-b[0])/10;
a[i] = b[0];
b[0] = 0;
}
}
}
}void main()
{
int nNum ;
while(true)
{
memset(a,0,sizeof(a));
cout<<"please input a Integer Number:";
cin>>nNum;
if ( nNum <= 0 )
{
continue;
} Print(nNum); //打印输出
bool bl = false;
for ( int i = sizeof(a)/sizeof(int)-1 ;i >= 0;i-- )
{
if ( a[i] != 0 || bl)
{
cout<<a[i];
bl = true;
}
}
cout<<"\n";
}
}
public static void main(String str[]) { int[] res = new int[3000]; final int limit = 1000; res[1] = 1;
int max_now = 1; for(int step = 1; step <= limit;step++) { int temp = 0; int now = max_now; //40320 int zero; for(zero = 1; zero <=now;zero++) { if(res[zero] != 0) break; } for(int carry = zero-1;carry <= now;carry++) { res[carry] *= step; res[carry] += temp; temp = 0; if(res[carry] >= 10) { int carry_temp = carry; temp = res[carry]; if(carry_temp <= max_now) { res[carry_temp] = temp%10; temp/=10; carry_temp++; } if(carry_temp > max_now) { while(temp >= 10) { res[carry_temp] = temp%10; temp /= 10; carry_temp++; } res[carry_temp] = temp; temp = 0; max_now = carry_temp; } } } } System.out.println(max_now); for(int j = max_now; j > 0; j--) { System.out.print(res[j]); } }
public static void main(String args[])
{
int b=1000; //要计算的数
int temp=0; //用于最后去掉整个数组中的前面没用的 0
int tt=0; //用于记录每次乘的进位数；
int[] a=new int[9000]; //
a[8999]=1; //把数组最后一位设为了1，从最后一位开始乘，
for(int i=1;i<=b;i++) //用从 1 到 b 的每一个数去乘数组的每个元素，
{
for(int j=8999;j>=0;j--)
{
a[j]=a[j]*i+tt; //数组中的元素=原来的数*i+进位数，
tt=0; //进位数清0，用于下回记录；
if((a[j]+"").length()>=2) //此元素大于10则进位，本身只保留余数;
{
tt=a[j]/10;
a[j]=a[j]%10;
}
}
}
for(int i=0;i<a.length;i++)//去掉数组前的0000
{
if(a[i]!=0)
{
temp=i;
break;
}
}
for(int i=temp;i<a.length;i++)//输出
{
System.out.print(a[i]);
}
}
import java.util.*;
import java.util.regex.*;
/**
*
*/
public class Expression{
//优先级数组，precede[i][j],表示第i个操作符与第j个操作符的优先级，0，1，2，3，4，5，6分别是'+', '-', '*', '/', '(', ')', '#'
//0表示，第i个操作符优先级小于第j个操作符。1表示大于，2表示相等，3是表示不可能的。
private int precede[][]={{1 , 1 , 0 , 0 , 0 , 1 , 1},
{1 , 1 , 0 , 0 , 0 , 1 , 1},
{1 , 1 , 1 , 1 , 0 , 1 , 1},
{1 , 1 , 1 , 1 , 0 , 1 , 1},
{0 , 0 , 0 , 0 , 0 , 2 , 3},
{1 , 1 , 1 , 1 , 3 , 1 , 1},
{0 , 0 , 0 , 0 , 0 , 3 , 2}};
private char[] operator={'+', '-', '*', '/', '(', ')', '#'};
private String infixExpression=null;
private ArrayList<MetaData> postfixExpression=new ArrayList<MetaData>();
public Expression(String exp){
infixExpression=exp+"#";
}
/**定义一个内部类表示表达式中的"元数据",操作数,或者是操作符,只能是两者之一.
*
*
*/
private class MetaData{
double dData; //float operand
int iData; // int operand
char operator; //operator
boolean isOperator=false;
MetaData(double dNum){
dData=dNum;
}
MetaData(int iNum){
iData=iNum;
}
MetaData(char operator){
this.operator=operator;
isOperator=true;
}
public boolean isOperand(){
return !isOperator;
}
public String toString(){
if(isOperator){
return ""+operator;
}else{
return ""+dData;
}
}
}//end of inner class MetaData
/**由中缀表达式得到后缀表达式。
* 设一个堆栈，用来存放操作符，先放一个自定义的操作符’#’，它的优先级是最小的。
* 扫描整个中缀表达式，操作数直接输出到结果postfixExpression中
* 如果是操作符，就和堆栈栈顶操作符比较，如果栈顶的优先级高则出栈并输出到结果，直到找到优先小的运算符为止。
* 如果两者优先级相同，表示是配对的括号，或'#'。
* 把当前的操作入栈。
*/
private void getPostfixExp(){
Stack<Integer> optrStack=new Stack<Integer>(); // Integer is a index of operator.
int index=0; // index: index of charachter in infixExpression.
double num=0; //
char c=0; //
optrStack.push(6); //'#' index is 6
//下面的正则用来提取一个数值
//
String regex="([-]?[0-9]+(\\.([0-9]+)?)?)";
Pattern numberPattern=Pattern.compile(regex);
Matcher numberMatcher=numberPattern.matcher(infixExpression);
while(index<infixExpression.length()){
if(numberMatcher.find(index)){
if(numberMatcher.start()==index){
num=Double.parseDouble(numberMatcher.group(1));
postfixExpression.add(new MetaData(num));
index=numberMatcher.end();
}
}
c=infixExpression.charAt(index++);
switch(precede[optrStack.peek()][getOperatorOrder(c)]){ //compare operator in stack with operator in c . get precede.
case 0 : //precede is 0 . means operator'precede in stack small than in c
optrStack.push(getOperatorOrder(c));
break;
case 1 :
while(precede[optrStack.peek()][getOperatorOrder(c)]==1){
postfixExpression.add(new MetaData(operator[optrStack.pop()]));
}
if(precede[optrStack.peek()][getOperatorOrder(c)]==2){
optrStack.pop(); //pop '('
}else{
optrStack.push(getOperatorOrder(c));
}
break;
case 2 :
optrStack.pop();
break;
case 3 :
System.out.println("括号不配对Expression Error!");
System.exit(0);
}//switch
}//while
}
/*对后缀表达式求值。
* 扫描整个后缀表达式，如果是数值，直接入栈。如果是运算符，出栈两个操作数，运算后，再把结果入栈。
*
*/
public double evaluate(){
getPostfixExp();
Stack<Double> valueStack=new Stack <Double>();
//System.out.println(postfixExpression);
for(MetaData md : postfixExpression){
if(md.isOperand()){
valueStack.push(md.dData);
}else{
double num1=valueStack.pop();
double num2=valueStack.pop();
valueStack.push(binaryOperation(num2,getOperatorOrder(md.operator),num1));
}
//System.out.println(valueStack);
}
return valueStack.pop();
}
/*取得操作符的序号，主要是为了比较优先级时，方便的访问precede这个二维数组。
*/
private int getOperatorOrder(char optr){
int order;
switch(optr){
case '+': order=0; break;
case '-': order=1; break;
case '*': order=2; break;
case '/': order=3; break;
case '(': order=4; break;
case ')': order=5; break;
case '#': order=6; break;
default : order=-1;
}
return order;
}
/*对两个操作数据进行运算。
*/
private double binaryOperation(double operand1,int opt,double operand2 ){
switch(opt){
case 0:
return operand1+operand2;
case 1:
return operand1-operand2;
case 2:
return operand1*operand2;
case 3:
return operand1/operand2;
}
return 0;
}
public static void main(String[] args){
Expression e=new Expression("((1+3)*3+(2+2)*5)/-4");
//Expression e=new Expression("1+5");
System.out.println(e.evaluate()); }
}