Gesamtleistung bei Generatoren

[Zdravko]

Hallo!
Ich muss die folgende Aufgabe lösen:
"Für die Erzeugung von elektrischer Energie stehen n Generatoren zur Verfügung. Jeder Generator hat eine Leistung Pi. Um den Bedarf von Energie zu decken, werden m Generatoren eingeschaltet (m<=n) . Sie arbeiten mit einer Gesamtleistung Pges = Summe(Sj). Man braucht alle mögliche Gesamtleistungen, sortiert in einer Reihung: 0, Pges1, Pges2,. . . , Pgesmax. Versuchen Sie die Lösung zu definieren, indem Sie Algorithmus durch Reduktion anwenden. Statt Summe(Pj) ist Summe(BiPi) zu berechnen. Was ist Bi ?"


Also ich habe mir schon ein Paar Ideen ausgedacht. Die Koeffizienten vor jeder Energie sind entweder 0 oder 1. Also brauche ich alle mögliche Kombinationen als Binärdarstellung einer Zahl, die sich immer um 1 inkrementiert. Bis hier - alles klar. Jetzt kommt aber die Implementierung, wo ich Schwierigkeiten habe. Ich würde die Aufgabe folgenderweise lösen - für n Generatoren gibt es eine Menge von Summen von n-1 Generatoren, wobei der n-te Generator mit 0 multipliziert wurde. Dazu haben wir noch eine andere Menge von Summen von n-1 Generatoren, wo wir der n-te Generator addieren. Wie mache ich das? Mit Rekursion?
Mit freundlichen Grüßen
Zdravko

 

[SlaterB]

jo,
bzw. kannst auch bei 0 anfangen: ersten Generator auswählen oder nicht + Rekursion mit restlichen Generatoren

n ist in deinen letzten Sätzen unglücklich gewählt, da n schon benutzt wird,
nimm lieber k als unbestimmt Variable

beachte bei der Rekursion die unmöglichen Fälle, bei denen zu viele oder zu wenige Generatoren ausgewäht wurden,
entweder ganz am Ende oder wenn du das schlauer machst bereits während der Bearbeitung,

Beispiel:
7 von 10 Generatoren zu wählen,

* die ersten vier wurden alle nicht gewählt
-> restliche Rekursion unnötig, können eh maximal 6 werden

* die ersten acht wurden alle gewählt
-> restliche Rekursion unnötig, sind schon zu viele

 

[Zdravko]

Ok, hier sollte die Idee sein, obwohl sie nicht korrekt funktioniert

import java.util.Scanner;

public class Leistung {
	
	private static double a[];
	
	private static double reduktion(int n, double add) {
		if(n == 1) {
			return add;
		}
	        double s1 = reduktion(n-1, 0);
	        double s2 = reduktion(n-1, a[n-1]);
                return s1+s2;
	}
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = 0;
		do {
			System.out.println("Anzahl der Generatoren: ");
			n = s.nextInt();
		} while (n <= 0);
		a = new double[n];
		for(int i = 0; i < n; ++i) {
			System.out.println("Eingabe der Energie[" + i + "]:");
			a[i] = s.nextDouble();
		}
		reduktion(a.length, 0);
	}

}

 

[SlaterB]

wieso addierst du s1 und s2 zusammen was soll das bewirken?
was ist überhaupt der Rückgabewert von reduktion, was macht diese Operation?

wozu wird a[n-1] als Parameter add übergeben, welches Ziel verfolgst du damit?
dieser Parameter wird nur bei n=1 benutzt, ansonsten ignoriert,

bevor man irgendwas codet muss man sich doch ersmal klar machen,
WAS überhaupt passieren soll,
z.B. auf Papier drei Generatoren malen und alle gewünschten Lösungen und wie man die per Hand berechnen würde,

---
dazu natürlich in deinem Programm unbedingt ein Test-Array
private static double a[] = new double[] {4, 5,6};
definieren,
willst du bei jedem Test die Zahlen neu eintippen?
was hat das für einen Sinn, das stört doch extrem?
oder testest du gar nicht/ kaum?

 

[Zdravko]

O, sorry! Ich habe nur eine grobe Idee skizziert. Ich erkläre mein Gedanke.
Wir haben n Generatoren. Wir können dann alle Summen in 2 Teilmengen unterteilen - eine Menge von Summen, die ohne den letzten Generator, arbeiten, und noch eine Menge - die Summen inklusiv den letzten Generator.

Beispiel:
Sei n = 3.
Dann haben wir 2 Mengen von Summen: S1 und S2, mit:
S1 = S(n-1) + 0 (also der letzte Generator funktioniert hier nicht).
S2 = S(n-1) + a[n-1] (hier addieren wir zu jeder Summe die Leistung der letzten Generator).
...
So kommen wir bis zu n=1, wo es auch 2 mögliche Summen gibt - entweder 0, oder a[0].
Ist das schon klar?

 

[SlaterB]

jo das ist mir schon klar, dir aber anscheinend noch nicht,
da geht es um Mengen von Summen,
da weden S1 = 5 Lösungen und S2 = 4 Lösungen zu insgesamt 9 Lösungen einer neuen Aufgabe zusammengefasst,
die dann nachher einzeln ausgegeben werden können,

aber dann daraus zwei Double zu machen und die zu addieren hat damit sehr wenig zu tun

also du musst irgendwas mit Mengen machen, mit Listen von Listen arbeiten,
und wie gesagt musst du berücksichtigen was geht und was nicht geht,
im Moment machtst du (wenn es denn irgendwann mal was mit Lösungen zu tun hätte) einen binären Baum auf,
für n=8 insgesamt 2^8 =256 Lösungen mit allen denkbaren Kombination unabhängig davon, viele viele Generatoren in einer Lösung enthalten sind,
das muss also später noch rein,
im Moment versuche aber lieber erstmal zu Lösungen zu kommen,

dazu überlege dir erstmal wie eine Lösung, wie eine Konfiguration von Generatoren überhaupt aussieht,
für n Generatoren könnte ich mir ein boolean[] der Länge n vorstellen,
jeder Wert gibt an, ob Generator i dazugehört oder nicht

 

[Zdravko]

Hm, den letzten Vorschlag finde ich am einfachsten. Also für n Generatoren brauche ich ein boolean Feld aus n Elementen - die entweder 0 oder 1 sind. Dann muss ich einen Weg finden, alle mögliche Kombinationen von 1 und 0-en zu kriegen und gleichzeitig die Leistungen mit diesen Koeffizienten zu multiplizieren.
Das beste, was ich kenne, ist die reine Inkrementierung einer positiven ganzen Zahl, die binär dargestellt wird.
Wie das zu machen ist, kann ich aber nicht sagen.

 

[SlaterB]

lasse die Leistung doch mal weg,
versuche rekursiv für n=2
die vier möglichen Array zu erstellen
[0,0]
[0,1]
[1,0]
[1,1]

das geht per Reduktion,
S1 = [0],
S2 = [1],
dann jeweils 0 oder 1 anhängen, voila da sind die 4 möglichen Fälle

so das ist was ich mit 'auf Papier drei Generatoren malen und alle gewünschten Lösungen und wie man die per Hand berechnen würde' meinte..

 

[Zdravko]

Aber ich verstehe nicht wie es weitergeht. Wie bestimme ich diese Koeffizienten? Durch Rekursion?

 

[SlaterB]

na gut ist ein bisschen falsch, da ich immer vorne anfange und nicht hinten,

also nochmal: alle Lösungen für n=2,
S1 = hinten ne 0, vorne alle Lösungen für n=1
S2 = hinten ne 1, vorne alle Lösungen für n=1

so erzählst du es doch selber, hinten 0 einfügen oder a[n-1]
(=1, alle Koeffizienten sind 1, Generatorleistung kommt später)


Lösungen für n=1 sind [0] und [1]

->
S1 = hinten ne 0, vorne [0] oder [1]
S2 = hinten ne 1, vorne [0] oder [1]

->
S1 = [0][0], [1][0]
S2 = [0][1], [1][1]


für höhere n einfach Rekursion
z.B.

alle Lösungen für n=3,
S1 = hinten ne 0, vorne alle Lösungen für n=2
S2 = hinten ne 1, vorne alle Lösungen für n=2

 

[Zdravko]

Aja, aber... Wie sieht das in Java? SlaterB, du hast mich wirklich sehr viel geholfen! Ich hoffe, dass du mir noch weiter Java Kode gibst, so dass es schneller geht.

 

[SlaterB]

ich habe kein Interesse daran, dass es schneller geht
ich gebe grundsätzlich nur Tipps beim Denken, was schon schlimm genug ist,
das zu programmieren wäre dann wenigstens noch eine kleine Eigenleistung

zumal du noch überlegen solltest, ob das überhaupt der Aufgabenstellung entspricht,

 

[Zdravko]

Ich habe endlich die Binärdarstellung einer Zahl gekriegt! Jetzt muss ich eine Schleife durchlaufen bis alle Koeffizienten im boolean Feld 1 sind. Aber wo kann ich die Summen speichern, damit sie dann sortiert werden?

import java.util.Scanner;

public class Leistung {
	
	private double a[];
	private boolean b[];
	
	private void toBinary(int counter) {
		int pad = 0;
		for(;;++pad) {
			int rest = counter%2;
			b[pad] = rest == 1 ? true : false;
			if((counter/= 2) == 0)
				break;
		}
		for(int j = pad+1; j < b.length; ++j)
			b[j] = false;
	}
	
	public void reduktion() {
		
		for(int counter = 0; /*irgendwelche Bedingung*/; ++counter) {
			toBinary(counter);
			for(int i = b.length-1; i >= 0; --i)
				System.out.print(b[i] ? 1 : 0);
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = 0;
		do {
			System.out.println("Anzahl der Generatoren: ");
			n = s.nextInt();
		} while (n <= 0);
		Leistung g = new Leistung();
		g.a = new double[n];
		g.b = new boolean[n];
		for(int i = 0; i < n; ++i) {
			System.out.println("Eingabe der Energie[" + i + "]:");
			g.a[i] = s.nextDouble();
		}
		g.reduktion();
	}

}

 

[SlaterB]

du brauchst eine eigene Klasse, wo so ein Array drinsteht und die Summe der zugehörigen Generatoren,

und dann natürlich eine Liste mit ganz vielen Objekten dieser Klasse,
diese dann sortieren

 

[Zdravko]

Das Problem ist dass ich das Sortieren Algorythmus nicht kenne.

 

[SlaterB]

na dann tippe 'java sortieren' bei google ein oder ähnliches

steht auch in jedem Lehrbuch unter Sortieren,
http://www.galileocomputing.de/open...sel11_008.htm#Rxx747java11008040003941F04D1ED

bzw. hätte man schon gewußt wenn man einmal so ein Lehrbuch normal liest,
Aufgabensteller fragen ist auch nicht verboten

aber ganz ohne Denken kommt man nicht weit

 

[Zdravko]

Ich kenne die Kollektionen nicht! Wie kann ich eine Menge von Daten sortieren, wenn ich die Menge selbst nicht kenne?

 

[SlaterB]

gar nicht, deshalb lerne erst die Menge kennen

wenn du damit die Benutzung der Java-Klassen meinst
-> Lehrbuch oder intelligente Fragen stellen (alle Fragen außer 'wie geht das, ich weiß von nix')


wenn du damit die Menge der Objekte in deinem Programm meinst:
die sollst du dir doch erst generieren, die Menge von Lösungen,
also viele boolean-Arrays, dazu die Summen der zugehörigen Leistungen,
und dann sortieren,

da verstehe ich nicht wie man die 'nicht kennen' kann?

 

[Zdravko]

Hier ist mein Fortschritt:

import java.util.Scanner;

public class Leistung {
	
	private double a[];
	private boolean b[];
	
	private void toBinary(int counter) {
		int pad = 0;
		for(;;++pad) {
			int rest = counter%2;
			b[pad] = rest == 1 ? true : false;
			if((counter/= 2) == 0)
				break;
		}
		for(int j = pad+1; j < b.length; ++j)
			b[j] = false;
	}
	
	private boolean weitereKombinationen() {
		for(boolean bi: b)
			if(bi == false)
				return true;
		return false;
	}
	
	public void reduktion() {
		
		for(int counter = 0; weitereKombinationen(); ++counter) {
			toBinary(counter);
			double sum = 0;
			for(int i = b.length-1; i >= 0; --i)
				sum += a[i]*((b[i]) ? (1) : (0));
		}
	}
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = 0;
		do {
			System.out.println("Anzahl der Generatoren: ");
			n = s.nextInt();
		} while (n <= 0);
		Leistung g = new Leistung();
		g.a = new double[n];
		g.b = new boolean[n];
		for(int i = 0; i < n; ++i) {
			System.out.println("Eingabe der Energie[" + i + "]:");
			g.a[i] = s.nextDouble();
		}
		g.reduktion();
	}

}

 

[Zdravko]

Ich suche nach einer dynamischen Datenstruktur, die noch beim Einfügen eines neuen Elements, sortiert wird. :### ???:L

 

[SlaterB]

falls übersehen: da ist noch ein Post von mir um 11:34,

du brauchst keine Datenstruktur, die automatisch sortiert wird,
es reicht einmal am Ende sort() aufzurufen,
jede Datenstruktur, die automatisches sortieren unterstützt, wird sowas auch haben

meine Empfehlung: ArrayList, Collections.sort()

--------

aber bevor du dir darüber Gedanken machst, solltest du erstmal überlegen, was denn ein 'Element' ist, noch feht sowas komplett in deinem Programm,

mein Vorschlag: eine eigene Klasse, mindestens mit Platz für das boolean-Array und ein int/ double für die Summe

edit:
oder du speicherst nur die Summen als double, das geht vielleicht auch

 

[Zdravko]

Ich spüre ich komme immer näher zur Lösung... dank dir, SlaterB!

import java.util.Scanner;
import java.util.ArrayList;

public class Leistung {
	
	class Energie {
		private double energie = 0;
		
		public void addEnergie(double e) {
			energie += e;
		}
		
		public double getEnergie() {
			return energie;
		}
	}
	
	private double a[];
	private boolean b[];
	
	private void toBinary(int counter) {
		int pad = 0;
		for(;;++pad) {
			int rest = counter%2;
			b[pad] = rest == 1 ? true : false;
			if((counter/= 2) == 0)
				break;
		}
		for(int j = pad+1; j < b.length; ++j)
			b[j] = false;
	}
	
	private boolean weitereKombinationen() {
		for(boolean bi: b)
			if(bi == false)
				return true;
		return false;
	}
	
	public void reduktion() {
		ArrayList arr = new ArrayList();
		for(int counter = 0; weitereKombinationen(); ++counter) {
			toBinary(counter);
			Energie e = new Energie();
			for(int i = b.length-1; i >= 0; --i)
				 e.addEnergie(a[i]*((b[i]) ? (1) : (0)));
			arr.add(e);
		}
		
		System.out.println("Alle moegliche Kombinationen von Gesamtleistungen sind:");
		
	}
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = 0;
		do {
			System.out.println("Anzahl der Generatoren: ");
			n = s.nextInt();
		} while (n <= 0);
		Leistung g = new Leistung();
		g.a = new double[n];
		g.b = new boolean[n];
		for(int i = 0; i < n; ++i) {
			System.out.println("Eingabe der Energie[" + i + "]:");
			g.a[i] = s.nextDouble();
		}
		g.reduktion();
	}

}

 

[Zdravko]

So, vielen Dank! Nun verstehe ich nicht ob die "unique" Summen ausgegeben werden? Nach einem Sortieren könnten wir die sich wiederholende Elemente wegschmeißen, oder?

import java.util.ArrayList;
import java.util.Collections;

public class Leistung {
	
	class Energie implements Comparable {
		private double energie = 0;
		
		public void addEnergie(double e) {
			energie += e;
		}
		
		public double getEnergie() {
			return energie;
		}

		public int compareTo(Object arg0) {
			double d = energie - ((Energie)arg0).energie;
			if(d < 0)
				return -1;
			if(d == 0)
				return 0;
			return 1;
		}
		public String toString() {
			return energie + " ";
		}
	}
	
	private double a[];
	private boolean b[];
	
	private void toBinary(int counter) {
		int pad = 0;
		for(;;++pad) {
			int rest = counter%2;
			b[pad] = rest == 1 ? true : false;
			if((counter/= 2) == 0)
				break;
		}
		for(int j = pad+1; j < b.length; ++j)
			b[j] = false;
	}
	
	private boolean weitereKombinationen() {
		for(boolean bi: b)
			if(bi == false)
				return true;
		return false;
	}
	
	public void reduktion() {
		ArrayList arr = new ArrayList();
		for(int counter = 0; weitereKombinationen(); ++counter) {
			toBinary(counter);
			Energie e = new Energie();
			for(int i = b.length-1; i >= 0; --i)
				 e.addEnergie(a[i]*((b[i]) ? (1) : (0)));
			arr.add(e);
		}
		
		System.out.println("Alle moegliche Kombinationen von Gesamtleistungen sind:");
		Collections.sort(arr);
		
		System.out.println(arr);
	}
}

 

[SlaterB]

das ist eine logische Frage, was soll man dazu antworten?
ja oder nein, wenn sie drin bleiben, weiß man wieviele Kombinationen zu Summe x führen,

ansonsten wundert man sich vielleicht wieso statt erwarteter 64 Ergebnisse nur 55 erscheinen