遞歸方式窮舉Google方程式（javascript實現(xiàn)）

tianlai 發(fā)布于2019-08-19 18:02 / 1536人閱讀

摘要：搜索函數(shù)第一層調(diào)用，設置第一個字符后遞歸調(diào)用，字符規(guī)模減少了首字符邊界條件是所有的字符都設置完成，即調(diào)用回調(diào)函數(shù)，檢測等式是否成立，并輸出等式成立的方案。

此為《算法的樂趣》讀書筆記，我用javascript重新實現(xiàn)算法。這個實現(xiàn)方案還很通用，應用了策略模式，把具體的方程計算隔離包裝到了回調(diào)函數(shù)中。

Google方程式

題目：有一個由字符組成的等式：WWWDOT - GOOGLE = DOTCOM，每個字符代表一個0~9之間的數(shù)字，請找出一組字符和數(shù)字的對應關(guān)系，使等式成立。

定義數(shù)據(jù)結(jié)構(gòu)

定義charItem數(shù)組保存問題中所有出現(xiàn)的字母，leading屬性表示該字母會出現(xiàn)在首位；定義tagCharValue數(shù)組保存數(shù)字，used屬性表示該字母的使用狀態(tài)，因為不同的字母在同一時間不能相等。

var charItem = [
    { c:"W", value:-1, leading:true},
    { c:"D", value:-1, leading:true},
    { c:"O", value:-1, leading:false},
    { c:"T", value:-1, leading:false},
    { c:"G", value:-1, leading:true},
    { c:"L", value:-1, leading:false},
    { c:"E", value:-1, leading:false},
    { c:"C", value:-1, leading:false},
    { c:"M", value:-1, leading:false}
];
var tagCharValue = [
    { used:false, value:0 },
    { used:false, value:1 },
    { used:false, value:2 },
    { used:false, value:3 },
    { used:false, value:4 },
    { used:false, value:5 },
    { used:false, value:6 },
    { used:false, value:7 },
    { used:false, value:8 },
    { used:false, value:9 }
];

回調(diào)函數(shù)（具體計算規(guī)則）

把具體計算規(guī)則提取出來，放到回調(diào)函數(shù)中，使用算法具有能用性。

searchingResult(charItem,tagCharValue,0,function(ci){
    var minuend = "WWWDOT";
    var subtrahend = "GOOGLE";
    var diff = "DOTCOM";

    var m = MakeIntegerValue(ci, minuend);
    var s = MakeIntegerValue(ci, subtrahend);
    var d = MakeIntegerValue(ci, diff);

    if(m - s == d){
        console.log(m + " - " + s + " = " + d);
    }
})

字符串到整數(shù)的轉(zhuǎn)換

把字符替換成相應的數(shù)字。

function MakeIntegerValue(ci, str){
    var rs = str.split("");
    var outcome = 0;
    rs.forEach(function(al){
        for(var i=0; i
有效性檢測
基于數(shù)字的位置及其使用情況，進行有效性檢測。零不能在首位，不同字符不能相等。
function isValueValid(item, value){
    if(item.leading){
        return !value.used && value.value;
    }else{
        return !value.used;
    }
}
搜索函數(shù)
第一層調(diào)用，設置第一個字符后遞歸調(diào)用，字符規(guī)模減少了首字符；邊界條件是所有的字符都設置完成，即調(diào)用回調(diào)函數(shù)，檢測等式是否成立，并輸出等式成立的方案。
function searchingResult(ci, cv, index, callback){
    if(index == charItem.length){
        callback(ci);
        return;
    }
    for(var i=0; i
輸出結(jié)果
本題有兩個解。
777589 - 188103 = 589486
777589 - 188106 = 589483
比較非遞歸方案
我的第一反應，非遞歸方案應該效率要高，為了驗證，我寫如下的非遞歸實現(xiàn)。運行的結(jié)果超出我的預期，非遞歸方案比遞歸方案慢了不止一個數(shù)量級。
分析原因，非遞歸對不同字符不能取相同的數(shù)字的判斷不好實現(xiàn)，且不能避免（也有可能是我的判重算法效率太低）；而遞歸方案卻很自然的避免了這個問題。
for(var w = 1; w <= 9; w++)
for(var d = 1; d <= 9; d++)
for(var o = 0; o <= 9; o++)
for(var t = 0; t <= 9; t++)
for(var g = 1; g <= 9; g++)
for(var l = 0; l <= 9; l++)
for(var e = 0; e <= 9; e++)
for(var c = 0; c <= 9; c++)
for(var m = 0; m <= 9; m++){
    var tmp = {};
    tmp[w]=1;
    tmp[d]=1;
    tmp[o]=1;
    tmp[t]=1;
    tmp[g]=1;
    tmp[l]=1;
    tmp[e]=1;
    tmp[c]=1;
    tmp[m]=1;
    if(Object.keys(tmp).length == 9){
        if(w*100000+w*10000+w*1000+d*100+o*10+t - g*100000-o*10000-o*1000-g*100-l*10-e == d*100000+o*10000+t*1000+c*100+o*10+m)
            console.log(w.toString()+w.toString()+w.toString()+d.toString()+o.toString()+t.toString()+"-"+ 
                        g.toString()+o.toString()+o.toString()+g.toString()+l.toString()+e.toString()+"="+ 
                        d.toString()+o.toString()+t.toString()+c.toString()+o.toString()+m.toString());
    }
}