Fonctions

Définitions

Les fonctions permettent de définir un traitement complexe une fois et de le réutiliser. Nous avons déjà utilisé cette idée en TD avec le quotient et l’intégration.

Comme un algorithme, une fonction a un nom, un rôle, des entrées, des sorties et des déclarations. Cependant, en java, nous n’aurons droit qu’à 1 sortie.

La syntaxe java pour une fonction f prenant en entrée 2 réels et donnant un entier en sortie est la suivante :

//      ,- Type de la sortie
//      |  ,- Nom de la fonction
//      |  |   ,---------,- Types des entrées
//      v  v   v         v
static int f(double a, double b) {
    int x;
    ...
    return x;
}

a et b sont les paramètres formels de la fonction et peuvent être utilisés dans le corps. Quand la fonction est appelée, on lui passe des expressions du bon type comme paramètres effectifs, ces expressions sont évaluées et ces valeurs sont affectées aux paramètres formels respectifs.

On peut ensuite utiliser la fonction f(1.0, 1+1) comme une expression.

On s’attachera à faire des fonctions sans effets de bords, c’est-à-dire des fonctions qui n’affichent rien et ne demandent pas de valeur à l’utilisateur.

Les fonction correspondent donc à des expressions. Il existe une construction similaire qui correspond aux instructions : les procédures. Les procédures n’ont pas de résultats, donc pas de return et pas de type de sortie. Cela se dénote par le pseudo-type void.

main est une procédure. System.out.println est une procédure.

Exercices

Exercice 1

Écrire une fonction quotient qui prend deux entiers et calcule le quotient de la division entière sans utiliser / ou %.

Utiliser cette fonction quotient pour faire la décomposition d’une somme en billets et pièces de 10, 5, 2 et 1 (toujours sans utiliser %).

Exercice 2

Écrire une fonction puissance. Choisir les meilleurs types possible. La tester pour calculer 2^{10}, 10^2, 3.14^2 et 2^{3.14}.

Exercice 3

Écrire une fonction qui renverse un tableau d’entiers.

Écrire une procédure qui affiche un tableau d’entiers.

Demander un tableau à l’utilisateur. Sans utiliser de nouvelles variables, afficher le tableau puis afficher son renversé à l’aide des fonctions définies ci-dessus.

Exercice 4

Écrire une procédure qui affiche un tableau de tableaux d’entiers sous forme rectangulaire, par exemple

[[ 1, 2],
 [ 3, 4],
 [ 5, 6],
 [ 7, 8]]

Il ne doit pas y avoir de virgules superflues.

Exercice 5

Écrire une fonction qui teste la primalité d’un nombre. La tester avec les valeurs 1, 2, 3, 53, 54, et 55.

L’utiliser pour afficher tous les nombres premiers inférieurs à 100.

Écrire une fonction qui renvoie les facteurs (diviseurs) premiers d’un nombre donné. Par exemple, les facteurs premiers de 63 sont 3 et 7.

Quel est le plus grand facteur premier de 13195 ?

Exercice 6

La fonction de Collatz est définie pour les entiers naturels par “si n est pair, collatz(n)=n/2 ; sinon, collatz(n)=3n+1”.

Écrire cette fonction collatz et la tester pour les entrées 3, 10, 5, 16, 8, 4, 2 et 1.

Écrire une fonction syracuse qui calcule le nombre d’applications de collatz suffisant pour obtenir 1. Par exemple, syracuse(2) vaut 1 ; syracuse(3) vaut 7 ; syracuse(4) vaut 2.

Quelle est la plus grande valeur de syracuse pour les entiers jusqu’à 100 ?

Exercice 7

Écrire une fonction de conversion d’un nombre en base 10 vers un nombre en base 2 représenté par un tableau de 0 et de 1.

Écrire une fonction qui fait l’inverse.

Écrire une fonction de conversion de base pour n’importe quelle paire de bases. Les “chiffres” de la base n seront les entiers de 0 à n-1 (donc en hexadécimal, on a des chiffres 10, 11, …, 15 et non a, b, …, f.

Exercice 8

Écrire une fonction estDans qui teste si un entier fait partie d’un tableau.

Exercice 9

Écrire une fonction sousTableau qui prend deux tableaux t1 et t2en entrée et teste si t1 est inclus dans t2, c’est-à-dire si t2 est une suite de cases quelconque, puis les mêmes cases que t1 puis une autre suite quelconque de cases.

Exercice 10

Écrire un programme de quiz. Une structure contient des questions, une structure contient les bonnes réponses associées. Le programme pose les questions dans un ordre aléatoire et attribue 1 point à l’utilisateur s’il donne exactement la bonne réponse. Une fois toutes les questions posées, afficher le score.

Exercice 11 : Multiplication de chaîne

Écrire une fonction multiplieCh qui prend une chaîne de caractère ch et un nombre entier n et renvoie la chaîne répêtant n fois la chaîn ch.

Par exemple multiplieCh("ah", 5) vaut "ahahahahah".

Exercice 15 : Motus

Dans le jeu Motus, le joueur doit deviner un mot dont la première lettre et la longueur sont données. Le joueur propose un mot et pour chaque lettre, il va savoir si elle est bonne et bien placée, présente dans le mot mais mal placée ou absente dans le mot.

Ainsi, dans la grille ci-dessus, je sais que le “L” et le “O” sont bien placés, qu’il y a un “U”, un “T” et un “E” mais pas aux endroits proposés et qu’il n’y a ni “R”, ni “S”.

Pour manipuler les chaînes plus simplement, nous les convertirons en tableaux de caractères avec toCharArray :

String ch = "ancre";
char[] tc = ch.toCharArray();

Pour l’affichage, nous utiliserons des codePoints qui représentent les caractères unicodes par des entiers. Il existe dans unicode des caractères représentant les lettres dans des carrés ou des ronds : le nombre hexadécimal 0x1F170 représente 🅰 (lettre bien placée) ; le nombre 0x1F150 représente 🅐 (lettre mal placée) ; le nombre 0x1F130 représente 🄰 (lettre absente).

On peut fabriquer une chaîne composée des caractères correspondant à des codePoints donnés avec new String(int[] codePoints, int offset, int length).

int[] tcp = {0x1F15D, 0x1F130, 0x1F172, 0x1F181, 0x1F174};
String resultat = new String(tcp, 0, 5);

Écrire une fonction estDans qui dit si un caractère est présent dans un tableau de caractères.
Écrire 3 fonctions :
- bienPlacee qui prend un caractère et renvoie le codePoint de ce caractère dans un carré plein.
- malPlacee qui prend un caractère et renvoie le codePoint de ce caractère dans un rond plein.
- absent qui prend un caractère et renvoie le codePoint de ce caractère dans un carré.
Écrire une procédure testeMot qui prend le mot à trouver, demande à l’utilisateur une proposition et affiche les indices liés à cette proposition.
Écrire un programme qui répête cette procédure jusqu’à ce que le joueur ait trouvé le mot correct.
Dans le cas des lettres répêtées, dans la proposition, une lettre ne doit pas être correcte trop souvent : s’il y a un seul “E” dans le mot à trouver, on ne doit pas dire pour chaque “E” de la proposition qu’il est présent mais mal placé (ou bien placé) mais seulement le dire pour 1. Par exemple si le joueur propose “encre” pour “ancre”, le premier “E” doit être considéré comme absent.

Exercice 98 : Sudoku

Une grille de sudoku est un tableau de 9 tableaux de 9 entiers.

-------------------------------
|       9 |         |         |
|    2    |    8  3 |         |
|    5    | 4       |         |
-------------------------------
|         | 8  4    | 1  5    |
| 6       |    9    |         |
|    1    |       2 |       7 |
-------------------------------
|    6    |         |    7    |
|         | 5     9 |    4  3 |
|       3 | 2       |       9 |
-------------------------------

Écrire une procédure affichant une grille de sudoku.
Écrire une fonction vérifiant que chaque ligne ne comporte pas deux fois le même chiffre (hors 0).
Écrire une fonction vérifiant que chaque colonne ne comporte pas deux fois le même chiffre.
Écrire une fonction qui pour chaque carré 3x3 vérifie que le même chiffre n’apparaît pas deux fois.
Écrire une fonction qui vérifie si la grille ne contient aucune incohérence. Si la grille est complète, cette fonction permet de tester si la grille est ou non correcte.
Écrire une fonction énumérant les cases n’ayant pas encore de valeur.
Écrire une fonction énumérant les possibilités pour remplir les cases n’ayant pas encore de valeurs. Par exemple, s’il y a deux cases sans valeurs, les possibilités seront : [1, 1], [1, 2], [1, 3], .., [1, 9], [2, 1], [2, 2], …, [9, 9].
Résoudre la grille de sudoku.

Exercice 99 : Sudoku

La méthode de résolution de l’exercice précédent est trop inefficace pour résoudre une grille. Il faudrait une quantité de mémoire énorme pour stocker l’ensemble des possibilités créées dans l’avant-dernier point (s’il manque 2 cases, il y a 9 \times 9 tableaux de 2 entiers à stocker, soit 162 int donc 648 octets).

Quelle serait la mémoire nécessaire pour stocker l’ensemble des possibilités pour la grille proposée ci-dessus (qui a 23 cases remplies) ?

Nous allons utiliser une méthode plus intelligente¹ : pour chaque case, nous allons lister les valeurs impossibles. Ainsi, pour la case en haut à gauche de la grille, les valeurs impossibles sont 9 (à cause de la ligne), 9, 2, et 5 (à cause du carré) et 6 (à cause de la colonne), donc la liste des valeurs impossibles est : [2, 5, 6, 9]. Ensuite, on va choisir la case où cette liste est la plus courte et tester si on peut résoudre par la même méthode avec chacune des valeurs possibles.

Reprendre la fonction estDans de l’exercice 8.
Écrire une fonction union qui prend en entrée 2 tableaux sans doublons et renvoie un tableau sans doublon contenant toutes les valeurs présentes dans au moins un des tableaux d’entrée.
Écrire une fonction ajoute qui prend un tableau et une valeur en entrée et renvoie le tableau initial auquel on a ajouté la valeur.
Écrire une fonction impossibles qui prend une grille (partielle), et les indices d’une case et renvoie le tableau des valeurs interdites (sans doublon). Si une case est déjà remplie, toutes les autres valeurs sont impossibles.
Écrire une fonction antigrille qui renvoie la grille des impossibles.
Écrire une fonction trouvemin qui prend une antigrille et renvoie une paire (un tableau à deux éléments) contenant les indices d’une des cases ayant le plus d’impossibles en dessous de 8. Cette fonction devra renvoyer une paire spéciale représentant le succès si tous les impossibles sont à 8, ou une autre paire spéciale si un des impossibles est de longueur 9 (donc la grille n’a pas de solution).
Écrire une fonction grilleNeuve qui prend une antigrille, les indices d’une case et une valeur et produit une grille contenant les valeurs de toutes les case nécessaires (la liste des impossibles a 8 éléments) plus la valeur passée en argument dans la case indiquée par ses indices.
Écrire une fonction resolution qui prend une grille en entrée,
1. calcule son antigrille,
2. trouve une case minimisant les possibles,
3. pour chaque valeur possible exécute la fonction résolution sur la grilleNeuve produite en affectant cette valeur dans la case considérée.
4. affiche la grille trouvée en cas de succès, ne dit rien en cas d’échec.
Tester la résolution avec la grille précédente.
Tester la résoution avec des grilles réputées difficiles : https://github.com/attractivechaos/plb/blob/master/sudoku/sudoku.txt. Il pourra être nécessaire de créer une fonction qui transforme une chaîne de 81 caractères en la grille de Sudoku associée.

http://norvig.com/sudoku.html↩︎