30/09/2018, 16:43
Không hiểu về cách xử lí bignum
#include "stdafx.h"
#include<stdio.h>
#include<iostream>
#include<fstream>
#include<string>
#define MAXDIGITS 100
#define PLUS 1
#define MINUS -1
using namespace std;
typedef struct
{
char digits[MAXDIGITS];
int signbit;
int lastdigit;
} bignum;
// khai bao
void main();
void print_bignum(bignum n);
int kiemtra(char s[]);
void scan_bignum(bignum &n);
void zero_justify(bignum n);
void add_bignum(bignum a, bignum b, bignum &c);
void subtract_bignum(bignum a, bignum b, bignum &c);
int compare_bignum(bignum a, bignum b);
// cai
void main()
{
bignum a, b, c;
cout << "nhap vao so lon a:";
scan_bignum(a);
cout << "nhap vao so lon b:";
scan_bignum(b);
add_bignum(a, b, c);
cout << "a+b=";
print_bignum(c);
subtract_bignum(a, b, c);
cout << "a-b=";
print_bignum(c);
cout << endl;
}
int max(int a, int b)
{
return (a>b) ? a : b;
}
void print_bignum(bignum n)
{
int i;
if (n.signbit == MINUS) cout << "-";
for (i = n.lastdigit; i >= 0; i--)
{
cout << int(n.digits[i]);
}
cout << "
";
}
int kiemtra(char s[])
{
//ktra ký tự dau
if (s[0] != '-' && !isdigit(s[0]))
return 0;
//ktra các ký t? ti?p theo
int len = strlen(s);
for (int i = 1; i<len; i++)
if (!isdigit(s[i])) return 0;
//không phát hi?n vi ph?m
return 1;
}
void scan_bignum(bignum &n)
{
//B1: Nhập chuỗi
char temp[256];
cin.getline(temp, 256);
//B2: Kiểm tra
if (!kiemtra(temp))
{ //không hợp lệ
//gán bignum = 0
n.signbit = PLUS;
n.lastdigit = 0;
n.digits[0] = 0;
}
else
{ //hợp lệ. B3: chuyển thành số bignum
//xét 2 tru?ng h?p
if (temp[0] != '-')
{ //s? duong
n.signbit = PLUS;
n.lastdigit = strlen(temp) - 1;
for (int i = 0; i <= n.lastdigit; i++)
n.digits[i] = temp[n.lastdigit - i] - 48;
}
else
{ //s? âm
n.signbit = MINUS;
n.lastdigit = strlen(temp) - 2;
for (int i = 0; i <= n.lastdigit; i++)
n.digits[i] = temp[n.lastdigit + 1 - i] - 48;
}
}
}
void zero_justify(bignum n)
{
while ((n.lastdigit > 0) && (n.digits[n.lastdigit] == 0))
n.lastdigit--;
if ((n.lastdigit == 0) && (n.digits[0] == 0))
n.signbit = PLUS; /* hack to avoid -0 */
}
void add_bignum(bignum a, bignum b, bignum &c)
{
int carry; /* carry digit */
int i; /* counter */
//initialize_bignum(c); //khoi gan chu so = 0;
if (a.signbit == b.signbit) c.signbit = a.signbit;
else
{
if (a.signbit == MINUS)
{
a.signbit = PLUS;
subtract_bignum(b, a, c);
a.signbit = MINUS;
}
else
{
b.signbit = PLUS;
subtract_bignum(a, b, c);
b.signbit = MINUS;
}
return;
}
c.lastdigit = max(a.lastdigit, b.lastdigit) + 1;
//dieu chinh a,b
for (i = a.lastdigit + 1; i <= c.lastdigit; i++)
a.digits[i] = 0;
for (i = b.lastdigit + 1; i <= c.lastdigit; i++)
b.digits[i] = 0;
//tinh
carry = 0;
for (i = 0; i <= (c.lastdigit); i++)
{
c.digits[i] = (char)
(carry + a.digits[i] + b.digits[i]) % 10;
carry = (carry + a.digits[i] + b.digits[i]) / 10;
}
zero_justify(c);
}
void subtract_bignum(bignum a, bignum b, bignum &c)
{
int borrow; /* anything borrowed? */
int v; /* placeholder digit */
int i; /* counter */
if ((a.signbit == MINUS) || (b.signbit == MINUS)) {
b.signbit = -1 * b.signbit;
add_bignum(a, b, c);
b.signbit = -1 * b.signbit;
return;
}
if (compare_bignum(a, b) == PLUS) {
subtract_bignum(b, a, c);
c.signbit = MINUS;
return;
}
c.signbit = PLUS;
c.lastdigit = max(a.lastdigit, b.lastdigit);
//dieu chinh a,b
for (i = a.lastdigit + 1; i <= c.lastdigit; i++)
a.digits[i] = 0;
for (i = b.lastdigit + 1; i <= c.lastdigit; i++)
b.digits[i] = 0;
borrow = 0;
//5.3. High-Precision Arithmetic 107
for (i = 0; i <= (c.lastdigit); i++) {
v = (a.digits[i] - borrow - b.digits[i]);
if (a.digits[i] > 0)
borrow = 0;
if (v < 0) {
v = v + 10;
borrow = 1;
}
c.digits[i] = (char)v % 10;
}
zero_justify(c);
}
int compare_bignum(bignum a, bignum b)
{
int i; /* counter */
if ((a.signbit == MINUS) && (b.signbit == PLUS)) return(PLUS);
if ((a.signbit == PLUS) && (b.signbit == MINUS)) return(MINUS);
if (b.lastdigit > a.lastdigit) return (PLUS * a.signbit);
if (a.lastdigit > b.lastdigit) return (MINUS * a.signbit);
for (i = a.lastdigit; i >= 0; i--) { // so sanh so chu so bang nhau
if (a.digits[i] > b.digits[i])
return(MINUS * a.signbit);
if (b.digits[i] > a.digits[i])
return(PLUS * a.signbit);
}
return(0);
}
Bài liên quan
Bạn nên code lại để hiểu code, nên xem ý tưởng thôi
ý tưởng của phép cộng và phép trừ là thêm các chữ số 0 vào đầu 2 số bignum để số chữ số bằng nhau, sau đó thì thực hiện như cấp 1 từng học.
VD: 123 và 234567 thì sẽ đổi thành 000123 và 234567, rồi cộng theo cột là ra
Ý tưởng của Bignum(cộng, trừ, nhân, chia, lũy thừa, khai căn, sin, cos,tan ,…v…v…) nói chung là dụ thằng user nhập số int hay float nhưng lại thực hiện gán vào biến string. Sau đó dùng phương pháp đặc biệt nào đó, cắt ghép, mổ xẻ rồi đưa ra ngoài 1 string rồi bảo nó là big number