更新：《24 点》APP—— 提示功能实现#
背景#
商店里所有 24 点 APP 的一个付费功能是提示的获取，会通过限制提示次数，超出次数后观看广告或者购买来解锁额外次数。比如：
这里就来分享一下，类似 24 点的提示功能是怎么实现的，其实现步骤如下：
步骤一：判断结果能不能等于 24；
步骤二：如果能等于 24，显示出能得到 24 的表达式。
下面详细记录一下实现的过程：
解法原理#
步骤一，判断能不能等于 24#
有 [a, b, c, d] 四个数字，任取两个数字，通过遍历运算符得到运算结果 e，然后把运算结果和剩余的数字放入新的数组中，重复上面的计算过程，直到数组中有一个元素为止；最后判断数组中唯一的数字是否等于 24 即可。
这里需要注意几点，一是遍历运算符的时候，加和乘符合交换律，所以不需要重复计算；二是除法会有小数，所以最终判断是否等于 24 的时候，需要通过设置误差范围来判断；再有就是除法的除数不能为零。
所以最终解法描述如下：
- 定义误差范围，定义要对比的值，定义运算符数组；
- 定义判断是否相等的判断方法，传入值和要对比的值的绝对值小于误差范围，即视作相等；
- 数据转换，由于传入的数字是 Int，所以通过 map 转为 Double 类型；
- 实现计算方法
- 数组为空，不合法；
- 数组中只有一个数字，即停止，调用判断相等方法判断是否相等
- 从数组中依次取两个数字，两个数字不能相等
- 把余下的数字放入新的数组中
- 遍历运算符数组
- 运算符为 "+" 或 "*" 时，注意交换律，刚开始 i <j，所以到 i> j 时，就不需要重复计算了
- 运算符为 "-" 时，除数不能为 0
- 把取出的两个数字通过运算符计算出结果，放入余下数字的新数组中，新数组中即有 3 个数字
- 再从这个新数组中取出两个数字重复上面的计算过程，递归调用，得到返回结果
- 如果返回结果不为真，则从 3 个数字的新数组中，移除最后一个元素即此次通过运算符运算后的数字；然后再继续遍历下一个运算符
- 如果所有运算符已遍历完成，结果还不为真，则继续遍历原始数组，取出后面的数字。
流程图如下：
代码实现如下：
// 1. 定义误差范围，定义要对比的值，定义运算符数组；
let elipson = 0.001
let TargetReuslt = 24
let OperationList = ["+", "-", "*", "/"]
class Solution {
// 2. 定义判断是否相等的判断方法，传入值和要对比的值的绝对值小于误差范围，即视作相等；
func isEqual24(_ value: Double) -> Bool {
return abs(value - Double(TargetReuslt)) < elipson
}
func judgePoint24(_ list: [Int]) -> Bool {
// 3. 数据转换，由于传入的数字是Int，所以通过 map 转为 Double 类型；
let resultList: [Double] = list.map({ Double($0) })
return find24(resultList)
}
// 每次都是选取两张牌
func find24(_ cards: [Double]) -> Bool {
// 4.1 数组为空，不合法；
if cards.count == 0 {
return false
}
// 4.2 数组中只有一个数字，即停止，调用判断相等方法判断是否相等
if cards.count == 1 {
let result = isEqual24(cards[0])
return result
}
let count = cards.count
// 4.3 从数组中依次取两个数字，两个数字不能相等
for i in 0..<count {
for j in 0..<count {
if i != j {
let a = cards[i]
let b = cards[j]
// 4.4 把余下的数字放入新的数组中
var restCards: [Double] = []
for k in 0..<count {
if k != i && k != j {
restCards.append(cards[k])
}
}
// 4.5 遍历运算符数组
for op in OperationList {
// 4.5.1 运算符为"+"或"*"时，注意交换律，刚开始 i < j，所以到 i > j 时，就不需要重复计算了
if ((op == "+" || op == "*") && (i > j)) {
// "+"、"*", a + b = b + a, no need to recalculate
continue
}
// 4.5.2 运算符为"-"时，除数不能为0
if (op == "/") && b < elipson {
// "/" dividend can not equal to zero
continue
}
// 4.5.3 把取出的两个数字通过运算符计算出结果，放入余下数字的新数组中，新数组中即有3个数字
switch op {
case "+":
restCards.append(a+b)
case "-":
restCards.append(a-b)
case "*":
restCards.append(a*b)
case "/":
restCards.append(a/b)
default:
break
}
// 4.5.4 再从这个新数组中取出两个数字重复上面的计算过程，递归调用，得到返回结果
let result = find24(restCards)
if result == true {
return true
}
// 4.5.5 如果返回结果不为真，则从3个数字的新数组中，移除最后一个元素即此次通过运算符运算后的数字；然后再继续遍历下一个运算符
restCards.removeLast()
}
}
}
}
return false
}
}
步骤二，获得等于 24 时的表达式#
上面的逻辑计算出能否等于 24，那在计算出 24 的情况下，如何把得到这个结果的表达式显示出来？
回过头来看上面的代码，在步骤 4.5.3 时，进行了表达式和运算符计算的操作，所以如果想要得到计算的表达式的话，需要在这个计算地方把表达式也存储一下。
然后问题是，计算过程是一个递归的过程，如何在递归的过程中保证前面步骤的表达式不丢失，从而得到递归过程中所有计算的表达式，最终在得到结果时，得到一个表达式数组。
修改func find24(_ cards: [Double]) -> Bool方法，传入参数中增加resultExpressList参数，类型为数组，用于保存每次递归的表达式；传出参数改为增加数组，用于获取最终计算出结果时的表达式。
需要注意：
func find24(_ cards: [Double]) -> Bool返回类型为元组- 传入表达式数组不可变，故而需要转为可变的
- 表达式的中数字使用 NSNumber 转换，避免浮点精度问题
代码如下：
// 1. 定义误差范围，定义要对比的值，定义运算符数组；
let elipson = 0.001
let TargetReuslt = 24
let OperationList = ["+", "-", "*", "/"]
class Solution {
// 2. 定义判断是否相等的判断方法，传入值和要对比的值的绝对值小于误差范围，即视作相等；
func isEqual24(_ value: Double) -> Bool {
return abs(value - Double(TargetReuslt)) < elipson
}
func judgePoint24(_ list: [Int]) -> Bool {
// 3. 数据转换，由于传入的数字是Int，所以通过 map 转为 Double 类型；
let resultList: [Double] = list.map({ Double($0) })
let value: (result: Bool, expressList: [String]) = find24(resultList, resultExpressList: [])
return value.result
}
// 每次都是选取两张牌
func find24(_ cards: [Double], resultExpressList: [String]) -> (Bool, [String]) {
// 4.1 数组为空，不合法；
if cards.count == 0 {
return (false, resultExpressList)
}
// 4.2 数组中只有一个数字，即停止，调用判断相等方法判断是否相等
if cards.count == 1 {
let result = isEqual24(cards[0])
return (result, resultExpressList)
}
// 将传入数据变为可变数组
var expressionList: [String] = []
expressionList.append(contentsOf: resultExpressList)
let count = cards.count
// 4.3 从数组中依次取两个数字，两个数字不能相等
for i in 0..<count {
for j in 0..<count {
if i != j {
let a = cards[i]
let b = cards[j]
// 4.4 把余下的数字放入新的数组中
var restCards: [Double] = []
for k in 0..<count {
if k != i && k != j {
restCards.append(cards[k])
}
}
// 4.5 遍历运算符数组
for op in OperationList {
// 4.5.1 运算符为"+"或"*"时，注意交换律，刚开始 i < j，所以到 i > j 时，就不需要重复计算了
if ((op == "+" || op == "*") && (i > j)) {
// "+"、"*", a + b = b + a, no need to recalculate
continue
}
// 4.5.2 运算符为"-"时，除数不能为0
if (op == "/") && b < elipson {
// "/" dividend can not equal to zero
continue
}
// 4.5.3 把取出的两个数字通过运算符计算出结果，放入余下数字的新数组中，新数组中即有3个数字
// 计算后，将表达式保存到 expressionList 中，并作为下次递归的参数
// 注意：表达式的中数字使用 NSNumber，避免浮点精度问题
switch op {
case "+":
restCards.append(a+b)
expressionList.append(String(format: "(%@ + %@) = %@", NSNumber(value: a), NSNumber(value: b), NSNumber(value: a + b)))
case "-":
restCards.append(a-b)
expressionList.append(String(format: "(%@ - %@) = %@", NSNumber(value: a), NSNumber(value: b), NSNumber(value: a - b)))
case "*":
restCards.append(a*b)
expressionList.append(String(format: "(%@ * %@) = %@", NSNumber(value: a), NSNumber(value: b), NSNumber(value: a * b)))
case "/":
restCards.append(a/b)
expressionList.append(String(format: "(%@ / %@) = %@", NSNumber(value: a), NSNumber(value: b), NSNumber(value: a / b)))
default:
break
}
// 4.5.4 再从这个新数组中取出两个数字重复上面的计算过程，递归调用，得到返回结果
let resultValue: (result: Bool, list: [String]) = find24(tempList, resultExpressList: expressionList, level: level)
if resultValue.result {
return (true, resultValue.list)
}
// 4.5.5 如果返回结果不为真，则从3个数字的新数组中，移除最后一个元素即此次通过运算符运算后的数字；然后再继续遍历下一个运算符
restCards.removeLast()
}
}
}
}
return false
}
}
测试上面的代码：
给定 [6, 8, 5, 8] 四个数字，判断能否等于 24，如果能，打印表达式，最终打印出的表达式数组如下：
["(6 - 8) = -2", "(5 + -2) = 3", "(8 * 3) = 24"]
从上面打印出的日志可以看到，确实可以计算出 24，且把计算出 24 过程保存下来了，但是跟想象中的不一样，因为同类型《24 点》APP 的提示功能中，提示的表达式是把步骤合一，最后是一个整体的表达式，而不是分步骤的，所以要怎么把这个步骤合一呢？
再看一遍上面的数字和表达式数组：
数字： [6, 8, 5, 8]
表达式数组： ["(6 - 8) = -2", "(5 + -2) = 3", "(8 * 3) = 24"]
要做的就是把表达式数组换成一个完整的表达式：
- 把 5+ -2 中的 - 2 替换为 (6 - 8)
- 把 8 * 3 中的 3 替换为 (5 + (6- 8))，从而得到最终的 (8 * (5 + (6 - 8)))
这个转换需要注意两点：
- 每个数组只能用一遍
- 每个表达式只能用一次
笔者这里转换的步骤如下：
- 定义一个字典数组，用于存储每一步转换的字典
- 遍历上面的表达式数组
- 定义一个字典，三个 key，表达式，表达式结果，表达式是否使用过，{"expressionStr": "a + b", "expressionValue": "c", "expressionUsed": "0"}
- 将表达式和结果分开，存储到字典里，默认没使用过，并且存储到字典数组中
- 遍历非第一个元素时
- 遍历字典数组，判断是否使用过，元素是否包含字典表达式元素的值，
- 包含则把元素中对应的值替换为字典表达式元素的表达式，且标记字典表达式为使用过，且把新的字典存储到字典数组中
- 不包含，则把新的字典存储到字典数组中
- 遍历字典数组，判断是否使用过，元素是否包含字典表达式元素的值，
- 最后返回字典数组最后一个元素的表达式，即是所需结果
流程图如下：
代码如下：
func generateExpressStr(from list: [String]) -> String {
var resultStrList: [NSMutableDictionary] = []
let strKey = "expressionStr"
let valueKey = "expressionValue"
let statusKey = "expressionUsed"
var newResultStrList: [NSMutableDictionary] = []
for index in 0..<list.count {
let itemStr = list[index]
let componentList = itemStr.components(separatedBy: " = ")
var expressionStr = componentList[0]
let expressionValue = componentList[1]
if index == 0 {
let tempDic = NSMutableDictionary()
tempDic.setValue(expressionStr, forKey: strKey)
tempDic.setValue(expressionValue, forKey: valueKey)
tempDic.setValue("0", forKey: statusKey)
newResultStrList.append(tempDic)
}
else {
for itemDic in resultStrList {
print(itemDic)
if let previousExpressionStr = itemDic.value(forKey: strKey) as? String,
let previousExpressionValueStr = itemDic.value(forKey: valueKey) as? String,
let previousStatusValue = itemDic.value(forKey: statusKey) as? String,
previousStatusValue == "0" {
let tempDic = NSMutableDictionary()
if expressionStr.contains(previousExpressionValueStr) {
let range = (expressionStr as NSString).range(of: previousExpressionValueStr)
let newExpressionStr = (expressionStr as NSString).replacingCharacters(in: range, with: previousExpressionStr)
expressionStr = newExpressionStr
let newExpressionValue = expressionValue
tempDic.setValue(newExpressionStr, forKey: strKey)
tempDic.setValue(newExpressionValue, forKey: valueKey)
tempDic.setValue("0", forKey: statusKey)
newResultStrList.append(tempDic)
itemDic.setValue("1", forKey: statusKey)
}
else {
let newExpressionStr = expressionStr
let newExpressionValue = expressionValue
let tempDic = NSMutableDictionary()
tempDic.setValue(newExpressionStr, forKey: strKey)
tempDic.setValue(newExpressionValue, forKey: valueKey)
tempDic.setValue("0", forKey: statusKey)
newResultStrList.append(tempDic)
}
}
}
}
resultStrList = newResultStrList
}
let resultStr = resultStrList.last?.value(forKey: strKey) as? String ?? ""
print(resultStr)
return resultStr
}
完整代码#
本篇的完整代码已整理放在Github，链接如下：
https://github.com/mokong/game24HintDemo
最终效果如下：
结语#
通过Swift 后缀表达式和24点提示功能的实现两篇文章，介绍了做一个《24 点 APP》所需的主要功能，感兴趣的可以自己设计 UI、动效，加上自己独有的功能实现，比如换肤、闯关、内购等等，可以做出自己的独特的《24 点 APP》，欢迎大家尝试。