divide and conquer

[alva]

servus!

habe ne kleine aufgabe die ehrlich geht mir auf dem.......

hoffentlich kann mir dabei helfen,

und zwar:

Schreiben Sie ein Java-Programm, das eine beliebig lange Folge von n ganzen Zahlen (Typ long)
einliest und dann das Produkt der enthaltenen ungeraden Zahlen ausgibt. Das Programm soll auf
dem rekursiven Divide-and-Conquer Ansatz beruhen und mit m?oglichst wenigen Multiplikationen
auskommen. Die Zahl der aktuell ben?otigten Multiplikationen soll das Programm nach dem
eigentlichen Ergebnis ausgeben.
Geben Sie auf jeden Fall noch eine Absch?atzung der Anzahl der ben?otigten Multiplikationen ihres
Programms in Abh?angigkeit von n an im besten, schlechtesten und mittleren Fall!




vielen dank im voraus

 

[Wildcard]

Hausaufgaben werden hier nicht gelöst.
Du musst dich erstmal selbst an einem Ansatz versuchen und bei konkreten Problemen wird dir geholfen.

 

[alva]

sorry habe erst gerade gelesen ...


naja ich habe bis jetzt dass hingekriegt:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class aufgabe21{




public static void main(String[] args) {

int[] zahlen = new int[10];
int i=0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Multiplikation der ungeraden Zahlen");
System.out.println("Bitte geben Sie 10 Zahlen hintereinander ein");

try {
for (i=0; i < zahlen.length; i++){
String eing = br.readLine();
zahlen = Integer.parseInt(eing);

System.out.println("Die eingegebenen zahl ist " + (zahlen));}
} catch (IOException e) {
e.printStackTrace();

}
}
}
ich habe hingekriegt dass die angegebene zahlen gelesen wurden und bei der zenhte zahl gestoppt
ich komme ganz ehrlich nicht weiter deswegen wurde gern bissle hilfe falls es geht

 

[Der Müde Joe]

http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm

 

[Leroy42]

Das Programm soll auf dem rekursiven Divide-and-Conquer Ansatz beruhen und mit möglichst
wenigen Multiplikationen auskommen

Was ist denn das für ein Schwachsinn? :shock:

Da jede (ungerade) Zahl in das Produkt mit eingehen muß,
muß es auch mindestens soviele Multiplikationen geben
wie es (ungerade) Zahlen gibt.

Ein Divide-and Conquer – Algorithmus bringt hier überhaupt nichts.

Die Anzahl der Multiplikationen ist immer größer
oder gleich der Anzahl der Faktoren minus eins.
(Größer nur dann wenn man zwischendurch mal
mit 42 und 1.0/42 multipliziert ).

Erklär das deinem “Lehrer” mal!

 

[Lim_Dul]

Das Programm soll auf dem rekursiven Divide-and-Conquer Ansatz beruhen und mit möglichst
wenigen Multiplikationen auskommen

Was ist denn das für ein Schwachsinn? :shock:

Da jede (ungerade) Zahl in das Produkt mit eingehen muß,
muß es auch mindestens soviele Multiplikationen geben
wie es (ungerade) Zahlen gibt.

Ein Divide-and Conquer – Algorithmus bringt hier überhaupt nichts.

Die Anzahl der Multiplikationen ist immer größer
oder gleich der Anzahl der Faktoren minus eins.
(Größer nur dann wenn man zwischendurch mal
mit 42 und 1.0/42 multipliziert ).

Erklär das deinem “Lehrer” mal!

Ob man das nun iterativ oder rekursiv macht, ist immer von der Laufzeit her wurscht.

Das Problem hier kann man mit D&C lösen, wenn man will.

 

[Leroy42]

Ich würde dem Lehrer diese multAll – Methode vor den Latz knallen.

public class Test {
	static int multAll(int[] array, int anz) {
		return anz==0 ? 1 : array[anz-1] * multAll(array, anz-1);
	}
	public static void main(String args[]) {
		int[] array = {1,3,5,7,9,11,13,15};
		System.out.println(multAll(array, array.length));
	}
}

Sie multipliziert alle übergebenen Zahlen
Sie ist rekursiv
Sie arbeitet nach Divide-And-Conquer (Aufteilung in 1 und n-1 Zahlen)
Sie benötigt die geringsmögliche Anzahl an Multiplikationen

Dann würde ich mit ihm um ein Jahresgehalt wetten, daß er keine Methode
vorweisen kann, die mit weniger Multiplikationen auskommt.

(Mehr als zwei Zahlen auf einmal zu multiplizieren
gilt natürlich nicht als EINE Multiplikation)

 

[kleiner_held]

eine Folge 1, 1, 1, 1, 3, 3, 3, 3, 5, 5, 5, 5, 7, 7, 7, 7 kann man miteinander multiplizieren

- indem man jede neue Zahl mit dem vorherigen Ergebnis multipliziert (quasi linear) = 15 Multiplikationen
- man kann aber auch 1 * 3 * 5 * 7 rechnen und das Ergebnis 3 mal mit sich selbst multiplizieren = 6 Multiplikationen
- noch schneller ist man wenn man Ergebnis aus (1 * 3 * 5 * 7) einmal mit sich selbst multipliziert und das Ergebnis daraus noch einmal mit sich selbst multipliziert = 5 Multiplikationen

Nur so als Denkansatz.

@Leroy42
Dein Jahresgehalt oder meines?

 

[Leroy42]

Dein Jahresgehalt oder meines?

Du bist nicht alva's Lehrer! :bae:

Prinzipiell hast du recht aber:

1) Das gilt nicht allgemein.
2) Das hat alva's Lehrer mit Sicherheit nicht gemeint.

Ich vermute eher er hat eine rekursive Aufteilung des Arrays in jeweils
zwei gleich große Hälften gemeint, und geglaubt, dann gäbe es nur
noch ein O(ld n) großen Aufwand.

Edit: ld = logarithmus dualis (2-er Logarithmus)

 

[kleiner_held]

Ich denke schon, dass man mit Hilfe von Divide-and-Conquer und Memoization einen rekursiven Algorithmus erstellen soll, der das Problem wie gefordert loest. (Ohne Memoization haette ich jetzt auch keinen Plan)

Ob das ganze bei Multiplikationen in Hinsicht auf Performace Sinn macht sei einmal dahin gestellt.

 

[Lim_Dul]

Leute, es geht um eine Schulaufgabe. Ob da überhaupt Laufzeitbtrachtungen eine Rolle spielen, halte ich für fraglich.

Die Aufgabe soll vermutlich dazu dienen, das Prinzip, wie man einen Divide & Conquer Algorithmus schreibt, zu verdeutlichen.

 

[Leroy42]

Das Programm soll auf
dem rekursiven Divide-and-Conquer Ansatz beruhen und mit möglichst wenigen Multiplikationen
auskommen.

Und was soll das fettgedruckte dann bitte schön. Da die Anzahl der Multiplikationen
nicht verringert wird, ist das doch nur irreführend.

Ich weiß nicht wieviele Schüler jetzt verzweifelt danach suchen
mit weniger Multiplikationen auszukommen.

 

[Der Müde Joe]

bescheissen und gar nie multiplizieren

int a = 5;
int b = 20;
int res = 0;
char bits[] = Integer.toBinaryString (b).toCharArray ();

for (int i = 0; i < bits.length; i++) {
res <<= 1;  // shift
if (bits[i] == '1') res += a;
}
System.out.println (res);

zwar ohne d&c oder so
:lol:

 

[Guest]

Vielen dank an allen ich habe von alle natworten was gelernt.
habe inszwischen die aufgabe gelöst und abgegebern mal warten was der prof sagt!!!