Euklidischer Algorithmus

6 Lösungen

Anfänger - Java von Jurom - 23.10.2012 um 11:49 Uhr

Erstellen Sie ein Programm, das den größten gemeinsamen Teiler zweier natürlicher Zahlen zurückgibt.
Benutzen Sie hierzu den euklidischen Algorithmus; sowohl den klassischen, als auch den modernen.
Geben Sie zum Vergleich beide Lösungen aus.
Auf ein Exception-Handling kann verzichtet werden.

Beispiele zum Lösungslayout sind beigefügt.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von 23Java (510 Punkte) - 29.10.2012 um 09:09 Uhr

Java-Code

import java.util.Scanner;

public class EuklidAlg {
	
	static Scanner sc;
	static int a, b;
	
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		
		System.out.println("Bitte erste Zahl eingeben.");
		a = sc.nextInt();
		
		System.out.println("Bitte zweite Zahl eingeben.");
		b = sc.nextInt();
		
		System.out.println("a: " + a + "\n" +
							"b: " + b);
		
		int ggTold = euklidOld(a, b);
		System.out.println("Ergebnis klassischer Algorithmus: " + ggTold);
		
		int ggTnew = euklidNew(a, b);
		System.out.println("Ergebnis moderner Algorithmus: " + ggTnew);
	}
	
	public static int euklidOld(int a, int b) {
		if(a == 0) {
			return b;
		} else {
			while(b != 0) {
				if(a > b) {
					a = a - b;
				} else {
					b = b - a;
				}
			}
		}
		return a;
	}
	
	public static int euklidNew(int a, int b) {
		if(b == 0) {
			return a;
		} else {
			return euklidNew(b, a % b);
		}
	}

}