移动一根火柴使等式成立js版本(递归)

时间:2022-11-05 15:54:28

修改成递归版本

思路:

  1、设定规则数组,比如:1加一根火柴只可以变成7.

  2、设定方法数组,比如:一个数增加了一根火柴,其他的数必然减少一根火柴。

  3、增加Array方法,由元素名和方法,得到规则对象。

  4、增加替换数组元素的方法,根据原数组和下标,得到 一个字符串。有2个方法,一个深度copy,一个普通指针,这样就可以*选择是否改变原来的数组了。

  5、主逻辑:

    根据式子生成数组

    遍历数组元素,匹配规则,匹配到,递归进行二次匹配。

    匹配不到规则,递归下一个元素。

      

<html>
<head>
<title>移动一根火柴使等式成立js版本</title>
<meta http-equiv="Content-Type" content="text/html; charset=gbk">
<script language="javascript">
//递归阶乘
function getNum(i){
    if (i>1){
        return i*getNum(i-1);
    }else{
        return 1;
    }
}
//console.log(getNum(3));


/**
* 规则的设定,按照信号灯样式,8就是由7根火柴棍组成
* 设定变化规则:
* add:    0-》8
*        1-》7
*        3-》9
*        5-》6,9
*        6-》8
*        9-》8
*        - -》+,=
* sub: 6-》5
*        7-》1
*        8-》0.6,9
*        9->3,5
*        + -> -
*        = -> -
* mv:    0 -> 6,9
*        2 -> 3
*        3 -> 5
*        6 -> 9
*        9 -> 0,6
*/        
var data = [];
data.push({a:0,b:[8],m:"add"}); //0加一根火柴可以变化为8以此类推
data.push({a:0,b:[6,9],m:"mv"});
data.push({a:1,b:[7],m:"add"});
data.push({a:2,b:[3],m:"mv"});
data.push({a:3,b:[5],m:"mv"});
data.push({a:3,b:[9],m:"add"});
data.push({a:5,b:[6,9],m:"add"});
data.push({a:6,b:[5],m:"sub"});
data.push({a:6,b:[9],m:"mv"});
data.push({a:6,b:[8],m:"add"});
data.push({a:7,b:[1],m:"sub"});
data.push({a:8,b:[0,6,9],m:"sub"});
data.push({a:9,b:[0,6],m:"mv"});
data.push({a:9,b:[3,5],m:"sub"});
data.push({a:9,b:[8],m:"add"});
data.push({a:"+",b:["-"],m:"sub"});
data.push({a:"-",b:["+","="],m:"add"});
data.push({a:"=",b:["-"],m:"sub"});

//修改数组,增加方法 可以由key和method得到唯一的变化规则对象。
Array.prototype.get = function(key, method){
    for(var i = 0; i < this.length; i++){
        if(this[i].a == key && this[i].m == method){
            return this[i];
        }
    }
}


/**
*    转换字符串:将原式子替换成根据规则变换后的式子
*    params:
*        ori:    原式子
*        index:    需要替换的位置
*        fin:    根据规则替换的数字
*
*    return 替换后的字符串
*/
function changeStr(ori, index, fin){
    var str = ori.substr(0, index) + fin + ori.substring(index+1, ori.length); 
    return str;
}

//返回替换后的字符串,并不改变原来数组的值,深度copy
function changeArrMirror(oriArr, index, fin){
    var tempArr = oriArr.slice(0);
    tempArr[index] = fin; 
    var str = tempArr.join("");
    return str;
}

//返回替换后的字符串,并改变原来数组的值,指针copy
function changeArrAll(oriArr, index, fin){
    oriArr[index] = fin; 
    var str = oriArr.join("");
    return str;
}

/**
* 计算主体方法:以2+3=6为例
* 基本逻辑:得到原字符串数组[2, +, 3, =, 6],从第一位开始,查找规则,
*        匹配到规则,递归下一个元素查找相反规则,构成字符串,查看是否成立,成立则打印,继续程序,查找下一个成立等式
*        匹配不到规则,递归下一个方法元素,都匹配不到,递归下一个式子元素。    
* param:
*        originArr: 拆分的待匹配的数组
*        originIndex: 式子数组的索引,正在匹配的元素下标
*        methodIndex: 方法数组的索引
*        isChanged: 是否匹配了第一个元素
* return:
*/
function compare(originArr, originIndex, methodIndex, isChanged){
    if (originIndex >= originArr.length){
        return;
    }
    if (methodIndex == 2){
        isChanged = true;
    }

    //已经匹配第一次的式子,进行第二次匹配,需要得到 methodArr[methodIndex]的成对方法匹配
    //        匹配不到规则,递归式子数组的下一个值
    //        匹配到规则,循环查看规则的值,看是否有能另等式成立的,如果都不能成立,递归式子数组的下一个值
    if(isChanged){
        var role = data.get(originArr[originIndex], methodArr[methodIndex][1]);
        if (role == undefined || role == null){
            compare(originArr, originIndex + 1, methodIndex, isChanged);
        }else{
            for (var matchIndex=0; matchIndex < role.b.length; matchIndex++){
                var changedStr = changeArrMirror(originArr, originIndex, role.b[matchIndex]);    
                if (eval(changedStr.split("=")[0]) == eval(changedStr.split("=")[1])){
                    console.log(changedStr);
                    flag = true;
                    return;
                }
            }
            compare(originArr, originIndex + 1, methodIndex, isChanged);
        }
    }else{
        //匹配方法数组元素的第一个method,看是否有规则
        //        如果有,设定匹配标识isChanged=true,进行二次匹配
        //        如果没有,递归下一个式子数组元素。
        var role = data.get(originArr[originIndex], methodArr[methodIndex][0]);
        
        //如果没有相应rule,匹配方法数组的其他方法,直到都匹配了
        if (role == undefined || role == null){
            if (methodIndex >= methodArr.length)
                compare(originArr, originIndex + 1, 0, isChanged);
            else
                compare(originArr, originIndex, methodIndex + 1, isChanged);
        }else{
            for (var matchIndex=0; matchIndex < role.b.length; matchIndex++){
                var changedStr = changeArrAll(originArr, originIndex, role.b[matchIndex]);    
                isChanged = !isChanged;
                compare(originArr, originIndex + 1, methodIndex, isChanged);
            }
        }

    }
}

//方法数组,成对出现
var methodArr = [["add", "sub"], ["sub", "add"], ["mv", "mv"]];
var flag = false;

//得到原始式子,分割成数组,调用递归函数进行计算。
function compute(){
    var originStr = document.getElementById("origin").value;
    
    var baseArr = originStr.split("");
    for (var i=0; i<baseArr.length; i++){
        var tempBaseArr = baseArr.slice(0);
        compare(tempBaseArr, i, 0, false);
    }
    if (!flag){
        console.log("没有匹配答案");
    }
    
}


 
</script>
</head>
<body>
输入一个需要计算的式子,例如:1+2+3=6
<input id="origin" onkeypress="if(event.keyCode == 13) compute();"/>
<input type="button" value="计算" onclick="compute()" />
</body>
</html>