PHP: Коды Грея и задачи перебора

260

10 декабря 2017, 12:43

Ребята помогите решить следующую задачу:

Надо было написать алгоритм перебора **Кода Грея: **

Но поскольку небыло времени вспоминать как работают с двоичными системами и.т.д, то написал по логике которая походу много памяти сожрала и тест не прошел.Но очень хочется решить его на PHP.

function collect($n = 3){
    $result = ["0", "1"];
    for($i = 1; $i < $n; $i++)
    {
        $default = $result;
        $count = count($result);
        for($j = 0; $j < $count; $j++) {
            $result[] = "0{$default[$j]}";
        }
        for($k = $count - 1; $k >= 0; $k--) {
            $result[] = "1{$result[$k]}";
        }
    }
    $result = array_unique($result);
    $output = array_slice($result, -$n);
    return implode(PHP_EOL, $output);
}
var_dump(collect());

Answer 1

Честно говоря подсмотрел ответ на java , и перебрал его на PHP. :)

function  Gray2($n){
    for($k= 1<<$n; --$k>=0;)
    {
        $s=$k^($k>>1);
        for($i = 0; $i < $n; $i++) printf("%d",($s>>$i)&1);
        printf("\n");
    }
}
echo Gray2(2);