큰 정수 (높 은 정밀도 정수) 개념, 생 성, 입력, 표시 와 네 가지 연산 (높 은 정밀도 의 가감 곱 하기) - 전체 코드 첨부
120620 단어 알고리즘
1.1 개념
큰 정수: 높 은 정밀도 의 정수, 그 의 미 는 기본 데이터 유형 이 그 정밀도 의 정 수 를 저장 할 수 없다 는 것 이다.
정수 의 높 은 위 치 는 배열 의 높 은 위치 에 저장 되 고 정수 의 낮은 위 치 는 배열 의 낮은 위치 에 저장 된다.반대로 연산 할 때 정수 의 낮은 위치 에서 높 은 위치 까지 매 거 를 하고 순위 저장 은 이런 사고 와 일치 하기 때문이다.
예 를 들 어 235813 은 배열 에 저 장 됩 니 다. 즉, d [0] = 3, d [1] = 1, d [2] = 8, d [3] = 5, d [4] = 3, d [5] = 2 가 있 습 니 다.
메모: 정 수 를 문자열% s 로 읽 을 때 실제 역 위치 로 저 장 됩 니 다. 즉, str [0] = '2', str [3] = '3', str [5] = '3' 입 니 다. 따라서 읽 은 후에 d [] 배열 로 저장 할 때 반전 해 야 합 니 다.
큰 정수 의 길 이 를 쉽게 얻 기 위해 서 는 int 류 변수 len 을 정의 하여 길 이 를 기록 하고 d 수 와 구조 체 로 조합 합 니 다.
1.2 기억 구조
struct bign{
int d[1000];
int len;
bign(){
memset(d,0, sizeof(d));
len = 0;
}
};
구조 체 를 초기 화 하 는 것 은 코드 를 입력 할 때 초기 화 문 제 를 잊 어 버 리 는 것 을 줄 이기 위해 서다.
struct bign
{
int d[1000];
int len;
bign(){// （ ， ）
memset(d, 0, sizeof(d));
len = 0;
}
};
1.3 읽 기
큰 정 수 를 입력 할 때 보통 문자열 로 읽 은 다음 에 문자열 을 bign 구조 체 에 저장 합 니 다.
bign change(char str[]){// bign
bign a;
a.len = strlen(str);//bign
for (int i = 0; i < a.len; ++i)
{
a.d[i] = str[a.len - i - 1] - '0';//
}
return a;
}
1.4 크기 비교
두 개의 bign 변수의 크기 를 비교 합 니 다. 먼저 두 개의 len 크기 를 판단 하고 기다 리 고 싶 지 않 으 면 긴 것 을 큰 것 으로 하고 같 으 면 높 은 위치 에서 낮은 위치 로 비교 합 니 다. 한 사람 이 같 지 않 을 때 까지 두 수의 크기 를 판단 할 수 있 습 니 다.
int campare(bign a, bign b){
if(a.len > b.len){//a
return 1;
}else if(a.len < b.len){//a
return -1;
}else{//
for (int i = a.len - 1; i >= 0; --i)
{
if(a.d[i] > b.d[i]){// a ， a
return 1;
}else if(a.d[i] < b.d[i]){// a ， a
return -1;
}
}
return 0;
}
}
2 대 정수 의 사 칙 연산
2.1 높 은 정밀도 의 덧셈
2.1.1 사상
정수 덧셈 에 따 르 면 그 중 한 명 을 덧셈 하 는 절차: 이 자리 의 배열 과 진 위 를 더 해 얻 은 결 과 를 이 자리 결과 로 하고 10 자리 수 를 새로운 진위 로 한다.
주의: 이러한 쓰기 조건: 두 대상 이 모두 비 마이너스 입 니 다. 만약 에 한 측 이 있 을 때 마이너스 가 있 으 면 배열 로 전환 할 때 기 호 를 제거 한 다음 에 높 은 정밀도 의 감법 을 사용 할 수 있 습 니 다.만약 둘 다 마이너스 라면 모두 음 호 를 제거 한 후 고정 밀 덧셈 을 사용 하고 마지막 에 음 수 를 다시 첨가 하면 된다.
2.1.1 모드 코드
bign add(bign a, bign b){
bign c;
int carry = 0;//
for (int i = 0; i < a.len || i < b.len; ++i)//
{
int temp = a.d[i] + b.d[i] + carry;//
carry = temp / 10;//
c.d[c.len++] = temp % 10;//
}
if(carry != 0){// 0，
c.d[c.len++] = carry;
}
return c;
}
2.1.2 덧셈 예시
#include 2.2 높 은 정밀도 의 감법
2.2.1 사상
어떤 단계 에 대해 서 는 감 위 와 감 위 를 비교 하고 감 위 를 하지 않 으 면 감 위 된 높 은 위 치 를 1 로 줄 이 고 감 위 된 위 치 를 10 으로 더 해 감법 한다.만약 충분히 줄 일 수 있다 면 바로 줄 여 라.마지막 단 계 는 감법 후 높 은 자리 에 0 이 남 을 수 있 으 니 무시 해 야 하지만 결과 가 적어도 한 명 은 있어 야 한다.
2.2.2 모드 코드
bign sub(bign a, bign b){
bign c;
for (int i = 0; i < a.len || i < b.len; ++i)//
{
if(a.d[i] < b.d[i]){//
a.d[i + 1]--;//
a.d[i]+=10;// 10
}
c.d[c.len++]= a.d[i] - b.d[i];//
}
while(c.len - 1 >= 1 && c.d[c.len - 1] == 0){
c.len--;// 0，
}
return c;
}
2.3 높 은 정밀도 와 낮은 정밀도 의 곱셈
2.3.1 사상
낮은 정밀 도 는 기본 데이터 형식 으로 저장 할 수 있 는 데이터, 예 를 들 어 int 형 이다.
147 로× 35 147\times35 147×35 예 를 들 어 여기 147 은 고정 밀 bign 유형 으로 보고 35 는 int 유형 으로 본다.그리고 다음 과정 에서 35 를 하나의 전체 로 본다.
147 × 35 2 4 5 140 35 5 1 4 5 \quad147\\ \frac{\times \quad35}{2\,4\,5}\\ 140\quad\\ \frac{35\quad\;\;}{5\,1\,4\,5} 147245×35140514535
단계:
2.3.2 모드 코드
bign multi(bign a, int b){
bign c;
int carry = 0;//
for (int i = 0; i < a.len; ++i)
{
int temp = a.d[i]* b + carry;
c.d[c.len++] = temp % 10;//
carry = temp /10;//
}
while(carry != 0){// ，
c.d[c.len++] = carry % 10;
carry /= 10;
}
return c;
}
2.4 높 은 정밀도 와 낮은 정밀도 의 나눗셈
2.4.1 사상
나눗셈 의 계산 방법 은 초등학교 의 것 과 같다.1234 / 7 을 예 로 들 면0176 \ \ \ \ \ \ \ \ \ \ \ ^ 2} \ \ sqrt {1234} \ \ \ \ \ \ \ \ \ frac {7} {\ \ quad \ \; 53 \ \ quad} \ \ \ \ \ \ \ frac {\ \; 49} {\ \ \ \; \ quad \ \ \ quad 44 \ \ quad}
그 중의 한 단 계 를 요약 한다. 지난 단계 의 나머지 를 10 에 곱 하고 이 단계 의 위 치 를 더 하면 이 단계 의 임시 피 제 수 를 얻 고 나 누 기 와 비교 한다. 만약 에 나 누 지 못 하면 이 자리 의 상 은 0 이다.만약 나 눌 수 있다 면 상 은 대응 하 는 상 이 고 나머지 는 대응 하 는 나머지 이다.마지막 단 계 는 감법 후 높 은 자리 에 0 이 남 을 수 있 으 니 무시 해 야 하지만 결과 가 적어도 한 명 은 있어 야 한다.
2.3.2 모드 코드
bign divide(bign a, int b, int &r){//r
bign c;
c.len = a.len;// ，
for (int i = a.len -1; i >= 0; --i)
{
r = r * 10 + a.d[i];//
if(r < b){//
c.d[i] = 0;
}else{//
c.d[i] = r/b; //
r = r %b;//
}
}
while(c.len - 1 >= 1 && c.d[c.len - 1] == 0){
c.len--;// 0，
}
return c;
}
2.3.3 높 은 정밀도 의 나 누 기 모델
높 은 정밀도 의 나눗셈 (a 는 b 보다 작고 소수 가 있 음):
int cmp(string a, string b){
unsigned long i1 = a.find_first_not_of('0');
unsigned long i2 = b.find_first_not_of('0');
if(i1 == string::npos) a = '0';
else a.substr(i1);
if(i2 == string::npos) b = '0';
else b.substr(i2);
if(a.length() > b.length()) return 1;
else if(a.length() < b.length()) return -1;
else{ //
if(a < b) return -1;
if(a > b) return 1;
else return 0;
}
}
// a b
string subtract(string a, string b){
// ，a b， ， ab
//
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
//
for (int i = 0; i < b.length(); ++i)
{
if(a[i] >= b[i]){
a[i] = a[i] - b[i] + '0';
}else{//
int k = 1;
while(a[i + k] == '0') {// i+k 0
a[i + k] = '9';
k++;
}
a[i + k] = a[i + k] - '1' + '0';
a[i] = (a[i] - '0' + 10) - (b[i] - '0') + '0';
}
}
reverse(a.begin(), a.end());
if(a.find_first_not_of('0') == string::npos) return "0";
return a.substr(a.find_first_not_of('0'));
}
//
string divide(string a, string b){
// a < b
string ans = "0.";
//
for (int i = 0; i < 101; ++i)
{
a.append("0");
int t = 0;
while(cmp(a,b) >= 0){ //a > b
a = subtract(a, b); //
t++;//
}
string t_str;
//i2s(t ,t_str); //is2（） windows
stringstream stream;
stream << t;
stream >> t_str;
ans.append(t_str);
}
return ans;
}
2.3.4 높 은 정밀도 와 높 은 정밀도 의 곱셈
#include 2.4.4 높 은 정밀도 와 높 은 정밀도 의 나눗셈 예제 (나눗셈 보다 작 음)
#include 2.4.5 적당 한 자릿수 를 유지 하 는 저 정밀도 나눗셈
#include
");
}
//
// for(;~scanf("%d%d%d",&a,&b,&n);printf("
"))
// for(printf("%d.",a/b);n>0;a=(a-a/b*b)*10,printf("%d",a/b),--n);
return 0;
}
3. 전체 예제 코드
#include 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
