Induktion - Quersumme < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:00 Do 14.11.2013 | | Autor: | Neongelb |
| Aufgabe | | Entwerfe mittels vollständiger Induktion einen Pseudocode zur Berechnung der Quersumme Q einer Zahl zahl der Länge n. Mit Zahl[i] kann auf die i-te Stelle der Zahl zugegriffen werden. |
Hi,
mein Gedanke:
Der Basisfall wäre ja n = 1, weil Q(zahl(1)) = Zahl[n] = zahl wäre.
Quersumme von zahl mit n Stellen:
Q(zahl(n)) = Zahl[1] + Zahl[2] + ...+ Zahl[n]
Quersumme von zahl mit n + 1 Stellen:
Q(zahl(n+1)) = Zahl[1] + Zahl[2] + ...+ Zahl[n] + Zahl[n+1]
oder Q(zahl(n+1)) = Q(zahl(n)) + Zahl[n+1]
Ist dieser Gedanke im Bezug auf Induktion korrekt? Und wenn ja wie beweise ich am besten den Schritt von n zu n+1
Ich weiss, dass das noch keine wirkliche Darstellung von Pseudocode ist, mir geht es nur um den Gedanken.
Freundliche Grüße
|
|
| |
|
> Entwerfe mittels vollständiger Induktion einen Pseudocode
> zur Berechnung der Quersumme Q einer Zahl zahl der Länge
> n. Mit Zahl kann auf die i-te Stelle der Zahl zugegriffen
> werden.
>
> Hi,
>
> mein Gedanke:
> Der Basisfall wäre ja n = 1, weil Q(zahl(1)) = Zahl[n] =
> zahl wäre.
>
> Quersumme von zahl mit n Stellen:
> Q(zahl(n)) = Zahl[1] + Zahl[2] + ...+ Zahl[n]
>
> Quersumme von zahl mit n + 1 Stellen:
> Q(zahl(n+1)) = Zahl[1] + Zahl[2] + ...+ Zahl[n] +
> Zahl[n+1]
> oder Q(zahl(n+1)) = Q(zahl(n)) + Zahl[n+1]
>
Die erste Zeile ist iterativ, die zweite rekursiv (mit Induktion).
> Ist dieser Gedanke im Bezug auf Induktion korrekt? Und wenn
> ja wie beweise ich am besten den Schritt von n zu n+1
>
> Ich weiss, dass das noch keine wirkliche Darstellung von
> Pseudocode ist, mir geht es nur um den Gedanken.
>
> Freundliche Grüße
Wenn ich die Aufgabe richtig verstehe, musst du keinen Induktionsbeweis durchführen, sondern nur das Prinzip der Induktion benutzen, um einen Algorithmus zu formulieren. Und das Prinzip hast du benutzt, jetzt musst du nur noch den Pseudocode aufschreiben.
|
|
|
|
