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);
}
Minh Hoàng viết 18:46 ngày 30/09/2018

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

GodOfGod viết 18:49 ngày 30/09/2018

Ý 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

Bài liên quan
0