Комбинаторика, нахождение слагаемых по сумме

Я начинал свой программистский путь с выполнения лаб по Delphi для друга и желания замутить свой футбольный менеджер. С первым у меня всё получилось, и товарищ благополучно отстрелялся, а с футбольным менеджером не вышло и вряд ли получится, потому что я теперь осознаю что не смогу сделать графический показ матча, как у конкурентов. Но у той мечты есть положительный момент — я столкнулся с комбинаторикой.

Вот один из примеров, служит для нахождения слагаемых по известной сумме. Алгоритм вроде бы не совсем мой, а переписан с варианта на pascal.

$parts = array(0, 1, 2, 3, 4, 5, 7, 8, 9);
rsort($parts);
$sum = 23;
var_dump(findSummand($sum, $parts));
function findSummand($sum, $parts, $depth = 0) {
    static $args = array();
    foreach ($parts as $k => $part) {
        if ($part == $sum) {
            $args[$depth] = $part;
            return true;
        }
        if ($part < $sum) {
            $args[$depth] = $part;
            if (findSummand($sum - $part, array_slice($parts, $k + 1), $depth + 1)) {
                if ($depth == 0) {
                    return $args;
                }
                return true;
            }
        }
    }
    if ($depth == 0) {
        return 'Решение не найдено';
    }
}

Этот алгоритм остался бы у меня в закромах, если бы не случайный вопрос на форуме phpclub. Да и руки давно не доходили до блога, решил совместить.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *