[자바]시 뮬 레이 션 실현 대 정수 류

14187 단어 Java
1.문제 해결:
    긴 정수 류 BigInt 를 실현 하고 임 의 정밀도 의 정수 와 연산 을 지원 합 니 다.
2.데이터 구조:
public class BigInt {
private int length;
         private boolean pn; //positiveor negative. + is true, - is false
         private String value;
}

         그 중에서 문자열 value 는 이 큰 정수 의 절대 값 이 고 length 는 이 절대 값 의 자릿수 를 저장 하 며 pn 은 이 큰 정수 의 기 호 를 기록 합 니 다.이렇게 하면 양수 문 제 를 해결 하 는 데 유리 하고 모든 큰 정 수 는 조작 할 때 value 를 직접 진행 할 수 있 으 며 마지막 으로 결 과 를 얻 은 기 호 를 통일 적 으로 고려 할 수 있다.
3.구체 적 인 방법:
1.        매개 변수 없 는 구조 함수 BigInt()
BigInt() {
		this.length = 1;
		this.pn = true;
		this.value = "0";
	}

2.        문자열 이 있 는 구조 함수 BigInt(String s)
a)        개인 적 인 방법 인 isLegal(s)을 통 해 매개 변 수 를 합 법성 으로 판단 한다.
b)        이 문자열 에 기호 가 있 는 지 판단 하고 기호 pn 을 설정 합 니 다.
c)        개인 적 인 방법 으로 findStartPos(s)를 통 해 문자열 의 진정한 의미 가 있 는 가장 높 은 위 치 를 찾 습 니 다.
d)        가장 높 은 자리 에 있 는 모든 문 자 를 value 에 저장 하고 length 에 이 value 의 길 이 를 기록 합 니 다.
e)        0 을 특별 처리 하 다.
BigInt(String s) {
		//assert isLegal(s);
		if (isLegal(s)) {
			if (s.charAt(0)=='+' || s.charAt(0)=='-') {
				this.pn = s.charAt(0)=='+' ? true:false;
			}
			else {
				this.length = s.length();
				this.pn = true;
			}
			int sp = findStartPos(s);
			this.value = s.substring(sp);
			this.length = s.length()-sp;
			if (this.value.charAt(0) == '0') {
				this.pn = true;
				this.length = 1;
				this.value = "0";
			}
		}
		else {
			System.out.println("This BigInt is not legal!");
		}
	}

3.        BigInt 문자열 변환 publicString toString()
데이터 구조 에서 기호 위치 와 데이터 위 치 를 분리 하기 때문에 출력 할 때 기호 위치 pn==false 를 고려 할 때 value 앞 에 마이너스 번 호 를 추가 하면 됩 니 다.
public String toString() {
		if (pn == false) {
			return "-" + value;
		}
		return value;
	}

4.        큰 정수 비교 가 같은 지 public boolean equals(BigInt x)
toString()과 유사 하 며 두 개의 큰 정수 기호 위치 와 데이터 위치 가 같 는 지 비교 하면 됩 니 다.주의해 야 할 것 은 데이터 비트 를 비교 할 때 equals()를 사용 하고 등호 로 실제 데이터 가 아 닌 인용 값 을 직접 비교 하 는 것 입 니 다.
public boolean equals(BigInt x) {
		if (this.pn==x.pn && this.length==x.length && this.value.equals(x.value)) {
			return true;
		}
		return false;
	}

5.        큰 정수 크기 비교 public int compare(BigInt x)
반환 1 보다 크 면 반환 0,반환-1 보다 작 습 니 다.
a)        기호 비트 pn 을 통 해 두 수의 크기 를 동시에 비교 하지 않 습 니 다.
b)        기호 가 서로 다른 동시에 길이 가 서로 다른 두 수의 크기 를 비교 하면 양수 의 길이 가 크 고 음수 의 길이 가 작다.
c)        기호 길이 가 모두 같 으 면 copare To 를 통 해 두 수의 value 를 비교 하고 정 수 는 copare To 의 결과 대응 점 1 과-1 을 되 돌려 주 며 음 수 는 copare To 결과 의 반대 수의-1 과 1 을 되 돌려 줍 니 다.
public int compare(BigInt x) {
		if (this.pn != x.pn) {
			return this.pn==true ? 1:-1;
		}
		if (this.length!=x.length) {
			if (this.pn) {
				return this.length>x.length ? 1:-1;
			}
			else {
				return this.length 0) {
			return -1;
		}
		if (tmp < 0) {
			return 1;
		}
		return tmp;
	}

6.        큰 정수 덧셈 public BigInt add(BigInt x)
덧셈 조작 에 있어 서 기호 위치 가 같은 상황 만 고려 하고 기호 위치 가 다른 상황 을 뺄셈 에 버린다.
a)        0 을 특수 처리 하고 다른 수 를 되 돌려 줍 니 다.new BigInt(this.toString()와 같은 새로운 큰 정 수 를 만 드 는 것 을 주의 하 십시오.
b)        두 개의 기호 위치 가 다 르 면 x 의 백업 xx 를 만 들 고 개인 적 인 방법 으로 changePN()을 사용 하여 xx 의 기호 위 치 를 바 꾸 고 this-xx 를 계산 하여 결 과 를 되 돌려 줍 니 다.
c)        두 문자열 bigger 와 smaller 를 만 들 고 데이터 비트 가 큰 데이터 비트 와 작은 데이터 비트 를 각각 기록 합 니 다.
d)        아 날로 그 덧셈 작업:bigger 와 smaller 로 가장 낮은 위치 에서 덧셈 작업 을 하고 개인 적 인 방법 인 charAdd()를 통 해 비트 별로 추가 한 결 과 는 문자열 ans 에 기록 합 니 다.그리고 carry Value 를 통 해 현재 위치 에 따라 결 과 를 추가 하 는 지 여 부 를 기록 합 니 다.만약 에 위치 가 있 으 면 다음 덧셈 작업 을 할 때 carry Value 를 위치 에 따라 추가 하 는 작업 에 넣 어야 합 니 다.그렇지 않 으 면 이 를 제거 해 야 합 니 다.
ans[i] =bigger[bigger.length-i]+smaller[smaller.length-i]+carryValue
e)        smaller 의 최고 위 치 를 다 추가 한 후에 bigger 가 더 많은 높 은 위 치 를 carry Value 와 계속 위치 별로 추가 해 야 합 니 다.
f)         가장 높 은 자리 에 진위 가 발생 하 는 지 판단 하고 발생 하면 가장 높 은 자리 1 을 보충 합 니 다.
g)        ans 를 반전 시 키 고 큰 정 수 를 구성 하 며 그 기호 위 치 를 this 의 기호 위치 로 합 니 다.
	public BigInt add(BigInt x) {
		if (x.value.equals("0")) {
			return new BigInt(this.toString());
		}
		if (this.value.equals("0")) {
			return new BigInt(x.toString());
		}
		if (this.pn != x.pn) {
			BigInt xx = new BigInt(x.toString());
			xx.changePN();
			return this.substract(xx);
		}
		String bigger, smaller;
		if ((this.compare(x)>=0&&this.pn)||(this.compare(x)<0&&!this.pn)) {
			bigger = new String(this.value);
			smaller = new String(x.value);
		}
		else {
			bigger = new String(x.value);
			smaller = new String(this.value);
		}
		String tmpAns = new String();
		int carryValue = 0;
		for (int i = 1; i <= smaller.length(); i++) {
			int tmpAdd = charAdd(bigger.charAt(bigger.length()-i), smaller.charAt(smaller.length()-i)) + carryValue;
			carryValue = tmpAdd>=10 ? 1:0;
			tmpAns += String.valueOf(tmpAdd-carryValue*10);
		}
		int pos = bigger.length()-smaller.length()-1;
		while(carryValue!=0 && pos>=0) {
			int tmpAdd = charAdd(bigger.charAt(pos), '1');
			carryValue = tmpAdd>=10 ? 1:0;
			tmpAns += String.valueOf(tmpAdd-carryValue*10);
			pos--;
		}
		String ans = new String();
		tmpAns = reverse(tmpAns);
		if (carryValue == 0) {
			ans = bigger.substring(0, Math.max(pos+1, 0))+tmpAns;
		}
		else if (pos < 0) {
			ans = "1"+tmpAns;
		}
		if (!this.pn) {
			ans = "-"+ans;
		}
		return new BigInt(ans);
	}

7.        큰 정수 감법 조작 public BigInt substract(BigInt x)
덧셈 과 같이 기호 위치 가 같은 상황 만 고려 하여 기호 위치 가 다른 상황 을 덧셈 에 던 집 니 다.다음은 시 뮬 레이 션 감법 조작 만 소개 한다.
tmpSub= charSub(bigger[bigger.length()-i], smaller[smaller.length()-i], carryValue); 
public BigInt substract(BigInt x) {
		if (x.value.equals("0")) {
			return new BigInt(this.toString());
		}
		else if (this.value.equals("0")) {
			BigInt ans = new BigInt(x.toString());
			ans.changePN();
			return ans;
		}
		if (this.pn != x.pn) {
			BigInt xx = new BigInt(x.toString());
			xx.changePN();
			return this.add(xx);
		}
		String bigger, smaller;
		boolean tag = this.compare(x)>=0 ? true:false;
		if ((this.compare(x)>=0&&this.pn)||(this.compare(x)<=0&&!this.pn)) {
			bigger = new String(this.value);
			smaller = new String(x.value);
		}
		else {
			bigger = new String(x.value);
			smaller = new String(this.value);
		}
		String tmpAns = new String();
		int carryValue = 0;
		for (int i = 1; i <= smaller.length(); i++) {
			int tmpAdd = charSub(bigger.charAt(bigger.length()-i), smaller.charAt(smaller.length()-i), carryValue);
			carryValue = tmpAdd<0 ? 1:0;
			if (tmpAdd == -100) {
				carryValue = 1;
				tmpAdd = 0;
			}
			tmpAns += String.valueOf(Math.abs(tmpAdd));
		}
		int pos = bigger.length()-smaller.length()-1;
		while(carryValue!=0 && pos>=0) {
			int tmpAdd = charSub(bigger.charAt(pos), '0', carryValue);
			carryValue = tmpAdd<0 ? 1:0;
			tmpAns += String.valueOf(Math.abs(tmpAdd));
			pos--;
		}
		String ansStr = new String();
		tmpAns = reverse(tmpAns);
		if (carryValue == 0) {
			ansStr = bigger.substring(0, Math.max(pos+1, 0))+tmpAns;
		}
		BigInt ans = new BigInt(ansStr);
		ans.pn = tag;
		return ans;		
	}

         그 중 개인 적 인 방법 charSub():
          
private int charSub(char x, char y, int c) {
		int ans = x + 10 - c - y;
		if (ans < 10) {
			if (ans == 0) {
				ans = 100;
			}
			return ans*(-1); // there is a negative zero problem
		}
		return ans-10;
	}

         매개 변수 0,9,1 과 같은 마이너스 0 문 제 를 해결 하기 위해 이 결 과 를-100 으로 설정 하여 특수 처 리 를 한다.
8.        큰 정수 곱셈 조작 public BigInt multiply(BigInt x)
분 치 된 사상 을 사용 하여 두 개의 수 를 각각 M1,M2 로 설정 하고 길 이 는 모두 l 이다.이 를 다음 과 같이 표시 할 수 있다.
M1=AB,A 는 전 l/2 길이 의 데이터 비트 이 고 B 는 후 l-l/2 길이 의 데이터 비트 이다.
M2=CD,C 는 앞 l/2 길이 의 데이터 비트 이 고 D 는 뒤 l-l/2 길이 의 데이터 비트 입 니 다.
그래서 M1*M2 는
M1*M2 = A*C*(10^((l-l/2)*2)) + B*D + ((A-B)*(D-C)+A*C+B*D) *(10^(l-l/2))
그러나 두 개의 데이터 비트 길이 가 모두 l 이라는 것 을 보장 할 수 없 기 때문에 데이터 비트 가 짧 은 앞 에 0 을 보충 하여 l 비트 를 보충 해 야 합 니 다.이러한 방법 을 채택 한 것 은 원래 의 곱셈 조작 이 분 해 된 후에 도 네 번 의 곱셈 이 되 고,상식 적 인 곱셈 조작 으로 분 해 된 후에 세 번 의 곱셈 조작 만 하면 시간 복잡 도 는 O(l^log(3)로 떨 어 지기 때문이다.
public BigInt multiply(BigInt x) {
		if (x.value.equals("0") || this.value.equals("0")) {
			return new BigInt();
		}
		boolean ansPN = !(this.pn ^ x.pn);
		if (x.length == 1 && this.length == 1) {
			int ians = Integer.parseInt(x.value)*Integer.parseInt(this.value);
			BigInt ans = new BigInt(String.valueOf(ians));
			ans.setPN(ansPN);
			return ans;
		}
		String a = this.value, b = x.value;
		/**********Unify Length**********/
		int len1 = Math.max(a.length(), b.length())-a.length();
		int len2 = Math.max(a.length(), b.length())-b.length();
		for (int i = 0; i < len1; i++) {
			a = "0" + a;
		}
		for (int i = 0; i < len2; i++) {
			b = "0" + b;
		}
		BigInt a1 = new BigInt(a.substring(0, a.length()/2));
		BigInt a2 = new BigInt(a.substring(a.length()/2));
		BigInt b1 = new BigInt(b.substring(0, b.length()/2));
		BigInt b2 = new BigInt(b.substring(b.length()/2));
		BigInt ans1 = a1.multiply(b1);//a1*b1
		BigInt ans2 = a2.multiply(b2);//a2*b2
		BigInt sub1 = a1.substract(a2);
		BigInt sub2 = b2.substract(b1);
		BigInt ans3 = sub1.multiply(sub2);//(a1-a2)(b2-b1)
		ans3 = ans3.add(ans1);
		ans3 = ans3.add(ans2);
		String tmp = ans1.value;
		for (int i = 0; i < (a.length()-a.length()/2)*2; i++) {
			tmp += "0";
		}
		ans1 = new BigInt(tmp);
		tmp = ans3.value;
		for (int i = 0; i < (a.length()-a.length()/2); i++) {
			tmp += "0";
		}
		if (!ans3.pn) {
			tmp = "-"+tmp;
		}
		ans3 = new BigInt(tmp);
		BigInt ans = ans1.add(ans3).add(ans2);
		ans.setPN(ansPN);
		return ans;
	}

9.        큰 정수 나 누 기 동작 Public BigInt divide(BigInt x)(나 누 기 0 이 아 님)
a)        나눗셈 의 데이터 비트 가 나 누 어 진 데이터 비트 보다 큰 지 판단 하고 크 면 0 을 되 돌려 줍 니 다.
b)        x 후 0 을 보충 하여 x 를 this 보다 크 지 않 은 최대 0 으로 바 꾸 고 cnct 개 0 을 기록 하여 조작 하기에 편리 하도록 x*addZero,addZero=100...00 에 해당 하 며 그 중에서 cnct 개 0 이 있 습 니 다.
c)        업 체 quotint 를 0 으로 초기 화 합 니 다.
d)        LOOP 1:cnt 회 순환 하기;
e)        LOOP 2:매번 this-x,this=this-x,quotint=quotient+addZero 를 계산 합 니 다.
f)         addZero 와 x 끝 을 0 으로 제거 하고 LOOP 1 로 돌리 기;
g)        상의 기호 위 치 를 this 와 x 의 기호 위치의 차이 또는 로 합 니 다.
public BigInt divide(BigInt x) {
		boolean ansPN = !(this.pn ^ x.pn);
		if (x.toString().equals("0")) {
			System.out.println("The divider cannot be 0!");
			BigInt ans = new BigInt("1");
			ans.setPN(ansPN);
			return ans;
		}
		if (unsignedCompare(x) < 0) {
			return new BigInt("0");
		}
		String a = this.value, b = x.value, addZero = new String("1");
		int cnt = a.length()-b.length();
		for (int i = 0; i < cnt; i++) {
			b += "0";
			addZero += "0";
		}
		BigInt divA = new BigInt(a), divB = new BigInt(b);
		BigInt quotien = new BigInt("0");
		while(cnt >= 0) {
			BigInt addBI = new BigInt(addZero);
			while(divA.compare(divB) >= 0) {
				quotien = quotien.add(addBI);
				divA = divA.substract(divB);
			}
			divB = new BigInt(divB.value.substring(0, Math.max(1,divB.value.length()-1)));
			addZero = addZero.substring(0, Math.max(1,cnt));
			cnt--;
		}
		quotien.setPN(ansPN);
		return quotien;
	}

10.    큰 정수 취 여 작업 public BigInt mod(BigInt x)
a)        this.divid(x)를 호출 하여 상 q 받 기;
b)        q.multiply(x)를 호출 하여 적 tmp 얻 기;
c)        this.substract(tmp)를 되 돌려 줍 니 다.
public BigInt mod(BigInt x) {
		BigInt tmp = this.divide(x);
		tmp = tmp.multiply(x);
		return this.substract(tmp);
	}

11.    단계 곱 하기 조작 public static BigInt factorial(BigInt x):
x.multiply(factorial(x.substract(ONE))를 재 귀적 으로 호출 하면 됩 니 다.
public BigInt factorial(BigInt x) {
		if (!x.equals(ZERO)) {
			return x.multiply(factorial(x.substract(ONE)));
		}
		return new BigInt("1");
	}

12.    지수 함수 public static BigInt expo(BigInt x):
TWO.multiply(expo(x.substract(ONE)))를 재 귀적 으로 호출 하면 됩 니 다.
public BigInt expo(BigInt x) {
		if (!x.equals(ZERO)) {
			return TWO.multiply(expo(x.substract(ONE)));
		}
		return new BigInt("1");
	}

4.사유 방법 과 상수:
상수:
public static final BigInt ZERO = new BigInt();
public static final BigInt ONE = new BigInt("1");
public static final BigInt TWO = new BigInt("2");

개인 정보 보호 방법:
private int unsignedCompare(BigInt x) {//     
		BigInt a = new BigInt(this.value);
		BigInt b = new BigInt(x.value);
		return a.compare(b);
	}
	private String reverse(String s) {//     
		StringBuffer sb = new StringBuffer(s);
		return sb.reverse().toString();
	}
	private int charAdd(char x, char y) {//   
		return x + y - '0' - '0';
	}
	private int charSub(char x, char y, int c) {//   
		int ans = x + 10 - c - y;
		if (ans < 10) {
			if (ans == 0) {
				ans = 100;
			}
			return ans*(-1); // there is a negative zero problem
		}
		return ans-10;
	}
	private void changePN() {//     
		this.pn = this.pn==true ? false:true;
		if (this.value.charAt(0) == '0') {
			this.pn = true;
		}
	}
	private void setPN(boolean targetPN) {//     
		this.pn = targetPN;
	}
	private int findStartPos(String s) {//           
		for (int i = 0; i < s.length(); i++) {
			if (Character.isDigit(s.charAt(i)) && s.charAt(i)!='0') {
				return i;
			}
		}
		return s.length()-1;//this is a zero!
	}
	private boolean isLegal(String s) {//              
		if (s == null || ((s.length()==1)&&(!Character.isDigit(s.charAt(0)))) || ((s.length()>1)&&(s.charAt(0)!='+')&&(s.charAt(0)!='-')&&(!Character.isDigit(s.charAt(0))))) {
			return false;
		}
		for (int i = 1; i < s.length(); i++) {
			if (!Character.isDigit(s.charAt(i))) {
				return false;
			}
		}
		return true;
	}
Poj 1013 Counterfeit Dollar/OpenJudge 1013(2692)위 폐 문제
자바 로 Python:Jython 디 딤 노트 실행

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage