遞歸方式窮舉Google方程式（javascript實現）

tianlai 發布于2019-08-19 18:02 / 1530人閱讀

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

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

Google方程式

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

定義數據結構

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

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 }
];

回調函數（具體計算規則）

把具體計算規則提取出來，放到回調函數中，使用算法具有能用性。

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);
    }
})

字符串到整數的轉換

把字符替換成相應的數字。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/79124.html

大廠算法面試之leetcode精講3.動態規劃

摘要：動態規劃問題一定會具備最優子結構，才能通過子問題的最值得到原問題的最值。另外，雖然動態規劃的核心思想就是窮舉求最值，但是問題可以千變萬化，窮舉所有可行解其實并不是一件容易的事，只有列出正確的狀態轉移方程才能正確地窮舉。大廠算法面試之leetcode精講3.動態規劃視頻教程（高效學習）:點擊學習目錄：1.開篇介...

番茄西紅柿 2021-11-22 14:56 評論0 收藏2637
n階貝塞爾曲線（bezier）javascript 實現解析

摘要：最近學習，看到曲線，所以補充了下知識，另外相關的數學定律都忘光了需要了解的前期需要了解相關的知識，可以看下維基百科什么是貝塞爾曲線什么是線性插值繪制本身只提供了二次和三次的繪制函數，如果更高階級的怎么辦呢要對起進行降階拆分。最近學習canvas，看到bezier曲線，所以補充了下知識，另外相關的數學定律都忘光了~ 需要了解的前期需要了解相關的知識，可以看下維基百科什么是貝塞爾曲...

Labradors 2019-06-27 15:03 評論0 收藏0
n階貝塞爾曲線（bezier）javascript 實現解析

摘要：最近學習，看到曲線，所以補充了下知識，另外相關的數學定律都忘光了需要了解的前期需要了解相關的知識，可以看下維基百科什么是貝塞爾曲線什么是線性插值繪制本身只提供了二次和三次的繪制函數，如果更高階級的怎么辦呢要對起進行降階拆分。最近學習canvas，看到bezier曲線，所以補充了下知識，另外相關的數學定律都忘光了~ 需要了解的前期需要了解相關的知識，可以看下維基百科什么是貝塞爾曲...

EastWoodYang 2019-08-22 10:50 評論0 收藏0
神經網絡中的梯度下降與反向傳播的關系（大白話，通俗易懂版本）

摘要：損失函數的作用可以理解為當前向傳播得到的預測值與真實值接近時，取較小值。神經網絡神經網絡就是一個萬能的模型+誤差修正函數，每次根據訓練得到的結果與預想結果進行誤差分析，進而修改權值和閾值，一步一步得到能輸出和預想結果一致的模型。舉一個例子：比如某廠商生產一種產品，投放到市場之后得到了消費者的反饋，根據消費者的反饋，廠商對產品進一步升級，優化，從而生產出讓消費者更滿意的產品。這就是...

鄒立鵬 2019-07-31 11:30 評論0 收藏0