Jean-Jacques BOURDIN
Les projets doivent
être réalisés par binômes (C'est-à-dire par groupe de DEUX
étudiants).
Les projets devront être rendus le 12 avril 2023, avant 14 heures (heure de Paris)
Tout jour de retard entamé coûte deux points sur la note (sur vingt).
Il faut fournir :
Les énoncés sont accompagnés d'un indice de difficulté de 0 à 3 étoiles (*). Les projets les plus difficiles sont ceux pour lesquels l'écart-type est le plus important : on peut ne pas réussir et avoir une très mauvaise note, il est possible d'obtenir une excellente note. Les projets les plus faciles devraient ne pas présenter de difficulté mais il est quasi-impossible d'avoir une très bonne note.
Écrire en C un programme capable d'exécuter du scheme standard. Les programmes scheme peuvent être :
Soit un terrain discret, donné par un tableau d'altitude de ses points. Le marcheur choisit deux points, un point de départ et un point d'arrivée. Il faut trouver un itinéraire entre ces deux points.
1) Essayer la ligne droite et calculer le dénivelé positif et le dénivelé négatif (i.e. le total des montées à faire et le total des descentes).
2) Essayer des variations autour de la ligne droite pour réduire le dénivelé positif.
3) Chercher un chemin réaliste, voire, chercher le meilleur chemin (par exemple le chemin qui minimise le dénivelé positif de tous les chemins possibles).
À défaut de trouver le meilleur chemin, chercher une méthode qui permette de trouver un chemin acceptable, au moins.
Un labyrinthe peut être vu comme une structure de graphe, c'est-à-dire que, pour chaque position, on connait un pointeur sur les positions disponibles à partir de là. Dans un labyrinthe 3D à salles cubiques, il y a au maximum 6 voisins pour chaque salle. Il faut donc disposer de six successeurs pour chaque noeud.
Ou encore, à partir de chaque salle, il faut disposer d'une liste de salles atteignables directement.
Définir le labyrinthe de la façon la plus simple possible.
Programmer un algorithme qui trouve une façon de sortir du
labyrinthe quelle que soit la salle dans laquelle on se trouve.
Programmer une méthode permettant de trouver la façon la plus courte de sortir du labyrinthe quelle que soit la salle dans laquelle on se trouve.
Nous donnons ici un exemple de labyrinthe simple, mais il est possible
de faire plus retort.
Exemple
Chaque salle est donnée avec U (up) si on peut monter, D (down) si on
peut descendre et les quatre (eventuellement) murs.
|
|
||
| ----------------| | | | | | | | | | | | --------- | | | | | | | | | U | | | | | | | | | ---- | | | | | | | | | | | | | | | ------------- | | | | | | | |-------------------| | | | U U | | | |-------------------| |
|-------------------| | | | | | U | | | | | | | | -------- | | | | | D | | | | | | | ----| | | | | | | | | | | ------------ | | | | | | | | U | | | | | |---| ----- ----| | | | | D U | D | | | | --------------------- | |
|-------------------| | | | | D | U | | | | | | | | | | | | | |-------| | | | | | | | | | | | | ------------| | | | | | | | U D | | | | | | ----| --------| | | | | U | D | | | | --------------------- |
|-------------------| | | | D | | | | ------------- | | | | | | | | | | | | ------------| | | | | | | | | | | | | | ----- | | | | | | | | | | | D | | | | | | | |-------| |---| | | | | | | U D | U | U | | | | | |-------------------| |
|-------------------| | | | | | | | ------------- | | | | | | | | | | | | | --------| | | | | | | | | | | | | | | | | | | |---| | | | | | | | | | | | | | | | | | | ----| | | | | | | | | D | D | D | | | | | | | |---------------| | |
Dans beaucoup de calculs, une matrice est un grand tableau quasiment
vide. Au lieu de mémoriser la totalité du tableau, il convient
de ne remplir que les cases non nulles. On peut alors les mémoriser
sous la forme d'un triplet : < x, y, valeur >. De telles cases
sont liées entre elles par des pointeurs. Vous fabriquerez donc une
liste des cases non nulles de la matrice.
Cela s'étend bien sûr à
une autre matrice et à leur addition, leur multiplication... et à la
résolution d'une équation linéaire.
Mettre en place
une telle structure puis les opérations élémentaires entre deux ou
trois matrices.
Voici un exemple de système à résoudre :
( 5 0 2 0 1 0 0 0) ( a) ( 5) ( 0 3 0 2 0 0 0 0) ( b) ( 1) ( 2 0 3 0 2 0 0 0) ( c) ( 3) ( 0 2 0 3 0 2 0 0) ( d) ( 3) ( 0 0 2 0 3 0 2 0) x ( e) = ( 2) ( 0 0 0 2 0 3 0 2) ( f) ( 2) ( 0 0 0 0 2 0 3 0) ( g) ( 1) ( 0 0 0 1 0 2 0 3) ( h) ( 0)Vous pouvez, bien sûr le résoudre "à la main", mais les déterminants et les méthodes génériques sont vraiment utiles :-)
Vous pouvez obtenir une bonne infinité d'autres exemples auprès de votre enseignant (essayez tous les nombres possibles pour toutes les tailles possibles de matrice...).
Le principe de ce jeu est simple : relier ses deux côtés opposés d'un plateau à maillage carré avec une chaîne ininterrompue de ponts. Les ponts sont à poser entre deux piles de la même couleur distantes d'un saut de cavalier des échecs.
On ne peut pas poser un pont qui croiserait un autre pont.
À chaque tour de jeu chaque joueur doit :
Créer un programme qui
Si vous avez le temps, vous pouvez aussi faire une présentation du jeu autrement que par des printf.
Ce jeu se joue sur un damier à deux joueurs. Il y a un pion blanc positionné au départ au centre du damier. A chaque tour chaque joueur peut soit positionner un pion noir sur le damier, soit deplacer le pion blanc. Le pion blanc se déplace comme un pion qui "mange un autre pion aux dames". Le but du jeu est d'emmener le pion blanc sur un des bords du damier (Nord pour le premier joueur et Sud pour le second).
On trouvera un bon résumé des règles sur ce site
Créer un programme qui
Soit un espace formé de cases cubiques (voxels) toutes de même taille. Il s'agit de calculer la trajectoire d'un rayon lumineux dans cet espace. On donnera ce rayon par les coordonnées de deux de ses points.
Puis calculer les voxels appartenant à un plan, puis à une sphère, puis à une surface complexe.
Il faudra enfin calculer l'intersection entre un rayon lumineux et une surface préalablement définie.
Soit un graphe, dont deux noeuds (D et A) sont particuliers et deux
joueurs, le lieur et le casseur. À chaque tour
de jeu, le casseur casse une arête entre deux noeuds. À chaque tour de
jeu, le lieur rend incassable une arête (non cassée) entre deux
noeuds. Si, à un moment du jeu, il n'y a plus aucun moyen d'aller de D
à A, le casseur a gagné. Si, à un moment donné, il existe un chemin
incassable reliant D à A, le lieur a gagné.
L'implémentation du ou des graphes devra être faite sous la forme soit de listes chaînées soit de tableaux d'arêtes et de brins (voir votre enseignant).
Jouer au morpion, c'est facile, vous avez tous fait cela.
On joue sur une grande grille régulière, par exemple une feuille A4
avec quadrillage 5 mm. Le joueur dessine des croix en cherchant à
en aligner des groupes de cinq.
La situation initiale consiste à prendre une page et à dessiner un
certain nombre de croix initiales. Puis, à chaque coup, le joueur doit
faire un nouvel alignement de
cinq croix. Un alignement est donc formé de quatre segments. Un
segment ne peut être utilisé qu'une fois.
Vous devez écrire un programme qui joue seul au morpion solitaire et tente de trouver le plus grand nombre possible de coups consécutifs.
Jusqu'à combien de croix suplémentaires ira votre programme ? 150 ? ****
* *
* *
**** ****
* *
* *
**** ****
* *
* *
****
Un premier coup pourrait être :
1----
* *
* *
**** ****
* *
* *
**** ****
* *
* *
****
À quoi peut succéder :
1---+
* |
* |
**** |***
* 2 *
* *
**** ****
* *
* *
****
puis :
1----+
* |
* |
**** 3+---
* 2 *
* *
**** ****
* *
* *
****
And so on...
Il arrive que les carrefours soient saturés. Dans ce cas il faut
réussir à débloquer la situation. Le principe du jeu est simple :
des véhicules sont bloqués à un carrefour, ils ne peuvent que avancer
ou reculer d'une case (plusieurs fois si nécessaire). L'un de ces
véhicules doit traverser.
Exemple de situation initiale
--------------------------- | EE DDDD | | EE DDDD | | EE BBBBBBBB| | EE BBBBBBBB| |VVVV CC S |VVVV CC S | FF CC| | FF CC| | FF AAAAAAAA| | FF AAAAAAAA| ---------------------------Notons que les véhicules V, D, B et A avancent horizontalement, les autres verticalement.
--------------------------- | EE DDDD | | EE DDDD | | EE BBBBBBBB| | EE BBBBBBBB| |VVVV CC S |VVVV CC S | IIIIIIIIIII CC| |GG HH IIIIIIIIIII CC| |GG HH FF AAAAAAAA| |GG HH FF AAAAAAAA| ---------------------------Il faut que le véhicule V sorte par la sortie S. Que devons-nous faire ?
Votre programme doit pouvoir lire une position initiale et trouver la suite de mouvements à faire pour résoudre le problème. La position initiale doit pouvoir être donnée dans un fichier.
Vous connaissez aux échecs le mouvement et le problème du cheval ? Il s'agit de faire parcourir toutes les cases à un cavalier, en suivant les mouvements normaux du cavalier aux échecs, sans jamais repasser par la même case.
Ici, avec un cheval ivre, tous les trois coups, il rue et saute, dans un mouvement plus long que d'habitude : au lieu d'un mouvement (2,1) il fait alors un mouvement (3,2). Par exemple, à partir de la case A1, le cheval fou peut passer (premier coup) en B3 (ou en C2) puis (deuxième coup) en C5 (ou C1 ou...) puis, de là, en (troisième coup, le saut) F7 (ou en E2...). And so on.
Il s'agit de
? (crible 10) = (2 3 5 7)Le crible est une méthode aisée pour chercher les nombres premiers :
Le taquin est un jeu dans lequel on déplace des pièces carrées jusqu'à les mettre toutes à leur place réservée. Une adaptation de ce jeu consiste à disposer de pièces de taille variée (par exemple des pièces de taille 1 x 1 et des pièces de taille 1 x 2) et des les amener à leur position.
Exemple :
ici, un numéro signifie une pièce et un numéro
répété est celui d'une pièce plus grande. Un vide signifie la case vide.
Situation initiale
--------------- | 7 1 3 3 | | 7 4 4 5 | | 8 10 9 | |11 2 12 6 | ---------------
--------------- | 1 2 3 3 | | 4 4 5 6 | | 7 8 9 10 | | 7 11 12 | ---------------Écrire un programme qui prend une situation initiale, une situation à obtenir et propose les mouvements pour y aboutir.
Principe du jeu : sur un plateau carré, deux joueurs
s'affrontent. Chacun joue à tour de rôle. Jouer consiste à construire
une tour sur une case. Un joueur peut jouer jusqu'à trois fois sur la
même case de façon à obtenir une tour de hauteur 3.
Toute tour posée
donne une domination sur les cases adjacentes (y compris sur la case
où elle est posée). Si la tour est de hauteur n elle donne un
contrôle de valeur n.
Quand une tour d'un joueur est sur une case dominée majoritairement
par l'autre joueur, elle est dominée et s'écroule.
Exemple :
-------------------------
| | | | | | |
6 | | | | | | |
| | | | | | |
-------------------------
| | | | | | |
5 | | | | | | |
| | | | | | |
-------------------------
| | | | | | |
4 | | a1| b1| | | |
| | | | | | |
-------------------------
| | | | | | |
3 | | | | | | |
| | | | | | |
-------------------------
| | | | | | |
2 | | | | | | |
| | | | | | |
-------------------------
| | | | | | |
1 | | | | | | |
| | | | | | |
-------------------------
1 2 3 4 5 6
Sur la case (2,4), le joueur a a posé une tour. Elle donne une case de
contrôle sur les cases voisines (2,3),(2,4),(2,5),(1,4),(3,4). Quand b
pose sa tour sur la case (3,4), il obtient un contrôle sur les cases
(3,3),(3,4),(3,5),(2,4),(4,4). Donc les contrôles sont annulés
(+1 -1 = 0) sur les cases (2,4) et (3,4). Ces deux
cases-là sont "neutres" en ce moment. Les tours qui s'y trouvent sont
en danger. Si a veut gagner, il lui suffit de jouer, par exemple,
(4,4). Dans ce cas, il prend un contrôle de plus sur la case (3,4) qui
est majoritairement dominée par a et donc la tour de b s'écroule.
Soit une grille d'anagrammes (c'est-à-dire de mots croisés dont on
connaît non pas une définition mais la liste des lettres). On suppose
l'existence d'un dictionnaire (qu'il faudra, en partie,
construire ou récupérer). Écrire un programme qui trouve la solution de ces
anagrammes.
Dans un premier temps le dictionnaire sera limité et la taille de
la grille aussi. Dans un second temps ces éléments pourront grandir
jusqu'à être en mesure de résoudre les anagrammes des journaux
spécialisés.
Il serait bon d'utiliser un fichier pour gérer le dictionnaire.
L'objectif de ce projet est de mettre en place un programme qui crée
des grilles de sudoku de différents niveaux de
difficulté.
Attention, une grille de sudoku doit respecter la
règle du sudoku (unicité des chiffres par ligne colonne et
sous-grille) ainsi que la règle suivante :
il existe une et une seule
solution à partir des valeurs déjà données.
Pour cela il faudra suivre et passer les étapes suivantes :
Si un individu est placé en face d'une série d'immeubles, il peut voir
le plus proche, P. Mais il peut voir aussi un immeuble P' si P' est
plus loin que P mais plus haut que P. De même pour P'' et les
suivants.
On veut fabriquer un paté d'immeubles. Les immeubles ont une hauteur,
donnée par un X ci-dessous. Les valeurs indiquées sur les bords sont
les nombres d'immeubles visibles de ce point. Par exemple si vous
êtes en bas et le plus à droite possible, que vous regardez vers le
haut, vous devez voir 3 immeubles, ce qui veut dire que un seul des
immeubles sera caché par les autres.
Dernières règles, dans chaque ligne et chaque colonne il y a un seul
immeuble d'une hauteur donnée et un problème a une solution
unique.
La taille du quartier est variable, l'exemple ci-dessous est de
taille 4 mais une taille 5, ou 6, ou plus doit être traitée.
1 2 3 2 1 X X X X 4 4 X X X X 1 2 X X X X 2 2 X X X X 2 2 1 2 3Vous devez maintenant trouver la hauteur de chacun des immeubles. Il est assez facile de trouver la solution :
1 2 3 2 1 4 3 2 1 4 4 1 2 3 4 1 2 2 1 4 3 2 2 3 4 1 2 2 2 1 2 3Il faut écrire un programme qui puisse
En français, il est parfois complexe de faire l'analyse
d'une phrase, même quand il n'y a pas d'ambiguïté. Il est
possible de procéder par étapes : associer les mots à
des catégories (noms, verbes, articles, adjectifs,...),
puis, en fonction de la forme de la phrase, déterminer quel
est le groupe nominal, quels sont les qualificatifs,
etc.
Le programme pourra ensuite analyser les phrases avec des
propositions subordonnées...
L'enseignant pourra donner des phrases et voir ce que votre
programme propose comme analyse.
Soit une série de n lettres, trouver tous les mots qui
existent et sont composés de ces n lettres.
Écrivez également une fonction qui calcule le nombre de points
rapportés par un mot au scrabble.
Profitez-en pour écrire une fonction qui permet de vous aider à jouer
au scrabble, c'est-à-dire qui, dans une certaine situation, propose
les mots qui rapportent le plus de points.
On peut à partir de là, mettre en place un solveur de problèmes de scrabble : on donne un problème et le programme trouve tous les scrabbles qu'on peut faire dans cette situation. (On trouvera de tels problèmes sur de vieux numéros de Jeux et Stratégie trouvables sur le web)
La dernière étape, facultative, consistera à écrire un programme qui joue contre vous en faisant à chaque tour de jeu, le plus grand total possible.NB. On se limitera à la version française du jeu.
Écrire en C un programme qui trouve toutes les solutions d'une grille de Boggle. Les mots authorisés peuvent être stockés dans un fichier texte où chaque ligne contiendra un mot. Le programme doit prendre en compte le fait qu'au Boggle toutes les lettres sont non accentuées. (à un E peut correspondre l'un des caractères suivants :ÉÈËÊ)
Dans ce jeu, des arbres et des indications sont donnés sur une grille carrée. On pourra voir des exemples sur jeux tentes
Il s'agit de poser des tentes qui doivent respecter les règles suivantes :
Écrire en C un programme qui prend trouve la solution à un tel problème. Pour cela il faudra :
Dans le jeu norinori , des régions sont délimitées sur une grille carrée. Il faut griser des dominos (groupes de deux cases) de façon à ce que :
Écrire en C un programme qui prend trouve la solution à un tel problème. Pour cela il faudra :
Mis à jour le 3/3/2023