ggT,kgV

[Xpxgiga]

Ich habe nun ca. 10 Schulstunden Java hinter mir und hab einen riesen Spaß dran und bin eigentlich immer nach 5 min fertig mit den Aufgaben des Lehrers.
Nun dachte ich mir ich versuchs mit einer GFS ( Vortrag + Ausarbeitung) da ich in der Arbeit eh schon 15 von 15 Punkten hatte kann ich mir da nichts versauen.
Falsch gedacht... ich kann mit der Aufgabe nichts Anfangen und finde einfach nichts dazu im Internet.
Vllt könntet ihr mir dabei helfen und mir einen Schubs in die richtige Richtung geben =)

Bevor jemand flamed... ich möchte keine Fertiglösung, sondern einfach nur Hilfe und ein paar Erklärungen dazu...
Ich Internet finde ich nur iwelche Codes und Aufgaben für Informatikstundenten von denen ich ca 80% der benutzten Programmcodes nicht verstehe...

Aufgabe ist es ein Programm zu entwerfen und vorzustellen dass ca wie folgt aussieht:

Wählen sie die Funktion :
ggT <1>
kgV <2>
...


Das ganze soll mit Hilfe von Arrays gelöst werden...
Bis jetzt haben wir gelernt : Auslesen von Eingaben, Ausgabe von Ergebnissen etc, If-Formel...+Verschachtelung

Sachen wie Schleifen und Arrays werd ich versuchen mit selbst anzueignen...
Nur bei ggT und kgV brauche ich Hilfe.

Mein Ansatz für ggT:

Basis : Euklidischer Algorithmus:



a = 44 b = 12
Führe Anweisung so lange aus bis a >= b
44 - 12 = 32 a = a - b
32 - 12 = 20 a = a - b
20 -12 = 8 a = a- b

Schleife bricht ab

Führe Anweisung so lange aus bis b >= a

12 - 8 = 4 b = b - a

Schleife bricht ab.

Führe anweisung so lange aus bis a >= b
a = a - b
Schleife bricht sofort ab da :

a = 4 b = 4



HILLFFEEEEEEEEEEEE .... ich hab keine Ahnung wie ich mit meinen Kentnissen diese Aufgabe lösen soll.

 

[Morgyr]

Ich kenne dieses Verfahren jetzt nicht. Aber nach dem ausgedachten Verfahren von mir, ist das doch richtig oder nicht? Der ggT ist 4.

Ansonsten benutz eine for-Schleife, die von der kleinsten Zahl runter bis 1 zählt. Dann prüfst du immer den Rest, wenn du die kleinste Zahl durch die Zahl der for-Schleife teilst, auf 0. Wenn der Rest 0 ist, schaust du, ob auch ein Rest von 0 rauskommt, wenn du die größte Zahl durch die Zahl der for-Schleife teilst. Wenn beide Reste 0 sind (oder alle Reste von mehreren Zahlen 0 sind) hast du an der Stelle den ggT.
Ich nehme mal an Rest-Berechnung hattet ihr schon? Wenn nicht, brauchst du den Modulo-Operator %:

10 % 4 = 2

Falls du die for-Schleife noch nicht kennst: openbook.galileocomputing.de/javainsel7/javainsel_02_006.htm#mj5c4acfdd6417ff63b5b7ab5c7ae28f31

 

[0x7F800000]

@Morgyr:
Zum einem Schlägst du vor, den ggT durch faktorisierung zu berechnen, was schon an sich extrem langsam ist, und dann schlägst du auch noch vor, die faktorisierung mithilfe der Probedivision zu bewerkstelligen, was die langsamst denkbare faktorisierungsmethode ist, die normalerweise nicht zu Lebzeiten praktikabel ist Nicht deine schuld , wenn man nichts besseres erzählt bekommen hat, dann kommt man nicht so leicht auf die guten algorithmen, die sind weit weniger intuitiv, als probedivision.

@XpXgiga:
Das was du da angeschrieben hast ist die "geometrische" Variante, die direkt vom Euklid so aufgeschrieben wurde, wenn ich mich nicht irre. Die tut genau dasselbe wie die normale variante Mit der modulo-division, ist aber imho weniger anschaulich und schwerer hinzuschreiben. Die normale version ist dagegen denkbar kurz:

	public static long gcd(long a,long b){
		while((b=a%(a=b))>0); return a;
	}
	
	public static long lcm(long a, long b){
		return a*b/gcd(a,b);
	}

Was man da macht, ist folgende überlegung:
Sei d der größte gemeinsame teiler von a und b, d.h. d|a und d|b (das zeichen "|" steht für die teilbarkeitsrelation, also "d|a" heißt "d teilt a")
Ist a>b, so lässt sich division mit rest darauf anwenden, so dass a=fb+r wobei f irgendein ganzer faktor, und r ein rest kleiner b ist. Dann sieht man aber sofort:

d|a , d|b => d|(a-fb) <=> d|r da ja r=a-fb ist.

Also teilt der Größte gemeinsame teiler von a und b auch den rest r. Insbesondere ist
ggT(a,b)=ggT(b,r)
was ausgeschrieben dasselbe ist, wie
ggT(a,b)=ggT(b, a mod b)

Das kann man natürlich mehrfach wiederholen, dann erhält man irgendwann:
ggt(a,b)=ggt(b,a mod b)=ggt(a mod b, b mod (a mod b))=...=ggt(x,0)=x
da die zahlen in jedem Schritt ja streng monoton fallend sind, und daher irgendwann die 0 erreicht werden muss. Im letzten Schritt gilt natürlich ggt(x,0)=x , da die 0 problemlos durch alles teilbar ist.

Also sieht der Algorithmus so aus:

Eingabe: a,b
1) berechne:   rest= a mod b
2) vertausche die werte so, dass  a=b b=r  zugewiesen wird, 
mache mit 1) weiter, solange b>0 ist, ansonsten gib a raus.

in java wäre das also sowas wie

    public static long ggt(long a, long b){
		while(b>0){
			long rest=a%b;
			a=b;
			b=rest;
		}
		return a;
	}

oder kürzer aufgeschrieben, so wie oben.

Es geht aber prinzipiell noch kürzer, wenn man das rekursiv hinschreibt:

public static long gcdRecursive(long a, long b){
		return b==0?a:gcdRecursive(b,a%b);
	}

aber das ist nur "theoretisch schön", eigentlich wird da unnötig viel Speicher benötigt.

Zu diesen Implementierungen muss noch gesagt werden, dass die alle nur für Natürliche Zahlen funktionieren. Wollte man das allgemein für alle ganzen zahlen, insbesondere für die 0 korrekt machen, so müsste man vor der anwendung dieser methoden das vorzeichen umbiegen, aber das ist eher ein "bürokratisches" problem, braucht man eigentlich eh nicht allzu oft.

 

[Xpxgiga]

Hmmm... Super nett so ne ausführliche Antwort zu schreiben.
Aber verstanden habe ich leider nicht wirklich viel^^
Mein Problem liegt einfach in den mangelnden Programmierbegriffen^^
Ich müsst Rücksicht darauf nehmen dass sich meine Kentnisse auf : Schleifen,If-Formel,Eingabe und Ausgabe, + - * / beschränken...



public static long ggt(long a, long b){
while(b>0){
long rest=a%b;
a=b;
b=rest;
}
return a;
}

So ca alles fette verstehe ich nicht^^ weder long , noch die Bedeutung von "%" noch return...
Ich bin am verzweifeln...so ne Aufgabe ist mit meinen Kentnissen unlösbar -.-

Vllt könnte sich jemand erbarmen und mir Schritt für Schritt für dumme kleine Anfänger jeden einzelnen Begriff erläutern warum und wieso das da steht und was es bedeutet.

Danke für eure Geduld =)

 

[hdi]

long ist ein primitiver Datentyp, und steht für grosse natürliche Zahlen. Also sowas wie int, nur eben
für noch grössere Zahlen.

return ist ein Befehl, den man an das Ende von jeder Methode schreiben muss, die etwas zurückliefert,
d.h. in der Definition nicht ein "void" drinnen stehen hat:

public static void main(String[] args)

gibt nichts zurück (void). Aber:

public static long ggt(long a, long b)

gibt "long" zurück, d.h. also eine Variable die diesen Wert hat. Und da man der Methode auch
2 long-Parameter gibt, kann man mit ihnen rumrechnen und dann eben auch einen long returnen.
return ist eben der Befehl, mit dem man etwas zurückgeben kann.

Zurückgeben heisst nur, man könnte zB sowas machen:

long ergebnis = ggt(10,20);

und in der Variablen ergebnis würde dann das stehen, was die Methode per return zurückgibt.

Und % ist das Zeichen in Java für Modulation (mod). Das weisste ja was ist nehme ich an,
der Rest von einer Teilung mit natürlichen Zahlen.

Bsp 10%4 ergibt 2.

Was mich aber wirklich erschreckt, ist dass du auch diese Zeilen hier:

a=b;
b=rest;

fett markiert hast. Du willst mir jetzt aber nicht sagen, dass du das nicht verstehst oder Das ist eine
Zuweisung, in die Variable die links vom "=" steht, wird der Wert von dem, was rechts vom "=" steht,
hineingespeichert.

 

[Xpxgiga]

Nein a=b usw verstehe ich natürlich^^
Und der Rest ist denke ich dank der wunderbaren Erklärung auch klar...zumindest die Zeichen und deren Bedeutungen....
Nun mangelt er aber noch am Verständniss der Schleife...


public static long ggt(long a, long b){
while(b>0){
long rest=a%b;
a=b;
b=rest;
}
return a;
}


Also verstanden habe ich : anfang eben Deklaration der Werte a und b als long bla bla
Dann while-Schleife so lange wie b>0
dann Deklaration von (rest=a%b)?
Wertzuweisung (a=b)?
und (b=rest)?
(return a)?

Warum machen wir dass und wieso kommen wir dann auf den ggT einer Zahl damit?^^

Bsp für den Algorithmus mit Rest :
1071 : 1029 = 1 rest 42
1029 : 42 = 24 rest 21
42 : 21 = 2 rest 0

Somit ist 21 der größte gemeinsame Teiler von 1071 und 1029.

dh. ich soweit verstanden.... aber die genauen Zusammenhänge zwischen der Rechnung und der Programmierung ist mir etwas unklar...

 

[0x7F800000]

aaa, vorsicht...
% ist nicht mod.
"mod n" liefert immer den kanonischen resklassenrepresentant aus {0,..,n-1} zu einer natürlichen zahl n
"% n" kann dagegen auch irgendwas negatives liefern, s.d (a/b)*b+a%b=a immer erfüllt ist.
Das ist halt nicht ganz die normale mod-operation, deswegen sag ich ja: nicht über's vorzeichen stolpern

 

[0x7F800000]

@XpXGiga
naja, zumindest die rekursive variante dürfte doch vollkommen sonnenklar sein, hoffe ich mal?
Da du aber weißt, dass rekursion nur speicher frisst, solltest du das in eine schleife umschreiben wollen. Wenn du das irgendwie hinbekommen hast, fängst du an, das alles zu vereinfachen, und unnötige hilfsvariablen rauszuschmeissen, bis da eben nur die eine zeile aus der ersten variante übrigbleibt. Das in dieser form gleich beim ersten mal hinzuschreiben ist unrealistisch, aber zumindest die zweite variante sollte doch schon verständlicher sein... schnapp dir halt ein zettel und ein bleistift, und versuche die ersten paar schritte nachzuvollziehen, dann siehst du es ja...

 

[hdi]

@Andrey
und wie geht die "normale" mod-Operation in Java?

 

[0x7F800000]

naja, also, einen speziellen Operator gibt es dafür nicht.
"normales" mod würde ich wohl am ehesten irgendwie so hinschreiben

public static long mod(long a, long b){
	if(b<1) throw new IllegalArgumentException();
	long result=a%b;
	if(result<0) result+=b;
	return result;
}

aber bei der benutzung von dieser konstruktion müsste man genauso lange nachdenken und genauso aufpassen, wie beim %, also sollte man vielleicht doch lieber % benutzen, und dabei im hinterkopf behalten, dass da auch was negatives rauskommen kann.

Bei Math.abs() kann ja auch was negatives rauskommen

 

[Landei]

Bei Math.abs(Integer.MIN_VALUE) ?

 

[0x7F800000]

was'n sonst, ist doch klar

 

[Xpxgiga]

Öhm.. joa^^ gut dann hätten wir das auch geklärt^^ möchte mir jetzt jemand wieder bei meinem thema helfen?^^
Die zusammenhänge zwischen Programmierung und Rechnung ist mir immer noch nicht klar...
Und dann ist da noch das Problem des kgV...

 

[0x7F800000]

Öhm.. joa^^ gut dann hätten wir das auch geklärt^^ möchte mir jetzt jemand wieder bei meinem thema helfen?^^

ja, das ist halt der "nachteil" von boards gegenüber foren: da nerven so abschweifungen etwas mehr, ich find's trotzdem übersichtlicher

Die zusammenhänge zwischen Programmierung und Rechnung ist mir immer noch nicht klar...

dann bau in's programm eben ein paar Ausgaben ein, dass da auch zwischenergebnisse presentiert werden, und vergleich's mit dem, was du selbst auf papier ausrechnest.

Und dann ist da noch das Problem des kgV...

a*b/ggt(a,b)

welcher der beiden Operatoren * / macht denn probleme?

 

[Marco13]

Die zusammenhänge zwischen Programmierung und Rechnung ist mir immer noch nicht klar...

Ich versuch's mal:

Bsp für den Algorithmus mit Rest :
1071 : 1029 = 1 rest 42
1029 : 42 = 24 rest 21
42 : 21 = 2 rest 0


Woher wußtest du, dass du fertig bist? Ja, weil der rest==0 war. Das ist schonmal die Abbruchbedingung

while (rest > 0)
{
...
}

und was hast du so lange gemacht? Ja, immer wieder das gleiche
1071 : 1029 = 1 rest 42 // Den rest ausrechnen, der bei der Division der aktuellen Zahlen durcheinander entsteht

 rest = a % b;

1029 : 42 = 24 rest 21 // Die erste Zahl durch die zweite ersetzen, und die zweite Zahl durch den Rest ersetzen

a = b;
b = rest;

Und das war's dann eigentlich schon...

 

[Xpxgiga]

Nochmal für alle^^
Wir ham bis jetzt nicht viel mehr als Schleifen, Ein- und Ausgabe und If-Formeln behandelt^^
Auf Deutsch -> ich verstehe nichts von dem was ihr sagt xD

  a*b/ggt(a,b)

Von Diesem hier weis ich weder was es macht , noch was die klammer dahinter bringt....
Dazu kommt dass es ggt vorraussetzt...
Sinn des Programms ist es ein wie oben beschriebenes Bild zu haben:

Wähle eine Berechnung:
GGT <1>
KGV <2>
Primzahlen <3>
Programmende <4>

Das ganze soll mit arrays gelöst werden. Dass muss ich vortragen und erklären können...
Und meine Kentnisse beschränken sich auf Schleifen und If-Formeln...
Ich versuche schon seit Tagen einfach das mathematische in iwelche Schleifen zu basteln aber iwie komme ich einfach nicht weiter^^
Wäre toll wenns mir jemand am bsten so erklärt dass es auch jemand versteht der nichts von Java weis^^

 

[Xpxgiga]

ahh da kam grad die antwort von marco13^^

So verstehe ichs xD

Ok das hilft mir schonma weiter^^ ich versuchs einfach mal wenn ich Zeit hab in ein Programm zu basteln und ihr sagt mir dann ob das klappt^^

 

[0x7F800000]

Wäre toll wenns mir jemand am bsten so erklärt dass es auch jemand versteht der nichts von Java weis^^

dreifach lol^^ in dem ganzen thread hier ist noch nichts java-spezifisches vorgekommen, zumindest die zweite variante würde in jeder der Siebzig Milliarden Sprachen aus der C-Sprachfamilie auf den Buchstaben gleich aussehen, dein problem kann doch nicht an java liegen. Lass java für ein paar minuten in ruhe, und versuche den algorithmus an sich mit buntstiften und papier nachzuvollziehen... :roll:

 

[hdi]

a*b/ggt(a,b)

Von Diesem hier weis ich weder was es macht , noch was die klammer dahinter bringt....

Du weisst nicht was a*b macht?
Du weisst nicht was b/x macht?
du weisst nicht was ggt(a,b) ist?

D.h. du weisst goar nix Bitte bei Kapitel 1 anfangen und mindestens bis einschl. Kapitel 6 komplett durchlesen:
(Kapitel 4 kannst du vorerst weglasse, wenn du extrem faul bist. Aber irgendwann musst du auch das können, also
les es lieber gleich)

http://openbook.galileocomputing.de...01_001.htm#mj98617e6126cf93a8bcdf3968e311bd6f