Such-Algorythmus

Hallo zusammen

Ich suche einen Such-Algorythmus in PHP, mit dem ich eine bestimmte Zahl als Summe innerhalb einer Zahlenmenge finden kann.

Beispiel:

Suche: 8
Menge: 1,2,5,3,10,15

Finde z.B.: 1+2+5, oder auch 5+3

Hat jemand eine Idee oder kennt jemand ein Beispiel-Skript? Ich hab bis jetzt im Netz nichts passendes gefunden.

Liebe Grüsse,
Janosh

Ich hab mal ne function erstellt, welche aber voraussetzt, dass die Zahlenmenge absteigend vorsortiert ist. (Ist ja in PHP kein Problem: z.B. mit rsort())

<?php
function finde($suchzahl, $workmenge) {
    while (true) {
        $summe = 0;
        $erstes_element = false;
        unset($used_indexes);
        foreach ($workmenge as $key => $val) {
            if ($erstes_element === false and $val > 0) {
                $erstes_element = $key;
            }
            $summe += $val;
            $used_indexes[$key] = true;
            if ($summe == $suchzahl) {
                 echo "
[b]Gefunden: [/b]";
                 foreach ($used_indexes as $k => $v) echo $workmenge[$k]." + ";
                 echo "= ".$summe;
            }
            if ($summe > $suchzahl) {
                $summe -= $val;
                unset($used_indexes[$key]);
                if ($key == $erstes_element) break;
            }
        }
        if ($erstes_element === false) {
            echo "
Keine (weiteren) Funde.";
            return;
        }    
        $workmenge[$erstes_element] = 0;
    }
}
?>

Nunja, m�glicherweise ist die Performance dieser function absolut schlecht, also falls jemand eine bessere L�sung kennt... nur her damit.

Gruss,
Janosh

Danke für eure bisherigen Antworten.
@Michigras: Wäre schön, wenns so einfach wär. Aber es sollen ja die Summen gefunden werden, nicht einzelne Werte.

@betterknower: Das Skript funktioniert nicht immer, z.B. wenn Werte summiert werden müssten, die nicht aufeinanderfolgend sind.

@karl-150: Schade, dass du grad keine Lust hast Hab mir schon überlegt, ob es was bringt, das Array im Vorfeld nach Grösse zu sortieren.

Gruss
Janosh

@Michigras:

<?php
    $a=array(3,4,5,6,77,6,5,4,3,33,4,5,3,4);
    $suche=6;
    if(in_array($suche, $array))
    {
        //Wenn ja
    }
    else
    {
        //Wenn nicht
    }
?>

Ich denke mal die Zahlen werden nicht immer die gleiche Reihenfolge haben. Hier könnte z.B. auch stehen:

<?php
$a = array(1,2,3,5,10,15);
?>

Hab gerade aber leider keine Lust nach einer besseren Methode zu suchen. Vielleicht später... :wink:

wie wärs damit:

<?php
  $a = array(1,2,5,3,10,15);
  $suchzahl = 8;
  $alength = count($a);

  for($i = 0; $i < $alength; $i++)
  {
    $l = 1;
    while($i + $l <= $alength)
    {
      $atest = array_slice($a, $i, $l++);
      $sum = array_sum($atest);
      if($sum == $suchzahl)
      {
        echo "

Suchzahl gefunden:
";
        var_dump($atest);
      }
      else if($sum > $suchzahl)
        break;
    }
  }

?>

[FloMX]

Hi,

Eine vordefinierte Suchfunktion stellt Php sofern ich weiß nicht bereit.
Ein kleiner Lösungsansatz wäre doch, dass Zahlen welche 8 ergeben können <= 8 sein müssen, demnach kommen 0,1,2,3,4,5,6,7,8 in Frage.
suchst du nun nach diesen zahlen in einem array, kannst du alle möglichen Additions-Gleichungen aufstellen.

Hoffe, dass hilft dir weiter...
Gruß Flo