bin均匀：剩余的间距不平坦
https://stackoverflow.com/questions/7811075
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在编写一个脚本以平均为一个任意号码 $epi 进入任意数量的垃圾箱 $dpi. 。 EPI代表每英寸的末端。 DPI表示每英寸凹痕。有3个要求：
- 如果可能
- 例如，6 dpi中的10个EPI应由3 dpi中的5 EPI代表
- 垃圾箱种群应尽可能统一
- 例如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(&$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(&$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
)
虽然结果是偶数分布。
附言：我不太了解您处理的实际网站相关问题，但我希望我能正确掌握数学概念。
其他提示
您可以尝试以下空间功能吗？
protected function space(&$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(&$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]++;
}
}
我希望这有效。我不确定您在评论中所说的其他意见的预期结果。因此，我认为以下内容是正确的。如果我错了，请发布其他输入的预期结果。
问候，
哇，这个代码是可怕的，恕我直言:)递归是为了找到常见的分区，疯狂地使用is_numeric and intval，一个孤独的execteption等。课堂架构也很奇怪，我会作为静态类做到这一点。
老实说，我没有得到数学问题，因为我发现的关于垃圾箱和凹痕的所有内容都在编织（我不是母语的人，所以我可能会错过一些明显的东西），但是我想我理解了您的要求（如果是不是严格的数学问题）。
无论如何，我对其进行了一些清理，因此我发布了完整的类代码，但是如果您不喜欢它，则可以分开使用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(&$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;
}
}
不隶属于 StackOverflow
