Gemeinsamer Teiler

Übersicht

BlitzBasic

Allgemein

	Apocalyptic Betreff: Gemeinsamer Teiler	Di, Feb 03, 2004 18:36 Antworten mit Zitat
Hi, ich hab da eine Frage: Wie kann ich rausfinden, ob zwei Zahlen einen gemeinsamen Teiler haben? Mein erster Lösungsansatz sieht so aus: Code: [AUSKLAPPEN] [EINKLAPPEN] Select True Case (Zahl1 Mod 2)=0 And (Zahl2 Mod 2)=0 t=1 Case (Zahl1 Mod 3)=0 And (Zahl2 Mod 3)=0 t=1 Case (Zahl1 Mod 5)=0 And (Zahl2 Mod 5)=0 t=1 ;... End Select Etwas eleganter wäre es dann so: Code: [AUSKLAPPEN] [EINKLAPPEN] For i=2 To Limit If (Zahl1 Mod i)=0 And (Zahl2 Mod i)=0 Then t=1 Next Aber so richtig zufrieden bin ich damit nicht und es gibt doch sicher eine bessere, mathematische Lösung, oder?
Suum cuique [ www.ffs-net.de.vu ] [ Raycaster ]

Apocalyptic

Betreff: Gemeinsamer Teiler

Di, Feb 03, 2004 18:36
Antworten mit Zitat

Hi,

ich hab da eine Frage: Wie kann ich rausfinden, ob zwei Zahlen einen gemeinsamen Teiler haben?
Mein erster Lösungsansatz sieht so aus:

Code: [AUSKLAPPEN]

Select True
Case (Zahl1 Mod 2)=0 And (Zahl2 Mod 2)=0
   t=1
Case (Zahl1 Mod 3)=0 And (Zahl2 Mod 3)=0
   t=1
Case (Zahl1 Mod 5)=0 And (Zahl2 Mod 5)=0
   t=1
;...

End Select

Etwas eleganter wäre es dann so:

Code: [AUSKLAPPEN]

For i=2 To Limit
If (Zahl1 Mod i)=0 And (Zahl2 Mod i)=0 Then t=1
Next

Aber so richtig zufrieden bin ich damit nicht und es gibt doch sicher eine bessere, mathematische Lösung, oder?

Suum cuique

[ www.ffs-net.de.vu ] [ Raycaster ]

	Vertex	Di, Feb 03, 2004 18:54 Antworten mit Zitat
Suche mal nach Euklid
vertex.dreamfall.at \| GitHub

Vertex

Di, Feb 03, 2004 18:54
Antworten mit Zitat

Suche mal nach Euklid

vertex.dreamfall.at | GitHub

	walski Ehemaliger Admin	Di, Feb 03, 2004 19:10 Antworten mit Zitat
Code: [AUSKLAPPEN] [EINKLAPPEN] Zahl1 = Int(Input$("Zahl 1: ")) Zahl2 = Int(Input$("Zahl 2: ")) Repeat If Zahl2>Zahl1 Then ;SwapVars Zahl1 = Zahl1 + Zahl2 Zahl2 = Zahl1 - Zahl2 Zahl1 = Zahl1 - Zahl2 EndIf r = Zahl1 - Zahl2 Zahl1 = Zahl2 Zahl2 = r AppTitle "Current Calculation Step: " + Str(r) Until r=0 If r>0 Then Print "ggT: " + Str(r) Else Print "Kein gemeinsamer Teiler" EndIf WaitKey() Hier der Code nach dem euklidschen Verfahren. Allerdings dient das natürlich nur zur Findung des GRÖßTEN gemeinsamen Teilers... wenn man alle haben will muss man den Code eben solange laufen lassen, bis keine weiteren gemeinsamen Teiler gefunden werden. walski
buh!

walski

Ehemaliger Admin

Di, Feb 03, 2004 19:10
Antworten mit Zitat

Code: [AUSKLAPPEN]

Zahl1 = Int(Input$("Zahl 1: "))
Zahl2 = Int(Input$("Zahl 2: "))
Repeat
If Zahl2>Zahl1 Then
   ;SwapVars
   Zahl1 = Zahl1 + Zahl2
   Zahl2 = Zahl1 - Zahl2
   Zahl1 = Zahl1 - Zahl2
EndIf
r = Zahl1 - Zahl2
Zahl1 = Zahl2
Zahl2 = r
AppTitle "Current Calculation Step: " + Str(r)
Until r=0
If r>0 Then
Print "ggT: " + Str(r)
Else
Print "Kein gemeinsamer Teiler"
EndIf
WaitKey()

Hier der Code nach dem euklidschen Verfahren.
Allerdings dient das natürlich nur zur Findung des GRÖßTEN gemeinsamen Teilers... wenn man alle haben will muss man den Code eben solange laufen lassen, bis keine weiteren gemeinsamen Teiler gefunden werden.

walski

buh!

	Apocalyptic	Di, Feb 03, 2004 19:22 Antworten mit Zitat
Danke, danach hatte ich gesucht (Forencrashs sind böse!) Ich brauch eigentlich nur die Information, ob die Zahlen einen gemeinsamen Teiler haben, gibts da vielleicht eine schnellere Lösung? Edit: Ich hab mir den Code noch nicht so genau angeschaut, aber irgendetwas stimmt da nicht... laut dem Prog hat 14 und 35 keinen gemeinsamen Teiler... und die Zeilen: Code: [AUSKLAPPEN] [EINKLAPPEN] Until r=0 If r>0 Then stimmen wohl auch nicht so ganz
Suum cuique [ www.ffs-net.de.vu ] [ Raycaster ]

Apocalyptic

Di, Feb 03, 2004 19:22
Antworten mit Zitat

Danke, danach hatte ich gesucht (Forencrashs sind böse!)

Ich brauch eigentlich nur die Information, ob die Zahlen einen gemeinsamen Teiler haben, gibts da vielleicht eine schnellere Lösung?

Edit: Ich hab mir den Code noch nicht so genau angeschaut, aber irgendetwas stimmt da nicht... laut dem Prog hat 14 und 35 keinen gemeinsamen Teiler... und die Zeilen:

Code: [AUSKLAPPEN]

Until r=0
If r>0 Then

stimmen wohl auch nicht so ganz Wink

Suum cuique

[ www.ffs-net.de.vu ] [ Raycaster ]

	Apocalyptic	Di, Feb 03, 2004 20:29 Antworten mit Zitat
Also, ich hab das ganze mal mit dieser Site http://de.wikipedia.org/wiki/E...lgorithmus so umgesetzt: Code: [AUSKLAPPEN] [EINKLAPPEN] ;1. setze m = a; n = b ;2. ist m < n, so vertausche m und n ;3. berechne r = m - n ;4. setze m = n, n = r ;5. ist r <> 0 fahre fort mit Schritt 2 ;Nach Ablauf des Verfahrens hat man mit m den ggT von a und b gefunden. a=35 b=14 m=a n=b Repeat If m<n Then t=m m=n n=t EndIf r=m-n m=n n=r Until r=0 If m=1 Then Print "Kein gemeinsamer Teiler" Else Print m EndIf WaitKey() Ich denke mal, das stimmt jetzt PS: Die binäre Lösung (auf der oben genannten Site) find ich jetzt nicht unbedingt besser. Warum soll die bei Computern schneller sein? Zitat: Ein Problem bei der Umsetzung des Euklidischen Algorithmus auf Computer ist Division, die unter Umständen einen hohen Rechenaufwand bedeutet Bei der klassischen Version taucht doch keine Division auf... Edit: Falls es jemand braucht, hier noch eine Version: Code: [AUSKLAPPEN] [EINKLAPPEN] Function ggT(a%,b%) While b<>0 r = a Mod b a = b b = r Wend Return a End Function
Suum cuique [ www.ffs-net.de.vu ] [ Raycaster ]

Apocalyptic

Di, Feb 03, 2004 20:29
Antworten mit Zitat

Also, ich hab das ganze mal mit dieser Site
http://de.wikipedia.org/wiki/E...lgorithmus
so umgesetzt:
Code: [AUSKLAPPEN]

;1. setze m = a; n = b
;2. ist m < n, so vertausche m und n
;3. berechne r = m - n
;4. setze m = n, n = r
;5. ist r <> 0 fahre fort mit Schritt 2
;Nach Ablauf des Verfahrens hat man mit m den ggT von a und b gefunden.

a=35
b=14

m=a
n=b

Repeat

If m<n Then
   t=m
   m=n
   n=t
EndIf

r=m-n

m=n
n=r

Until r=0

If m=1 Then
Print "Kein gemeinsamer Teiler"
Else
Print m
EndIf

WaitKey()

Ich denke mal, das stimmt jetzt Smile

PS: Die binäre Lösung (auf der oben genannten Site) find ich jetzt nicht unbedingt besser. Warum soll die bei Computern schneller sein?
Zitat:

Ein Problem bei der Umsetzung des Euklidischen Algorithmus auf Computer ist Division, die unter Umständen einen hohen Rechenaufwand bedeutet

Bei der klassischen Version taucht doch keine Division auf...

Edit:

Falls es jemand braucht, hier noch eine Version:
Code: [AUSKLAPPEN]

Function ggT(a%,b%)

While b<>0
   r = a Mod b
   a = b
   b = r
Wend

Return a

End Function

Suum cuique

[ www.ffs-net.de.vu ] [ Raycaster ]

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Gemeinsamer Teiler

Apocalyptic

Betreff: Gemeinsamer Teiler

Vertex

walski

Apocalyptic

Apocalyptic