面试题：如何使用PHP递归算法算出如下数字?

Question

请写出一个函数，计算出如下几个字母代表的数字：

AB-CD=EF
EF+GH=PPP

使用推断法算推论出的正确答案是 8-6-5-4-3-2-7-9-1，但如何使用程序来计算这个正确答案？
推论过程，首先推论出 P=1，在根据P=1推论出 F H只能是 [5,6] [4,7] [8,3]再依次推论。另外一个推论是 A C E G P 中没有一个会是0.

写的PHP函数，不过运行不出来，卡死：

for ($a = 0; $a < 10; $a++) {
    for ($b = 0; $b < 10; $b++) {
        for ($c = 0; $c < 10; $c++) {
            for ($d = 0; $d < 10; $d++) {
                for ($e = 0; $e < 10; $e++) {
                    for ($f = 0; $f < 10; $f++) {
                        for ($g = 0; $g < 10; $g++) {
                            for ($h = 0; $h < 10; $h++) {
                                for ($p = 0; $p < 10; $p++) {
                                    $arr = [$a, $b, $c, $d, $e, $f, $g, $h];
                                     if (count(array_unique($arr)) == count($arr) && $a > 0 && $c > 0 && $e > 0 && $g > 0 && $p > 0 && ($a . $b) - ($c . $d) + ($e . $h) == ($p . $p . $p)) {
                                        print_r($arr);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

Answer 1

答案貌似不唯一，下面是我计算出来的结果

95-27=68
68+43=111

86-54=32
32+79=111

85-46=39
39+72=111

Python写的代码，PHP估计稍微费事点，我这边全部跑完花了快7秒。

# t3.py

el = 'AB-CD=EF EF+GH=PPP'
ns = '123456789'

el = el.replace('=','==').replace(' ', ' and ')
vs = list(set([s for s in el if s>='A' and s<='Z']))

ns = [s for s in ns]
def fs(el, vs, ns):
    if not vs:
        if eval(el):
            print el.replace('and ', '').replace('==', '=')
    else:
        v = vs[0]
        ix = len(ns)
        while ix:
            ix -= 1
            nel = el.replace(v, ns[ix])
            fs(nel, vs[1:], ns[0:ix]+ns[ix+1:])

import time
st = time.time()
fs(el,vs,ns)
print 'time:%dms'%((time.time()-st)*1000)

输出：

95-27=68 68+43=111
86-54=32 32+79=111
85-46=39 39+72=111
time:6780ms

Answer 2

简化你的写法，

<?php
for ($a = 1; $a < 10; $a++) {
    for ($b = 1; $b < 10; $b++) {
        for ($c = 1; $c < 10; $c++) {
            for ($d = 1; $d < 10; $d++) {
                if(($a * 10 + $b) - ($c * 10 + $d) < 0){
                    continue;
                }
                for ($e = 1; $e < 10; $e++) {
                    for ($f = 1; $f < 10; $f++) {
                        if(($a * 10 + $b) - ($c * 10 + $d) !== ($e * 10 + $f)){
                            continue;
                        }
                        for ($g = 1; $g < 10; $g++) {
                            for ($h = 1; $h < 10; $h++) {
                                    for ($p=1; $p < 10; $p++) { 
                                        $arr = [$a, $b, $c, $d, $e, $f, $g, $h ,$p];
                                         if (count(array_unique($arr))==count($arr)&&($e * 10 + $f) + ($g * 10 + $h) == $p*100+$p*10+$p) {
                                            print_r($arr);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

5秒钟以内可以出结果

修改答案

for ($a = 1; $a < 10; $a++) {
    for ($b = 0; $b < 10; $b++) {
        if ($a == $b) {
            continue;
        }
        for ($c = 1; $c < 10; $c++) {
            if(count([$a,$b,$c])!==count(array_unique([$a,$b,$c]))){
                continue;
            }
            for ($d = 0; $d < 10; $d++) {
                if(count([$a,$b,$c,$d])!==count(array_unique([$a,$b,$c,$d]))){
                continue;
            }
                if(($a * 10 + $b) - ($c * 10 + $d) < 0){
                    continue;
                }
                for ($e = 1; $e < 10; $e++) {
                    if(count([$a,$b,$c,$d,$e])!==count(array_unique([$a,$b,$c,$d,$e]))){
                continue;
            }
                    for ($f = 0; $f < 10; $f++) {
                        if(count([$a,$b,$c,$d,$e,$f])!==count(array_unique([$a,$b,$c,$d,$e,$f]))){
                continue;
            }
                        if(($a * 10 + $b) - ($c * 10 + $d) !== ($e * 10 + $f)){
                            continue;
                        }
                        for ($g = 1; $g < 10; $g++) {
                            if(count([$a,$b,$c,$d,$e,$f,$g])!==count(array_unique([$a,$b,$c,$d,$e,$f,$g]))){
                continue;
            }
                            for ($h = 0; $h < 10; $h++) {
                                if(count([$a,$b,$c,$d,$e,$f,$g,$h])!==count(array_unique([$a,$b,$c,$d,$e,$f,$g,$h]))){
                continue;
            }
                                    for ($p=1; $p < 10; $p++) { 
                                        $arr = [$a, $b, $c, $d, $e, $f, $g, $h ,$p];
                                         if (count(array_unique($arr))==count($arr)&&($e * 10 + $f) + ($g * 10 + $h) == $p*100+$p*10+$p) {
                                            print_r($arr);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

时间0.553s，还是基于你的思想，只判断条件，未做任何推理

Answer 3

不要这么暴力枚举，尝试做一些剪枝。

我的想法：
1.首先枚举E, F, G, H,检查运算的结果是不是一个满足PPP形式的三位数，需要枚举的情况数是10^4. 假设通过检查的组合数是N。

2.对于第一步每一个通过检查的组合，枚举A, B, C, D的值，判断能否满足第一个等式的约束，每次需要枚举的情况数也是10^4.

这样总的运算次数是10^4 + N * 10^4，N应该是一个很小的数，很快就可以出结果。

Answer 4

小亮的答案是挺快的。。。

for ($e=2; $e < 10; $e++) { 
    for ($f=2; $f < 10; $f++) { 
        if ($e==$f) {
            continue;
        }
        for ($g=2; $g < 10; $g++) { 
            if ($g==$e ||$g==$f) {
                continue;
            }
            for ($h=2; $h < 10; $h++) { 
                if ($h==$e ||$h==$f || $h==$g) {
                    continue;
                }
                $sum = ($e+$g)*10+$f+$h;
                if ($sum == 111) {
                    for ($a=2; $a < 10; $a++) { 
                        if ($a==$e ||$a==$f || $a==$g ||$a==$h) {
                            continue;
                        }
                        for ($b=2; $b < 10; $b++) { 
                            if ($b==$e ||$b==$f || $b==$g ||$b==$h ||$b==$a) {
                                continue;
                            }
                            for ($c=2; $c < 10; $c++) { 
                                if ($c==$e ||$c==$f || $c==$g ||$c==$h ||$c==$a||$c==$b) {
                                    continue;
                                }
                                for ($d=2; $d < 10; $d++) { 
                                    if ($d==$e ||$d==$f || $d==$g ||$d==$h ||$d==$a||$d==$b||$d==$c) {
                                        continue;
                                    }
                                    if (($a-$c-$e)*10+$b-$d-$f==0) {
                                        printf("$a$b-$c$d=$e$f $e$f+$g$h=111 \n");
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
    
86-54=32 32+79=111 
85-46=39 39+72=111 
95-27=68 68+43=111 
[Finished in 0.1s]

Answer 5

php算的

85-46=39 # 39+72=111
86-54=32 # 32+79=111
90-27=63 # 63+48=111
90-63=27 # 27+84=111
95-27=68 # 68+43=111

其实这道题 可以直接出ppp=111 因为就算CD=0 AB+GH不可能大于200
这样可以少一些循环

Answer 6

你们的答案都好快...不过貌似没有一个符合要求的，要递归算法啊，递归会有堆栈操作，肯定慢很多。我这个的测试结果是13秒。

//删掉了，直接看下面最终执行的代码吧

@RobinTang 结果和你的是一致的。

无聊之下又跑了一次带0的结果，花费31秒。运行的源码如下

<?php
set_time_limit(0);
$time = time();
//测试1
function isValid1($u) {
    list($a, $b, $c, $d, $e, $f) = $u;
    return 10 * $a + $b - 10 * $c - $d - 10 * $e - $f === 0;
}
//测试2
function isValid2($u) {
    list($a, $b, $c, $d, $e, $f, $g, $h, $p) = $u;
    return 10 * $e + $f + 10 * $g + $h - 111 * $p === 0;
}
//递归求值
function foo($u, $key, &$results) {
    if (count($u) < 6) {
        $index = count($u);
        for($i = 0; $i < 10; $i ++) {
            if (! in_array($i, $u)) {
                $u[$index] = $i;
                foo($u, $key, $results);
            }
        }
    } else if (count($u) < 9) {
        if (isValid1($u)) {
            $index = count($u);
            for($i = 1; $i < 10; $i ++) {
                if (! in_array($i, $u)) {
                    $u[$index] = $i;
                    foo($u, $key, $results);
                }
            }
        }
    } else if (isValid2($u)) {
        $results[] = $u;
    }
}
//运行
$results = [];
foo([], 9, $results);
foreach ($results as $result) {
    echo implode(', ', $result) . "<br />\n";
}
echo "Time:" . (time() - $time);

3, 4, 0, 9, 2, 5, 8, 6, 1
3, 6, 0, 9, 2, 7, 8, 4, 1
4, 5, 0, 6, 3, 9, 7, 2, 1
5, 2, 0, 9, 4, 3, 6, 8, 1
5, 7, 0, 8, 4, 9, 6, 2, 1
5, 7, 0, 9, 4, 8, 6, 3, 1
7, 2, 0, 9, 6, 3, 4, 8, 1
8, 4, 0, 5, 7, 9, 3, 2, 1
8, 4, 0, 9, 7, 5, 3, 6, 1
8, 5, 0, 6, 7, 9, 3, 2, 1
8, 5, 4, 6, 3, 9, 7, 2, 1
8, 6, 5, 4, 3, 2, 7, 9, 1
9, 0, 2, 7, 6, 3, 4, 8, 1
9, 0, 6, 3, 2, 7, 8, 4, 1
9, 3, 0, 6, 8, 7, 2, 4, 1
9, 3, 0, 7, 8, 6, 2, 5, 1
9, 5, 2, 7, 6, 8, 4, 3, 1
Time:31
面试考这个你们考官你也真是强大，这东西花了我40分钟的时间。

从数学角度说，P只能是1，所以这个代码还有优化的空间。

Answer 7

<?php

$arr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ];
$v   = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ];

function f($step) {
    global $arr;
    global $v;

    if ($step == 10) {           // 取第 10 个的时候
        $num1 = $arr[1] * 10 + $arr[2];
        $num2 = $arr[3] * 10 + $arr[4];
        $num3 = $arr[5] * 10 + $arr[6];
        $num4 = $arr[7] * 10 + $arr[8];
        $num5 = $arr[9] * 100 + $arr[9] * 10 + $arr[9];

        if ($num1 - $num2 == $num3 && $num3 + $num4 == $num5) {
            echo $num1 . ' - ' . $num2 . ' = ' . $num3. '<br/>';
            echo $num3 . ' + ' . $num4 . ' = ' . $num5. '<br/>';
        }

        return;
    }

    for ($i = 0; $i <= 9; $i++) {
        if (!$v[$i]) {
            $v[$i] = 1;
            $arr[$step] = $i;
            f($step + 1);      // 前进
            $v[$i] = 0;        // 回溯
        }
    }
}

Answer 8

$nonZeroLetters = ['C', 'G'];
function generateCombinationAndHandle($alphabet, $map, $callback)
{
    global $nonZeroLetters;

    if (empty($alphabet)) {
        $callback($map);
        return;
    }

    $letter = array_pop($alphabet);

    for ($i = in_array($letter, $nonZeroLetters) ? 1 : 0; $i < 10; $i++) {
        if (in_array($i, $map) || $i === 1) continue;
        $map[$letter] = $i;
        generateCombinationAndHandle($alphabet, $map, $callback);
    }
}

generateCombinationAndHandle(['G', 'H'], [], function ($result) {
    foreach ($result as $letter => $value) {
        $$letter = $value;
    }
    $gh = $G * 10 + $H;
    $ef = 111 - $gh;
    $E = floor($ef / 10);
    $F = $ef % 10;

    $eNonEqual = [$F, $G, $H, 1];
    $fNonEqual = [$G, $H, 1];

    if (in_array($E, $eNonEqual) || in_array($F, $fNonEqual))
        return;

    generateCombinationAndHandle(['C', 'D'], [], function ($result) use ($ef, $gh, $E, $F, $G, $H) {
        foreach ($result as $letter => $value) {
            $$letter = $value;
        }
        $cd = $C * 10 + $D;
        $ab = $cd + $ef;
        $A = floor($ab / 10);
        $B = $ab % 10;

        $aNonEqual = [$B, $C, $D, $E, $F, $G, $H, 1];
        $bNonEqual = [$C, $D, $E, $F, $G, $H, 1];
        $cNonEqual = [$D, $E, $F, $G, $H];
        $dNonEqual = [$E, $F, $G, $H];
        if (
            $ab < 100 &&
            ! in_array($A, $aNonEqual) &&
            ! in_array($B, $bNonEqual) &&
            ! in_array($C, $cNonEqual) &&
            ! in_array($D, $dNonEqual)
        ) {
            echo "{$ab} - {$cd} = {$ef} + {$gh} = 111<br>";
        }
    });
});

递归生成字母与数字映射的关联数组,然后取出判断是否满足等式.

结果:
85 - 46 = 39 + 72 = 111
95 - 27 = 68 + 43 = 111
90 - 63 = 27 + 84 = 111
90 - 27 = 63 + 48 = 111
86 - 54 = 32 + 79 = 111

大概几十毫秒出结果吧

Answer 9

难道还有什么条件没看出来，结果还是不唯一!!

// P 大于等于 1
// F+H 余数 大于等于 1
function FH(){
    for($f=0;$f<=9;$f++){
        for($h=0;$h<=9;$h++){
            $p = ($f+$h)%10;
            if($p>=1){
                call_user_func('EG',$f,$h,$p);
            }
        }
    }
}

// EF+GH = PPP
function EG($f,$h,$p){
    for($e=1;$e<=9;$e++){
        for($g=1;$g<=9;$g++){
            if( intval($e.$f) + intval($g.$h) == intval($p.$p.$p) ){
                call_user_func('ABCD',$f,$h,$p,$e,$g);
            }
        }
    }
}

// AB - CD = EF
function ABCD($f,$h,$p,$e,$g){
    for($a=1;$a<=9;$a++){
        for($b=0;$b<=9;$b++){
            for($c=1;$c<=9;$c++){
                for($d=0;$d<=9;$d++){
                    if( intval($a.$b)-intval($c.$d) == intval($e.$f)
                        && count(array_unique([$a,$b,$c,$d,$e,$f,$g,$h,$p])) == 9 ){
                        echo $a.$b, '-' .$c.$d .'='.$e.$f.chr(10);
                        echo $e.$f. '+' .$g.$h .'='. $p.$p.$p.chr(10);
                        echo chr(10);
                    }
                }
            }
        }
    }

}


FH();

86-54=32
32+79=111

90-27=63
63+48=111

90-63=27
27+84=111

95-27=68
68+43=111

85-46=39
39+72=111

php -f Test.php  0.88s user 0.05s system 94% cpu 0.978 total

Answer 10

因为前面好像有答案了所以就想写个快速点的,写的比较久OTZ(一上午...doge脸
可能是公司服务器跑的比较快惹?
结果:
time:0.0034201145172119
90-63=27
27+84=111

86-54=32
32+79=111

85-46=39
39+72=111

90-27=63
63+48=111

95-27=68
68+43=111

不过感觉递归用的不伦不类_(:з」∠)_

// AB-CD=EF
// EF+GH=PPP
$start = microtime(true);
$ppp = 111;
$max_dbl = 99;
$min_dbl = 10;
$max_ef = $max_dbl - $min_dbl;
$min_ef = $ppp - $max_dbl;
$ret = [];
getRetMin2Max($min_ef, $ret);
$end = microtime(true);
echo "time:", $end - $start, PHP_EOL;

foreach ($ret as $nums) {
    echo "{$nums['ab']}-{$nums['cd']}={$nums['ef']}\n{$nums['ef']}+{$nums['gh']}=$ppp", PHP_EOL, PHP_EOL;
}

function getRetMin2Max($ef, &$ret) {
    global $ppp;
    global $max_dbl;
    global $min_dbl;
    global $max_ef;
    if($ef > $max_ef) return;

    $arrFlag = array_fill(0, 10, true);
    $arrFlag[1] = false; // 1被p占用

    // 判断传入的数字是否有效,有效时同步$arrFlag
    $isValid = function($num) use(&$arrFlag, &$min_dbl, &$max_dbl) {
        if($num >= $min_dbl && $num < $max_dbl) {
            $p2 = $num % 10;
            if($arrFlag[$p2] === false)
                return false;
            $arrFlag[$p2] = false;

            $p1 = intval($num / 10);
            if($arrFlag[$p1] === false)
                return false;
            $arrFlag[$p1] = false;
        } else if($num < $min_dbl) {
            if($arrFlag[$num] === false)
                return false;
            $arrFlag[$num] = false;
        } else { // 3位数
            return false;
        }
        return true;
    };

    if($isValid($ef)) {
        $gh = $ppp - $ef;
        if($isValid($gh)) {
            // 在剩下的有效值内暴力匹配
            for($c = 1/*c不能为0*/; $c < count($arrFlag); $arrFlag[$c] = $cFlag, ++$c) {
                $cFlag = $arrFlag[$c]; // 每次循环都要复位c,d标志
                if($isValid($c) === false) continue;
                for($d = 0; $d < count($arrFlag); $arrFlag[$d] = $dFlag, ++$d) {
                    $dFlag = $arrFlag[$d];
                    if($isValid($d) === false) continue;
                    $cd = $c * 10 + $d;
                    $ab = $ef + $cd;
                    if($ab >= $max_dbl) continue;
                    $a = intval($ab / 10);
                    $b = $ab % 10;
                    if($a === $b || $arrFlag[$a] === false || $arrFlag[$b] === false) continue;
                    $ret[] = [
                        'ab' => $ab, 
                        'cd' => $cd, 
                        'ef' => $ef,
                        'gh' => $gh
                    ];
                }
            }
        }
    }

    ++$ef;
    getRetMin2Max($ef, $ret);
}