编写一个在1，2，…，9（顺序不能变）数字之间插入+或-或什么都不插入，使得计算结果总是100的程序，并输出所有的可能性。例如：1 + 2 + 34 – 5 + 67 – 8 + 9 = 100
拿到这个题我很快就想到了1~9之间有8个位置,每个位置可以放+/-/*(暂时用*号来表示什么也不插入) 这样就有3^8(3的8次方)种可能性, 只要把这3^8种可能性循环遍历一下等于100的筛选出来不就得了, 思路没问题, 但是3^8次方种可能性怎么获得呢,我进入了懵逼状态,(也许是思维定式吧,也可能是智商不过关,但是希望别喷我^_^)地铁上想了一路,然后有那么点儿思路,用递归来算,然后飞奔到家.......
(事先声明哈,本人ios开发,所以用OC代码实现,不过思路应该是一样的)
第一步: 解决这3^8种符号的组合
我的思路是从后往前来找 ,暂且默认前7个位置的符号都是+,这样 最后一个位置的可能性就是 +/-/* 3种组合, 这样往前在看一位找规律前6个位置都是+ 那么就是第七个位置的 "+"和之前的 "+/-/*"3种组合, "-"和之前的 "+/-/*"3种组合 , "*"和之前的 "+/-/*"3种组合总共就是9种,
以此类推,每往前推1个位置,就会有之前组合数组的3倍数量,按照这个思路我写了递归的OC代码如下
贴个log日志更好理解
@property (nonatomic, strong) NSMutableArray *lastArray; /**< 最终的结果数组 */
@property (nonatomic, strong) NSArray *staticArray;
self.staticArray = @[@"+",@"-",@"*"];
/**
用递归获取所有组合方式
@param index 第几个位置(总共8个位置 我们开始传入6最后一个位置的可能性数组已经确定就是 @[@"+",@"-",@"*"])
@param dataArray 最终输出所有组合结果
*/
- (void)configIndex:(NSInteger)index dataArray:(NSMutableArray*)dataArray
{
if(index <0) {
return;
}
NSMutableArray *tempArray = [NSMutableArray array];
for(NSIntegeri=0; i
NSString*tempString =self.staticArray[i];
[tempArrayaddObject:[selfconfigWithString:tempStringdataArray:dataArray]];
}
NSMutableArray *result = [NSMutableArray array];
for(NSMutableArray*arrayintempArray) {
for(NSIntegeri=0; i
[resultaddObject:array[i]];
}
}
self.lastArray= [NSMutableArrayarrayWithArray:result];
index--;
[self configIndex:index dataArray:self.lastArray];
}
/**
返回
@param str 需要拼接的字符(这里就是 +/-/(*))
@param dataArray 已经拼接好的数组
@return 新的拼接后的数组
*/
- (NSMutableArray*)configWithString:(NSString*)str dataArray:(NSMutableArray*)dataArray
{
NSMutableArray *resultArray = [NSMutableArray array];
for(NSString*nameindataArray) {
NSString*tempString = [NSStringstringWithFormat:@"%@/%@",str,name];
[resultArrayaddObject:tempString];
}
returnresultArray;
}
这样 self.lastArray 中存储的就是 8个位置 3中符号组合的所以有可能性
第二步: 把这6561种组合 插入到1,2,3...9的位置中, 然后计算组合值为100,输出符合条件的组合
- (NSMutableArray*)getEqualTo100Array
{
/**< 将3^8 符号组合 和 1,2....9 进行组合获取最终的数学表达式 */
NSMutableArray *array = [NSMutableArray array];
NSArray *numArray = @[@"1",@"2",@"3",@"4",@"5",@"6",@"7",@"8",@"9"];
for(NSIntegeri=0; i
NSString*lastString =self.lastArray[i];
NSArray*lastArray = [lastStringcomponentsSeparatedByString:@"/"];
NSString*tempString =@"";
for(NSIntegerj=0; j
if(j
NSString*nextString = lastArray[j];
if([nextStringisEqualToString:@"*"]) {
nextString =@"";
}
tempString = [tempStringstringByAppendingString:[NSStringstringWithFormat:@"%@%@",numArray[j],nextString]];
}else{
tempString = [tempStringstringByAppendingString:numArray[j]];
}
}
[arrayaddObject:tempString];
}
/**< 计算数学表达式结果是100 将符合条件的数学表达式输出 */
NSMutableArray *resultArray = [NSMutableArray array];
for(NSIntegeri=0; i
NSString*result = [FormulaStringCalcUtilitycalcComplexFormulaString:array[i]];
if([resultintegerValue] ==100) {
[resultArrayaddObject:array[i]];
}
}
returnresultArray;
}
最终结果就是11种如下图
其中计算一个数学表达式字符串的结果也让我有点儿惆怅,因为实在遇到过,有思路就是一个个遍历然后计算结果,不过感觉自己写也会费带点儿功夫,然后就求助度娘, 果真度娘没有袖手旁观光, https://www.cnblogs.com/Kurodo/p/3456642.html 这为仁兄,已经实现了,我就直接拿来试用下,毕竟我很迫切想要知道题目的答案(^<^),顺便看了下 安卓和 H5都有计算字符串数学表达式的方法,挺好用的哦.
说实话,可能基本功的问题吧,实现这个确实花费了我不少时间,不过对我来说是个宝贵的经历,至少让我没有把这时间浪费在游戏上吧,至少我今晚可以安然入睡哈哈 晚安了各位!
欢迎各位大神讨论思路
(来自一个爱学习的蜗牛在路上)
网友评论