Hausaufgabe: Java-Programm schreiben zur Berechnung von x und y

[schumikersch]

Hallo,

habe Probleme mit folgender Aufgabe, die ich lösen muss:

Schreiben Sie ein Java-Programm Diophant.java zur Berechnung der Lösungen x und y der Gleichung
ax + by = ggT(a,b) bei gegebenen natürlichen Zahlen a > b.

Das Programm sollte die 2 statischen Methoden

berechneGGT(long a, long b) und
berechneXY(long ggt, long[] q, long k)

verwenden, um den ggT der vorgegebenen Zahlen a und b zu berechnen und die Lösungen x und y.

berechneGGT() muss die beim ggT(a,b) berechneten qi zurückgeben, den berechneten ggT und die Anzahl der Iterationen, die der Euklidische Algorithmus gebraucht hat.

berechneXY() liefert die Lösungen x und y zurück an das Hauptprogramm.

Das Hauptprogramm (main) sollte nur als Dispatcher für die Ein- und Ausgabe dienen und
die Berechnungen an die Methoden delegieren.

Die Eingabe der natürlichen Zahlen a und b soll über einen Konsolendialog erfolgen.

Achten Sie auf eine ausführliche Ausgabe!

Ich habe durch einen Krankenhausaufenthalt eine große Wissenlücke bekommen und hoffe, dass mir jemand helfen kann diese Aufgabe zu lösen!

Vielen Dank schonmal für Hilfe

 

[xip]

mmh, was kriege ich für deine Hausaufgaben?

 

[dhachim]

Dann zeig doch mal, was du bisher hast. Schwierig ist das Ganze nicht.

 

[schumikersch]

was stellst du dir denn vor?

ich hab echt noch keinen Anfang für dieses Programm ich fange im Prinzip bei Null an!

 

[ARadauer]

Ich habe durch einen Krankenhausaufenthalt eine große Wissenlücke bekommen und hoffe, dass mir jemand helfen kann diese Aufgabe zu lösen!

sehr gefährlich... Ich würde die Chance nutzen und das nachlernen... wenn du wirklich im Krankenhaus warst ist es für deinen Prof sicher keine Problem, wenn du die Übung etwas später abgiebst

Euklidischer Algorithmus ? Wikipedia das ist nich so schwer
Wenn du dir jetzt die Lösung kopierst, kommst du später wenns wirklich hart wird auf keinen Fall mehr mit...

 

[schumikersch]

ich weiss, wie man ggT ausrechnent, aber wie man das als programm schreibt weiss ich nicht.

Habe mit meinem Prof schon darüber gesprochen, hat auch einige Übungen nicht mitbewertet, aber bei dieser Übung kann ich nichts machen.

Wie könnte ich denn anfangen?
Ich weiss ja, dass mir die Lösung zu der Aufgabe nichts bringt, also rein vom verstehen her, aber es wäre doch schön, wenn mir jemand helfen könnte den Lösungsweg zu finden

 

[Wortraum]

was stellst du dir denn vor?

ich hab echt noch keinen Anfang für dieses Programm ich fange im Prinzip bei Null an!

Dann gibt es wohl auch noch nicht allzu viele Probleme, bei denen man helfen kann. Also am besten einfach mal anfangen und dann gezielt Fragen stellen.

Java wird Dir hier niemand beibringen, dafür gibt es Bücher und Dokumentationen – auch kostenlos.

 

[dhachim]

Hier haste mal n grobes Gerüst für deine Aufgabe.... jetzt ist es an dir das Ganze mit Inhalten zu füllen. Das ist nur ein Vorschlag und sicher nicht die einzige Lösung.

public class Diophant {

	public static long berechneGGT(long a, long b) {
		long lresult = 0;

		/*
		 * Hier muss dein Code hin
		 */

		return lresult;
	}

	public static long[] berechneXY(long ggt, long[] q, long k) {
		long[] lresult = new long[2];// x,y Wert darin speichern
		// [url=http://www.programmersbase.net/Content/Java/Content/Tutorial/Java/Array.htm]Tutorial / Java Grundlagen / Arrays[/url]
		/*
		 * Hier muss dein Code hin
		 */

		return lresult;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Diophant dio = new Diophant();
		/*
		 * Hier wieder dein Code...
		 * 
		 * Konsoleneingabe mit
		 * [url=http://java.sun.com/j2se/1.5.0/docs/api/java/util/Scanner.html]Scanner (Java 2 Platform SE 5.0)[/url]
		 * 
		 * Dann musste hier deine Methodenaufrufe niederschreiben.
		 */

		System.out.println("Hallo Welt!");

	}

}

 

[schumikersch]

und wie siehts damit aus?
:

package mypack;

import mypack.util.SimpleInput;

public class Diophant {

/**
*
*/
//Zählvariable für GGT Funktion
static int iter = 0;


public static long[][] berechneGGT(long a, long b)
{
long r0,r1,r2,q0;
int iterakt;
//Iterationsschritte
iter++;
iterakt=iter;

//Falls b>a dann tauschen
if(a>b)
{
r0=a;
r1=b;
}
else
{
r0=b;
r1=a;
}

//Berechnen von Faktor qo und rest r2
q0 = r0/r1;
r2 = r0%r1;

//Wenn Rest = 0 dann ist GGT gefunden
if(r2==0)
{
long temp[][]= new long[3][];
//Feld für GGT
temp[0]=new long[1];
//Array für qi's anlegen in entsprechender größe
temp[1]=new long[iter];
//Feld für Iterationen
temp[2]=new long[1];

//Formel Ausgeben
System.out.println(r0+" = "+q0+" * "+r1+" + "+r2);
//Letztes qi speichern
temp[1][iter-1]=q0;
//GGT In Temp Feld Schreiben
temp[0][0]=r1;
//Anzahl der Iterationsschritte Speichern
temp[2][0]=iter;

//Zähler zurücksetzten für erneuten aufruf
iter=0;

return temp;
}
else
{
//Formel Ausgeben
System.out.println(r0+" = "+q0+" * "+r1+" + "+r2);
//GGT Temporär speichern damit vor Rückgabe des GGT noch q0 gespeichert werden kann
long temp[][];
temp = berechneGGT(r1,r2);

temp[1][iterakt-1]=q0;
return temp;
}
}

public static long[] berechneXY(long ggt, long[] q, long k)
{
//2 Ringspeicher für X und Y
long x[] = new long[2];
long y[] = new long[2];
long ergxy[] = new long[2];
//Startwerte Initialisieren
x[0]=y[1]=1;
x[1]=y[0]=0;
System.out.println("\nBerechne X,Y:\n\n");
System.out.println("X0: "+x[0]+"\t\tY0: "+y[0]);
System.out.println("X1: "+x[1]+"\t\tY1: "+y[1]);

//Berechnung von X und Y
for(int i=0;i<k-1;i++)
{
//Xi+2=Xi-qi*Xi+1
ergxy[0]=x[i%2]- q*x[(i+1)%2];
//Yi+2=Yi-qi*Yi+1
ergxy[1]=y[i%2]- q*y[(i+1)%2];

//Ausgabe und Werte in entsprechenden Ringpuffer Speichern
System.out.println("X"+(i+2)+" = "+x[i%2]+" - "+q+" * "+x[(i+1)%2]+" = "+ergxy[0]+"\t\t\t"+"Y"+(i+2)+" = "+y[i%2]+" - "+q+" * "+y[(i+1)%2]+" = "+ergxy[1]);
x[i%2]=ergxy[0];
y[i%2]=ergxy[1];

}
return ergxy;

}

public static String[] berechneXYDio(long xs, long ys, long z, long a, long b, long ggt)
{
long c,alpha,beta;
String lsgxy[] = new String[2];
//Prüfen ob die Gleichung Diophantisch ist

if(z%ggt==0)
{
//Berechnen von Faktor c: z= c*ggt
c=z/ggt;
//Alpha berechnen a= alpha*ggt
alpha=a/ggt;
//Beta berechnen b= beta*ggt
beta=b/ggt;
//Strings für Lösungsmengen zusammensetzen
lsgxy[0]="X = "+(c*xs)+" + k*"+beta;
lsgxy[1]="Y = "+(c*ys)+" - k*"+alpha;
//System.out.println(lsgxy[0]+", "+lsgxy[1]);
return lsgxy;
}
else
{
System.out.println("Keine Diophantische Gleichung");
return lsgxy;
}
}

public static void main(String[] args) {
String lsg[];
long ggt[][];
long xy[];
long a,b,z;

a=SimpleInput.readLong("Bitte a eingeben: ");
b=SimpleInput.readLong("Bitte b eingeben: ");
System.out.println("GGT Berechnen:\n\n");

ggt=berechneGGT(a,b);

xy=berechneXY(ggt[0][0],ggt[1],ggt[2][0]);

System.out.println("X: "+xy[0]+" Y: "+xy[1]+"\n\n");

z=SimpleInput.readLong("Bitte z für Diophantische Gleichung eingeben:");

lsg=berechneXYDio(xy[0],xy[1],z,a,b,ggt[0][0]);
System.out.println(lsg[0]+ " "+ lsg[1]);
}

}

 

[schumikersch]

Hier habe ich noch Fragen zu der Aufgabe berechen ggt

Das Hauptprogramm (main) sollte nur als Dispatcher für die Ein- und Ausgabe dienen und
die Berechnungen an die Methoden delegieren.

Die Eingabe der natürlichen Zahlen a und b soll über einen Konsolendialog erfolgen.

Achten Sie auf eine ausführliche Ausgabe!


Wie soll ich das denn verstehen? Was muss ich da machen?
dann soll ich noch:

a) Bestimmen sie die Lösungsmengen der folgenden Diophantischen Gleichung:

104=x*728+y*96

b) Untersuchen Sie, ob die folgende Gleichung diophantisch ist und bestimmen Sie, falls dies der Fall ist, die allgemeine Lösungsmenge:

360=984*x+264*y


Und dann noch eine 3. Aufgabe zur Aufgabe 1 machen:

Erweitern Sie das Programm Diophant.java aus Aufgabe 1 um eine Methode berechneXYDio(long xs, long ys, long z, long a, long b, long ggt), die aus den Übergabeparametern die Lösungen der diophantischen Gleichung ax+by=z berechnet, falls die Gleichung diophantisch ist! xs und ys sind dabei die speziellen Lösungen der Methode berechneXY().

Rückgabewert der Methode an das Hauptprogramm sind 2 Strings, die die kompletten Lösungen x und y enthalten.

Die Methode braucht als Eingabe auch die rechte Seite z der Gleichung, die über einen Konsolendialog erfragt werden soll.


Ich brauche dringend Hilfe bei der Lösung der Aufgaben!
Ich weiss jetzt echt nicht weiter. Bin schon richtig am verzweifeln :-shock: