# divide and conquer



## alva (4. Apr 2007)

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 (4. Apr 2007)

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


----------



## alva (4. Apr 2007)

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 (4. Apr 2007)

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


----------



## Leroy42 (4. Apr 2007)

Lehrer hat gesagt.:
			
		

> 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 (4. Apr 2007)

Leroy42 hat gesagt.:
			
		

> Lehrer hat gesagt.:
> 
> 
> 
> ...


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 (4. Apr 2007)

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 (4. Apr 2007)

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 (4. Apr 2007)

kleiner_held hat gesagt.:
			
		

> 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 (4. Apr 2007)

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 (4. Apr 2007)

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 (4. Apr 2007)

alva hat gesagt.:
			
		

> 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 (4. Apr 2007)

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 (7. Apr 2007)

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!!!


----------

