# brüche kürzen/erweitern



## DarkSean (17. September 2005)

jo hab mich ma so im forum umgeschaut aber nichts gefunden und das was bei google stand hab ich nicht verstanden, wie kürzt man denn nen normale brüche?


----------



## hpvw (18. September 2005)

Vielleicht helfen Dir zwei Methoden, die ich mal für eine Java-Bruch-Klasse geschrieben habe. Du müßtest sie dann natürlich auf VB portieren. Das sollte aber nicht weiter schwierig sein.
	
	
	



```
public static long greatestCommonDivisor(
		long _numerator,
		long _denominator) {
		long a = Math.abs(_numerator);
		long b = Math.abs(_denominator);
		if (a == 0 || b == 0) {
			if (a == 0) {
				a = 1;
				b = 1;
			}
		} else {
			while (a != b) {
				if (a > b)
					a -= b; //a = a -b
				else
					b -= a; //b = b - a
			}
		}
		return a;
	}

	private void reduce() {
		long a = greatestCommonDivisor(this.numerator, this.denominator);

		this.numerator = this.numerator / a;
		this.denominator = this.denominator / a;

		if (this.numerator == 0) {
			this.denominator = 1;
		}

		if (this.denominator < 0) {
			this.numerator *= -1;
			this.denominator *= -1;
		}
	}
```
Ist alles leider etwas uneinheitlich und unkommentiert. Was da gerechnet wird dürfte ersichtlich sein, warum das (mit dem größten gemeinsamen Teiler) funktioniert kann ich Dir aber nicht erklären.

Gruß hpvw


----------



## DarkSean (18. September 2005)

für mich ist das leider nicht ersichtlich *grml*
könntest du mir den ersten weg nur in rechenoperationen nochmal wiedergeben?


----------



## hpvw (18. September 2005)

Ich versuche mich mal in Pseudo-Code:
	
	
	



```
Numerator: Zähler
Denominator: Nenner
a, b: Hilfsvariablen
gcd: Greatest Commen Divisor, größter gemeinsamer Teiler
-------------------------------------------------
# a und b sind jeweils der Betrag von Zähler und Nenner:
a := | Numerator |
b := | Denominator |

# Wenn a gleich 0 oder b gleich 0
IF  a = 0 OR b = 0
    # Wenn a gleich 0
    IF a = 0
        # Setze a gleich 1
        a := 1
        # Und setze b gleich 1
        b := 1
    END IF
ELSE 
    # a ist ungleich 0 und b ist ungleich 0
    # Solange a ungleich b
    WHILE a != b
        # Wenn a größer als b
        IF a > b
            # Setze a gleich a minus b
            a := a - b
        ELSE
            # Ansonsten setze b gleich b minus a
            b := b - a
        END ELSE
    END WHILE
END ELSE

# Der größte gemeinsame Teile ist gleich a
gcd := a

# Teile Zähler und Nenner durch den größten gemeinsamen Teiler
Numerator = Numerator / gcd
Denominator = Denominator / gcd

# Numerator und Denominator kennzeichnen jetzt
# den gekürzten Bruch
```
Gruß hpvw


----------



## DarkSean (21. Oktober 2005)

nun ja, mit dem ansatz konnte ich nicht anfangen, aber jetzt hat unser infolehrer irgendwas von div und mod zum kürzen gelabert, wie kann ich denn damit kürzen, bzw. erweitern?


----------



## hpvw (21. Oktober 2005)

Du könntest mit modulo (Rest der Division) auf äußerst ineffiziente Weise durch probieren ermitteln, durch welche Zahlen beide Teile des Bruchs teilbar sind. Vielleicht gibt es auch einen effizienten Algorithmus, der mit modulo arbeitet, dann ist er mir aber nicht bekannt.

Die Probiervariante in Pseudo-Code:
	
	
	



```
Numerator: Zähler
Denominator: Nenner
a,b: Hilfsvariablen
i: Laufvariable
gcd: Greatest Commen Divisor, größter gemeinsamer Teiler
-------------------------------------------------
# a und b sind jeweils der Betrag von Zähler und Nenner:
a := | Numerator |
b := | Denominator |
gcd:=0
# Wenn Zähler gleich Nenner, ist der größte 
# gemeinsame Teiler klar.
if (a=b) 
  gcd:=a
end if
# i ist das abgerundete Maximum aus Zähler bzw. Nenner durch 2
# es kann keinen gemeinsamen Teiler geben, 
# der größer als dieser Wert ist, außer Zähler und
# Nenner sind gleich.
i:=floor(max(a/2,b/2))
while (gcd=0 and i>0)
    # wenn a und b durch i teilbar sind (die Division keinen Rest
    # ergibt), hast du den größten gemeinsamen Teiler gefunden, 
    # spätestens bei i=1
    if ((a mod i)=0 and (b mod i)=0)
        gcd:=i
    end if
    i:=i-1
end while
```
Theoretisch ist die Bedingung i>0 im while-Kopf sogar überflüssig.

Gruß hpvw


----------



## DarkSean (18. November 2005)

Heute hat es unser Info-Lehrer es uns gezeigt, ich trag den Code mal hier ein.

```
weiter: z = z1 * n2 + z2 * n1
        n = n1 * n2
    I = 0
        While z Mod (n - I) <> 0 Or n Mod (n - I) <> 0
            I = I + 1
        Wend
            ggt = n - I
        Text3.Text = z / ggt
        Text4.Text = n / ggt
```
z=Zähler des Ergebnisses
n=Nenner des Ergebnisses
z1=Zähler des ersten Summanden
n1=Nenner des ersten Summanden
z2=Zähler des zweiten Summanden
n2=Nenner des zweiten Summanden

Ist dieser Code für dich effizent o. ineffizent?


----------



## hpvw (18. November 2005)

Ich würde behaupten, dass dieser Algorithmus noch ineffizienter ist, als der von mir als ineffizient gepostete.
In meinem vermutete ich übrigens noch einen Fehler. Ich habe zur Korrektur oben das "min" durch ein "max" ersetzt und prüfe, ob die Zahlen gleich sind.
Wenn nämlich eine der Zahlen gleich der Hälfte der anderen Zahl ist, hätte die erste Version nicht das richtige Ergebnis gebracht. Die einzige Möglichkeit, bei der der größte gemeinsame Teiler größer als das Maximum der Hälfte einer der Zahlen sein kann ist, wenn beide Zahlen gleich sind.
Der Algorithmus Deines Lehrers beginnt mit der größten Zahl zu prüfen.
Sind die Zahlen beispielsweise 500 und 1000, werden alle Zahlen zwischen (einschließlich) 1000 und 501 getestet, bevor das richtige Ergebnis gefunden werden kann. Diese Möglichkeiten (außer der 1000) werden in dem von mir abgeänderten Algorithmus gar nicht betrachtet, da sie nicht richtig sein können.

Gruß hpvw


----------



## DarkSean (20. November 2005)

Nochmal wegen dem ersten Werg, kannst du mir sagen was in VB das Zeichen für "Betrag aus x" ist?


----------



## hpvw (20. November 2005)

DarkSean hat gesagt.:
			
		

> Nochmal wegen dem ersten Werg, kannst du mir sagen was in VB das Zeichen für "Betrag aus x" ist?


Nicht direkt. In den meisten Programmiersprachen gibt es dafür keinen Operator, sondern eine Funktion, die ggf. in irgendeiner mathematischen Klasse liegt. Oft heißt diese Funktion abs().

Wenn Du keine Funktion findest, kannst Du Dir auch selbst schnell eine schreiben. Pseudo-Code:
	
	
	



```
if (aNumber<0)
  aNumber := - aNumber
end if
```

Gruß hpvw


----------



## DarkSean (20. November 2005)

Wow, kriegst von mir einen dicken Bussie . Als ich mit dem anderen Code große Brüche eingegeben hab, hat es endlange gedauert. Und jetzt hat VB die gekürzten Brüche sofort. Thx, thx, thx


----------

