| Autor |
Beitrag |
    
Ganymed
| | Veröffentlicht am Sonntag, den 01. Juli, 2001 - 15:11: | 
|
Hallo, ich möchte gerne die Methode der modulo-Argumentation ein wenig kennenlernen.
Im Beitrag Klassen 12/13:Sonstiges:Etwas ungewöhnliches Problem..... hat Ingo erklärt, wie man von der Bedingung 9y=47k+42 mit natürlichen Zahlen k und y auf eine Lösung y=36 kommen kann. Wie das geht, ist mir klargeworden, aber mir kommt meine Rechnung etwas komisch vor, wenn ich versuche, dies auf ein anderes Problem zu übertragen.
Ich versuche nochmal, Ingos Weg aus meiner Sicht wiederzugeben:
9y=47k+42
Dass gilt: 47=2 mod 9 und 42=6 mod 9 ist klar, mit anderen Worten:
47 lässt beim Teilen durch 9 den Rest 2,
42 lässt beim Teilen durch 9 den Rest 6,
bei beiden zusammen muss aber Rest 9 übrigbleiben, damit 47k+42 letztlich glatt durch 9 teilbar ist.
An dem Rest 6 kann ich nichts ändern, die 42 steht nur einmal zur Verfügung, aber die 47 darf ich sooft ich will dazuaddieren, und damit auch den Rest 2, also nehme ich den Rest 2 sooft zur 6 hinzu, bis diese Summe durch 9 teilbar ist. Das ist das erste Mal bei 6*2+6=18 der Fall.
Deshalb wählt man k=6 und kommt sofort auf y=36.
Jetzt habe ich das Problem: 60n = 7f+1 mit natürlichen Zahlen f und n.
"kopiere" ich jetzt den Rechenweg oben für dieses Problem:
60n=7f+1
Dass gilt: 7=7 mod 60 und 1=1 mod 60 ist klar, mit anderen Worten:
7 lässt beim Teilen durch 60 den Rest 7,
1 lässt beim Teilen durch 60 den Rest 1,
bei beiden zusammen muss aber Rest 60 übrigbleiben, damit 7f+1 letztlich glatt durch 60 teilbar ist.
An dem Rest 1 kann ich nichts ändern, die 1 steht nur einmal zur Verfügung, aber die 7 darf ich sooft ich will dazuaddieren, und damit auch den Rest 7, also nehme ich den Rest 7 sooft zur 1 hinzu, bis diese Summe durch 60 teilbar ist. Das ist das erste Mal bei 17*7+1=120 der Fall.
Deshalb wählt man f=17 und kommt sofort auf n=2.
Dauert ganz schön lang und kommt einem irgendwie so vor, als wenn man doch wieder durch Probieren weitergekommen ist anstatt durch Logik. Gibt es hier noch einen kürzeren Weg? |
holger
| | Veröffentlicht am Sonntag, den 01. Juli, 2001 - 21:54: |
|
Hallo,
ich bin ein wenig verwirrt. Versuchts du gezielt Euklid-Algorithmen zu vermeiden?
Theoretisch gilt auf jeden Fall nach Distributivgesetz:
n*GgT(a,b) = a*x + b*y.
Für n = 1 ist die Gleichung immer erfüllbar.
benutzt man die Beziehung:
GgT(a, b) = GgT(a, a - b * [a:b]) (mit b < a)
[a:b] ist eine Ganzteilfunktion
so kann man einen effizienten Algorithmus konstruieren.
Wenn dich das intressiert, kann ich dir mal einen kleinen Aufsatz dazu mailen.
-holger |
Ganymed
| | Veröffentlicht am Sonntag, den 01. Juli, 2001 - 22:23: |
|
Hallo holger, vielen Dank für die Meldung auf meine Frage. Ich habe leider keine Ahnung von Euklid-Algorithmen, wie überhaupt auf dem ganzen Gebiet der modulo-Anwendung, ich habe, wie beschrieben, einfach nur das nachvollziehen wollen, was Ingo dort vorgemacht hat.
Was du dort aufgeschrieben hast, ist Stoff genug für mich für eine Woche, glaube ich.
Leider ist das Wochenende jetzt schon wieder vorbei, so dass ich wohl erst in einer Woche wieder Zeit finden werde, mich zurückzumelden. |
Aur0n (Aur0n)
| | Veröffentlicht am Samstag, den 07. Juli, 2001 - 22:07: |
|
Hier ist ein Auszug aus einem kleinen Programm, das ich mal in C++ geschrieben habe. Es berechnet den GGT von zwei Werten a und b. Ich hoffe du kannst C++...% ist übrigens das Zeichen für Modulo.
// *** Groesster gemeinsamer Teiler ***
// nach Euklid
int GGT(int a, int b)
{
int temp;
if(a < b) swap(&a, &b);
while(b != 0)
{
temp = b;
b = a % b;
a = temp;
}
return a;
}
void swap(int *x, int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
aur0n |
clemens
| | Veröffentlicht am Montag, den 09. Juli, 2001 - 00:34: |
|
kleine bemerkung: die swap-abfrage brauchst du nicht unbedingt. falls a die kleinere zahl ist, wird a % b natürlich a und damit in der schleife sowieso getauscht. |
|
