kgv - Algorithmus...
-
Hi,
sagt mal, sollte man sich schämen, wenn man nicht auf den Algorithmus für das kgv kommt?
Ich habe den Algorithmus nie gesehen und kam auch nicht drauf, findet ihr das peinlich?MfG MAV
-
Nö, mach dir mal ein paar Gedanken. Dann klappts schon!
Ich hab dafür glaub ich auch 5 min. gebraucht
-
Wie soll man darauf kommen?
Kannst du mal deine Gedankengänge offenbaren?
-
Hi,
also kgV is das kleinste gemeinsame Vielfache! Wir suchen also die kleinste ZAhl die durch beiede Zahlen teilbar ist!
Wir fangen z.B. mit a an. und überprüfen ob a durch b teilbar ist! Wenn das der Fall ist haben wir's schon geschafft bevor wir richtig angefangen haben! Und wenn nicht? Na überleg mal ...MfG
Alexander Sulfrian
PS: Könnte man z.B. schön mit einer for machen!
-
-
Optimizer schrieb:
Mein Gedankengang, der recht schnell zum Erfolg geführt hat.
es geht hier glaube ich ehr um den weg wie man darauf kommt. nicht um die lösung.
-
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.
Naja, nachdem man mir den Algorithmus iterativ verraten hat, konnte ich ihn rekursiv nachprogrammieren, keine Kunst:
int kgv(int a, int b) { return kgv(a, b, a); } int kgv(int a, int b, int c) { if(a < b) return kgv(b, a, b); if(a % b == 0) return a; return kgv(a+c, b, c); }Man hat zwei Werte: a und b
a ist hierbei der größere Wert, man überprüft dann erst, ob dieser durch b ohne Rest teilbar ist, wenn ja, ist es das größte gemeinsame Vielfache.
Wenn nicht, addiert man einfach die Anfangszahl dazu und überprüft weiter.Aber das ist doch so einfach, ich kapiere es jetzt auch...
Aber nur halbwegs und ich wäre da nie alleine drauf gekommen, das kann doch nicht sein, kann mir jemand eine Funktion sagen, die man nachprogrammieren soll, und auch rekursiv zu implementieren ist???MfG MAV, der einfach nur verzweifelt ist
-
ggT :p
-
Aber nur halbwegs und ich wäre da nie alleine drauf gekommen, das kann doch nicht sein, kann mir jemand eine Funktion sagen, die man nachprogrammieren soll, und auch rekursiv zu implementieren ist???
Das mit dem nie alleine drauf kommn würde ich nicht so dramatisieren. es wird halt ab und zu so sein, dass einem lösungen nicht mehr gleich logisch erscheinen und ins auge springen wie in der 8. klasse! manchmal sitzt man halt mal 5 stunden an einem beweis bis man was sinnvolles produziert hat!
das mit der rekursion...es gibt da doch so viel...zwar nicht direkt ne funktion (eigentlich garnicht *G*) aber wie wäre es mit einem Binärbaum? Oder Kochkurve oder oder oder
-
btw: das mit dem rekursiven abziehen hat doch mal ein herr euler erfunden (der ein ziemlicher freak war ;). ob unsereins da spontan draufkommen würde ist die frage, weils ja eigentlich mit division und teilbarkeit nur ueber ecken zu tun hat
-
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!