当前位置：Gxlcms > PHP教程 > 面试题：如何使用PHP递归算法算出如下数字?

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

时间：2021-07-01 10:21:17 帮助过：23人阅读

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

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

回复内容：

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

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

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

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

简化你的写法，

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，还是基于你的思想，只判断条件，未做任何推理

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

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

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

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

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

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]

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
这样可以少一些循环

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

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

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

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

\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，所以这个代码还有优化的空间。

';
            echo $num3 . ' + ' . $num4 . ' = ' . $num5. '
';
        }

        return;
    }

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

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

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

结果:
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

大概几十毫秒出结果吧

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

// 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

因为前面好像有答案了所以就想写个快速点的,写的比较久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);
}

//前提，a,b,c,d,e,f,g,p=1 互不相同
function abc($array,$start,$end){

list($a,$b,$c,$d,$e,$f,$g,$h,$p)=$array;
if(10*$a+$b-10*$c-$d==10*$e+$f){
    if(10*$e+$f+10*$g+$h==111){
        echo json_encode($array); //
输出，直接输出个数组，【a,b,c,d,e,f,g,h,p,多余项】 return ; } } for($i=$start+1;$i<$end;$i++){//交换一次位置 $array1=$array; $array1[$start]=$array[$i]; $array1[$i]=$array[$start]; abc($array1,$start+1,$end);//递归 }

}
abc([0,2,3,4,5,6,7,8,9],0,9);
这样写我试了下，挺快的，一秒以内吧

不好意思，输出错了啊，没有输出p，想输出p的话，当然输出形式你可以随便定义
把 if(10$e+$f+10$g+$h==111){
改为 if(10$e+$f+10$g+$h==111*p){
以及 abc([0,2,3,4,5,6,7,8,9],0,9);
改为 abc([0,1,2,3,4,5,6,7,8,9],0,10);

希望是你要的答案

不好意思，突然想到此代码存在错误，然后就过来改一下
（我也不知道为什么我在写项目时，还会想起这个 T_T ）
重新给出代码，以及思路

先说思路，根据题意，这题里面9个数字应该互不相同，排列组合共有10！的可能。
我们将这10个数字依次列出来，其中有一个是不需要的。
问题转换为怎么实现这10！的可能，我的答案就是交换，一次交换其中的两个数字。
于是自然而然想到递归，先判断当前情形是否满足条件，满足则输出。
当然其实这里还有个错误，此时不应该立即return，修改方法很多，比如把判断移到for后面；
【比如我初始条件就是一个正确答案，则输出一个就结束了，随便尝试改一下。】
然后将目标位$start与之后的每一位分别进行交换，目标位后移，递归，直到结束。
此时罗列出了所有的可能，只要满足判断就可以输出了，去掉时间函数，15行内搞定。
用时3秒，吧$p=1写死，如我上面做的，则可以在0.5秒内结束。
【这回大概不会有错了，继续写项目了 。。。 】

function abc($array,$start,$end){

list($a,$b,$c,$d,$e,$f,$g,$h,$p)=$array;
if(10*$a+$b-10*$c-$d==10*$e+$f){
    if(10*$e+$f+10*$g+$h==111*$p){
        echo json_encode($array)."\r\n";
        return ;
    }
}
for($i=$start;$i<$end;$i++){//只在原来基础上修改此句，$i从$start开始。
    $array1=$array;
    $array1[$start]=$array[$i];
    $array1[$i]=$array[$start];
    abc($array1,$start+1,$end);
}

}
function getMillisecond() {

list($t1, $t2) = explode(' ', microtime());
return (float)sprintf('%.0f',(floatval($t1)+floatval($t2))*1000);

}
$a=getMillisecond();
abc([0,1,2,3,4,5,6,7,8,9],0,10);
$b=getMillisecond();
echo ($b-$a)."ms";

//输出数组的最后一个数字是多余项，懒得改了
C:\Users\shentianmei\Desktop>php a.php
[3,4,0,9,2,5,8,6,1,7]
[3,6,0,9,2,7,8,4,1,5]
[4,5,0,6,3,9,7,2,1,8]
[5,2,0,9,4,3,6,8,1,7]
[5,7,0,8,4,9,6,2,1,3]
[5,7,0,9,4,8,6,3,1,2]
[7,2,0,9,6,3,4,8,1,5]
[8,4,0,5,7,9,3,2,1,6]
[8,4,0,9,7,5,3,6,1,2]
[8,5,4,6,3,9,7,2,1,0]
[8,5,0,6,7,9,3,2,1,4]
[8,6,5,4,3,2,7,9,1,0]
[9,3,0,6,8,7,2,4,1,5]
[9,3,0,7,8,6,2,5,1,4]
[9,5,2,7,6,8,4,3,1,0]
[9,0,2,7,6,3,4,8,1,5]
[9,0,6,3,2,7,8,4,1,5]
3021ms

$res = array();
for ($p=1; $p < 10; $p++) { 
    $ppp = $p*100+$p*10+$p;
    for ($ab=10; $ab < 100; $ab++) { 
        for ($gh=10; $gh < 100; $gh++) {
            if ($ab+$gh<=$ppp)
                continue;
            for ($cd=10; $cd <100 ; $cd++) { 
                if($ab-$cd<10)
                    continue;
                if ($ab+$gh-$cd == $ppp) {
                    $res[] = [$ab,$cd,$ab-$cd,$gh];
                }
             } 
        }
    }
}
//依次为AB,CD,EF,GH
print_r($res);

上班的时候写的答案,没太多时间解释,结果被点了反对...
我是因为思路和上面都不太一样,所以才写的答案,简单说下吧.
这个题没说ABCDEFGHP的范围,假设他们都是0-9的自然数,然后十位上不能是0为前提.

AB-CD=EF
EF+GH=PPP

由上面可知,只要满足AB-CD+GH=PPP即可.
楼上都是把这几个数分开来写的,我是把AB,CD,EF,GH,PPP为一个整体做的,算出来之后,再单独求ABCDEFGHP
下面的代码中$i,$k,$i-$k,$j分别代表AB,CD,EF,GH.大致就这样,希望点反对的大哥看看,指点下哪里不对,谢谢

错误代码,勿看

人气教程排行

本站所有资源全部来源于网络，若本站发布的内容侵害到您的隐私或者利益，请联系我们删除！