Rechner für Zahlenmauer: Feld-Index aus Zähler bestimmen bzw. Index aus Teil einer Summe berechnen? Algorithmus?

Question

Ich möchte einen Rechner für Zahlenmauern erstellen und sitze vor einem kleinen Problem, das sich recht interessant darstellt.

Grundsätzlich haben wir eine Zahlenpyramide/Zahlenmauer:

   x
  x x
 x x x 
x x x x

Jedes Feld hat einen Index:

   0₀
  1₀ 1₁
 2₀ 2₁ 2₂ 
3₀ 3₁ 3₂ 3₃

In der Programmiersprache stehen uns meist jedoch nur Arrays zur Verfügung, die durchgängig nummeriert sind $array = array(0, 1, 2, 3, 4, 5, ...). 

Nun ist es Aufgabe, aus dem "Zähler", also zum Beispiel "5" den Index 2₂ zu ermitteln. 

1
1 2
1 2 3
1 2 3 4

Zähler:
1
2 3
4 5 6
7 8 9 10

Es ist ein Algorithmus gesucht, der aus der gegebenen 5 die Position Zeile 2, Wert 2 ermittelt. Ich vermute, hier könnten Summen helfen.

Warum brauche ich den Index? Damit ich prüfen kann, ob die drei Zahlen zusammen liegen und berechnet werden dürfen. Zum Beispiel müssen 3₂ 3₃ zusammen 2₂ ergeben, aber nicht 3₁ und 3₃. 

Ggf. mache ich es mir auch gerade zu schwer. Wenn jemand eine andere Lösungsidee hat, immer her damit!

Danke vorab.

PS: Eventuell ist die Lösung mit Hilfe von mehrdimensionalen Arrays wesentlich einfacher.

Comments

Okay, ich bin doch den Weg über mehrdimensionale Arrays gegangen.

Hier ein kleiner Auszug aus dem Quellcode: https://jsfiddle.net/cxyzwsge/

Answer 1

Soll der Benutzer in die Pyramide Zahlen eingeben und Dein Programm prüft dann, ob

Wert(0,0) = Wert(1,0) + Wert(1,1)
...
Wert(2,0) = Wert(3,0) + Wert(3,1)

usw. ist?

In der Programmiersprache stehen uns meist jedoch nur Arrays zur Verfügung, die durchgängig nummeriert sind ...

Um welche Programmiersprache geht es? Viele Sprachen bieten z.B. Strukturen oder Klassen an, in denen weitere Daten wie Zeilenindex, Spaltenindex und die Indizes der Elemente gespeichert werden können, von denen ein Element des Pyramidenbaums berechnet werden darf.

Man könnte z.B. ein Strukturarray struct Element[azahl_elemente] erstellen, wobei jedes Element einen Eintrag/Stelle in der Pyramide repräsentiert.

Jedes Element kann dann Informationen über seine eigene Position in der Pyramide sowie die Positionen der Elemente kennen, von denen es berechnet werden darf.

struct Element
{
    Zeile, Spalte // Eigene Position
    Element Element[2] // Darf von diesen Elementen berechnet werden
}

So könnte eine Initialisierung aussehen:

element_index=0;
for zeile=0 to anzahl_zeilen do
{
    Element[element_index].Zeile = zeile
    for spalte = 0; spalte < zeile+1 do
    {
        Element[element_index].Spalte=spalte;
      
        Element[element_index].Element[0].Zeile = zeile+1
        Element[element_index].Element[0].Spalte = spalte

        Element[element_index].Element[1].Zeile = zeile+1
        Element[element_index].Element[1].Spalte = spalte+1

        Wert(zeile,spalte) = Wert(zeile+1,spalte) + Wert(zeile+1,spalte+1) // Ausgabe nur für Demo-Zweck
    }  
}

https://ideone.com/M8cccj

Beste Grüße
gorgar

Comments

Vielen Dank für den Input. Ich habe mittlerweile das Ganze implementiert, und zwar in PHP, Javascript kommt später für den Rechner.

Hier ist ein Quellcode-Auszug:

// [0][0], [1][0], [1][1], [2][0], [2][1], [2][2], … 
for($i=0; $i<count($n_arr); $i++)
{
    for($k=0; $k<$rowlimit; $k++)
    {
        if($laufer<count($n_arr))
        {
            $fieldvalue = $n_arr[$laufer];
            // if not a number then empty
            if(!preg_match('/\\d/', $fieldvalue))
            {
                $fieldvalue = null;
            }
            $multi[$i][$k] = $fieldvalue;
            $laufer++;
        }
    }
    $rowlimit++;
}

// remember the array fields holding the solutions
$solutionids = [];

// var_dump($multi);
$linecount = count($multi);

// all fields we need with values
$valuefields_needed = $linecount*($linecount + 1) / 2;

// non empty fields
$valuefields_count = 0;

while($valuefields_count < $valuefields_needed)
{
    $valuefields_count = 0;
    for($i=0; $i<$linecount; $i++)
    {
        $valuefields_count += count( array_filter($multi[$i]) );
    }
    
    // var_dump($valuefields_count.' / '.$valuefields_needed);
    
    // now comes the tough part, go over multiarray and find the fields for possible additions
    for($i=0; $i<$linecount-1; $i++)
    {
        // go along fields in line 
        for($k=0; $k<=$i; $k++)
        {
            // check tripel that there are two values set
            if( count($multi[$i][$k]) + count($multi[$i+1][$k]) + count($multi[$i+1][$k+1]) == 2 )
            {
                // var_dump('calculatable: ' $i.' | '.$k);
                if(count($multi[$i][$k]) + count($multi[$i+1][$k]) == 2)
                {
                    // set value x = x + N
                    // $multi[$i+1][$k+1] = $multi[$i][$k].' - '.$multi[$i+1][$k];
                    $multi[$i+1][$k+1] = math_fractions_addsub($multi[$i][$k], $multi[$i+1][$k], '-');
                    // var_dump('A: '.$multi[$i+1][$k+1]);
                    
                    // remember index of solution for single array from [$i+1][$k+1] 
                    $fieldcount_prev = ($i+1) * ($i+1+1) / 2;
                    
                    $solutionids[] = $fieldcount_prev + $k+1;
                }
                else if(count($multi[$i][$k]) + count($multi[$i+1][$k+1]) == 2)
                {
                    // set value x = N + x
                    // $multi[$i+1][$k] = $multi[$i][$k].' - '.$multi[$i+1][$k+1];
                    $multi[$i+1][$k] = math_fractions_addsub($multi[$i][$k], $multi[$i+1][$k+1], '-');
                    // var_dump('B: '.$multi[$i+1][$k]);
                    
                    // remember index of solution for single array from [$i+1][$k+1] 
                    $fieldcount_prev = ($i+1) * ($i+1+1) / 2;
                    $solutionids[] = $fieldcount_prev + $k;
                }
                else if(count($multi[$i+1][$k]) + count($multi[$i+1][$k+1]) == 2)
                {
                    // set value N = x + x
                    // $multi[$i][$k] = $multi[$i+1][$k].' + '.$multi[$i+1][$k+1];
                    $multi[$i][$k] = math_fractions_addsub($multi[$i+1][$k], $multi[$i+1][$k+1], '+');
                    // var_dump('C: '.$multi[$i][$k]);
                    
                    // remember index of solution for single array from [$i+1][$k+1] 
                    $fieldcount_prev = ($i) * ($i+1) / 2;
                    $solutionids[] = $fieldcount_prev + $k;
                }
            }
        }
    }
} // END if($valuefields_count < $valuefields_needed)

Und hier eine erste Anwendung (Lösung von vorgegebenen Aufgaben) - Bruchmauern: https://www.matheretter.de/ab/bruch/240

Alle Brüche dort werden von dem Code berechnet.