Outils pour utilisateurs

Outils du site


tp:python:prog01

Exercices de programmation

Important Vous ne pouvez pas suivre les liens Solution à la fin de chaque exercice. C'est normal.

Solutions

Années bissextiles

Ecrivez une fonction qui prend en paramètre une année et indique si elle correspond à une année bissextile (la fonction renverra donc True ou False).

Une année est généralement bissextile si elle est divisible par 4. Les exceptions sont les années divisibles aussi par 100, qui ne sont pas bissextiles. Les années multiples de 400, elles, sont cependant bissextiles…

Bref, 1964 et 1968 sont bissextiles ; 1900 et 2100 ne le sont pas ; 2000 et 2400 le sont. L'opérateur binaire (%) calcule le reste d'une division entière.

Les affichages ne devront pas être faits dans la fonction, mais dans le programme principal.

Extrait de Wikipedia :

Depuis l'instauration du calendrier grégorien, sont bissextiles les années:

  • soit divisibles par 4 mais non divisibles par 100
  • soit divisibles par 400.

Donc, inversement, ne sont pas bissextiles les années :

  • soit non divisibles par 4
  • soit divisibles par 100, mais pas par 400.

Tours de Hanoï

Le jeu des tours de Hanoï (vu en 1A) est typique d'un programme simple à résoudre en utilisant la récursivité. Il s'agit de déplacer une tour de n disques du piquet de départ au piquet d'arrivé, en s'aidant d'un troisième piquet, en déplaçant les disques 1 par 1, et sans jamais poser un grand disque sur un plus petit.

Vous trouverez un rappel des règles ici : Tours_de_Hanoï

La procédure récursive suivante permet de résoudre le problème :

# déplace n disques du piquet i au piquet j
Procédure Tour(n, i, j) :
    Si n > 0 
        Tour(n-1, i, 6-i-j)
        Afficher ("Déplacer du piquet" i "au piquet" j)
        Tour(n-1, 6-i-j, j)
    Fin Si
Fin Procédure

Codez cette procédure en Python et utilisez la pour trouver la solution au déplacement d'une tour de 5 disques, du piquet 1 au piquet 3. Combien faut-il de déplacements ?

Chiffre de César

Le chiffre de César consiste à décaler chaque lettre du message d'origine de n rangs dans l'alphabet (la valeur de n est la clé de déchiffrement). Par exemple, sachant que le message suivant a été chiffré avec la clé 7 :

  ZHSBAHAVBZ

on retrouvera facilement le message d'origine (l'alphabet est cyclique est les espaces sont enlevés, ce qui est habituel).

Pour programmer le chiffre de César en Python, vous aurez besoin de faire de l'arithmétique sur les lettres :

  • ord(s) convertit le caractère s en nombre
  • chr(i) réalise la conversion inverse
  • % donne le reste de la division entière entre deux nombres

Écrivez une fonction cesar qui prend en paramètres une chaîne de caractères et un entier (le décalage) et renvoie la chaîne avec chaque lettre décalée. Par exemple, cesar('BONJOUR', 2) doit renvoyer : DQPLQWT

Faites un programme ( qui utilisera la fonction cesar) qui vous aidera à déchiffrer ce message (la clé n'est pas forcément 7) :

  QNAFYRPNFNPGHRYRGRAFBZZRQNAFGBHFYRFPNFQRPEVGHERFRPERGRYNCERZ
  VRERDHRFGVBANIVQREPRFGYNYNATHRQHPUVSSERPNEYRFCEVAPVCRFQRFBYH
  GVBACNEGVPHYVRERZRAGDHNAQVYFNTVGQRFPUVSSERFYRFCYHFFVZCYRFQRC
  RAQRAGQHTRAVRQRPUNDHRVQVBZRRGCRHIRAGRGERZBQVSVRF

D'où provient-il ?

Suite du lézard

La suite du lézard est une suite infinie, composée de 0 et de 1 uniquement, et a la remarquable propriété suivante :

Si on retire de la suite les termes de rang 3, 6, 9, etc, ce qui reste est la suite elle-même. De même, les nombres enlevés forment la même suite.
Il existe deux suites non triviale (non triviale = qui contient à la fois des 0 et des 1). L'une commence par 0, et l'autre par 1.
Voici le début de la suite qui commence par 0 :
010001010010000101
000011010000001110
010000000001110101
010000000000001011

En ne lisant que les caractères en gras, vous retrouvez la suite complète. En lisant uniquement les caractères qui ne sont pas en gras, vous retrouvez aussi la suite complète.

Écrivez un programme qui génère les n premiers termes de la suite du lézard.

Vendredi 13

Après avoir pris connaissance du contenu de l'article sur les vendredi 13, vérifiez par un programme ce qui est annoncé.

Conversion en binaire

Conversion d'un nombre n en binaire : le résultat est rangé dans un tableau B contenant 0 ou 1 dans chaque case.

Dans un premier temps, le nombre binaire pourra être écrit à l'envers dans le tableau. Puis le tableau sera inversé pour que les chiffres soient dans le bon ordre.

Pour extraire le chiffre binaire de poids faible d'un nombre n, il suffit de calculer le reste de la division par 2. Pour extraire le chiffre suivant, il faut, avant de calculer le reste, diviser n par 2.

Remarque : en remplaçant «2» par «k» dans l'énoncé, vous faites une conversion en base k.

Tri à bulle

Le principe du tri à bulles d'un tableau A de taille n est, lors de chaque passe, de comparer chaque paire de cases côte à côte, et de les permuter si elles ne sont pas dans le bon ordre.

On note que :

  • lors de la première passe, le maximum du tableau trouve sa place (en dernière position) ;
  • lors de la deuxième passe, le deuxième maximum du tableau trouve sa place (en avant-dernière position) ;
  1. Donc en n-1 passes on est sûr de trier le tableau. Proposez un algorithme pour cette solution simpliste. Donnez le nombre de tests effectués par cet algorithme.
  2. Il est évidemment dommage de faire toutes ces passes si le tableau est déjà trié ou se retrouve trié avant la dernière passe. Proposez un algorithme pour cette nouvelle solution. Donnez le nombre de tests effectués dans le cas le meilleur et le pire.

Vous pouvez répondre au questions en commentaire dans le code que vous rendrez.

Pile ou Face

Tiré (à pile ou face) de Logique et Calcul, Les surprises du jeu de pile ou face, de Jean-Paul Delahaye (PLS 409).

On réalise des tirages à pile ou face et on note la séquence obtenue : FFFPFFPFPFFPF.

Dans la séquence obtenue, on veut pouvoir compter le nombre d'apparitions d'un motif, et la position de sa première apparition dans la séquence.

Utilisez ces outils pour vérifier que si la séquence est assez grande, le motif PF apparaît autant de fois que le motif FF. Sur un grand nombre de tirages, suffisamment longs pour que la propriété précédente soit vraie, recherchez, des motifs FF et PF, lequel apparaît en premier dans la séquence. Celui qui apparaît en premier est appelé motif vainqueur. FF est il vainqueur aussi souvent que PF ?

Refaites des expériences, en opposant les séquences FF…FFF (n fois F) et PF…FFF (un P suivi de n-1 F). Opérez sur ces séquences assez longues pour que le nombre d'apparition des deux motifs soit à peu près égal. Quel motif est le plus souvent vainqueur ? Faites varier n (la longueur du motif) et conjecturez quelque chose.

Optimisation équation entière

(Tangente HS 39)

Tableau des investissements potentiels

N. Projet Montant à investir Valeurs actuelles nettes
1 100 80
2 80 120
3 150 60
4 20 30
5 100 -10

Exemple : Investir dans les projets 2 et 5 nécessite un investissement de 80+100=180 UM (Unité Monétaire). Cet investissement rapportera 110 UM.

Sachant qu'on dispose d'une somme totale de 200 UM, où faut-il investir pour maximiser la valeur actuelle nette totale ?

Et si à présent, on se trouve dans la situation suivante (en disposant d'une somme totale de 500 UM) ?

invest=[100 80 20 50 250 120 60 180 75 300 210]
valeur=[50  60 12 40 100 80  20  80 40 100 80]

Solution

Petites devinettes numériques

Avec la somme des chiffres

(La Recherche, été 2010)

Trouver les nombres de deux chiffres divisibles par la somme de leurs chiffres et tel que le quotient soit égal au chiffre des unités du nombre de départ.

Début des carrés

(La Recherche, été 2010)

Trouver le plus petit nombre qui élevé au carré commence par 9999.

Chiffres au cube

(La Chasse aux trésors mathématiques, I. Stewart)

Le nombre 153 est égal à la somme des cubes de ces chiffres :

\begin{displaymath}
1^3+5^3+3^3=1+125+27=153
\end{displaymath}

De tels nombres appartiennent à la catégorie des nombres narcissiques ou nombres d'Armstrong.

Trois autres nombres à trois chiffres possèdent la même propriété (sans tenir compte des nombres comme 001 qui commencent par 0). Saurez-vous les trouver ?

Solution

Catching the mice

Problème 232 de “Amusements in mathematics de Ernest Dudeney”

  232.—CATCHING THE MICE. “Play fair!” said the mice. “You know the rules of the game.”

“Yes, I know the rules,” said the cat. “I've got to go round and round the circle, in the direction that you are looking, and eat every thirteenth mouse, but I must keep the white mouse for a tit-bit at the finish. Thirteen is an unlucky number, but I will do my best to oblige you.”

“Hurry up, then!” shouted the mice.

“Give a fellow time to think,” said the cat. “I don't know which of you to start at. I must figure it out.”

While the cat was working out the puzzle he fell asleep, and, the spell being thus broken, the mice returned home in safety. At which mouse should the cat have started the count in order that the white mouse should be the last eaten?

When the reader has solved that little puzzle, here is a second one for him. What is the smallest number that the cat can count round and round the circle, if he must start at the white mouse (calling that “one” in the count) and still eat the white mouse last of all?

And as a third puzzle try to discover what is the smallest number that the cat can count round and round if she must start at the white mouse (calling that “one”) and make the white mouse the third eaten.

Solution

Conjecture de Goldbach

Conjecture de Goldbach

Goldbach (XVIIIe) a conjecturé que tout entier pair (>2) pouvait s'écrire comme la somme de deux entiers premiers. Vérifiez la conjecture pour les entiers inférieurs à mille. Réfléchissez à la meilleur façon de procéder.

Fonctions utiles :

  • zeros(m,n) (Scilab) crée une matrice nulle de m lignes et n colonnes
  • primes(n) renvoie un vecteur contenant tous les nombres premiers ${}\leq{}$ n
  • factor(n) renvoie un vecteur contenant la décomposition en facteurs premiers de n
  • length(t) donne la taille du vecteur t

Essayez de comptabiliser de combien de manières différentes chaque entier pair peut être obtenu. Vous pourrez tracer un graphique avec en abscisse les entiers pairs et en ordonnées le nombre de façons différentes dont ils peuvent être décomposés.

Solution

Dés Toscans

Le problème qui suit a été posé à Galilée (1564-1642) par Cosme II de Médicis (1590-1621), Grand Duc de Toscane (son ancien élève). Ce dernier, amateur de jeux, avait remarqué qu'au jeu qui consiste à jeter 3 dés, il atteignait plus souvent le total 10 que le total 9. Néanmoins, il avait lui même trouvé 6 façons différentes de faire 9 (6,2,1) (5,3,1) (5,2,2) (4,4,1) (4,3,2) (3,3,3) et 6 façons différentes de faire 10 (6,3,1) (6,2,2) (5,4,1) (5,3,2) (4,4,2) (4,3,3). Son expérience lui paraissait donc contraire à ce qu'il avait calculé. En 1620, Galilée rédigea dans un mémoire une explication à ce problème.

En simulant les tirages ($10^6$ reste abordable), tracez un diagramme à barres indiquant le nombre de fois où chaque total a été obtenu. Les observations du Grand Duc de Toscane étaient-elles correctes ? Avez-vous une explication ?

Solution

tp/python/prog01.txt · Dernière modification: 2018/01/03 23:01 (modification externe)