大整數加法與乘法（高精度算法）
一、大整數加法
原理：
當資料的位置太長時，我們品是剋有運用的short、 int 、 long long 型變量都無法滿足要求，我們就需要用到大整數的加法運算思想了：
要點：
- 開一個數組，存儲需要計算的數字，注意，數組的首位存的是數字的長度，其他位将數字的每一位倒過來存放
- 定義一個總和的數組，和上面的數組一樣存
- 相加過程中，數字會出現進位的情況，進位有可能會導緻綜合的長度發生改變
例題
- 計算兩個數字的和
#include<iostream> #include<cstring> using namespace std; int num1[1005], num2[1005] , sum[1005]; char s1[1005], s2[1005]; int main() { cin >> s1 >> s2; num1[0] = strlen(s1);//兩個數組的首位存儲字元串的長度 num2[0] = strlen(s2); //數字的每一位到這存儲到num數組中 for (int i = 0, j = num1[0]; i < num1[0]; i++, j--) { num1[j] = s1[i] - '0'; } for (int i = 0, j = num2[0]; i < num2[0]; i++, j--) { num2[j] = s2[i] - '0'; } sum[0] = max(num1[0], num2[0]);//兩個數相加，最小長度是較大長度的數字的長度 for (int i = 1; i <= sum[0]; i++) { sum[i] = num1[i] + num2[i]; //對應的位相加 //進位操作 if(sum[i] > 9) { sum[i + 1] += sum[i] / 10; sum[i] %= 10; if ( i == sum[0]) {//進位可能會改變數字的長度 sum[0]++; } } } for (int i = sum[0]; i > 0; i--) { cout << sum[i]; } cout << endl; return 0; } - euler13(具體清搜尋網站“歐拉計劃”）
#include<iostream>
#include<cstring>
using namespace std;
int num1[1005], num2[1005], sum[1100], t = 50;
char s1[1005], s2[1005];
int main() {
while(t--) {
cin >> s1 >> s2;
num1[0] = strlen(s1);
num2[0] = strlen(s2);
for (int i = 0, j = num1[0]; i < num1[0]; i++, j--) {
num1[j] = s1[i] - '0';
}
for (int i = 0, j = num2[0]; i < num2[0]; i++, j--) {
num2[j] = s2[i] - '0';
}
int k = max(num1[0], num2[0]);
sum[0] = max(sum[0], k);
for (int i = 1; i <= sum[0]; i++) {
sum[i] += num1[i] + num2[i];
if (sum[i] > 9) {
sum[i + 1] += sum[i] / 10;
sum[i] %= 10;
if ( i == sum[0] ) sum[0]++;
}
}
}
for (int i = sum[0]; i > 0; i--) {
cout << sum[i];
}
cout << endl;
return 0;
}
3.euler25
分析：
首先我們先用兩個資料相加，比如 a, b, 将a加到b中，此時b變為了他們之和，再交換将b加到a中，就實作了斐波那契數列的相加，模拟一下：
一開始 ： a = 1, b = 1, b+=a ,b= 2 -----> a+= b, a = 3, b= 2 -----> b+= a, b = 5 , a =3-----…就這樣子循環下去就好了
#include<iostream>
using namespace std;
int func(int *n1, int *n2) {//n1是數組num[a], n2是數組num[b]
n2[0] = n1[0];
for (int i = 1; i <= n2[0]; i++) {
n2[i] += n1[i];
if (n2[i] > 9) {//進位
n2[i + 1] += n2[i] / 10;
n2[i] %= 10;
if (i == n2[0]) n2[0]++;
}
}
return n2[0] == 1000;//如果有1000位，傳回1
}
int main() {
int num[2][1005] = {{1, 1}, {1, 1}};//num[0][0]代表長度，num[0][1]代表第一個數值是1
int a = 0, b = 1;
for (int i = 3; 1; i++) {
if (func(num[a], num[b])) {
cout << i << endl;
break;
}
swap(a, b);//num[a] --> num[b] ,變為num[b] --->num[a]
}
return 0;
}
二、大整數乘法
原理：
見下圖：
要點：
- 數字儲存到數組中位置： 比如 num1[i] * num2[j]—》 那麼放在在ans[i + j -1]的位置，可以看上圖模拟出來
- ans數組中乘積結果的初始長度 ，定義為乘積的最小長度 i + j - 1
代碼
#include<iostream>
#include <cstring>
using namespace std;
char s1[1005], s2[1005];//要計算的字元串資料
int num1[1005], num2[1005], ans[2005]; //存兩個乘數， 還有存相乘結果的數組
int main() {
cin >> s1 >> s2;
num1[0] = strlen(s1);
num2[0] = strlen(s2);
//數字倒過來存
for (int i = 1, j = num1[0] - 1; i <= num1[0]; i++, j--) {
num1[i] = s1[j] - '0';
}
for (int i = 1, j = num2[0] - 1; i <= num2[0]; i++, j--) {
num2[i] = s2[j] - '0';
}
ans[0] = num1[0] + num2[0] - 1;//ans中數字的長度（相乘之後的）
for (int i = 1; i <= num1[0]; i++) {//相乘結果存到ans中，順序存下去
for (int j = 1; j <= num2[0]; j++) {
ans[i + j -1] += num1[i] * num2[j];
}
}
for (int i = 1; i <= ans[0]; i++) {//進位操作
if (ans[i] > 9) {
ans[i + 1] += ans[i] / 10;
ans[i] %= 10;
if (i == ans[0]) ans[0]++;
}
}
for (int i = ans[0]; i > 0; i--) {
cout << ans[i];
}
cout << endl;
return 0;
}
三、大整數減法
直接上代碼：
#include<iostream>
#include <cstring>
using namespace std;
char s1[1005], s2[10055];
int num1[1005], num2[1005], ans[1005];
int main() {
cin >> s1 >> s2;
num1[0] = strlen(s1);
num2[0] = strlen(s2);
for (int i = 1, j = num1[0] - 1; i <= num1[0]; i++, j--) {
num1[i] = s1[j] - '0';
}
for (int i = 1, j = num2[0] - 1; i <= num2[0]; i++, j--) {
num2[i] = s2[j] - '0';
}
ans[0] = max(num1[0], num2[0]);
for (int i = 1; i <= ans[0]; i++) {
if (num1[i] < num2[i]) {//直接減，不夠減，借1，即+10
num1[i] += 10;
ans[i] = num1[i] - num2[i];
num1[i + 1]--;//借了一位給上面，是以值減1
} else {
ans[i] = num1[i] - num2[i];
}
}
//下面步驟去前導0，因為計算結束後，可能會出現前導0的情況
int m = ans[0];
if (ans[m] == 0) ans[0]--;//去掉最高位的前導0
for (int i = ans[0]; i > 0; i--) {
cout << ans[i];
}
cout << endl;
return 0;
}
寫于2021-07-08