均等にビン：残りの間隔は不均一です
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
)
結果は均等な分布ですが。
PS私はあなたが扱っている本当のウェブサイト関連の問題をよく理解していませんでしたが、私は数学の概念を正しく把握したことを願っています。
他のヒント
スペースのために次の関数を試してみてください。
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とintvalの非常識な使用、1つの孤独な脱出などを見つけます。
正直なところ、私はそれについて数学の問題を抱えていませんでした。ビンやへこみについて見つけたものはすべて織り込まれているので（私はネイティブスピーカーではないので、明らかな何かを見逃すことができました）、私はあなたの要件を理解したと思います（これは厳格な数学の問題ではありません）。
とにかく、私はそれを少しクリーンアップしたので、完全なクラスコードを投稿しますが、気に入らない場合はSpace（）を分離できます。私のアルゴリズムは多くのことを最適化することができます（2番目のサイクルを削除できます）が、私はそれをするのが面倒すぎます。
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
