大数演算の加減乗除
6790 ワード
だいすうえんざん
1.なぜ大数演算が必要なのか
コンピュータが格納できる様々なタイプの数の大きさが限られていることはよく知られています.例えばint型は32ビットの場合、-2^31~2^31-1の範囲ですが、計算する数が非常に大きい場合は、どうすればいいのでしょうか.それは大数演算に応用する必要がある.
2.大数演算はどのように実現するか
大数演算は本質的に人々が筆算を行う際の操作を模倣し,人々の筆算時の操作をコードで実現し,大数運転を実現した結果である.
3.大数加算
c++コードは以下の通りです.
4.大数減算
C++コードは以下の通りです.
5.大数乗算
C++コードは以下の通りです.
6.大数除算
C++コードは以下の通りです.
転載先:https://www.cnblogs.com/FZfangzheng/p/7700699.html
1.なぜ大数演算が必要なのか
コンピュータが格納できる様々なタイプの数の大きさが限られていることはよく知られています.例えばint型は32ビットの場合、-2^31~2^31-1の範囲ですが、計算する数が非常に大きい場合は、どうすればいいのでしょうか.それは大数演算に応用する必要がある.
2.大数演算はどのように実現するか
大数演算は本質的に人々が筆算を行う際の操作を模倣し,人々の筆算時の操作をコードで実現し,大数運転を実現した結果である.
3.大数加算
c++コードは以下の通りです.
#include
#include
using namespace std;
const int Max =10001;
int main(){
char a[Max],b[Max];//
int aa[Max],bb[Max];//
int sum[Max];//
int lena,lenb;
scanf("%s%s",a,b);
lena = strlen(a);//
lenb = strlen(b);
//
for(int i= 0 ; i < lena; i ++){
aa[i] = a[i] - 48;
}
for(int i= 0 ; i < lenb; i ++){
bb[i] = b[i] - 48;
}
int num = 0;
//
while(lena > 0 && lenb > 0){
lena -- ;
lenb -- ;
sum[num ++ ] = aa[lena] + bb[lenb];
}
// sum
while(lena > 0){
lena --;
sum[num ++] = aa[lena] ;
}
while(lenb > 0){
lenb -- ;
sum[num ++ ] = bb[lenb];
}
// ,sum[i]>10
for(int i = 0 ; i < num ; i ++ ){
if(sum[i] >= 10){
sum[i+1] += 1;
sum[i] -= 10;
}
}
//
if(sum[num] != 0){
num ++ ;
}
for(int i = num -1 ; i >= 0 ; i -- ){
printf("%d",sum[i]);
}
printf("
");
return 0;
}
4.大数減算
C++コードは以下の通りです.
#include
#include
using namespace std;
const int Max = 10001;
char a[Max], b[Max];
int aa[Max], bb[Max];
int sum[Max];
int lena, lenb;
int flag = 0;
// aa>bb true
bool cmp() {
//
bool f = false;
if (lena > lenb) {
return true;
}
else if (lena == lenb){
for (int i = 0; i < lena; i++) {
if (aa[i] > bb[i])
f = true;
if (aa[i] < bb[i] && f != true)
return false;
}
return true;
}
return false;
}
int main() {
scanf("%s%s", a, b);
lena = strlen(a);
lenb = strlen(b);
for (int i = 0; i < lena; i++) {
aa[i] = a[i] - 48;
}
for (int i = 0; i < lenb; i++) {
bb[i] = b[i] - 48;
}
int num = 0;
//
if (cmp()) {
while (lena > 0 && lenb > 0) {
lena--;
lenb--;
sum[num++] = aa[lena] - bb[lenb];
}
while (lena > 0) {
lena--;
sum[num++] = aa[lena];
}
}
else {
flag = 1;
while (lena > 0 && lenb > 0) {
lena--;
lenb--;
sum[num++] = bb[lenb] - aa[lena];
}
while (lenb > 0) {
lenb--;
sum[num++] = bb[lenb];
}
}
// ,
for (int i = 0; i < num; i++) {
if (sum[i] < 0) {
sum[i + 1] -= 1;
sum[i] += 10;
}
}
//
if (flag) {
for (int i = num - 1; i >= 0; i--) {
if (sum[i] != 0) {
sum[i] = -sum[i];
break;
}
}
}
bool zero = false;
for (int i = num - 1; i >= 0; i--) {
if (sum[i] != 0)
zero = true;
if(zero == true)
printf("%d", sum[i]);
}
if (zero == false) {
printf("0");
}
printf("
");
return 0;
}
5.大数乗算
C++コードは以下の通りです.
#include
#include
using namespace std;
const int Max = 10001;
int main(){
char a[Max],b[Max];
int aa[Max],bb[Max];
int sum[Max*2];
scanf("%s%s",a,b);
int lena = strlen(a);
int lenb = strlen(b);
for (int i = 0 ; i < lena; i ++ ){
aa[i] = a[i] - 48;
}
for (int i = 0 ; i < lenb; i ++ ){
bb[i] = b[i] - 48;
}
memset(sum,0,sizeof(sum));
int num;
for(int j = lenb - 1 ; j >= 0 ; j --){
// , , ,
num = lenb - 1 - j;
for(int i = lena - 1 ; i >= 0 ; i -- ){
sum[num ++ ] += bb[j] * aa[i];
}
}
for (int i = 0 ; i < num ; i ++ ){
// 10, , 10
if(sum[num - 1] >= 10){
num ++ ;
}
sum[i + 1] += sum[i] /10 ;
sum[i] = sum[i] % 10;
}
for (int i = num- 1 ; i >= 0 ; i-- ){
printf("%d",sum[i]);
}
printf("
");
return 0;
}
6.大数除算
C++コードは以下の通りです.
#include
#include
using namespace std;
const int Max = 10001;
int Sub(int * aa , int * bb , int lena , int lenb){
// , -1
if (lena < lenb){
return -1;
}
else if(lena == lenb){
for(int i = lena -1 ; i >=0 ; i--){
if (aa[i] > bb[i]) break;
else if(aa[i] < bb[i]) return -1;
}
}
for(int i = 0; i < lena ; i ++){
aa[i] -= bb[i];
if(aa[i] < 0){
aa[i+1] -= 1;
aa[i] += 10;
}
}
for (int i = lena -1 ; i >= 0 ; i--){
if (aa[i]) return (i+1);
}
return 0;
}
int main(){
char a[Max],b[Max];
int aa[Max],bb[Max];
int sum[Max];
// , ( )
int maxlen;
scanf("%s%s",a,b);
int lena = strlen(a);
int lenb = strlen(b);
memset(aa,0,sizeof(aa));
memset(bb,0,sizeof(bb));
memset(sum,0,sizeof(sum));
//
for(int i = lena - 1 , j = 0 ; i >= 0 ; i -- ,j ++){
aa[j] = a[i] - 48 ;
}
for(int i = lenb - 1 , j = 0 ; i >= 0 ; i -- ,j ++){
bb[j] = b[i] - 48 ;
}
// , 0
if(lena < lenb){
printf("0
");
return 0;
}
maxlen = lena;
int n = lena - lenb;
// bb aa
for(int i = lena - 1 ; i >= 0 ; i --){
if(i >= n){
bb[i] = bb[i-n];
}
else{
bb[i] = 0;
}
}
lenb = lena;
int t;
for (int i = 0 ; i <= n ; i ++ ){
//
while((t = Sub(aa,bb+i,lena,lenb-i)) >= 0){
lena = t;
sum[n - i] ++;
}
}
int i;
for( i = maxlen -1 ;i >= 0 ;i--){
if(sum[i]) break;
}
if(i >= 0){
for(;i>=0;i--){
printf("%d",sum[i]);
}
}
else{
printf("0");
}
printf("
");
return 0;
}
転載先:https://www.cnblogs.com/FZfangzheng/p/7700699.html