/

超长阶乘的计算

extra-long-factorials

打印 n! 的结果(1 <= n <= 100)。注意:当 n > 20 时 64 位的 Int 将无法直接存储结果。

思路

  • 将大数字用 数组 形式表示。比如 987 使用 [9,8,7] 代替。
  • 每一位乘以 n,再进行进位操作,得到新数组。
let nums = [9, 8, 7]
let tmpNums = nums.map { $0 * 2 } // [18, 16, 14]

// 遍历 tmpNums 每一个数字,进行进制操作

[18, 16, 14] -> [18, 17, 4] -> [19, 7, 4] -> [1, 9, 7, 4]

print(tmpNums.map(String.init).joined()) // 1974

解答项目

func extraLongFactorials(n: Int) -> Void {
guard n > 0 else {
return
}
// 结果数组
var result: [Int] = [1]
for index in 1...n {
// 数组翻转 从低位开始每一位乘以本次的数字
let tmpNums = result.reversed().map { $0 * index }
// 进位数
var carryNum = 0
// 重置结果
result = []
tmpNums.forEach {
// 每一位加上上一位的进的数
let tmpNum = $0 + carryNum
// 向下一位进制的数
carryNum = tmpNum / 10
// 本位实际剩下的数 插入结果
result.append(tmpNum % 10)
}
// 处理剩余进位数 进位数是可能大于 100
while carryNum > 0 {
// 逐渐插入进制
result.append(carryNum % 10)
carryNum /= 10
}
// 翻转回数组
result = result.reversed()
}
// 连接字符串
print(result.map(String.init).joined())
}

Reference:

– EOF –