Teilsummenproblem

Bitte aktiviere JavaScript!
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.
 
A

Anzeige




Schau mal hier —> (hier klicken)
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:
        / 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]
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben