Ankündigung

Einklappen
Keine Ankündigung bisher.

Such-Algorythmus

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • 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


  • #2
    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

    Kommentar


    • #3
      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;
          }
        }

      ?>

      Kommentar


      • #4
        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:

        Kommentar


        • #5
          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
              
          }
          ?>

          Kommentar


          • #6
            @Michigras:

            Kommentar


            • #7
              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

              Kommentar


              • #8
                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

                Kommentar

                Lädt...
                X