再帰 : PHPで実装

Tweet

Pocket

n個の数である数で作成できるか調べる問題を再帰で求めます。
例として 1, 3, 5が与えられたとき数9が作成できるかを考えます。
再帰で求めるとき計算量はO(2ⁿ)になります。

<?php
class Calculator
{

    private $n;
    private $a = [];
    private $selectedList = [];
    private $result = false;
    function __construct($n, $a)
    {
        $this->n = $n;
        $this->a = $a;
    }
    public function calc($i, $value, $isSelected = false, $selected = [])
    {
        if ($value === 0 && $isSelected) {
            $this->result = true;
            array_push($this->selectedList, $selected);

            return;
        }
        if ($i >= $this->n) {
            return;
        }
        array_push($selected, $i);
        $this->calc($i + 1, $value - $this->a[$i], true, $selected); // $a[$i]を選ぶ
        array_pop($selected);
        $this->calc($i + 1, $value, false, $selected); // $a[$i]を選ぶ

        return;
    }

    public function getSelectedList()
    {
        return $this->selectedList;
    }
    public function getResult()
    {
        return $this->result;
    }

}

$a = [1, 3, 5];
$o = new Calculator(3, $a);
$o->calc(0, 7);
var_dump($o->getResult());
var_dump($o->getSelectedList());