kgv - Algorithmus...
-
ggt(a,b) * kgv(a,b) = a * b
-
a=a->next schrieb:
ggt(a,b) * kgv(a,b) = a * b
Beweis das!
-
@a=a->next:
In der Tat, was glaubt ihr, wie ich in der Infostunde die Lösung herausgefunden habe?
Dass kgv(a,b)*ggt(a,b) = a*b ist mir auch klar.
-
Glaubt ihr, es macht Sinn, sich mal diverse Algorithmen anzuschauen?
-
Mis2com schrieb:
Glaubt ihr, es macht Sinn, sich mal diverse Algorithmen anzuschauen?
Ein Nachteil kann es nicht sein
mfg
v R
-
Nagut, kennt jemand eine nette Übungsaufgabe für einen einfachen Algorithmus in der Klasse von kgv?
Also wirklich sehr einfach, ich will nur sehen, ob ich immernoch ein Brett vor dem Kopf habe.MfG MAV
-
Mis2com schrieb:
Nagut, kennt jemand eine nette Übungsaufgabe für einen einfachen Algorithmus in der Klasse von kgv?
ggt?
-
Das finde ich persönlicher sogar schwieriger, aber wir haben den euklidischen Algorithmus schon:
int ggt(int a, int b) { if(b == 0) return a; return ggt(b, a%b); }Aber kann man erwarten, dass man auf einen Algorithmus, der sicher nicht so leicht herauszufinden ist, weil er sogar den Namen von seinem ersten Finder trägt, finden kann in so kurzer Zeit?
Euklid hat das sicher auch nicht in ein paar Minuten herausgefunden oder?
Wenn doch, wieso heißt er dann überhaupt ,,euklidischer Algorithmus'', wenn es doch so leicht war?
Oder trägt er den Namen nur, weil sich Euklid nähere Gedanken im Bereich der Beweise etc. gemacht hat?MfG MAV
-
Er traegt den Namen, weil Euklid der vermeindliche "Erfinder" des Algorithmus
ist. Vom Namen her kannst du natuerlich nicht auf die Funktionsweise des
Algorithmuses rueckschliessen und ihn somit auch nicht implementieren, wenn man
nicht weiss, was der Algorithmus macht.mfg
v R
-
Euklid hat das sicher auch nicht in ein paar Minuten herausgefunden oder?
Wenn du mal einen Geistesblitz hast, fällt dir sowas bestimmt in einer Minute ei. Wobei diese Algorithmen wirklich noch trivial sind. Aber du musst aufhören zu denken, dass man alles sofort rausbekommt! Diese Zeiten sind wohl vorbei für dich *g* Und man kann auch nicht alles wissen, herausfinden etc. Also mach dich damit mal nicht selber fertig!
-
Ich habe den kgv-Algorithmus auch nicht gesehen, habe deshalb auch mal versucht kgv zu implementieren. Das ist bis jetzt rausgekommen:
int kgv(int a,int b)
{
const int BIG=a>b?a:b;
const int SMALL=a<b?a:b;int tmp_big=BIG;
int tmp_small=SMALL;for(;;)
if(tmp_small==tmp_big) return tmp_big;
else if((tmp_small+=SMALL)>tmp_big) tmp_big+=BIG;
}Sieht nicht besondrs elegant aus, dafür gibts nicht so viele (sichtbaren
)Funktionsaufrufe.Was haltet ihr davon?
-
@Griffin:
Aber du sagst es doch selbst, das ist noch ein relativ einfacher Algorithmus; wenn ich nicht mal auf den komme... was dann???
-
Mach dir mal nicht ins Hemd. Nur weil du den Algo nicht gefunden hast, heißt's noch lange nicht, dass du für den Job ungeeignet bist.
Und lass dir nicht so viel von anderen erzählen, die kriegen auch nicht immer alles auf die Reihe, wie sie immer behaupten.
-
Von Berufen will ich gar nichts wissen, das ist mir egal...
Aber heißt das jetzt automatisch, dass ich auch in Sachen Algorithmen später nix schaffen werde?
-
Wie wär's mit folgeber kgV-Implementierung:
int kgV(int a, int b) { return a * b/ggT(a,b); }Den ggT dann halt mir Euklid. Das dürfte eigentlich recht flott sein.
MfG Jester
-
@Jester:
Lies richtig, ich habe schon zum zweiten Mal aufgeführt, dass ich kgv(a,b)*ggt(a,b) = a*b kannte.
-
Lies richtig, ich habe schon zum zweiten Mal aufgeführt, dass ich kgv(a,b)*ggt(a,b) = a*b kannte.
Denk richtig, verwende dieses Wissen.
-
Mis2com schrieb:
Von Berufen will ich gar nichts wissen, das ist mir egal...
Aber heißt das jetzt automatisch, dass ich auch in Sachen Algorithmen später nix schaffen werde?
Erwartest du eine Antort darauf?
Gut bekommst du!
"Du wirst es nie schaffen später mit Algo. umzugehen weil du einen nicht kanntest.""OH MAN"
-
Äh, gut, sehr wahr, dumme Frage.
@Helium:
So habe ich die Funktion ja schon implementiert, aber ich wollte es als Übung auch als Extraalgorithmus machen...Na ok, danke jedenfalls für die Tipps.
-
Mis2com schrieb:
Glaubt ihr, es macht Sinn, sich mal diverse Algorithmen anzuschauen?
Das könnte durchaus Sinn ergeben; ich glaube nicht, daß es sinnlos wäre.
http://www.spiegel.de/kultur/gesellschaft/0,1518,261738,00.html