Hier könnt Ihr Eure Funktionen zu den Aufgabe 1a bis d testen
Achtung: Hier müsst Ihr nur eine Funktion und den oder die Rückgabewerte definieren. Eine Ein- oder Ausgabe ist nicht nötig (und würde eh zu falschen Testergebnissen führen.) |
Achtung: Hier müsst Ihr nur eine Funktion und den oder die Rückgabewerte definieren. Eine Ein- oder Ausgabe ist nicht nötig (und würde eh zu falschen Testergebnissen führen.) |
def geheim(x):
a = [0, 4, 0, 3, 2]
while x > 0:
x = a[x]
return "Fertig!"
a[3]=3
(das erste Element hat ja den Index 0
) und dabei bleibt es dann auch. Achtung: Hier müsst Ihr nur eine Funktion und den oder die Rückgabewerte definieren. Eine Ein- oder Ausgabe ist (bis auf eine Ausnahme) nicht nötig (und würde eh zu falschen Testergebnissen führen.) |
for
-Schleifenwhile
-SchleifenMan kann auch mit einer while
-Schleife zählen, muss sich aber selbst um die Zählvariable i
kümmern:
Ein paar kleinere Übungen zur bedingten Verzweigung
Achtung: Hier müsst Ihr nur eine Funktion und den oder die Rückgabewerte definieren. Eine Ein- oder Ausgabe ist nicht nötig (und würde eh zu falschen Testergebnissen führen.) |
Im Folgenden sollst Du Dir auch Gedanken über die Implementierung verschiedener Funktionen machen, die es in Python eventuell schon gibt. Diese Funktionen, z.B. min()
und max()
, darfst Du aber nicht benutzen. :-P
In der Mathematik gibt es neben der Betragsfunktion (in Python: abs()
auch die Signum-Funktion, die das Vorzeichen einer Zahl x zurück gibt.
Es gilt: x = Signum(x) * Betrag(x)
Mit der folgenden Information habe ich vor über 20 Jahren eine Flasche Sekt gewonnen, weil jemand dachte, 2000 sei kein Schaltjahr. :-) (1900 war ja tatsächlich keines.)
Programmierung ist die Algorithmierung eines Problems in ein Programm, d.h. in eine Notation, die von der konkreten Anlage, auf der das Problem behandelt werden soll, „verstanden“ wird.
Die Anlage kann das Programm als eine Anweisungsfolge interpretieren, die die Problemdaten verarbeitet.
Gegenstand der Algorithmierung ist die Erarbeitung der Programmstruktur im Rahmen der durch die Programmumgebung vorgegebenen Bedingungen.
Gegenstand der Codierung, auch Implementierung genannt, ist, eine Programmniederschrift zu schaffen, auf auf dem Computer abgearbeitet werden kann.
(vgl. Duden Informatik SII: S. 245)
Der euklidische Algorithmus zur Ermittlung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen:
Beispiel: Suche den ggT von 544 und 391
544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 85 : 68 = 1 Rest 17 68 : 17 = 4 Rest 0Die Division geht auf, ggT(544; 391) = 17
while
-Schleife.On veut retourner une liste (c'est à dire ranger ses éléments dans l'ordre inverse) et on va procéder par ajouter successifs (il existe d'autres façons de le faire).
L'algorithme est assez simple :
fonction retourner(lst) : lstReverse = [ ] tant que lst non vide : retirer le dernier elem de lst et l'ajouter à la fin de lstReverse fin de pour renvoyer lstReverseCoder ceci en python ne pose pas de grosse difficulté, mais il faut se souvenir de la méthode pop et de son usage….
Rappel :pyBox slug='5.1_reversePOP' solver="def reversePOP(lst: list ) -> list : lstR=[] while len(lst) > 0: e=lst.pop() lstR.append(e) return lstR lst=[3,1,6,7,2] print(reversePOP(lst)) " defaultcode="def reversePOP(lst: list ) -> list : # votre code ici lst=[3,1,6,7,2] print(reversePOP(lst)) " taboo="insert" title='reverse avec pop' ] [/pyBox]
lst = [1,2,3]
a = lst.pop()
-> a=3 et maintenant lst=[1,2]
lst.pop() retire le dernier élément de la liste lst et renvoie sa valeur.
Au lieu de append, on pourrait aussi utiliser une concaténation de liste : lstR = lstR + [val] donnera le même résultat, essaye les deux façons.
(attention : en réalité ces deux façon de procéder ne sont pas équivalentes. Elle donnent le même résultat et pour cette année nous n'entreront pas dans les détails sr la différence de traitement entre les deux)
On pourrait même ne rien ajouter et ne rien concaténer :
def reversePOP(lst: list ) -> list :Et là encore, le résultat est le même mais les opérations réalisées ne sont pas les même en réalités. Et ici aussi nous n'entreront pas cette année dans les détails.
lstR=[0] * len(lst) # initialise une liste avec len(lst) 0
idx=0
while len(lst) > 0:
e=lst.pop()
lstR[idx]=e
idx+=1
return lstR
Toutefois nous aurions pu écrire aussi bien cet algorithme :
onction retourner(lst) : lstReverse = [ ] tant que lst non vide : retirer le premier elem de lst et l'ajouter au début de lstReverse fin de pour renvoyer lstReverseTu pourras coder ce second algorithme en utilisant lst.pop(0) qui retire l'élément d'indice 0 et lstR.insert(0,val) qui insère val en tête de liste.
On pourrait aussi utiliser une concaténation de liste : lstR = [val] + lstR donnera le même résultat, essaye les deux façons, et surtout remarque bien :
ajouter en tête : lst.insert(0,val) ou lst=[val] + lst ajouter en queue : lst.append(val) ou lst=lst+[val] retirer en tête : val = lst.pop(0) retirer en queue :val = lst.pop()
Rappel :
lst = [1,2,3]
lst.insert(0,7)
-> Maintenant lst vaut [7,1,2,3]
Complexité
Pouvez vous estimer la complexité de ces différents codes de retournement ? Sont ils tous équivalent ?
Vous aller programmer ici une fonction tri(lst) qui va trier une liste. L'algorithme utilisé, que nous reverrons plus tard dans une autre forme, est le suivant :
fonction triInsertion(lst) : listTriee=[] Tant que longueur(lst) > 0 : rechercher l'indice du min dans lst retirer cet élément (avec pop) et l'ajouter (en queue) dans listeTrie fin de tant que renvoyer listeTriee (la fonction idxMin(list) est disponible dans cet exercice)
Dans ce code, que vous venez de faire, on n'a pas vraiment de curseurs (il y en a cependant un, caché dans la fonction idxMin que vous avez utilisé), d'accumulateur, ou de compteur. En effet ici on ne compte rien, on ne somme rien, et on ne localise rien.
L'ajout successif d'élément dans une liste est un autre outil indispensable que vous serez souvent amenés à utiliser.
Complexité
Estimons la complexité de cet algorithme expérimentalement avec time().
En raison de limitations sur ce site, il n'est pas possible de travailler sur de très grandes listes. Néanmoins, ici, on a pris une séries de valeurs de N allant de 10 à 2560. A chaque fois on multiplie N par 2. Le temps de calcul évolue d'abord linéairement pour les petites valeurs de N mais rapidement on voit que quand N est multiplié par 2, le temps est multiplié par 4 (2² !)
La complexité semble donc plutôt proportionnelle à N² dans cet exemple.
Combien de fois est exécutée la boucle while ?
Combien d'opération sont executées dans cette boucle while ?
La réponse est que la boucle while est exécutée N fois, mais dans la boucle, on appelle idxMin. idxMin a une complexité en O(N), mais comme la liste lst est raccourcie au fur et a mesure, c'est un peu compliqué….
si le temps de idxMin est N, alors le temps de tout les appels est :
1 + 2 + … + N = N(N+1)/2 = N² /2 + N/2
pour de grandes valeurs de N, N² >> N, la complexité sera proportionnelle à N². On parle ici de complexité quadratique que l'on note O(N²)
Ecrire l'algorithme d'une fonction sommePaires(lst) qui renvoie la somme des valeurs paires d'une liste.
Ecrire un second algorithme pour moyPaires qui renvoie la moyenne des valeurs paires d'une liste.
N'oubliez pas que vous pouvez visualiser l'exécution de votre code pour vous aider à le mettre au point. |
Nous avons déjà traité la question de la recherche d'un caractère dans un texte. Nous allons ici traiter un problème assez similaire mais un peu plus délicat : chercher une chaine dans une autre. Pour plus de clarté, nous appellerons mot
la chaine recherchée, et texte
la chaine dans laquelle on effectue la recherche.
Commencez par regarder la vidéo ci-dessous pour comprendre le problème.
Ecrivez le pseudo code sur votre feuille et faites le valider : |
Utiliser un compteur, un accumulateur, ou un curseur (le tryptique CAC)
Dans de nombreux cas, on doit :
Un compteur en action
Les compteurs sont des variables qu'on incrémente quand on trouve un éléments correspondant à un critère. Parfois il n'y a pas vraiment de critère, on compte simplement tout les éléments ou toutes les occurrences, mais la notion de comptage est fréquente en algorithmique. Nous avons déjà vu des utilisations de compteurs.
Avant de coder cette fonction, écrit le pseudocode de l'algo au brouillon
quand tu as écrit ton pseudo code, demande à ton professeur de le valider puis
recopie le sur le document papier puis implémente le ci-dessous.
Ecrire une fonction qui prend en argument une liste de nombres et renvoi le nombre de multiples de 3 dans cette liste
📌 Utiliser la syntaxe ne portant pas sur les indices pour parcourir la liste
Complexité
L'algorithme contient une boucle sur les éléments de la liste lst.
On a donc au total, 1+4N + 0 opérations élémentaires dans ce code.
<br>
4N+1 est une fonction linéaire, on dit qu'on a une complexité linéaire et on note O(N)
Pour appréhender cette complexité "proportionnelle à N" on va mesurer le temps mis par l'algorithme pour donner la réponse
on va mesurer le temps mis pour calculer la moyenne d'une liste de N nombres avec N=10 puis 100 puis 1000 etc … jusqu'à 1 million.
A chaque fois on multiplie N par 10 et on obtient un temps t (on à par exemple le t100 pour n=100, et le t1000 pour N=100 ) et on affichera t1000 / t100 pour voir le rapport entre le deux.
pour le 1er calcul on ne peux pas comparer au t précédent, on le divisera par 1.
On observe donc que lorsque le nombre N d'éléments de la liste est multiplié 10, le temps de calcul est multiplié aussi par un facteur du même ordre de grandeur. Nous observons donc encore bien ici une complexité linéaire.
Un accumulateur en action
Pour sommer ou multiplier (ou soustraire ou diviser) dans une boucle, on utilise une variable accumulateur. Nous avons déjà vu des utilisations d'accumulateurs.
Avant de coder cette fonction, écrit le pseudocode de l'algo au brouillon
quand tu as écrit ton pseudo code, demande à ton professeur de le valider puis
recopie le sur le document papier puis implémente le ci-dessous.
Complexité
L'algorithme contient une boucle sur les éléments de la liste lst.
On a donc au total, 1+2N + 0 opérations élémentaires dans ce code.
<br>
2N+1 est une fonction linéaire, la complexité est linéaire soit O(N)
Comme pour les multiples de 3 précédemment évaluons la complexité en executant le programme ci-dessous.
On observe bien lorsque le nombre N d'éléments de la liste est multiplié 10, le temps de calcul est multiplié aussi par un facteur du même ordre de grandeur. Nous observons donc encore bien ici une complexité linéaire.
Un curseur en action
Les curseurs sont des variables qui retiennent la position (l'index) d'un élément présentant une caractéristique particulière dans une liste. Un bon exemple est la recherche de la position du max des éléments d'une liste.
Avant de coder cette fonction, écrit le pseudocode de l'algo au brouillon
quand tu as écrit ton pseudo code, demande à ton professeur de le valider puis
recopie le sur le document papier puis implémente le ci-dessous.
Complexité
L'algorithme contient une boucle sur les éléments de la liste lst de longueur N (en partant du 2ème)
il y a donc 1+2N-2 = 2N-1 opérations élémentaires
On a donc une complexité linéaire soit O(N)
Il existe une variante (qu'on retrouve généralement dans tous les algorithme utilisant un curseur) à l'algorithme que nous venons de voir.
Si, au lieu de l'indice de la valeur maxi, on cherche la valeur elle même, l'algorithme est légèrement différent.:
Écrivez le pseudo-code modifié pour satisfaire cette recherche, faites le valider par votre professeur, recopier le sur votre feuille puis implementer le ci-dessous.
pyexample : insérer code court
Test avec les sorties consoles :
avec un precode et repeats
avec autotest : on teste le résultat sur la valeur d'une variable
avec autotest : on teste ce que la fonction renvoie
avec autotest : on teste ce que la fonction renvoie
on peut mettre plusieurs appels dans autotests
on peut appeler avec des variables définies dans precode ou des tests choisis
Exemple d'utilisation de taboo
Vous devez écrire un code qui va produire une recette de cuisine.
Vous devrez écrire les fonction suivantes :
La recette que votre code doit produire :
ingredients : 6 pommes et un fond de tarte.
Epluchez les pommes, garnir le plat.
enfourner la tarte 45mn à 180°
servir la tarte aux pommes
Mais attention ! Dans le cas d'une tarte aux fraise, on ne doit pas cuire les fraises... dans ce cas la recette sera :
ingredients : 26 fraises et un fond de tarte.
enfourner la tarte 45mn à 180°
Epluchez les fraises, garnir le plat.
servir la tarte aux fraises
Le nombre de fruits est celui calculé par la fonction garnir.
for
-Schleife.for
-Schleife definiert wurde. for
-Schleife, um auf die einzelnen Elemente der Liste zuzugreifen.for
-Schleifen, um auf die Listenelemente zuzugreifen.for
-Schleife, läuft bis zu dem Element, bei der sich die erste (äußere) for
-Schleife momentan befindet.for
-Schleife definiert wurde.
for
-Schleife definiert wurde.
while
-Zählschleife, siehe oben.
%
-Operator.
**
-Operator.
%
-Zeichen.%