Cộng trừ nhân chia 2 số nguyên lớn C++
Hướng dẫn và code mẫu cộng trừ 2 số lớn trong C/C++. Show Trong các ngôn ngữ lập trình, khả năng lưu trữ của kiểu số thường có 1 giới hạn. Ví dụ kiểu dữ liệu Có những bài toán thực tế cần thao tác với những số vượt quá giới hạn này. Do đó cần phải có những phương pháp để giải quyết như:
Phép cộng hai số lớnLựa chọn kiểu dữ liệuVới một số nguyên lớn có 20 độ dài 20 ký số, một biến thông thường không thể hiện được toàn bộ số lớn này. Vì vậy chọn cách dùng nhiều biến để biểu diễn từng chữ số, như vậy có thể sử dụng một mảng các ký số để biểu diễn cho một số lớn. Một chữ số có giá trị từ 0 – 9 nên để tối ưu và đơn giản cho thao tác nhập mảng, có thể sử dụng mảng kiểu Hàm cộng hai số lớn có dạng: char* addBigNumber(char* number1, char* number2); Với hai chuỗi Hiện thực phép toánCó 2 trường hợp sau khi cộng hai số
Để tổng quát hóa hai trường hợp trên, cần so sánh chiều dài hai số Để đơn giản cho thao tác với chuỗi, sử dụng hàm if (strlen(number1) < strlen(number2)) { swapPointer(&number1, &number2); } Hàm void swapPointer(char** a, char** b) { char* temp = *a; *a = *b; *b = temp; } Khai báo một số biến cần thiết trong quá trình tính toán như sau:
size_t number1Len = strlen(number1), number2Len = strlen(number2); char* result = new char[number1len + 2]; bool remember = false; Có hai công đoạn khi thực hiện cộng 2 số:
Như vậy cần hai vòng lặp để làm những việc này. Bước 1Số lần lặp của công đoạn này sẽ là for (int i = 0; i < number2Len; i++) { //... } Cần tính tổng các chữ số từ phải qua trái, lấy giá trị các chữ số này
bằng cách sử dụng Mỗi giá trị hiện tại đang được lưu trong mảng với kiểu Dùng một biến tạm để lưu tổng của 2 giá trị này: int temp = number2[number2Len - i - 1] - '0' + number1[number1Len - i - 1] - '0'; Ví dụ: khi cộng Theo logic đó, tiếp xét giá trị biến if (remember) temp++; remember = temp > 9; temp = temp % 10; Tổng các chữ số của *(result + number1Len - i) = temp + '0'; Vậy ta có code hoàn chỉnh cho vòng lặp vừa rồi như sau: for (int i = 0; i < number2Len; i++) { int temp = *(b + number2Len - i - 1) - '0' + *(a + number1Len - i - 1) - '0'; if (remember) temp++; remember = temp > 9; temp = temp % 10; result[number1Len - i] = temp + '0'; } Với vòng lặp này, có thể cộng hai số lớn có chiều dài bằng nhau. Bước 2Tương tự các bước của công đoạn thứ nhất, số lần lặp của công đoạn này là: Giai đoạn này lấy giá trị các ký số của int temp = number1[number1Len - number2Len - i – 1] - '0'; Tương tự giá trị
result[number1Len - number2Len – i] = temp + '0'; Code hoàn chỉnh: for (int i = 0; i < number1Len - number2Len; i++) { int temp = *(number1 + number1Len - number2Len - i - 1) - '0'; if (remember) temp++; remember = temp > 9; temp = temp % 10; result[number1Len - number2Len - i] = temp + '0'; } Để đánh dấu kết thúc chuỗi result[number1Len + 1] = '\0'; Ví dụ if (remember) { result[0] = '1'; } else { for (int i = 0; i <= number1Len; i++) result[i] = result[i + 1]; } Cuối cùng, trả về Kiểm thử với hàm
int main() { char* a = "12345678987654321", *b = "98765432123456789"; char* c = addBigNumber(a, b); printf("%s", c); delete[] c; } Kết quả: Code hoàn chỉnh cộng 2 số lớnvoid swapPointer(char** a, char** b) { char* temp = *a; *a = *b; *b = temp; } char* addBigNumber(char* number1, char* number2) { if (strlen(number1) < strlen(number1)) { swapPointer(&number1, &number2); } size_t number1Len = strlen(number1), number2Len = strlen(number2); char* result = new char[number1Len + 2]; memset(result, '0', number1Len); bool remember = false; for (int i = 0; i < number2Len; i++) { int temp = number2[number2Len - i - 1] - '0' + number1[number1Len - i - 1] - '0'; if (remember) temp++; remember = temp > 9; temp = temp % 10; result[number1Len - i] = temp + '0'; } for (int i = 0; i < number1Len - number2Len; i++) { int temp = number1[number1Len - number2Len - i - 1] - '0'; if (remember) temp++; Phép trừ hai số lớnHàm trừ hai số lớn có dạng: char* subBigNumber(char* number1, char* number2); Với hai chuỗi Hiện thực phép toánKhi trừ hai số Để cho thuận tiện kiểm tra bool sign = false, remember = false; if (strlen(number1) < strlen(number2)) { sign = true; swapPointer(&number1, &number2); } else if (strlen(number1) == strlen(number2)) { for (int i = strlen(number1) - 1; i >= 0; i--) { if (*(number1 + i) < *(number2 + i)) { swapPointer(&number1, &number2); sign = true; } } } Đoạn code trên kiểm tra độ dài 2 số, nếu bằng nhau sẽ tiếp tục so sánh từng chữ số từ phải qua trái để tìm ra số lớn hơn, sau đó đảo vị trí các pointer (nếu cần). Khai báo và gán giá trị một số biến cần thiết trong quá trình tính toán như sau: size_t number1Len = strlen(number1), number2Len = strlen(number2); char* result = new char[number1Len + 2]; memset(result, '0', number1Len + 2);
Có hai công đoạn khi thực hiện trừ hai số:
Như vậy cần hai vòng lặp để làm việc này. Bước 1Số lần lặp của công đoạn này là for (int i = 0; i < number2Len; i++) { //... } Cần tính hiệu các ký số từ phải qua trái, vì phép trừ nên chỉ cần số chênh lệch giữa 2 số: int temp = number1[number1Len - i - 1] - number2[number2Len – i - 1]; Theo như logic của phép trừ, khi một chữ số của if (remember == true) temp--; if (temp < 0) { temp += 10; remember = true; } else remember = false; Gán kết quả vừa
tính vào result[number1Len – i] = temp + '0'; Code hoàn chỉnh cho vòng lặp vừa rồi như sau: for (int i = 0; i < number2Len; i++) { int temp = number1[number1Len – i - 1] - number2[number2Len – i - 1]; if (remember == true) temp--; if (temp < 0) { temp += 10; remember = true; } else remember = false; result[number1Len - i] = temp + '0'; } Bước 2Số lần lặp của công đoạn này là: Giai đoạn này chỉ cần lấy giá trị các ký số của int temp = number1[number1Len - number2Len - i] - '0'; tương tự ta có giá trị result như sau: result[number1Len - number2Len – i + 1] = temp + '0'; vậy ta có code hoàn chỉnh: for (int i = 0; i < number1Len - number2Len; i++) { int temp = *(a + number1Len - number2Len – i - 1) - '0'; if (remember == true) temp--; if (temp < 0) { temp += 10; remember = true; } else remember = false; result[number1Len - number2Len - i] = temp + '0'; } Ví dụ: while (result[0] == '0') { if (result[1] != '0' && sign == true) { result[0] = '-'; result[number1Len + 1] = '\0'; break; } for (int i = 0; i < number1Len; i++) { result[i] = result[i + 1]; } result[number1Len] = '\0'; } Cuối cùng, ta trả về Test thử với hàm main: int main() { char* a = "12345678987654321", *b = "98765432123456789"; char* c = subBigNumber(a, b); printf("%s", c); delete[] c; } Ta được output: -6419753135802468 là chính xác. Code hoàn chỉnh trừ 2 số lớnvoid swapPointer(char** a, char** b) { char* temp = *a; *a = *b; *b = temp; } char* subBigNumber(char* number1, char* number2) { bool sign = false, remember = false; if (strlen(number1) < strlen(number2)) { sign = true; swapPointer(&number1, &number2); } else if (strlen(number1) == strlen(number2)) { for (int i = strlen(number1) - 1; i >= 0; i--) { if (number1[i] < number2[i]) { swapPointer(&number1, &number2); sign = true; } } } size_t number1Len = strlen(number1); size_t number2Len = strlen(number2); char* result = new char [number1Len + 2]; memset(result, '0', number1Len + 2); for (int i = 0; i < number2Len; i++) { int temp = number1[number1Len - i - 1] - number2[number2Len - i - 1]; if (remember) temp--; if (temp < 0) { temp += 10; remember = true; } else remember = false; result[number1Len - i] = temp + '0'; } for (int i = 0; i < number1Len - number2Len; i++) { int temp = number1[number1Len - number2Len - i - 1] - '0'; if (remember == true) temp--; if (temp < 0) { temp += 10; remember = true; } else remember = false; result[number1Len - number2Len - i] = temp + '0'; } while (result[0] == '0') { if (result[1] != '0' && sign == true) { result[0] = '-'; result[number1Len + 1] = '\0'; break; } for (int i = 0; i < number1Len; i++) { result[i] = result[i + 1]; } result[number1Len] = '\0'; } return result; } |