递归方式穷举Google方程式（javascript实现）

tianlai 发布于2019-08-19 18:02 / 1403人阅读

摘要：搜索函数第一层调用，设置第一个字符后递归调用，字符规模减少了首字符边界条件是所有的字符都设置完成，即调用回调函数，检测等式是否成立，并输出等式成立的方案。

此为《算法的乐趣》读书笔记，我用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());
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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