Pseudocode Logik < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:13 Di 18.12.2012 | | Autor: | Coup |
| Aufgabe | Eingabe: a und b positive ganze Zahlen
Wenn a > b: a[0] := a, b[0] := b
Sonst: a[0] := b, b[0] := a n := 0
Solange b[n] groeßer als 0 wiederhole n := n + 1
a[n] := b[n-1]
b[n] := a[n-1] mod b[n-1] Ende der Schleife
Ausgabe: a[n]
Zeige, dass b[n] < b[n-1] und folgern Sie daraus , dass es ein m [mm] \in \IN_{0} [/mm] gibt sodass b[m]= 0 wird und die Schleife abbricht |
Hallo,
Ich habe mir einige Gedanken dazu gemacht.
Es ist ja nicht gesagt auf welchem Weg ich zeigen soll, dass
$b[n] < b[n-1] $
Ich bin daher einfach mit Zahlbeispielen den Code durchgegangen.
1. Egal ob mein a oder b größer ist, beide Variablen bekommen in beiden Fällen den gleichen Wert an Stelle 0 zugewiesen ( im Array ).
Für a=2 und b=1 hieße das ja : a[0] =2 und b[0]=1. Egal welcher Fall.
Nun beginnt die Variable n auf Speicherstelle 0 und die Schleife beginnt zu laufen.
Variable n wird erhöht und a[n]=a[1] definiert durch b[n-1]=b[0]=1 ( für mein Zahlenbeispiel ).
Da im nächsten Schritt mein a[n-1] modulo b[n-1] gerechnet wird folgt daraus das b[n]=b[1]=0 kleiner ist als b[n-1]=b[1-1]=1.
Es dürfte sich hier ja um den ggT handeln. Demnach wird der Rest immer kleiner und deshalb ist b[n] immer kleiner als b[n-1], da der alte Rest demzufolge größer war.
Ist das so korrekt ?
Vielen Dank schonmal fürs reinlesen und mitdenken :)
lg
Micha
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:46 Do 20.12.2012 | | Autor: | meili |
Hallo Micha,
> Eingabe: a und b positive ganze Zahlen
>
> Wenn a > b: a[0] := a, b[0] := b
> Sonst: a[0] := b, b[0] := a n := 0
>
> Solange b[n] groeßer als 0 wiederhole n := n + 1
> a[n] := b[n-1]
> b[n] := a[n-1] mod b[n-1] Ende der Schleife
> Ausgabe: a[n]
>
> Zeige, dass b[n] < b[n-1] und folgern Sie daraus , dass es
> ein m [mm]\in \IN_{0}[/mm] gibt sodass b[m]= 0 wird und die Schleife abbricht
> Hallo,
>
> Ich habe mir einige Gedanken dazu gemacht.
> Es ist ja nicht gesagt auf welchem Weg ich zeigen soll, dass
> [mm]b[n] < b[n-1][/mm]
> Ich bin daher einfach mit Zahlbeispielen den Code durchgegangen.
> 1. Egal ob mein a oder b größer ist, beide Variablen bekommen in beiden Fällen den gleichen Wert an Stelle 0 zugewiesen ( im Array ).
> Für a=2 und b=1 hieße das ja : a[0] =2 und b[0]=1. Egal welcher Fall.
> Nun beginnt die Variable n auf Speicherstelle 0 und die Schleife beginnt zu laufen.
> Variable n wird erhöht und a[n]=a[1] definiert durch b[n-1]=b[0]=1 ( für mein Zahlenbeispiel ).
>
> Da im nächsten Schritt mein a[n-1] modulo b[n-1] gerechnet wird folgt daraus das b[n]=b[1]=0 kleiner ist als b[n-1]=b[1-1]=1.
>
> Es dürfte sich hier ja um den ggT handeln. Demnach wird der Rest immer kleiner und deshalb ist b[n] immer kleiner als b[n-1], da der alte Rest demzufolge größer war.
>
Es ist sicher gut, sich an einem Beispiel klar zu machen, wie es abläuft.
Um b[n] < b[n-1] zu zeigen, reicht eine Eigenschaft von "mod".
b[n] entsteht aus b[n-1] durch b[n] := a[n-1] mod b[n-1].
(a[n-1] mod b[n-1]) $ [mm] \in \{0, \ldots , b[n-1]-1\}$.
[/mm]
> Ist das so korrekt ?
> Vielen Dank schonmal fürs reinlesen und mitdenken :)
>
> lg
> Micha
Gruß
meili
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:47 Do 20.12.2012 | | Autor: | Coup |
Okay danke, das hilft sehr !
Wie könnte ich denn mittles Induktion zeigen, dass ggT(a[n],b[n]) = ggT(a,b) ist ?
Für n=1 stimmt die Behauptung natürlich aber im Induktionsschritt
ggT(a[n+1],b[n+1]) = ggT(a,b) hängt es leider.
lg
und danke :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Sa 22.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
