Teilsummenproblem

Diskutiere Teilsummenproblem im Hausaufgaben Forum; Aufgabe: Java Programm erstellen welches folgendes tut: 1. Eine Zahlenmenge einlesen ( Benutzer Fragen wie viele Zahlen er einlesen möchte und...

  1. Blubby0
    Blubby0 Neues Mitglied
    Aufgabe: Java Programm erstellen welches folgendes tut:
    1. Eine Zahlenmenge einlesen ( Benutzer Fragen wie viele Zahlen er einlesen möchte und dann jede Zahl einzel in einem double Array abspeichern)
    2. Alle Teilsummen berechnen und das Ergebnis welches am nächsten an Pi ist herausgeben.

    Ich komme bei der Aufgabe nicht wirklich weiter. Der erste Teil ist mir klar mit dem zweiten habe ich meine Schwierigkeiten. Als Hilfestellung habe ich folgenden Pseudocode für Menge M der Länge n:

    für alle ganzen Zahlen x von 0 bis 2^n
    für alle ganzen Zahlen i von 0 bis n
    wenn die Binärdarstellung von x an der stelle i eine 1 stehen hat
    dann
    füge M dem Ergebnis hinzu






    So weit ich das verstehe ist 2^n die Anzahl an Teilsummen von M und die soll der Algorithmus berechnen und dann vergleichen welche Teilsumme am nächsten an Pi ist. Wenn ich also eine Menge mit drei Elementen (1,2) nehme dann sind dass 4 verschiedene Teilsummen nämlich:
    0*1+0*2 ; 0*1+1*2; 1*1+0*2 ; 1*1+1*2
    So verstehe ich jetzt die dritte Zeile des Pseudocodes. Ist das so richtig?
    Ich verstehe das Prinzip des Pseudocodes nicht wirklich wenn mir das mal jemand erklären könnte wäre das super.
     
  2. Vielleicht hilft dir diese Seite hier weiter (Klick!)
  3. mihe7
    mihe7 Bekanntes Mitglied
    Du verstehst das schon richtig (im Code fehlen Indizes. Um das zu umgehen und auch der Lesbarkeit wegen solltest Du den Code so posten: [code]Dein Code[/code]).

    Du hast eine Menge mit n Elementen. Wenn Du eine Teilsumme bildest, musst Du aussuchen, welche Elemente Du in die Teilsumme aufnimmst. D. h. für jedes der n Elemente kannst Du angeben, ob es in der Teilsumme enthalten sein soll (1) oder nicht (0). Formal dargestellt
    Code (Text):

            / 1 falls M[i] in Teilsumme enthalten
    a[i] = {
            \ 0 sonst
     
    Für jede Teilsumme kann also ein binäres Wort der Länge n angegeben werden:
    a[n-1]a[n-2]...a[i]...a[2]a[1]a[0]

    Es gibt 2^n mögliche Belegungen. Diesen lassen sich die Zahlen von 0 bis einschließlich 2^(n-1) eineindeutig zuordnen. Der Code zählt jetzt x einfach von 0 bis einschließlich 2^(n-1) durch, d. h. x entspricht genau einer von 2^n möglichen Belegungen. Mit i werden einfach die a[i] (s. oben) durchgezählt.[/i][/i]
     
Thema: Teilsummenproblem

Besucher kamen mit folgenden Begriffen auf unsere Seite:

  1. teilsummen mit pi

    ,
  2. teilsummenproblem java