高精度加法
算法思路
- 用a、b两个字符串存储
- 将a、b逆序存储到int类型的数组中，A、B
- 新建数组C，用于保存结果；新建整数t=0，保存进位
- 将各个位上的数字进行相加，得出每一位的结果和进位值
代码模板
package main
import (
"fmt"
"strconv"
)
func Add(A, B []int) string {
// 让A的长度大于B
if len(A) < len(B) {
return Add(B, A)
}
C := make([]int, 0)
t := 0
for i := 0; i < len(A) || t > 0; i++ {
if i < len(A) {
t += A[i]
}
if i < len(B) {
t += B[i]
}
C = append(C, t%10)
t /= 10
}
var res = ""
// 转为结果字符串
for i := len(C) - 1; i >= 0; i-- {
res += strconv.Itoa(C[i])
}
return res
}
func main() {
var a, b string
fmt.Scanf("%s %s", &a, &b)
A, B := make([]int, len(a)), make([]int, len(b))
for i := len(a) - 1; i >= 0; i-- {1 2
A[len(a)-1-i] = int(a[i] - 48)
}
for i := len(b) - 1; i >= 0; i-- {
B[len(b)-1-i] = int(b[i] - 48)
}
fmt.Println(Add(A, B))
}
高精度减法
算法思路
- 和高精度加法差不多
- 新建整数t=0，用于保存借位
- 将各个位置上的数进行相减，得出每一位的结果和借位值
代码
package main
import (
"fmt"
)
// 判断是否有A>=B
func cmp(A, B []int) bool {
if len(A) != len(B) {
return len(A) > len(B)
}
for i := 0; i < len(A); i++ {
if A[i] != B[i] {
return A[i] > B[i]
}
}
return true
}
func Sub(A, B []int) {
C := make([]int, 0)
for i, t := 0, 0; i < len(A); i++ {
t = A[i] - t
if i < len(B) {
t -= B[i]
}
C = append(C, (t+10)%10)
if t >= 0 {
t = 0
} else {
t = 1
}
}
for len(C) > 1 && C[len(C)-1] == 0 {
C = C[:len(C)-1]
}
for i := len(C) - 1; i >= 0; i-- {
fmt.Print(C[i])
}
}
func main() {
var a, b string
fmt.Scanf("%s %s", &a, &b)
A, B := make([]int, len(a)), make([]int, len(b))
for i := len(a) - 1; i >= 0; i-- {
A[len(a)-1-i] = int(a[i] - 48)
}
for i := len(b) - 1; i >= 0; i-- {
B[len(b)-1-i] = int(b[i] - 48)
}
if cmp(A, B) {
Sub(A, B)
} else {
fmt.Print("-")
Sub(B, A)
}
}
需要注意的点
- 相减为负数的处理
- 需要对a，b的大小进行判断。若a>=b则为正整数，无需处理；若a<b则为负数，需要在输出时加前导"-"
- 前导0的处理
- 在得出逆序的结果数组C后，需要将后边多余的0去掉，但要注意结果为0的情况
代码技巧
相减后t的处理
- 当
t>=0时，结果为t；当t<0时，结果为10-t(因为借了10) - 改写为
t=(t+10)%10。用一个式子便可表示。
两个高精度数的大小比较
- 比较两个数的位数，位数多的数一定大
- 两个数从前往后比较，若比较的当前位不同，则结果为两者的大小结果
拓展
A B可以为正数或负数该怎么处理？
绝对值相减相加，判断字符串首字符的类型。
正正：直接计算正负：转化为高精度加法负负：高精度加法，加前导-
高精度减法
算法思路
- 和高精度加法差不多
- 新建整数t=0，用于保存借位
- 将各个位置上的数进行相减，得出每一位的结果和借位值
代码
package main
import (
"fmt"
)
// 判断是否有A>=B
func cmp(A, B []int) bool {
if len(A) != len(B) {
return len(A) > len(B)
}
for i := 0; i < len(A); i++ {
if A[i] != B[i] {
return A[i] > B[i]
}
}
return true
}
func Sub(A, B []int) {
C := make([]int, 0)
for i, t := 0, 0; i < len(A); i++ {
t = A[i] - t
if i < len(B) {
t -= B[i]
}
C = append(C, (t+10)%10)
if t >= 0 {
t = 0
} else {
t = 1
}
}
for len(C) > 1 && C[len(C)-1] == 0 {
C = C[:len(C)-1]
}
for i := len(C) - 1; i >= 0; i-- {
fmt.Print(C[i])
}
}
func main() {
var a, b string
fmt.Scanf("%s %s", &a, &b)
A, B := make([]int, len(a)), make([]int, len(b))
for i := len(a) - 1; i >= 0; i-- {
A[len(a)-1-i] = int(a[i] - 48)
}
for i := len(b) - 1; i >= 0; i-- {
B[len(b)-1-i] = int(b[i] - 48)
}
if cmp(A, B) {
Sub(A, B)
} else {
fmt.Print("-")
Sub(B, A)
}
}
需要注意的点
- 相减为负数的处理
- 需要对a，b的大小进行判断。若a>=b则为正整数，无需处理；若a<b则为负数，需要在输出时加前导"-"
- 前导0的处理
- 在得出逆序的结果数组C后，需要将后边多余的0去掉，但要注意结果为0的情况
代码技巧
相减后t的处理
- 当
t>=0时，结果为t；当t<0时，结果为10-t(因为借了10) - 改写为
t=(t+10)%10。用一个式子便可表示。
两个高精度数的大小比较
- 比较两个数的位数，位数多的数一定大
- 两个数从前往后比较，若比较的当前位不同，则结果为两者的大小结果
拓展
A B可以为正数或负数该怎么处理？
绝对值相减相加，判断字符串首字符的类型。
正正：直接计算正负：转化为高精度加法负负：高精度加法，加前导-
高精度除法
算法思路
- 创建整型变量r保存余数
- 遍历数组A，当前的被除数就是r*10+A[i]`
- 将商加入结果数组C，余数即被除数对除数b取余的结果
代码模板
package main
import (
"fmt"
)
func div(A []int, b int) ([]int, int) {
C := make([]int, 0)
r := 0
for i := len(A) - 1; i >= 0; i-- {
r = r*10 + A[i]
C = append(C, r/b)
r %= b
}
// 去前导0
for len(C) > 1 && C[0] == 0 {
C = C[1:]
}
return C, r
}
func main() {
var a string
var b int
fmt.Scanf("%s %d", &a, &b)
A := make([]int, len(a))
for i := len(a) - 1; i >= 0; i-- {
A[len(a)-1-i] = int(a[i] - 48)
}
C, r := div(A, b)
for i := 0; i < len(C); i++ {
fmt.Print(C[i])
}
fmt.Println()
fmt.Print(r)
}
高精度乘法
高精度×低精度
算法思路
- 与高精度加法类似
- 新建整型变量t，用于保存进位
- 让A上的每一位数字与b相乘
代码
package main
import (
"fmt"
)
func mul(A []int, b int) []int {
C := make([]int, 0)
t := 0
for i := 0; i < len(A) || t > 0; i++ {
if i < len(A) {
t += A[i] * b
}
C = append(C, t%10)
t /= 10
}
return C
}
func main() {
var a string
var b int
fmt.Scanf("%s %d", &a, &b)
A := make([]int, len(a))
for i := len(a) - 1; i >= 0; i-- {
A[len(a)-1-i] = int(a[i] - 48)
}
C := mul(A, b)
for i := len(C) - 1; i >= 0; i-- {
fmt.Print(C[i])
}
}
高精度×高精度
算法思路
- 新建整型数组C，大小为
len(A)+len(B),存储每一位相乘然后再相加的结果(C[i+j]+=A[i]*B[j]) - 遍历数组C，进行进位
- 去前导0
代码
package main
import (
"fmt"
)
func mul(A, B []int) []int {
C := make([]int, len(A)+len(B))
// 计算每一位的结果
for i := 0; i < len(A); i++ {
for j := 0; j < len(B); j++ {
C[i+j] += A[i] * B[i]
}
}
//进行进位
for i, t := 0, 0; i < len(C); i++ {
t += C[i]
C[i] = t % 10
t /= 10
}
// 去掉前导0
for len(C) > 1 && C[len(C)-1] == 0 {
C = C[:len(C)-1]
}
return C
}
func main() {
var a, b string
fmt.Scanf("%s %s", &a, &b)
A, B := make([]int, len(a)), make([]int, len(b))
for i := len(a) - 1; i >= 0; i-- {
A[len(a)-1-i] = int(a[i] - 48)
}
for i := len(b) - 1; i >= 0; i-- {
B[len(b)-1-i] = int(b[i] - 48)
}
C := mul(A, B)
for i := len(C) - 1; i >= 0; i-- {
fmt.Print(C[i])
}
}
