Such-Algorythmus

31.10.2005, 10:00

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

FloMX · 31.10.2005, 10:38

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

31.10.2005, 11:24

wie wärs damit:

PHP-Code:

  <?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;

    }

  }

 
?>

31.10.2005, 11:34

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

PHP-Code:

  <?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:

31.10.2005, 11:45

PHP-Code:

  <?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

    }

?>

31.10.2005, 11:54

@Michigras:

31.10.2005, 12:45

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

31.10.2005, 13:07

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-Code:

  <?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

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Problem bei einer Such Query	Schiedsrichter	Datenbanken	3	28.04.2008 17:10
session_start fehler? no such file found?	seejay	PHP Tipps 2006	11	10.01.2006 09:26
mkdir macht fehlermeldung ChDir: No such file	TaStEn	PHP Tipps 2005-2	3	25.09.2005 23:29
Such gutes einsteigerfreudliches Flash tutorial.. ^^		Beitragsarchiv	3	19.07.2005 16:36
Such kleine Auftrag	waltershausen	Beitragsarchiv	1	13.07.2005 22:24
Auf Such nach einem Befehl		PHP Tipps 2005-2	3	12.06.2005 20:58
include('~/files/file') --> »No such file or directory«.	tapferesschneiderlein	PHP Tipps 2005	7	14.04.2005 18:28
update auf php 5.0.4	robo47	Server, Hosting und Workstations	6	10.04.2005 19:00
Such MySQL ANLEITEUNG und Befehlsreferenz		Beitragsarchiv	5	15.11.2004 20:00
[Erledigt] Such Problem mit MySql Datenbank		PHP-Fortgeschrittene	9	25.10.2004 20:05
such nen programmierer		Beitragsarchiv	20	10.09.2004 17:21
Problem bei den Such und ersetz-Funktionen(ereg_replace)		PHP Tipps 2004	3	15.07.2004 18:10
Such Webseiten Uptime Script		PHP Tipps 2004	5	09.07.2004 21:22
[Erledigt] ich such 1einfaches Formular über Php das sachen aus einer..		PHP Tipps 2004	5	08.07.2004 23:56

31.10.2005, 10:00
Gast Beiträge: n/a	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


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

31.10.2005, 10:38
FloMX Benutzer Registriert seit: 21.01.2005 Beiträge: 34	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 __________________ Die schönsten Formulierungen sind üblicherweise auch die einfachsten. ADAM SMITH

31.10.2005, 11:24
Gast Beiträge: n/a	wie wärs damit: PHP-Code: <?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; } } ?>

31.10.2005, 11:34
Gast Beiträge: n/a	Ich denke mal die Zahlen werden nicht immer die gleiche Reihenfolge haben. Hier könnte z.B. auch stehen: PHP-Code: `<?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:

31.10.2005, 11:45
Gast Beiträge: n/a	PHP-Code: `<?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 } ?>`

31.10.2005, 12:45
Gast Beiträge: n/a	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

31.10.2005, 13:07
Gast Beiträge: n/a	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-Code: <?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