Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Maximale Teilsumme (Felder)

Bei der Mustererkennung in Bildern musste GrenanderUlf Grenander, Schwedischer Statistiker (* 1923) ein möglichst "helles" Rechteck ausschneiden (Anwendung z. B. Gesichtserkennung). Dabei ist er auf das folgende Problem gestoßen:

Ein Segment in einem Zahlenarray sei eine lückenlose Reihe benachbarter Elemente. Unter der Teilsumme einer Zahlenreihe versteht man die Summe aller Zahlen aus einem Segment dieser Reihe. Bei einer "maximalen Teilsumme" ist ein Segment zu suchen, dessen Teilsumme von keinem anderen Segment überstiegen werden kann.

Bestimmen Sie mittels Programm die maximale Teilsumme aus der folgenden Zahlenreihe:

-1, 2, -6, -14, 15, 12, -5, 0, 6, -6, 11, -4, -7, 1, -5, 1 

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

4 Lösung(en)

class MaxTeilSumme{
  
  public static void main (String []args){
    new MaxTeilSumme().start();
  }

  int [] x = new int [] {31,-41,59,26,-53,58,97,-93,-23,84};
  
  void start() {
    int scanMax  = 0;    
    int maxtsum  = 0; 
    int i        = 0;
    while(i < x.length) {
      if (scanMax + x[i] > 0) {
        scanMax = scanMax + x[i];
      } else {
        scanMax = 0;
      } 
      maxtsum = Math.max (maxtsum, scanMax); 
      i = i + 1;
    }
    System.out.println("Maximale Teilsumme: "+ maxtsum); 
  }
}
                
import java.text.DecimalFormat;

public class MaxTeilsumme{
   
  public static void main (String []args){
    new MaxTeilsumme().start(); }
 
  //int [] x = new int [] {31,-41,59,26,-53,58,97,-93,-23,84};
  //double [] x = new double [] {2, 5, -3, -11, -1, 18, 15,-4, 8, -2, 3, -15, 4, 5, 2, -1, -4, 4};
  double [] x = new double [] {2, 5, -3, -11, 18, 15, -2, 3, 9, -3, 14, -1, -4, 4, -2, 4};
  void start() {
    
    normalize(x);
    print(x);
    maxTeilsumme(x);
  }

 // Durchschnittswert auf 0.0 bringen
 void normalize(double[] x) {
    double sum = 0.0;
    for(double d : x) {
        sum = sum + d;  }
    double shift = sum / x.length;
    int pos = 0;
    while(pos < x.length) {
        x[pos] = x[pos] - shift;
        pos = pos + 1; }
  }
 
  void print(double[] x) {
    DecimalFormat df = new DecimalFormat("#0.0");
    System.out.println("Feld");
    for(double d: x) {
        System.out.print(df.format(d) + " "); }
    System.out.println(); }

  
  void maxTeilsumme(double [] x) {
    double scanMax  = 0;   
    double maxtsum  = 0;
    int i        = 0;
    // Indizes merken
    int _last_scan = -1, _last = -1;
    while(i < x.length) {
      if (scanMax + x[i] > 0) {
        scanMax = scanMax + x[i];
        _last_scan = i; } 
      else {
        scanMax = 0; }
      if(maxtsum < scanMax) {
          _last = _last_scan;  }
      maxtsum = Math.max (maxtsum, scanMax);
      i = i + 1;   }
    System.out.println("Maximale Teilsumme: "+ maxtsum);
    int _first = getFirstIndex(_last, maxtsum);
    System.out.println("index range: " + _first + "..." + _last); }


  int getFirstIndex(int last, double maxtsum) {
     int pos = last;
     double tmpsum = 0;
     while(pos >= 0) {
         tmpsum = tmpsum + x[pos];
         if(Math.abs(tmpsum - maxtsum) < 0.000001 ) {
             return pos;   }
         pos = pos - 1; }
     return pos; }
  
} //end class MaxTeilsumme
                
array = [-1, 2, -6, -14, 15, 12, -5, 0, 6, -6, 11, -4, -7, 1, -5, 1]
#array = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]
max = 0
summe = 0

for i in range(0, len(array) - 1):
    summe += array[i]
    for j in range(i + 1, len(array)):
        summe += array[j]
        if summe > max:
            max = summe
    summe = 0

print("Maximale Teilsumme:", max)
                

Lösung von: Peter Pan (Home Office)

Array.prototype.sum = function() {
  let s = 0;
  for (let i = 0; i < this.length; i++) s += this[i];
  return s;
}

Array.prototype.maxSubtotal = function(addIndices) {
  let max = [this.sum(), 0, this.length-1],
  i, j;
  for (i = 0; i < this.length; i++)
    for (j = 0; j < this.length; j++) {
      let tmp = this.slice(i, j+1).sum();
      if (tmp > max[0]) max = [tmp, i, j];
    }
  if (addIndices) return max;
  return max[0];
}

// ausgabe
let curMax;

curMax =
  [-1,2,-6,-14,15,12,-5,0,6,-6,11,-4,-7,1,-5,1].maxSubtotal(true);
console.log(`
  Maximale Teilsumme: ${curMax[0]} (Index ${curMax[1]}–${curMax[2]})
`);

curMax = [31,-41,59,26,-53,58,97,-93,-23,84].maxSubtotal(true);
console.log(`
  Maximale Teilsumme: ${curMax[0]} (Index ${curMax[1]}–${curMax[2]})
`);

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

Verifikation/Checksumme:

Erste Verifikation: -1, 2, -6, -14, 15, 12, -5, 0, 6, -6, 11, -4, -7, 1, -5, 1

Die Teilsumme ergibt 33 (vom 5. bis zum 11. Element).

 

Zweite Verifikation: 31, -41, 59, 26, -53, 58, 97, -93, -23, 84

Die Teilsumme ergibt 187.

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 0.5
Schwierigkeit: k.A.
Webcode: sypi-dsoh
Autor: Martin Guggisberg (Universität Basel / PH FHNW)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen