hey, tüftle schon seit einiger zeit aber so richtig schlau werd ich nicht :( -> wie kann ich am effizientesten den ggT von 4 ganzen zahlen mit einem mega32 ohne bibliotheken errechnen ??? .... am liebsten wär mir natürlich ein stückchen c-sourcecode :) thx Neubi
@ Neubi >-> wie kann ich am effizientesten den ggT von 4 ganzen zahlen mit einem >mega32 ohne bibliotheken errechnen ??? Das läuft wohl auf eine Primfaktorzerlegung hinaus. MFG Falk
Im Prinzip sollte der Euklidsche Algorithmus (http://de.wikipedia.org/wiki/Euklidischer_Algorithmus#Iterative_Variante) gehen. Bei vier Zahlen führt man den Algo einfach dreimal durch: ggT(A,B,C,D)=>ggT(ggT(ggT(A,B),C),D).
Eine gute Methode ist der Euklidische Algorithmus, der durch fortgesetzte Division arbeitet, Rekursion ist nicht erforderlich. Beispiel: ggT(40,25) gesucht Man dividiert ganzzahlig mit Rest nach folgendem Schema: 40: 25 = 1 R 15 25: 15 = 1 R 10 15: 10 = 1 R 5 10: 5 = 2 R 0 => Bei Rest 0 bricht der Algorithmus ab! Der letzte Divisor, also 5 ist der ggT! Funktioniert auch, wenn die kleinere Zahl beim Start genommen wird. Programmierung einfach zu machen mit einer WHILE - Schleife. Division mit DIV - bzw. MOD Operator, je nach Programmiersprache ...
Falls du das auf einem kleinen Controller ohne Division in Hardware realisieren willst, gibt's da noch eine einfachere Alternative: Du nimmst den obigen Algo, verwendest allerdings anstatt der Modulo-Division nur Subtraktionen. Da nimmt die Schrittzahl natürlich zu, aber schneller als Divisionen in Software zu realisieren dürfte es allemal sein. Beispiel mit obigen Zahlen: 40 - 25 = 15 25 - 15 = 10 15 - 10 = 5 10 - 05 = 5 05 - 05 = 0 -> ggT(40, 25) = 5 oder 54 - 29 = 25 29 - 25 = 4 25 - 04 = 21 21 - 04 = 17 17 - 04 = 13 13 - 04 = 9 09 - 04 = 5 05 - 04 = 1 04 - 01 = 3 03 - 01 = 2 02 - 01 = 1 01 - 01 = 0 -> ggT(54, 29) = 1 Zum Vergleich: 54 % 29 = 25 29 % 25 = 4 25 % 04 = 1 04 % 01 = 0 -> ggT(54, 29) = 1 Bei der Methode mit der Subtraktion ist halt zu beachten, dass IMMER die kleinere von der grösseren Zahl abgezogen wird. EDIT: Hab' überlesen, dass du den mega32 verwenden willst. Meinen ersten Satz oben bis zum Doppelpunkt kannste somit streichen, der mega32 ist für mich so ein kleiner Controller ;)
In C sieht das dann etwa so aus (Ok, ist C++, aber das spielt hier ja wohl keine Rolle...):
1 | #include <iostream> |
2 | |
3 | using namespace std; |
4 | |
5 | int CalcGCD(int a, int b) { |
6 | int x, y, diff; |
7 | |
8 | do { |
9 | if (a > b) { |
10 | x = a; y = b; |
11 | } else { |
12 | x = b; y = a; |
13 | }
|
14 | diff = x - y; |
15 | a = y; |
16 | b = diff; |
17 | } while (diff != 0); |
18 | |
19 | return a; |
20 | }
|
21 | |
22 | int main() |
23 | {
|
24 | int a, b; |
25 | |
26 | cout << "--- ggT-Berechnung ---\n"; |
27 | cout << "Zahl 1: "; |
28 | cin >> a; |
29 | cout << endl; |
30 | cout << "Zahl 2: "; |
31 | cin >> b; |
32 | cout << endl << endl; |
33 | |
34 | cout << "Der ggT von " << a << " und " << b << " ist "; |
35 | cout << CalcGCD(a, b); |
36 | |
37 | return 0; |
38 | }
|
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.