Блог

Я пишу скрипт для равномерного распределения произвольного числа $epi в произвольное количество ячеек $dpi . epi означает концы на дюйм. dpi означает вмятины на дюйм. Есть 3 требования:

• количество ячеек должно быть уменьшено на наименьший общий коэффициент, если это возможно
  • например, 10 epi в 6 dpi должны быть представлены 5 epi в 3 dpi
• заполнение ячеек должно быть как можно более равномерным
  • например, 2-2-1 лучше, чем 3-1-1
• короткие ячейки должны быть равномерно распределены по массиву ячеек
  • например, 1-0-1-0-1 лучше, чем 1-1-1-0-0

Это то, что у меня есть до сих пор. В основном он делает то, что мне нужно, но при запуске space() метода, если его foreach цикл должен выполняться более одного раза, распределение $ epi неравномерно.

 <?php
class ReedSubstitution{

    public $epi;
    public $dpi;

    function substitute($e,$d){
        $this->epi=is_numeric($e)?$e:0;
        $this->dpi=is_numeric($d)?$d:0;
        if(empty($this->epi)||empty($this->dpi)) throw new Exception('Both desired ends per unit and available dents per unit must be specified.');

        if($this->epi%$this->dpi ==0) return array($this->epi/$this->dpi);//short circuit for easy case
        $this->unfraction();//make equivalent integers if dpi or epi are fractional
        $gcd= ($this->epi < $this->dpi) ? $this->euclid($this->epi,$this->dpi) : $this->euclid($this->dpi,$this->epi);
        $e=$this->epi/$gcd;
        $d=$this->dpi/$gcd;

        $q=floor($e/$d);//count that every dent gets
        $r=$e%$d;//extra to be spread out over array
        $reed=array_fill(0,$d,$q);
        $this->space($reed,$r);
        return $reed;
    }

protected function unfraction(){
    $emult=1;
    $dmult=1;
    if($this->epi-intval($this->epi)){ //epi has a fractional component
        list($tmp,$er)=explode('.',$this->epi);
        $emult=pow(10,strlen($er));
    }
    if($this->dpi-intval($this->dpi)){//dpi has a fractional component
        list($tmp,$dr)=explode('.',$this->dpi);
        $dmult=pow(10,strlen($dr));
    }
    $mult=($emult>$dmult)?$emult:$dmult;
    $this->epi*=$mult;
    $this->dpi*=$mult;
}

/**
 * @desc  evenly distribute remaining ends over entirety of dents
 * @param Array $reed, dents in one pattern repeat
 * @param Integer $r, remaining ends to be distributed
 */
protected function space(amp;$reed,$r){
    $c=count($reed);
    $i=0;
    $jump=($r < $c-$r) ? $r : $c-$r;//use the smallest jump possible to reduce the looping
    do{
        for($i; $i<$c; $i=$i $jump, $r--){
            if($r==0)break;
            $reed[$i]  ;
        }
        $i=array_search(min($reed),$reed);//begin next loop (if necessary) at position with fewest ends
    }while($r>0);
}    
    /**
     * @desc return greatest common divisor as determined by Euclid's algorithm
     * @param integer $large
     * @param integer $small
     * @return integer
     */
    protected function euclid($large, $small){
        $modulus=$large%$small;
        if($modulus==0) {
            return $small;
        } else if($modulus==1){
            return 1;
        } else {
            return $this->euclid($small,$modulus);//recursion
        }
    }
}
?>
  

Плохой вывод:

 $r=new ReedSubstitution();

$arr=$r->substitute(9,28);
/* BAD DISTRIBUTION
Array
(
[0] => 1
[1] => 1
[2] => 1
[3] => 0
[4] => 0
[5] => 0
[6] => 0
[7] => 0
[8] => 0
[9] => 1
[10] => 1
[11] => 1
[12] => 0
[13] => 0
[14] => 0
[15] => 0
[16] => 0
[17] => 0
[18] => 1
[19] => 1
[20] => 0
[21] => 0
[22] => 0
[23] => 0
[24] => 0
[25] => 0
[26] => 0
[27] => 1
)
*/
  

Как должно выглядеть приведенное выше распределение:

 /* GOOD DISTRIBUTION
Array
(
[0] => 1
[1] => 0
[2] => 0
[3] => 1
[4] => 0
[5] => 0
[6] => 1
[7] => 0
[8] => 0
[9] => 1
[10] => 0
[11] => 0
[12] => 1
[13] => 0
[14] => 0
[15] => 1
[16] => 0
[17] => 0
[18] => 1
[19] => 0
[20] => 0
[21] => 1
[22] => 0
[23] => 0
[24] => 1
[25] => 0
[26] => 0
[27] => 0
)
*/
  

Как я могу исправить метод, чтобы объединение, требующее более одного цикла, приводило к приемлемому распределению? space()

Я надеюсь, что это поможет или, по крайней мере, укажет вам правильное направление:

 protected function space(amp;$reed, $r)
{
    $totalReeds = count($reed);

    $f = floor($r/$totalReeds);
    $d = ($r % $totalReeds) / $totalReeds;
    $c = 0;

    for ($i = 0; $i < $totalReeds; $i  )
    {
        $add = round($f   $d   $c);
        $reed[$i]  = $add;
        $c = $c   $f   $d - $add;
    }
}
  

Однако это может привести не совсем к тому, что вы могли бы ожидать:

 Array
(
    [0] => 2
    [1] => 1
    [2] => 2
    [3] => 2
    [4] => 1
    [5] => 2
    [6] => 1
    [7] => 2
)
  

Хотя результатом является равномерное распределение.

PS Я не совсем понял реальную проблему, связанную с сайтом, с которой вы имеете дело, но я надеюсь, что правильно понял математическую концепцию.

Можете ли вы попробовать следующую функцию для пробела.

 protected function space(amp;$reed, $r)
{
        $totalReeds = count ($reed);

        $postion = floor($totalReeds/$r);

        for ($i=0; $i<=$totalReeds; $i=$i $postion, $r--) {
                if ($r <= 0) break;
                $reed[$i]  ;
        }    
} 
  

Я просто попробовал с некоторыми входными данными, и это сработало для меня. Более того, это дало мне правильный вывод для предыдущего примера, который вы привели.

Можете ли вы попробовать использовать эту функцию и сообщить мне, работает ли она для всех ваших входных данных.

— РЕДАКТИРОВАТЬ —

Попробуйте этот код.

     protected function space(amp;$reed, $r)
    {
            $totalReeds = count ($reed);

            $postion = floor($totalReeds/$r);

            $postion = $postion == 1? 2 : $postion;

            for ($i=0; $i<=$totalReeds; $i=$i $postion, $r--) {
                    if ($r <= 0) break;

                    if (isset($reed[$i])) $reed[$i]  ;
            }    
    }     
  

Надеюсь, это сработает. Я не уверен в ожидаемых результатах других входных данных, которые вы указали в своем комментарии. Поэтому я предполагаю, что следующее верно. Если я ошибаюсь, пожалуйста, опубликуйте ожидаемые результаты других входных данных.

http://ideone.com/L4fUv

С уважением,

Вау, этот код ужасен, имхо 🙂 Рекурсия для поиска общего деления, безумное использование is_numeric и intval, одно одинокое исключение и т. Д.. Архитектура класса тоже странная, я бы сделал это как статический класс.

Честно говоря, я не понял математической проблемы, поскольку все, что я нашел о ячейках и вмятинах, переплетается (я не являюсь носителем языка, поэтому мог пропустить что-то очевидное), но я думаю, что понял ваши требования (если это не строгая математическая задача).

В любом случае, я немного почистил его, поэтому я публикую полный код класса, но вы можете использовать space() отдельно, если вам это не нравится. Мой алгоритм можно сильно оптимизировать (второй цикл можно удалить), но я слишком ленив, чтобы это делать.

 class ReedSubstitution {

    private $epi;
    private $dpi;

    public function substitute($e, $d) {
        $this->epi = floatval($e);
        $this->dpi = floatval($d);

        if (empty($this->epi) || empty($this->dpi)) {
            throw new Exception('Both desired ends per unit and available dents per unit must be specified.');
        }

        //make equivalent integers if dpi or epi are fractional
        $this->unfraction();

        if ($this->epi % $this->dpi == 0) {
            return array($this->epi / $this->dpi);
        }


        $gcd = $this->euclid($this->epi, $this->dpi);

        $e = $this->epi / $gcd;
        $d = $this->dpi / $gcd;

        $r = $e % $d; //extra to be spread out over array
        $q = ($e - $r) / $d; //count that every dent gets

        $reed = array_fill(0, $d, $q);
        $this->space($reed, $r);
        return $reed;
    }

    protected function unfraction() {
        //Find fraction start position
        $epi_fract_pos = strpos($this->epi, '.');
        $dpi_fract_pos = strpos($this->dpi, '.');
        //Find fraction length
        $epi_fract_len = $epi_fract_pos ? (strlen($this->epi) - $epi_fract_pos - 1) : 0;
        $dpi_fract_len = $dpi_fract_pos ? (strlen($this->dpi) - $dpi_fract_pos - 1) : 0;
        //Calculate max fraction length
        $fraction_len = max($epi_fract_len, $dpi_fract_len);
        //Unfraction variables
        $mult = pow(10, $fraction_len);
        $this->epi*=$mult;
        $this->dpi*=$mult;
    }

    /**
     * @desc  evenly distribute remaining ends over entirety of dents
     * @param Array $reed, dents in one pattern repeat
     * @param Integer $r, remaining ends to be distributed
     */
    protected function space(amp;$reed, $r) {
        $c = count($reed);
        $base = $reed[0];
        for ($i = 0; $i < $r; $i  ) {
            $reed[$i]  ;
        }

        while ($reed[$c - 1] === $base) {
            $reed[$c] = $base;
            //Find the longest $base 1 array with least $base behind it
            $max_base_plus_size = -$c;
            $cur_base_plus_size = 0;
            $cur_base_plus_pos = array(NULL, NULL);
            $max_base_plus_pos = NULL;

            for ($i = 0; $i <= $c; $i  ) {
                if ($reed[$i] != $base) {
                    if($cur_base_plus_pos[0]===NULL) {
                            $cur_base_plus_pos[0] = $i;
                    }
                    if ($reed[$i   1] == $base) {
                        $cur_base_plus_pos[1]=$i;
                        if ($max_base_plus_size < $cur_base_plus_size) {
                            $max_base_plus_size = $cur_base_plus_size;
                            $max_base_plus_pos = $cur_base_plus_pos;
                        }
                        $cur_base_plus_size = 0;
                        $cur_base_plus_pos = array(NULL, NULL);
                    }
                    else {
                        $cur_base_plus_size  ;
                    }
                } else {
                    $cur_base_plus_size--;
                    $cur_base_plus_pos[1] = $i - 1;
                }
            }
            $insert_pos=ceil(($max_base_plus_pos[1] $max_base_plus_pos[0])/2);
            array_splice($reed,$insert_pos,0,$base);
        }
        array_splice($reed,$c);
        $reed=array_reverse($reed);//Optional, just to get the same output as you submitted
    }

    /**
     * @desc return greatest common divisor as determined by Euclid's algorithm
     * @param integer $x
     * @param integer $y
     * @return integer
     */
    protected function euclid($x, $y) {
        while ($x) {
            $temp = $x;
            $x = $y % $x;
            $y = $temp;
        }
        return $temp;
    }

}