缺了什么就恶补一下😷
由于数字类型长度有限,超大数字相乘会造成溢出。这估计就是该算法的背景由来吧?(猜的哈哈哈😂)
好吧,进入正题啦~
先举个简单的例子: 789 * 456
1. 第一步,把数字逐个放到数组里,组成
【7,8,9】 和 【4,5,6】
2. 第二步,从低位向高位逐位相乘(右往左⬅️)
9 * 6
9 * 5
9 * 4
8 * 6
8 * 5
3.第三步,从低位向高位进位(右往左⬅️)
规则:个位数原地保留,十位数以上的数字向左移动一位
4. 最后把第一位的0舍弃,然后把数字串起来,就完成啦!!!🎉🎉🎉🎉🎉
最后上个完整代码
let result:String = getsTheResultOfMultiplyingTwoLargeNumbers(numberA: "789",
numberB: "456")
print("大数相乘结果-->\(result)")
//MARK: - -------- 两个大数相乘 算法 ---------
private func getsTheResultOfMultiplyingTwoLargeNumbers(numberA:String = "0" ,
numberB:String = "0") -> String {
guard numberA != "0" && numberB != "0" else {
return "0"
}
if numberA == "1" {
return numberB
}
if numberB == "1" {
return numberA
}
let numCountA:Int = numberA.count
let numCountB:Int = numberB.count
var resultArray:[Int] = Array.init(repeating: 0,
count: numCountA + numCountB)
var number1Array:[Int] = Array.init(repeating: 0,
count: numCountA)
var number2Array:[Int] = Array.init(repeating: 0,
count: numCountB)
//1. 把A数的每个数字遍历出来放到数组
for (index,charObject) in numberA.enumerated() {
let numberString:String = String.init(charObject)
number1Array[index] = Int(numberString) ?? 0
}
//2. 把B数的每个数字遍历出来放到数组
for (index,charObject) in numberB.enumerated() {
let numberString:String = String.init(charObject)
number2Array[index] = Int(numberString) ?? 0
}
//3.从右到左开始逐个数字相乘
// 789
// 456
//
for valueA in 0...numCountA - 1 {
let locationA = numCountA - 1 - valueA
for valueB in 0...numCountB - 1 {
let locationB = numCountB - 1 - valueB
/// 结果数组下标
let resultIndex:Int = locationA + locationB + 1
///相乘结果
let numberResult:Int = number1Array[locationA] * number2Array[locationB]
resultArray[resultIndex] += numberResult
print("循环数组A的下标-->\(valueA),循环数组B的下标-->\(valueB),结果数组下标-->\(resultIndex),相乘结果-->\(numberResult)")
}
}
//4. 计算每个数字的进位
var index:Int = numCountA + numCountB - 1
while index > 0 {
resultArray[index - 1] += resultArray[index] / 10
resultArray[index] %= 10
index -= 1
}
//5. 如果首位为0,则删除不要
if resultArray.first == 0 {
resultArray.removeFirst()
}
//6. 拼接数组成为最终结果
var resultString:String = ""
for (_,number) in resultArray.enumerated() {
resultString += "\(number)"
}
return resultString
}