PHP algorithm problem 1: the thief divides apples

(topic from the Internet) five people stole a pile of apples. They are going to share the stolen goods the next day. In the evening, a man slipped out. He divided all the apples into five parts, but there was one more. He threw the extra apple to the monkey in the tree and hid it with one fifth. Unexpectedly, the other four people all thought so. Like the first person, they divided the apple into five parts, threw the extra one to the monkey in the tree and stole one fifth. The next day, everyone shared the stolen goods. They also shared more than five of them and threw them to the monkey. The last man shared a share. Q: how many apples are there at least?

Assuming that the total number of apples is s, the remaining apples when the last person divided the apples are y, s/5 is a hidden share, and 1 is an apple thrown to the monkey, there is a formula y=s-s/5-1. Starting from this formula, the total number of apples distributed by the first person s is the original total number of apples, and this s is the remaining number of apples distributed by the last person until the end of the distribution. Therefore, according to this formula, we can find the final solution that conforms to this formula through circulation, so as to get the total number of apples.

Let's take a look at the simplest code:

for($s=5;;$s++){
    if($s % 5 == 1){
        $l = $s - round($s/5) - 1;
        if($l % 5 == 1){
            $q = $l - round($l/5) - 1;
            if($q % 5 == 1){
                $w = $q - round($q/5) - 1;
                if($w % 5 == 1){
                    $x = $w - round($w/5) - 1;
                    if($x % 5 == 1){
                        $y = $x - round($x/5) - 1;
                        if($y % 5 == 1){
                            echo $s;
                            exit;
                        }
                    }
                }
            }
        }
    }
}

We use recursion and closure to deal with similar problems:

class shareApples{
    private $apple_quantity; //Total number of apples
    private $men_quantity; //Total number
    public function __construct(int $men_quantity) {
        $this->men_quantity = $men_quantity;
        $this->apple_quantity = 0;
    }

    /**
     * Recursively check whether the number of apples meets the requirements
     * @param int $total Number of apples
     * @param int $num_left Number of apples remaining
     * @param int $seq Who is it now
     */
    public function share(int $total, int $num_left,  int $seq=1){
        $men_quantity = $this->men_quantity;
        if($seq <= $men_quantity && $num_left % $men_quantity == 1){
            $num_left2 = $num_left - (int)($num_left/$men_quantity) -1;
            if($num_left2 % $men_quantity == 1) {
                if($seq == $men_quantity){
                    $this->apple_quantity = $total;
                    return true;
                }else {
                    return $this->share($total, $num_left2, $seq + 1);
                }
            }
        }
        return false;
    }
    public function calc(){
        for($i=5; ; $i++) {
            $rt = $this->share($i, $i, 1);
            if($rt === true){
                $this->apple_quantity = $i;
                return $i;
            }
        }
    }

    /*
     * Calculate the minimum number of apples by closing
     */
    public function calc_closure(){
        for($i=5; ; $i++){
            $share = function (int $total, int $num_left,  int $seq=1)use(&$share){
                $men_quantity = $this->men_quantity;
                if($seq <= $men_quantity && $num_left % $men_quantity == 1){
                    $num_left2 = $num_left - (int)($num_left/$men_quantity) -1;
                    if($num_left2 % $men_quantity == 1) {
                        if($seq == $men_quantity){
                            $this->apple_quantity = $total;
                            return true;
                        }else {
                            return $share($total, $num_left2, $seq + 1);
                        }
                    }
                }
                return false;
            };
            $rt = $share($i, $i,1);
            if($rt === true){
                return $this->apple_quantity;
            }
        }
    }

    public function get(){
        return $this->apple_quantity;
    }
}
$m = new shareApples(5);
echo 'min Total: '.$m->calc().PHP_EOL;
echo 'min Total: '.$m->calc_closure().PHP_EOL;

Closures can also implement recursion However, after testing, the time consumption is twice that of direct recursion +:

$m = new shareApples(5); // 5, 6, 7, 8
$t1 = microtime(true);
echo 'min Total: '.$m->calc().PHP_EOL;
echo 'time: '.round(microtime(true) - $t1, 4).' s'.PHP_EOL;

$t1 = microtime(true);
echo 'min Total: '.$m->calc_closure().PHP_EOL;
echo 'time: '.round(microtime(true) - $t1, 4).' s'.PHP_EOL;

When the number of people is 5, the result is:

min Total: 15621
time: 0.0023 s
min Total: 15621
time: 0.0049 s

When the number of people is 6, the result is:

min Total: 279931
time: 0.041 s
min Total: 279931
time: 0.0889 s

When the number of people is 7, the result is:

min Total: 5764795
time: 0.8088 s
min Total: 5764795
time: 1.7936 s

When the number of people is 8, the result is:

min Total: 134217721
time: 18.268 s
min Total: 134217721
time: 44.3141 s

The running environment is win10+php7.2, which has not been tested under Linux.

Tags: Linux PHP

Posted by FrozNic on Tue, 31 May 2022 12:05:56 +0530