1.迭代通项
2.四则运算
[一]
x1, x2, x3, x4，四个数属于[1, 10]
f(x1, x2, x3, x4)，f表示四个数之间加减乘除且每个数字仅使用一次计算得到的结果
如果结果列表存在24返回true，否则false。
[二]
f: 多种算式
条件：运算符号为+ - * /，考虑括号
每个数字在算式出现一次
目标：f的所有结果列表，即需得到f通项结果，即需要得到f通项算式，即需要得到f算式列表
通项算式：
组成：数字、数子间3个符号、小括号对
[三]
数字: x 符号; s1一级符号， s2二级符号
A括号只有小括号(ok)
(x s2 x) s1 x s1 x
s2 s1 s1
[x s2 (x s2 x)] s1 x
等价于(x s2 x s2 x) s1 x
s2 s2 s1
[x s1 (x s2 x)] s1 x
等价于x s1 (x s2 x) s1 x
s1 s2 s1
s1 s1 s2
综上：无需中括号，只需小括号
B小括号数：最多两对
零对：x s1 x s1 x s1 x
一对：(x s1 x) s1 x s1 x
x s1 (x s1 x) s1 x
x s1 x s1 (x s1 x)
(x s1 x s1 x) s1 x
x s1 (x s1 x s1 x)
两对：(x s1 x) s1 (x s1 x)
[五]
迭代通式：
迭代法遍历数字和符号，获取无括号通项算式，基于无括号通项算式获得有括号通项算式。
迭代法本质：(((xsx)sx)sx)
迭代衍码：
f(x, list)=x
f(x s x s x, list) 值确定
f(x s x s x s x, list) = f( f(x s x s x) s x, list)
4! 已用数子坐标list，用于过滤数和确定返回最终结果。
统计如下：
str=""
str=x1+s1+x2+s2+x3+s3+x4
算式个数：72464=10752
括号对数(对数及位置)：7个
符号组合数：444=64个
数子组合数：432*1=24个
通项结果：
g(str)：四则运算
[六]
迭代通项代码
/**
* 24点游戏算法
* 1.通项算式
* 2.四则运算
* @author zhuyq
* @date 2020-12-08
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import com.tellhow.czp.netorder.app.nowcoder.huawei.Arithmetic;
public class TwentyFourPointGameArithmetic {
private static String points = "24";
public static ArrayList<String> arithmeticStrWithoutBracketList = new ArrayList<>();
public static void main(String[] args){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = null;
try {
while((str = br.readLine())!= null){
String[] strArr = str.split(" ");
ArrayList<Integer> numberList = new ArrayList<>();
for(int i=0; i<strArr.length; i++){
Integer val = Integer.valueOf(strArr[i]);
numberList.add(val);
}
ArrayList<String> arithmeticStrList = getArithmeticStrList1(numberList);
ArrayList<String> arithmeticResultList = getArithmeticResultList(arithmeticStrList);
boolean result = isTwentyFourPoint(arithmeticResultList);
System.out.println(result);
ArrayList<String> twentyFourPointarithmeticResultList = getTwentyFourPointArithmeticResultList(arithmeticStrList);
for(String s: twentyFourPointarithmeticResultList){
System.out.println(s);
}
}
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* 判断是否24点
* @author zhuyq
* @date 2020-12-08
*/
public static boolean isTwentyFourPoint(ArrayList<String> arithmeticResultList){
boolean isTwentyFourPoint = false;
for(int i=0; i<arithmeticResultList.size(); i++){
String result = arithmeticResultList.get(i);
if(result.equals(points)){
isTwentyFourPoint = true;
break;
}
}
return isTwentyFourPoint;
}
/**
* 获取24点算式列表
* @author zhuyq
* @date 2020-12-08
*/
public static ArrayList<String> getTwentyFourPointArithmeticResultList(ArrayList<String> arithmeticStrList){
ArrayList<String> twentyFourPointarithmeticResultList = new ArrayList<>();
for(int i=0; i<arithmeticStrList.size(); i++){
String arithmeticStr = arithmeticStrList.get(i);
String result = Arithmetic.arithmeticCaculate(arithmeticStr);
if(result.equals(points)){
twentyFourPointarithmeticResultList.add(arithmeticStr);
}
}
return twentyFourPointarithmeticResultList;
}
/**
* 算式结果列表
* @author zhuyq
* @date 2020-12-08
*/
public static ArrayList<String> getArithmeticResultList(ArrayList<String> arithmeticStrList){
ArrayList<String> arithmeticResultList = new ArrayList<>();
for(int i=0; i<arithmeticStrList.size(); i++){
String arithmeticStr = arithmeticStrList.get(i);
String result = Arithmetic.arithmeticCaculate(arithmeticStr);
arithmeticResultList.add(result);
}
return arithmeticResultList;
}
/**
* 迭代替换多层for
*
* f(x, list)=x
* f(x s x s x, list) 值确定
* f(x s x s x s x, list) = f( f(x s x s x) s x, list)
*
* list：已用数子坐标列表，用于过滤数和确定返回最终结果
*
* 细节点：迭代法参数有list，list必须clone
*
* @author zhuyq
* @date 2020-12-09
*/
public static ArrayList<String> getArithmeticStr(ArrayList<Integer> numberList, ArrayList<String> symbolList, String x, ArrayList<Integer> list){
if(list.size()==4){
arithmeticStrWithoutBracketList.add(x);
}
else{
for(int i=0; i<numberList.size(); i++){
boolean isExist = false;
for(int j=0; j<list.size(); j++){
if(list.get(j).equals(i)){
isExist = true;
}
}
if(!isExist){
ArrayList<Integer> list1 = (ArrayList<Integer>) list.clone();
list1.add(i);
for(int j=0; j<symbolList.size(); j++){
getArithmeticStr(numberList, symbolList, x+symbolList.get(j)+numberList.get(i), list1);
}
}
}
}
return arithmeticStrWithoutBracketList;
}
/**
* 算式列表
* @author zhuyq
* @date 2020-12-09
*/
public static ArrayList<String> getArithmeticStrList1(ArrayList<Integer> numberList){
ArrayList<String> arithmeticStrList = new ArrayList<>();
ArrayList<String> symbolList = new ArrayList<>();
symbolList.add("+");
symbolList.add("-");
symbolList.add("*");
symbolList.add("/");
for(int i=0; i<numberList.size(); i++){
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
String x = String.valueOf(numberList.get(i));
/**
* 零对：x s1 x s1 x s1 x
*/
getArithmeticStr(numberList, symbolList, x, list);
}
/**
* 通项算式(有括号)
*/
for(int i=0; i<arithmeticStrWithoutBracketList.size(); i++){
String arithmeticStrWithoutBracket = arithmeticStrWithoutBracketList.get(i);
ArrayList<String> bracketArithmeticStrList = getBracketArithmeticStrListForSpecifiedArithmeticStr(arithmeticStrWithoutBracket);
arithmeticStrList.add(arithmeticStrWithoutBracket);
for(int j=0; j<bracketArithmeticStrList.size(); j++){
arithmeticStrList.add(bracketArithmeticStrList.get(j));
}
}
return arithmeticStrList;
}
/**
* 通项算式(有括号)
* 一对：(x s1 x) s1 x s1 x
* x s1 (x s1 x) s1 x
* x s1 x s1 (x s1 x)
* (x s1 x s1 x) s1 x
* x s1 (x s1 x s1 x)
* 两对：(x s1 x) s1 (x s1 x)
*/
public static ArrayList<String> getBracketArithmeticStrListForSpecifiedArithmeticStr(String arithmeticStr){
ArrayList<String> bracketArithmeticStrList = new ArrayList<>();
ArrayList<String> bracketList = new ArrayList<>();
bracketList.add("(");
bracketList.add(")");
String regex = "[\\+\\-\\*/]";
String[] numArr = arithmeticStr.split(regex);
String[] symbolArr = new String[3];
Matcher slashMatcher = Pattern.compile(regex).matcher(arithmeticStr);
int idx = -1;
while(slashMatcher.find()) {
idx++;
symbolArr[idx] = slashMatcher.group();
}
String x1 = numArr[0];
String x2 = numArr[1];
String x3 = numArr[2];
String x4 = numArr[3];
String s1 = symbolArr[0];
String s2 = symbolArr[1];
String s3 = symbolArr[2];
StringBuilder sb1 = new StringBuilder();
sb1.append(bracketList.get(0)).append(x1).append(s1).append(x2).append(bracketList.get(1)).append(s2).append(x3).append(s3).append(x4);
StringBuilder sb2 = new StringBuilder();
sb2.append(x1).append(s1).append(bracketList.get(0)).append(x2).append(s2).append(x3).append(bracketList.get(1)).append(s3).append(x4);
StringBuilder sb3 = new StringBuilder();
sb3.append(x1).append(s1).append(x2).append(s2).append(bracketList.get(0)).append(x3).append(s3).append(x4).append(bracketList.get(1));
StringBuilder sb4 = new StringBuilder();
sb4.append(bracketList.get(0)).append(x1).append(s1).append(x2).append(s2).append(x3).append(bracketList.get(1)).append(s3).append(x4);
StringBuilder sb5 = new StringBuilder();
sb5.append(x1).append(s1).append(bracketList.get(0)).append(x2).append(s2).append(x3).append(s3).append(x4).append(bracketList.get(1));
StringBuilder sb6 = new StringBuilder();
sb6.append(bracketList.get(0)).append(x1).append(s1).append(x2).append(bracketList.get(1)).append(s2).append(bracketList.get(0)).append(x3).append(s3).append(x4).append(bracketList.get(1));
bracketArithmeticStrList.add(sb1.toString());
bracketArithmeticStrList.add(sb2.toString());
bracketArithmeticStrList.add(sb3.toString());
bracketArithmeticStrList.add(sb4.toString());
bracketArithmeticStrList.add(sb5.toString());
bracketArithmeticStrList.add(sb6.toString());
return bracketArithmeticStrList;
}
/**
* 基于list去掉指定项返回新(不同指针)的list
* @author zhuyq
* @date 2020-12-08
*/
public static ArrayList<Integer> getNewListByRemove(ArrayList<Integer> numberList, int i){
ArrayList<Integer> numberList1 = new ArrayList<>();
for(int k=0; k<numberList.size(); k++){
Integer xk = numberList.get(k);
if(k!=i){
numberList1.add(xk);
}
}
return numberList1;
}
}
四则算法代码如下：
package com.tellhow.czp.netorder.app.nowcoder.huawei;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import com.tellhow.czp.netorder.app.nowcoder.huawei.entity.UnitExpression;
import com.tellhow.czp.netorder.app.nowcoder.huawei.util.StrUtil;
/**
* 四则运算
* @author zhuyq
* @date 2020-11-11
*/
public class Arithmetic {
public static void main(String[] args){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String strExpression = null;
try {
while((strExpression = br.readLine())!= null){
String result = arithmeticCaculate(strExpression);
System.out.println(result);
}
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* 四则运算
* @author zhuyq
* @date 2020-11-11
*/
public static String arithmeticCaculate(String strExpression){
/*************************括号运算开始*****************************/
//小括号运算
strExpression = bracketCaculate(strExpression, "()");
//中括号运算
strExpression = bracketCaculate(strExpression, "[]");
//大括号运算
strExpression = bracketCaculate(strExpression, "{}");
/*************************括号运算结束*****************************/
/*************************单元算式开始*****************************/
//通用单元表达式解析计算
strExpression = UnitExpression.commonUnitExpressionParseCaculate(strExpression);
/*************************单元算式结束*****************************/
return strExpression;
}
/**
* 括号运算
* @author zhuyq
* @date 2020-11-11
*/
public static String bracketCaculate(String strExpression, String bracket){
ArrayList<UnitExpression> unitExpressionList = new ArrayList<>();
//截取所有小中大括号部分，并按UnitExpression格式及顺序存入List
Integer count = StrUtil.countChar(strExpression, bracket.substring(0, 1));
for(int i=0; i<count; i++){
Integer start = StrUtil.getCharacterPosition(strExpression, bracket.substring(0, 1), i+1);
Integer end = StrUtil.getCharacterPosition(strExpression, bracket.substring(1, 2), i+1);
String unitExpressionStr = strExpression.substring(start+1, end);
UnitExpression unitExpression = new UnitExpression(unitExpressionStr, start, end, bracket);
unitExpressionList.add(unitExpression);
}
//小中大括号计算，并替换到四则运算表达式中
StringBuilder strExpressionSb = new StringBuilder(strExpression);
for(int i=0; i<unitExpressionList.size(); i++){
UnitExpression unitExpression = unitExpressionList.get(i);
Integer start = StrUtil.getCharacterPosition(strExpressionSb.toString(), bracket.substring(0, 1), 1);
Integer end = StrUtil.getCharacterPosition(strExpressionSb.toString(), bracket.substring(1, 2), 1);
unitExpression.setStart(start);
unitExpression.setEnd(end);
//通用单元表达式解析计算
String result = UnitExpression.commonUnitExpressionParseCaculate(unitExpression.getUnitExpressionStr());
int position = strExpressionSb.toString().indexOf("("+unitExpression.getUnitExpressionStr()+")");
//特殊情况处理 小括号7+2+(1-10) 2020-12-08
if(unitExpression.getBracket().equals("()") && (new BigDecimal(result)).compareTo(BigDecimal.valueOf(0))==-1 && position>0){
strExpressionSb.replace(unitExpression.getStart()-1, unitExpression.getEnd()+1, result);
}
else{
strExpressionSb.replace(unitExpression.getStart(), unitExpression.getEnd()+1, result);
}
}
strExpression = strExpressionSb.toString();
return strExpression;
}
}
package com.tellhow.czp.netorder.app.nowcoder.huawei.entity;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import com.tellhow.czp.netorder.app.nowcoder.huawei.util.StrUtil;
/**
* 单元表达式(小/中/大括号里头的表达式和优先级表达式)
* @author zhuyq
* @date 2020-11-11
*/
public class UnitExpression {
String unitExpressionStr; //单元表达式
Integer start; //单元表达式左符号在四则运算表达式字符串定位
Integer end; //单元表达式右符号在四则运算表达式字符串定位
String bracket; //括号(小括号、中括号、大括号)及优先级符号(*/)
public UnitExpression() {
}
public UnitExpression(String unitExpressionStr, Integer start, Integer end, String bracket) {
super();
this.unitExpressionStr = unitExpressionStr;
this.start = start;
this.end = end;
this.bracket = bracket;
}
public String getUnitExpressionStr() {
return unitExpressionStr;
}
public void setUnitExpressionStr(String unitExpressionStr) {
this.unitExpressionStr = unitExpressionStr;
}
public Integer getStart() {
return start;
}
public void setStart(Integer start) {
this.start = start;
}
public Integer getEnd() {
return end;
}
public void setEnd(Integer end) {
this.end = end;
}
public String getBracket() {
return bracket;
}
public void setBracket(String bracket) {
this.bracket = bracket;
}
/**
* 通用单元表达式解析计算
* 方法：先算一级，再算二级
* @author zhuyq
* @date 2020-11-13
*/
public static String commonUnitExpressionParseCaculate(String strExpression){
//单元表达式解析计算--优先级(*/)
strExpression = priorityCaculate(strExpression);
//单元表达式解析计算--无优先级(+-)
strExpression = UnitExpression.unitExpressionParseCaculate(strExpression);
return strExpression;
}
/**
* 优先级(计算*和/，*和/优先级大于+和-，且*和/同优先级)
* 问题：连乘除和同优先级。方法：具体边解析边计算，逻辑或正则表达式 [乘除]。
* 优化：优先级多位数及小数问题。方法：解析添加正则引擎。根据数字[乘或除]数字匹配字符串中第一处。
* 兼容负数问题。方法：正则引擎数字兼容负数。
* @author zhuyq
* @date 2020-11-12
*/
public static String priorityCaculate(String strExpression){
StringBuilder strExpressionSb = new StringBuilder(strExpression);
//截取所有*和/算式部分
Integer count = StrUtil.countChar(strExpression, "*") + StrUtil.countChar(strExpression, "/");
for(int i=0; i<count; i++){
//解析
String regex = "-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))[*/]-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))";
Matcher slashMatcher = Pattern.compile(regex).matcher(strExpression);
Integer mIdx = 0;
while(slashMatcher.find()) {
mIdx++;
//当regex正则一级运算第1次出现的位置
if(mIdx == 1){
break;
}
}
Integer start = slashMatcher.start();
Integer end = slashMatcher.end();
String unitExpressionStr = strExpression.substring(start, end);
UnitExpression unitExpression = new UnitExpression(unitExpressionStr, start, end, "[*/]");
//计算
String result = UnitExpression.unitExpressionParseCaculate(unitExpression.getUnitExpressionStr());
//特殊情况处理:-0[*/]数或负数[*/]0
String regex1 = "(-0[*/]-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9])))|-(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))[*]0";
Matcher slashMatcher1 = Pattern.compile(regex1).matcher(unitExpressionStr);
if(slashMatcher1.find()){
result = "+0";
}
strExpressionSb.replace(unitExpression.getStart(), unitExpression.getEnd(), result);
strExpression = strExpressionSb.toString();
}
return strExpression;
}
/**
* 单元表达式解析计算, 优先级(无优先级按顺序计算)
* @author zhuyq
* @date 2020-11-11
*/
public static String unitExpressionParseCaculate(String unitExpressionStr){
BigDecimal result = new BigDecimal(0.00);
//ArrayList<Integer> numberList = new ArrayList<>();
ArrayList<String> numberList = new ArrayList<>();
ArrayList<String> symbolList = new ArrayList<>();
//特殊情况：表达式只有一个数字
String resultStr = "";
String regex0 = "-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))";
Matcher slashMatcher0 = Pattern.compile(regex0).matcher(unitExpressionStr);
Integer z = -1;
while(slashMatcher0.find()){
z++;
}
if(z==0){
resultStr = unitExpressionStr;
}
else{
/**
* 单元表达式解析，切割数字及符号并按顺序分别存入List
* @version V2.0 [正则解析] 适用正数(多位数、小数)、负数
* @author zhuyq
* @date 2020-11-13
*/
String regex = "-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))|[*/+]";
Matcher slashMatcher = Pattern.compile(regex).matcher(unitExpressionStr);
Integer j = -1;
while(slashMatcher.find()) {
String s = unitExpressionStr.substring(slashMatcher.start(), slashMatcher.end());
/**
* 问题：减号与负号冲突
* 方案：减号作负号用，如果数为负数，那么符号symbolList添加"+"
* @date 2020-11-13
*/
if( !(s.equals("*") || s.equals("/") || s.equals("+")) ){
j++;
numberList.add(s);
if( j>0 ){
String str = numberList.get(j-1)+s;
String regex1 = "-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))[-](([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))";
Matcher slashMatcher1 = Pattern.compile(regex1).matcher(str);
if(slashMatcher1.find()){
symbolList.add("+");
}
}
}
else{
symbolList.add(s);
}
}
//单元表达式计算
for(int i=0; i<symbolList.size(); i++){
String symbol = symbolList.get(i);
BigDecimal first = new BigDecimal(0.00);
if( i == 0 ){
first = new BigDecimal(numberList.get(i));
} else{
first = result;
}
BigDecimal second = new BigDecimal(numberList.get(i+1));
result = new BigDecimal( smallUnitCaculate(first, second, symbol ) );
}
resultStr = result.toString();
}
return resultStr;
}
/**
* 小单元运算
* @author zhuyq
* @date 2020-11-11
*/
public static String smallUnitCaculate(BigDecimal first, BigDecimal second, String symbol){
BigDecimal result = new BigDecimal(0.00);
if(symbol.equals("+")){
result = first.add(second);
}
else if(symbol.equals("-")){
result = first.subtract(second);
}
else if(symbol.equals("*")){
result = first.multiply(second);
}
else if(symbol.equals("/")){
if(second.compareTo(BigDecimal.valueOf(0)) == 0){
result = BigDecimal.valueOf(Double.MAX_VALUE);
}
else{
result = first.divide(second, 2, BigDecimal.ROUND_HALF_UP);
}
}
return result.toString();
}
}
package com.tellhow.czp.netorder.app.nowcoder.huawei.util;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* 字符串工具类
* @author zhuyq
* @date 2020-11-13
*/
public class StrUtil {
/**
* 获取指定字符在字符串第n次出现的位置
* @author zhuyq
* @date 2020-11-11
*/
public static Integer getCharacterPosition(String strExpression, String bracket, Integer n){
//这里是获取bracket符号的位置
Matcher slashMatcher;
//括号
if( bracket.equals("(") || bracket.equals(")") || bracket.equals("[") || bracket.equals("]") || bracket.equals("{") || bracket.equals("}") ){
slashMatcher = Pattern.compile("\\"+bracket).matcher(strExpression);
}
//乘除
else{
slashMatcher = Pattern.compile(bracket).matcher(strExpression);
}
Integer mIdx = 0;
while(slashMatcher.find()) {
mIdx++;
//当bracket符号第n次出现的位置
if(mIdx == n){
break;
}
}
return Integer.valueOf(slashMatcher.start());
}
/**
* 统计字符串中指定字符出现的次数
* @author zhuyq
* @date 2020-11-11
*/
public static Integer countChar(String strExpression, String bracket){
Integer count = 0;
for(int i=0; i<strExpression.length(); i++){
if(bracket.equals(String.valueOf(strExpression.charAt(i)))){
count++;
}
}
return count;
}
}
京公网安备 11010502036488号