събота, 4 декември 2010 г.

Задача 2 - числа и комбинации

Задача 2 - PHP
За числата 2,4,6,8 и операциите +, -, *, / намерете комбинацията от числата, операциите и произволен борй скоби, която да е валиден математически израз с решение 25.

<?php
$num = array(2,4,6,8);

function($x,$y){return $x+$y;},
  '-' => function($x,$y){return $x-$y;},
  '*' => function($x,$y){return $x*$y;},
  '/' => function($x,$y){return $x/$y;},
);

function calc($x, $y, $op){
  return $op($x,$y);
}

function recurse($level, $sum, $exp){
  global $num;
  global $op;
  if ($level == 4){
    if ($sum == 25){
      echo $exp."\n";
      die();
    }
    return;
  }
  $level++;
  foreach($num as $n){
    foreach($op as $s => $o){
      if (!($sum == 0 && $s == '/')){
        recurse ($level, calc($n, $sum, $o), '('.$n.$s.$exp.')');
      }
    }
  }
}

recurse(0,0,'');
?>


Използваме рекурсия за да обходим всички числа и операции. Методът не е е най-ефективен защото ползва евристично търсене но за толкова малко комбинации това не е проблем. Скрипта изисква PHP 5.3+ заради анонимните функции. За по-стари версии могат да се промени дефиницията им или да се ползва case за определяне на операцията.

~> php 02_chisla_operacii.php 
(4*(6+(2/(8+))))

Няма коментари:

Публикуване на коментар