TD1 - Rekursion
Übersetzt von
ScribdTranslationsTD1 - Rekursion
Übersetzt von
ScribdTranslationsStudienjahr 2021/2022 Niveau : MPI
Algorithmik und Datenstrukturen II
TD1 : Rekursion
Übung 1
Schreiben Sie eine rekursive Funktion in der Programmiersprache C, die, gegeben eine positive ganze Zahl n, die Summe zurückgibt.
der n ersten ganzen Zahlen.
Übung 2
Ecrire en langage C une fonction récursive permettant de convertir un nombre N donné (en base
10) in einer Basis b (2 <= b <= 10).
Exercice 3
Auf Zeichenketten stehen uns die folgenden 3 Operationen zur Verfügung:
-Dernier:Chaine Charakter
-Debüt: Kette Kette
-AjoutF:KetteXZeichen Kette
Die Operation gibt das letzte Zeichen der übergebenen Zeichenkette zurück.
Die Operation Beginn liefert die angegebene Zeichenkette privat von ihrem letzten Element.
Die Operation HinzufügenFdélivre gibt die übergebene Zeichenkette zurück, zu der am Ende hinzugefügt wurde.
gegebenes Zeichen als Argument.
In der Folge wird die leere Kette als „ChVide“ bezeichnet.
1 – Ecrire en C une fonction récursive qui calcule la longueur d’une chaîne.
2 – Schreibe in C eine rekursive Funktion, die testet, ob eine Zeichenkette1 aus einer Zeichenkette2 extrahiert ist, d.h. die
Zeichen von Zeichen1 sind vorhanden (in der Reihenfolge, aber nicht unbedingt zusammenhängend)
in der Kette2.
Beispiele :
EstExtraite('ABC', 'KVABTC')=Wahr
EstExtraite('ABC','ANMCB')=Falsch
Im Folgenden wird angenommen, dass die Zeichenfolgen dezimale Darstellungen (in Basis 10) beschreiben.
Ganzzahlen.
3 – Schreibe in C eine rekursive Funktion, die testet, ob eine solche Zeichenkette wachsend ist (d.h. die Ziffern
präsentieren sich in der Kette in aufsteigender Reihenfolge)
Beispiele :
Croissante(‘2468’)=Vrai
Croissante(‘2466’)=Vrai
Croissante(‘2168’)=Faux
1
4 – Schreibe eine rekursive Funktion, die den Nachfolger einer gegebenen ganzen Zahl konstruiert.
Beispiele:
Succ(‘2468’)=’2469’
Succ(‘78299’)=’78300’
Hinweis. Für die Fragen 3 und 4 können die folgenden beiden inversen Funktionen verwendet werden:
Charakter Ziffer
char: Chiffre Charakter
Übung 4
Wir schlagen vor, das Spiel zu untersuchen, das durch die folgenden Regeln beschrieben wird:
Wir haben n reversible Tokens, die ausgerichtet sind. Jeder Token hat eine Seite mit der Zahl 1 und eine Seite
markiert 0. Zu Beginn sind nur die Seiten 0 der n Chips sichtbar. Das Ziel des Spiels ist es, umzudrehen
die verschiedenen Jetons so, dass die einzigen sichtbaren Seiten die 1 sind
Nein. Jeton 123………….n
Konfiguration initial000………….0
Endkonfiguration 111………….1
Das Wenden der Chips unterliegt den folgenden Regeln:
Regel 1: Man kann immer den ersten Token (den, der am weitesten links ist) umdrehen.
Regel 2: Man kann den i-ten Token umdrehen, vorausgesetzt, die 0-Seiten der (i-2) sind sichtbar.
erste Tokens und die Seite 1 des (i-1)ten Tokens
Um von der Ausgangskonfiguration zur Endkonfiguration zu gelangen, während die Regeln beachtet werden.
Frühere, wir können zwei einander rekursive Funktionen einführen:
- Eine Funktion notiert Bag(jet, k), die ein Array von n Tokens transformiert, von denen die ersten k an sind
0 in einer neuen Tabelle, deren k erste Einsen sind.
- Eine Funktion notierteDebag(Wurf, k), die ein Array von n Jetons transformiert, wobei die ersten k
à 1 in a new table of n tokens, of which the first k are 0.
Schreiben Sie in der Sprache C die Funktionen Bag(jet, k) und Debag(jet, k).