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



## schumikersch (21. Jun 2010)

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 (21. Jun 2010)

mmh, was kriege ich für deine Hausaufgaben?


----------



## dhachim (21. Jun 2010)

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


----------



## schumikersch (21. Jun 2010)

was stellst du dir denn vor? 

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


----------



## ARadauer (21. Jun 2010)

> 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 (21. Jun 2010)

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 (21. Jun 2010)

schumikersch hat gesagt.:


> 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 (21. Jun 2010)

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 (24. Jun 2010)

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 (24. Jun 2010)

_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:_


----------

