ggT berechnen

Übersicht

BlitzBasic

Codearchiv

	Kabelbinder Sieger des WM-Contest 2006 Betreff: ggT berechnen	So, Nov 07, 2004 20:39 Antworten mit Zitat
Hi. Ich habe mal ein kleines Programm geschrieben, dass den ggT (größten gemeinsamen Teiler) von ZWEI Zahlen a und b berechnen kann. (Ich glaube Mathe 6. Klasse ist das ). Voila: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] AppTitle \"ggT-Funktion\" Graphics 640,480,16,2 Global a = Input(\"Wert für a eingeben : \") Global b = Input(\"Wert für b eingeben : \") Dim Primzahl(2000) Dim Primfaktor1(2000) Dim Primfaktor2(2000) Dim teiler(2000) Global num,xflex,yflex,fnum1,fnum2,x,y,z,wert,quo,div,tnum Function teilbar(quo,div) If quo Mod div = 0 Then Return 1 Else Return 0 EndIf End Function Function Primzahlen_erfassen(nr) Primzahl(0)=2 Primzahl(1)=3 Primzahl(2)=5 Primzahl(3)=7 num = 4 For i = 2 To nr If teilbar(i,2)=0 And teilbar(i,3)=0 And teilbar(i,5)=0 And teilbar(i,7)=0 Then Primzahl(num)=i num = num + 1 EndIf Next End Function Function ggT(x,y) If x>y Then Primzahlen_erfassen(x) If y>x Then Primzahlen_erfassen(y) If x=y Then Primzahlen_erfassen(x) xflex = x yflex = y ;Primfaktoren herausfinden Repeat For i = 0 To num-1 If teilbar(xflex,Primzahl(i))=1 Then xflex = xflex / Primzahl(i) Primfaktor1(fnum1)=Primzahl(i) fnum1 = fnum1 + 1 EndIf Next Until xflex = 1 Repeat For i = 0 To num-1 If teilbar(yflex,Primzahl(i))=1 Then yflex = yflex / Primzahl(i) Primfaktor2(fnum2)=Primzahl(i) fnum2 = fnum2 + 1 EndIf Next Until yflex = 1 ;Primfaktoren gegenüberstellen For i = 0 To fnum1-1 If Primfaktor1(i)>0 Then For j = 0 To fnum2-1 If Primfaktor2(j)>0 Then If Primfaktor1(i)=Primfaktor2(j) Then teiler(tnum) = Primfaktor1(i) Primfaktor1(i)=0 Primfaktor2(j)=0 tnum = tnum + 1 EndIf EndIf Next EndIf Next For i = 0 To tnum-2 teiler(i+1)=teiler(i+1)teiler(i) wert = teiler(i+1) Next Return wert End Function Print ggT(a,b) WaitKey End Nebenbei habe ich mir noch einen Algorithmus einfallen lassen (müssen), mit dem man alle einträge eines Arrays multiplizieren kann. ich poste ihn einfach mal: BlitzBasic:* [AUSKLAPPEN] [EINKLAPPEN] For i = 0 To anzahl_der_einträge-1 array(i+1)=array(i+1)*array(i) wert = array(i+1) Next
<Wing Avenger Download> ◊◊◊ <Macrophage Download>

Kabelbinder

Sieger des WM-Contest 2006

Betreff: ggT berechnen

So, Nov 07, 2004 20:39
Antworten mit Zitat

Hi.
Ich habe mal ein kleines Programm geschrieben, dass den ggT (größten gemeinsamen Teiler) von ZWEI Zahlen a und b berechnen kann. (Ich glaube Mathe 6. Klasse ist das Very Happy

).
Voila:
BlitzBasic: [AUSKLAPPEN]

AppTitle \"ggT-Funktion\"
Graphics 640,480,16,2

Global a = Input(\"Wert für a eingeben : \")
Global b = Input(\"Wert für b eingeben : \")

Dim Primzahl(2000)
Dim Primfaktor1(2000)
Dim Primfaktor2(2000)
Dim teiler(2000)

Global num,xflex,yflex,fnum1,fnum2,x,y,z,wert,quo,div,tnum

Function teilbar(quo,div)
If quo Mod div = 0 Then
Return 1
Else
Return 0
EndIf
End Function

Function Primzahlen_erfassen(nr)
Primzahl(0)=2
Primzahl(1)=3
Primzahl(2)=5
Primzahl(3)=7
num = 4
For i = 2 To nr
If teilbar(i,2)=0 And teilbar(i,3)=0 And teilbar(i,5)=0 And teilbar(i,7)=0 Then
Primzahl(num)=i
num = num + 1
EndIf
Next
End Function

Function ggT(x,y)
If x>y Then Primzahlen_erfassen(x)
If y>x Then Primzahlen_erfassen(y)
If x=y Then Primzahlen_erfassen(x)

xflex = x
yflex = y

;Primfaktoren herausfinden
Repeat
For i = 0 To num-1
If teilbar(xflex,Primzahl(i))=1 Then
xflex = xflex / Primzahl(i)
Primfaktor1(fnum1)=Primzahl(i)
fnum1 = fnum1 + 1
EndIf
Next
Until xflex = 1

Repeat
For i = 0 To num-1
If teilbar(yflex,Primzahl(i))=1 Then
yflex = yflex / Primzahl(i)
Primfaktor2(fnum2)=Primzahl(i)
fnum2 = fnum2 + 1
EndIf
Next
Until yflex = 1

;Primfaktoren gegenüberstellen

For i = 0 To fnum1-1
If Primfaktor1(i)>0 Then
For j = 0 To fnum2-1
If Primfaktor2(j)>0 Then
If Primfaktor1(i)=Primfaktor2(j) Then
teiler(tnum) = Primfaktor1(i)
Primfaktor1(i)=0
Primfaktor2(j)=0
tnum = tnum + 1
EndIf
EndIf
Next
EndIf
Next

For i = 0 To tnum-2
teiler(i+1)=teiler(i+1)*teiler(i)
wert = teiler(i+1)
Next

Return wert
End Function

Print ggT(a,b)					

WaitKey
End

Nebenbei habe ich mir noch einen Algorithmus einfallen lassen (müssen), mit dem man alle einträge eines Arrays multiplizieren kann. ich poste ihn einfach mal:
BlitzBasic: [AUSKLAPPEN]

For i = 0 To anzahl_der_einträge-1
array(i+1)=array(i+1)*array(i)
wert = array(i+1)
Next

	ke^kx	So, Nov 07, 2004 21:24 Antworten mit Zitat
Also, der Algorithmus ist zwar eigentlich nichts besonderes, gefällt mir aber trotzdem ganz gut. Der Rest ist halt (wie du gesagt hattest) Mathe 6te Klasse. Jiriki
http://i3u8.blogspot.com Asus Striker II Intel Core2Quad Q9300 @ 2,5 GHz (aber nur zwei Kerne aktiv aufgrund der Instabilität -.-) Geforce 9800 GTX 2GB RAM

ke^kx

So, Nov 07, 2004 21:24
Antworten mit Zitat

Also, der Algorithmus ist zwar eigentlich nichts besonderes, gefällt mir aber trotzdem ganz gut. Der Rest ist halt (wie du gesagt hattest) Mathe 6te Klasse.

Jiriki

http://i3u8.blogspot.com
Asus Striker II
Intel Core2Quad Q9300 @ 2,5 GHz (aber nur zwei Kerne aktiv aufgrund der Instabilität -.-)
Geforce 9800 GTX
2GB RAM

	Black	Mo, Nov 08, 2004 15:57 Antworten mit Zitat
Ehrlich gesagt, ist dein Algo viel, viel zu langsam. Hier ist einer, der ein bisschen schneller ist: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] AppTitle \"ggT-Funktion\" Graphics 640,480,16,2 Global a = Input(\"Wert für a eingeben : \") Global b = Input(\"Wert für b eingeben : \") Function ggT( m, n ) If m < n Then temp = m m = n n = temp End If Do r = m Mod n m = n n = r Loop Until r = 0 Return m End Function Print ggT( a, b ) WaitKey PS: Ich hab keine Ahnung ob das so kompiliert werden kann, ich kenn mich weder mit BB gut aus noch hab ich hier imo die Demo installiert, darum hab ich auch als Gerüst den Code von oben benutzt.

Black

Mo, Nov 08, 2004 15:57
Antworten mit Zitat

Ehrlich gesagt, ist dein Algo viel, viel zu langsam.
Hier ist einer, der ein bisschen schneller ist:
BlitzBasic: [AUSKLAPPEN]


AppTitle \"ggT-Funktion\" 
Graphics 640,480,16,2 

Global a = Input(\"Wert für a eingeben : \") 
Global b = Input(\"Wert für b eingeben : \") 

Function ggT( m, n )
 If m < n Then 
  temp = m
  m = n
  n = temp
 End If
 Do
    r = m Mod n
    m = n
    n = r
 Loop Until r = 0
 Return m
End Function

Print ggT( a, b )
WaitKey

PS: Ich hab keine Ahnung ob das so kompiliert werden kann, ich kenn mich weder mit BB gut aus noch hab ich hier imo die Demo installiert, darum hab ich auch als Gerüst den Code von oben benutzt.

	konstantin	Mo, Nov 08, 2004 16:28 Antworten mit Zitat
programm zum berechnen des kgT fände ich interessanter

konstantin

Mo, Nov 08, 2004 16:28
Antworten mit Zitat

programm zum berechnen des kgT fände ich interessanter

	Black	Mo, Nov 08, 2004 16:51 Antworten mit Zitat
Einfach: kgT von allen Zahlen ist 1 Nun zum kgV: a * b = ggT( a, b ) * kgV( a, b ) Also: kgV( a, b ) = a * b / ggT( a, b ) Mit der Funktion aus meinem vorigen Beitrag: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Function kgV( x, y ) If x = 0 And y = 0 Then Return 0 Else Return (x * y / ggT( x, y )) End If End Function

Black

Mo, Nov 08, 2004 16:51
Antworten mit Zitat

Einfach:

kgT von allen Zahlen ist 1

Nun zum kgV:

a * b = ggT( a, b ) * kgV( a, b )

Also:

kgV( a, b ) = a * b / ggT( a, b )

Mit der Funktion aus meinem vorigen Beitrag:
BlitzBasic: [AUSKLAPPEN]


Function kgV( x, y )
 If x = 0 And y = 0 Then 
  Return 0
 Else
  Return (x * y / ggT( x, y ))
 End If
End Function

	Kabelbinder Sieger des WM-Contest 2006	Mo, Nov 08, 2004 19:28 Antworten mit Zitat
@ Alu: Also ich nicht. Aber gut, hier hast du eins: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] AppTitle \"ggT-Funktion\" Graphics 640,480,16,2 Global a = Input(\"Wert für a eingeben : \") Global b = Input(\"Wert für b eingeben : \") Function kgT(x,y) wert = 0 If x<>0 And y<>0 Then wert = 1 Return wert End Function Print kgT(a,b) WaitKey End Und was soll das bringen?
<Wing Avenger Download> ◊◊◊ <Macrophage Download>

Kabelbinder

Sieger des WM-Contest 2006

Mo, Nov 08, 2004 19:28
Antworten mit Zitat

@ Alu: Also ich nicht. Rolling Eyes

Aber gut, hier hast du eins:
BlitzBasic: [AUSKLAPPEN]

AppTitle \"ggT-Funktion\" 
Graphics 640,480,16,2 

Global a = Input(\"Wert für a eingeben : \") 
Global b = Input(\"Wert für b eingeben : \") 

Function kgT(x,y)
wert = 0
If x<>0 And y<>0 Then wert = 1
Return wert 
End Function 

Print kgT(a,b) 

WaitKey 
End

Und was soll das bringen?

	ke^kx	Mo, Nov 08, 2004 19:50 Antworten mit Zitat
Also, normalerweise zählt 1 ja auch nicht zum kgT dazu Jiriki
http://i3u8.blogspot.com Asus Striker II Intel Core2Quad Q9300 @ 2,5 GHz (aber nur zwei Kerne aktiv aufgrund der Instabilität -.-) Geforce 9800 GTX 2GB RAM

ke^kx

Mo, Nov 08, 2004 19:50
Antworten mit Zitat

Also, normalerweise zählt 1 ja auch nicht zum kgT dazu Laughing

Jiriki

http://i3u8.blogspot.com
Asus Striker II
Intel Core2Quad Q9300 @ 2,5 GHz (aber nur zwei Kerne aktiv aufgrund der Instabilität -.-)
Geforce 9800 GTX
2GB RAM

	Kabelbinder Sieger des WM-Contest 2006	Mo, Nov 08, 2004 19:58 Antworten mit Zitat
Aha, wusste ich nicht. Aber was bringt es einem, wenn man den zweitkleinsten gemeinsamen Teiler zweier Zahlen kennt? Kann man damit irgendwas berechnen?
<Wing Avenger Download> ◊◊◊ <Macrophage Download>

Kabelbinder

Sieger des WM-Contest 2006

Mo, Nov 08, 2004 19:58
Antworten mit Zitat

Aha, wusste ich nicht. Aber was bringt es einem, wenn man den zweitkleinsten gemeinsamen Teiler zweier Zahlen kennt? Kann man damit irgendwas berechnen?

	Black	Mo, Nov 08, 2004 20:42 Antworten mit Zitat
Erm, ich würde schon sagen, dass die 1 immer der kgT von allen natürlichen Zahlen ist. Per Definition ist der kgT das kleinste Element der gemeinsamen Teilermenge der beiden Zahlen. Und da die 1 ein Teiler von allen natürlichen Zahlen ist und zusätzlich auch die kleinste natürliche Zahl, ist sie auch der kgT von allen natürlichen Zahlen. Dabei ist zu beachten, dass die 0 keine natürliche Zahl ist/kein Element vom normalen \|N ist.

Black

Mo, Nov 08, 2004 20:42
Antworten mit Zitat

Erm, ich würde schon sagen, dass die 1 immer der kgT von allen natürlichen Zahlen ist.

Per Definition ist der kgT das kleinste Element der gemeinsamen Teilermenge der beiden Zahlen. Und da die 1 ein Teiler von allen natürlichen Zahlen ist und zusätzlich auch die kleinste natürliche Zahl, ist sie auch der kgT von allen natürlichen Zahlen.

Dabei ist zu beachten, dass die 0 keine natürliche Zahl ist/kein Element vom normalen |N ist.

	ke^kx	Mo, Nov 08, 2004 21:48 Antworten mit Zitat
Aber es bringt einem doch nichts immer die Eins zu erechnen, oder? Sowit ich mich erinnern kann haben wir jedenfalls nie die Eins berechnet. Belehrt mich eines besseren wenn ich mich irre. Zur Not frage ich noch mal meinen Mathe-Lerer. Jiriki
http://i3u8.blogspot.com Asus Striker II Intel Core2Quad Q9300 @ 2,5 GHz (aber nur zwei Kerne aktiv aufgrund der Instabilität -.-) Geforce 9800 GTX 2GB RAM

ke^kx

Mo, Nov 08, 2004 21:48
Antworten mit Zitat

Aber es bringt einem doch nichts immer die Eins zu erechnen, oder?
Sowit ich mich erinnern kann haben wir jedenfalls nie die Eins berechnet.
Belehrt mich eines besseren wenn ich mich irre. Zur Not frage ich noch mal meinen Mathe-Lerer.

Jiriki

http://i3u8.blogspot.com
Asus Striker II
Intel Core2Quad Q9300 @ 2,5 GHz (aber nur zwei Kerne aktiv aufgrund der Instabilität -.-)
Geforce 9800 GTX
2GB RAM

	Blatolo	Mo, Nov 08, 2004 21:58 Antworten mit Zitat
Das einzige das SInn macht sind ggT und kgV. Am besten wollt ihr jetzt auch noch das ggV(größte gemeinsame vielfache) berechnen

Blatolo

Mo, Nov 08, 2004 21:58
Antworten mit Zitat

Das einzige das SInn macht sind ggT und kgV.
Am besten wollt ihr jetzt auch noch das ggV(größte gemeinsame vielfache) berechnen Laughing

	Black	Mo, Nov 08, 2004 22:30 Antworten mit Zitat
Jiriki hat Folgendes geschrieben: Aber es bringt einem doch nichts immer die Eins zu erechnen, oder? Sowit ich mich erinnern kann haben wir jedenfalls nie die Eins berechnet. Belehrt mich eines besseren wenn ich mich irre. Zur Not frage ich noch mal meinen Mathe-Lerer. Jiriki Ihr habt auch nicht den kgT berechnet sondern den ggT oder das kgV...

Black

Mo, Nov 08, 2004 22:30
Antworten mit Zitat

Jiriki hat Folgendes geschrieben:

Ihr habt auch nicht den kgT berechnet sondern den ggT oder das kgV...

	Kabelbinder Sieger des WM-Contest 2006	Mo, Nov 08, 2004 23:24 Antworten mit Zitat
Das ist auch nicht auf meinem Mist gewachsen, das war Alu's Idee.... Ich welcher Klasse ist der eigentlich ?
<Wing Avenger Download> ◊◊◊ <Macrophage Download>

Kabelbinder

Sieger des WM-Contest 2006

Mo, Nov 08, 2004 23:24
Antworten mit Zitat

Das ist auch nicht auf meinem Mist gewachsen, das war Alu's Idee....
Ich welcher Klasse ist der eigentlich Confused

	hot-bit Gast	Mo, Nov 08, 2004 23:44 Antworten mit Zitat
Hi... Soweit ich mich erinnern kann, war er in der Baumschule, letzte Reihe, und blieb immer in der ersten Klasse hängen. Er meinte, die Lehrerin habe ihm so gefallen Toni

hot-bit

Gast

Mo, Nov 08, 2004 23:44
Antworten mit Zitat

Hi...

Soweit ich mich erinnern kann, war er in der Baumschule, letzte Reihe, und blieb immer in der ersten Klasse hängen.
Er meinte, die Lehrerin habe ihm so gefallen Wink

Toni

	Kabelbinder Sieger des WM-Contest 2006	Mo, Nov 08, 2004 23:53 Antworten mit Zitat
Hi. Ich hab nach ner Testreihe noch einen Bug in dem Programm gefunden. Lag an dem grottenschlechten Algorithmus, mit dem ich versucht habe, die Array-Einträge zu multiplizieren. Der ist aber jetzt zum Glück etwas ausgereifter. Hier die neue Version: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] AppTitle \"ggT-Funktion\" Graphics 640,480,16,2 Global a = Input(\"Wert für a eingeben : \") Global b = Input(\"Wert für b eingeben : \") Dim Primzahl(2000) Dim Primfaktor1(2000) Dim Primfaktor2(2000) Dim teiler(2000) Global num,xflex,yflex,fnum1,fnum2,x,y,z,wert,quo,div,tnum Function teilbar(quo,div) If quo Mod div = 0 Then Return 1 Else Return 0 EndIf End Function Function Primzahlen_erfassen(nr) Primzahl(0)=2 Primzahl(1)=3 Primzahl(2)=5 Primzahl(3)=7 num = 4 For i = 2 To nr If teilbar(i,2)=0 And teilbar(i,3)=0 And teilbar(i,5)=0 And teilbar(i,7)=0 Then Primzahl(num)=i num = num + 1 EndIf Next End Function Function ggT(x,y) If x>y Then Primzahlen_erfassen(x) If y>x Then Primzahlen_erfassen(y) If x=y Then Primzahlen_erfassen(x) xflex = x yflex = y ;Primfaktoren herausfinden Repeat For i = 0 To num-1 If teilbar(xflex,Primzahl(i))=1 Then xflex = xflex / Primzahl(i) Primfaktor1(fnum1)=Primzahl(i) fnum1 = fnum1 + 1 EndIf Next Until xflex = 1 Repeat For i = 0 To num-1 If teilbar(yflex,Primzahl(i))=1 Then yflex = yflex / Primzahl(i) Primfaktor2(fnum2)=Primzahl(i) fnum2 = fnum2 + 1 EndIf Next Until yflex = 1 ;Primfaktoren gegenüberstellen For i = 0 To fnum1-1 If Primfaktor1(i)>0 Then For j = 0 To fnum2-1 If Primfaktor2(j)>0 Then If Primfaktor1(i)=Primfaktor2(j) Then teiler(tnum) = Primfaktor1(i) Primfaktor1(i)=0 Primfaktor2(j)=0 tnum = tnum + 1 EndIf EndIf Next EndIf Next wert = teiler(0) If tnum > 1 Then For i = 1 To tnum-1 wert = wert * teiler(i) Next EndIf Return wert End Function Print ggT(a,b) WaitKey End
<Wing Avenger Download> ◊◊◊ <Macrophage Download>

Kabelbinder

Sieger des WM-Contest 2006

Mo, Nov 08, 2004 23:53
Antworten mit Zitat

Hi.
Ich hab nach ner Testreihe noch einen Bug in dem Programm gefunden. Lag an dem grottenschlechten Algorithmus, mit dem ich versucht habe, die Array-Einträge zu multiplizieren. Der ist aber jetzt zum Glück etwas ausgereifter. Hier die neue Version:
BlitzBasic: [AUSKLAPPEN]

AppTitle \"ggT-Funktion\" 
Graphics 640,480,16,2 

Global a = Input(\"Wert für a eingeben : \") 
Global b = Input(\"Wert für b eingeben : \") 

Dim Primzahl(2000) 
Dim Primfaktor1(2000) 
Dim Primfaktor2(2000) 
Dim teiler(2000) 

Global num,xflex,yflex,fnum1,fnum2,x,y,z,wert,quo,div,tnum 

Function teilbar(quo,div) 
If quo Mod div = 0 Then 
Return 1 
Else 
Return 0 
EndIf 
End Function 

Function Primzahlen_erfassen(nr) 
Primzahl(0)=2 
Primzahl(1)=3 
Primzahl(2)=5 
Primzahl(3)=7 
num = 4 
For i = 2 To nr 
If teilbar(i,2)=0 And teilbar(i,3)=0 And teilbar(i,5)=0 And teilbar(i,7)=0 Then 
Primzahl(num)=i 
num = num + 1 
EndIf 
Next 
End Function 

Function ggT(x,y) 
If x>y Then Primzahlen_erfassen(x) 
If y>x Then Primzahlen_erfassen(y) 
If x=y Then Primzahlen_erfassen(x) 

xflex = x 
yflex = y 

;Primfaktoren herausfinden 
Repeat 
For i = 0 To num-1 
If teilbar(xflex,Primzahl(i))=1 Then 
xflex = xflex / Primzahl(i) 
Primfaktor1(fnum1)=Primzahl(i) 
fnum1 = fnum1 + 1 
EndIf 
Next 
Until xflex = 1 

Repeat 
For i = 0 To num-1 
If teilbar(yflex,Primzahl(i))=1 Then 
yflex = yflex / Primzahl(i) 
Primfaktor2(fnum2)=Primzahl(i) 
fnum2 = fnum2 + 1 
EndIf 
Next 
Until yflex = 1 

;Primfaktoren gegenüberstellen 

For i = 0 To fnum1-1 
If Primfaktor1(i)>0 Then
For j = 0 To fnum2-1
If Primfaktor2(j)>0 Then 
If Primfaktor1(i)=Primfaktor2(j) Then 
teiler(tnum) = Primfaktor1(i) 
Primfaktor1(i)=0 
Primfaktor2(j)=0 
tnum = tnum + 1 
EndIf 
EndIf 
Next 
EndIf 
Next 

wert = teiler(0)
If tnum > 1 Then
For i = 1 To tnum-1
wert = wert * teiler(i)
Next
EndIf

Return wert 
End Function 

Print ggT(a,b) 
WaitKey 
End

Übersicht

BlitzBasic

Codearchiv

Nach Oben

BlitzBasic Portal

ggT berechnen

Betreff: ggT berechnen

hot-bit