代码如下
<?php
//农夫 狼 羊 菜
/*
每次的操作可能是
a.-农夫-另一个元素
b.+农夫+另一个元素
c.-农夫
d.+农夫
A是农夫
B是狼
C是羊
D是菜
*/
$leftBank = 'ABCD';
$rightBank = '';
//设定函数检查是否会用餐
function ifEat($str) {
//true表示会发生用餐
//没有羊肯定为false
//只有羊也为false
//有羊且有农民为false
//其他返回true
if (!strstr($str, 'C')) {
$result = false;
} else {
if ($str === 'C') {
$result = false;
} elseif (strstr($str, 'C') && strstr($str, 'A')) {
$result = false;
} else {
$result = true;
}
}
return $result;
}
$steps = 0;
$log = []; //记录每步棋
$circles = 0;
while ($leftBank != '') {
$c = mt_rand(1, 8);
switch ($c) {
case 1: //农夫带狼去右岸
$leftBankTmp = str_replace('A', '', $leftBank);
$leftBankTmp = str_replace('B', '', $leftBankTmp);
$rightBankTmp = $rightBank . 'AB';
$logOpTmp = '农民和狼 去右岸';
break;
case 2: //农夫带菜去右岸
$leftBankTmp = str_replace('A', '', $leftBank);
$leftBankTmp = str_replace('D', '', $leftBankTmp);
$rightBankTmp = $rightBank . 'AD';
$logOpTmp = '农民和菜 去右岸';
break;
case 3: //农夫带羊去右岸
$leftBankTmp = str_replace('A', '', $leftBank);
$leftBankTmp = str_replace('C', '', $leftBankTmp);
$rightBankTmp = $rightBank . 'AC';
$logOpTmp = '农民和羊 去右岸';
break;
case 4: //农夫独自去右岸
$leftBankTmp = str_replace('A', '', $leftBank);
$rightBankTmp = $rightBank . 'A';
$logOpTmp = '农民 去右岸';
break;
case 5: //农夫带狼来左岸
$rightBankTmp = str_replace('A', '', $rightBank);
$rightBankTmp = str_replace('B', '', $rightBankTmp);
$leftBankTmp = $leftBank . 'AB';
$logOpTmp = '农民和狼 去左岸';
break;
case 6: //农夫带羊来左岸
$rightBankTmp = str_replace('A', '', $rightBank);
$rightBankTmp = str_replace('C', '', $rightBankTmp);
$leftBankTmp = $leftBank . 'AC';
$logOpTmp = '农民和羊 去左岸';
break;
case 7: //农夫带菜来左岸
$rightBankTmp = str_replace('A', '', $rightBank);
$rightBankTmp = str_replace('D', '', $rightBankTmp);
$leftBankTmp = $leftBank . 'AD';
$logOpTmp = '农民和菜 去左岸';
break;
default: //农夫自己来左岸
$rightBankTmp = str_replace('A', '', $rightBank);
$leftBankTmp = $leftBank . 'A';
$logOpTmp = '农民 去左岸';
break;
}
$strlen = strlen($leftBankTmp) + strlen($rightBankTmp);
if (!($strlen !== 4 || ifEat($leftBankTmp) || ifEat($rightBankTmp))) {
$leftBank = $leftBankTmp;
$rightBank = $rightBankTmp;
$steps++;
// $log[$steps]['op']='-AB';
$log[$steps]['op'] = $logOpTmp;
$log[$steps]['state'] = $rightBank;
$log[$steps]['mark'] = '';
if ($rightBank === '') {
$steps = 0;
$log = [];
}
}
$circles++;
}
$m = sizeof($log);
for ($n = 1; $n <= $m; $n++) {
for ($p = $n + 2; $p <= $m; $p++) {
// for ($p = $m; $p >=$n+2; $p--) {
if ($log[$n]['mark'] === 'marked') {
break;
}
$leftState = str_split($log[$n]['state']);
$rightState = str_split($log[$p]['state']);
asort($leftState);
asort($rightState);
$leftState = array_values($leftState);
$rightState = array_values($rightState);
if ($leftState === $rightState) {
for ($x = $n + 1; $x <= $p; $x++) {
$log[$x]['mark'] = 'marked';
$circles++;
}
}
$circles++;
}
$circles++;
}
for ($n = 1; $n <= $m; $n++) {
if ($log[$n]['mark'] === 'marked') {
unset($log[$n]);
}
$circles++;
}
?>
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
<style type="text/css">
*{
font-size:20px;
}
</style>
</head>
<body>
<p>题目:农民要把狼, 羊, 菜 从左岸运到右岸, 只有农民能划船, 每次只能运1个东西; 没有农民看着, 狼会吃羊, 羊会吃菜.求解运送方案.</p>
<p>解答</p>
<?php
$log = array_values($log);
echo " <span style=\"color:blue\">原有</span>: 左岸: 农民 狼 羊 菜<br>";
echo " 右岸: <br>";
echo "<br>";
foreach ($log as $k => $v) {
$abcd = ['A', 'B', 'C', 'D'];
$stepNew = $k + 1;
$r_state = str_split($v['state']);
asort($r_state);
$l_state = array_diff($abcd, $r_state);
$tt = ['A' => '农民', 'B' => '狼', 'C' => '羊', 'D' => '菜'];
$leftStateWords = '';
$rightStateWords = '';
foreach ($l_state as $vv) {
$leftStateWords = $leftStateWords . $tt[$vv] . ' ';
$circles++;
}
foreach ($r_state as $vv) {
$rightStateWords = $rightStateWords . $tt[$vv] . ' ';
$circles++;
}
echo "第{$stepNew}步: {$v['op']}<br>";
echo " <span style=\"color:blue\">结果</span>: 左岸: $leftStateWords<br>";
echo " 右岸: $rightStateWords<br>";
echo "<br>";
$circles++;
}
echo "共使用{$circles}次循环.";
?>
</body>
</html>