PROJET BISTROMATHIQUE
--------------
Introduction
--------------
The Bistromatic Drive is a wonderful new method of crossing vast
interstellar distances without all that dangerous mucking about with
Improbability Factors.
Bistromathics itself is simply a revolutionary new way of understanding
the behaviour of numbers. Just as Einstein observed that time was not an
absolute but depended on the observer's movement in space, and that
space was not an absolute, but depended on the observer's movement in
time, so it is now realized that numbers are not absolute, but depend on
the observer's movement in restaurants.
The first non-absolute number is the number of people for whom the table
is reserved. This will vary during the course of the first three
telephone calls to the restaurant, and then bear no apparent relation to
the number of people who actually turn up, or to the number of people
who subsequently join them after the show/match/party/gig, or to the
number of people who leave when they see who else has turned up.
The second non-absolute number is the given time of arrival, which is
now known to be one of those most bizarre of mathematical concepts, a
recipriversexcluson, a number whose existence can only be defined as
being anything other than itself. In other words, the given time of
arrival is the one moment of time at which it is impossible that any
member of the party will arrive. Recipriversexclusons now play a vital
part in many branches of maths, including statistics and accountancy and
also form the basic equations used to engineer the Somebody Else's
Problem field.
The third and most mysterious piece of non-absoluteness of all lies in
the relationship between the number of items on the bill, the cost of
each item, the number of people at the table, and what they are each
prepared to pay for. (The number of people who have actually brought any
money is only a sub-phenomenon in this field.)
-----------------------
Principe fondamental
-----------------------
Il s'agit de réaliser une machine qui évalue une expression
arithmétique où interviennent des ``grands'' nombres, dans une base
quelconque.
--------------
Restrictions
--------------
Les sources de votre projet doivent être conformes au CSS, tant au
niveau de la mise en forme que de la structure du répertoire de
rendu (Makefile, AUTHORS, etc...)
Vous n'avez droit qu'aux fonctions suivantes :
malloc(3) realloc(3) free(3) read(2) write(2) exit(3) assert(3)
Votre programme devra compiler _et_ fonctionner sur _toutes_ les
architectures de l'école.
Vous ne devez rien afficher de plus ou de moins que ce qui est
demandé dans le sujet. Vous serez corrigés par une machine, qui ne
tolèrera aucun écart.
-----------
Modalités
-----------
Ce projet est à réaliser en binôme. Ces binômes doivent être formés
au plus tard une semaine après l'annonce du sujet.
Vous devez stocker vos sources dans le répertoire
~/c/rendu/proj/bistromathique, en les protégeant contre l'accès par
d'autres utilisateurs (droits 600 et 700).
Votre Makefile doit générer un exécutable nommé ``bistromathique''.
Vous devez rendre votre projet sous forme d'archive cryptée, comme
l'indique la page correspondante sur le site des ACUs, avant le
vendredi 8 novembre à 23:42.
-----------------------
Critères d'évaluation
-----------------------
Ceci est un sujet à deux étages. La gestion du premier doit être
parfaite pour que le second soit pris en compte.
La base de notation d'une bistromathique de niveau 1 est 10 points.
Celle d'une bistromathique de niveau 2 est 20 points.
Les performances de la bistromathique relativement à la machine de
référence déterminent la note finale (il est donc possible pour une
bistromathique de niveau 1 de dépasser 10 points, et au niveau 2 de
dépasser 20 points).
Les détails de l'évaluation sont donnés en fin de sujet.
------------------------------
Documentation complémentaire
------------------------------
Vous disposez d'un newsgroup dedié au projet :
epita.cours.c-unix.bistromatique
(oui il y a une faute dans le nom du newsgroup, mais il est comme ca
sur le serveur de news, on ne peut rien y changer, désolés pour la
confusion éventuelle...)
Une FAQ sera peut-etre mise en place, nous vous indiquerons dans le
newsgroup ad-hoc sa création et son emplacement.
===========================
Expressions arithmétiques
===========================
Les expressions que votre bistromathique doit évaluer peuvent être
données sous deux formes. La gestion de la deuxième forme est un
``plus'' par rapport à la première, qui permet de gagner plus de
points, mais ne sera considérée que si la gestion de la première
forme est parfaite.
Forme 1: R.P.N.
---------------
Les expressions sont données dans la notation dite ``polonaise
inversée'', où les opérations que subissent les nombres sont
indiquées _après_ leurs opérandes.
* Exemple d'expression :
234233 2324244432 234243243 234234243 23423423 +/+*
* Il existe 7 types d'opérateurs qui peuvent figurer dans une
expression arithmétique en notation RPN :
- l'opérateur d'empilage
- l'opérateur d'échange d'ordre (swap)
- l'opérateur d'addition
- l'opérateur de négation
- l'opérateur de soustraction
- l'opérateur de multiplication
- l'opérateur de division
- l'opérateur ``modulo''
Forme 2: notation infixe
------------------------
Les expressions sont données dans la forme connue à opérateurs
infixe, dont les priorités sont celles du C.
* Par exemple, l'expression précédente est équivalente à l'expression
infixe suivante :
234233*(2324244432+234243243/(234234243+23423423))
* Il existe 5 opérateurs qui peuvent figurer dans une expression
arithmétique en notation infixe :
- l'opérateur d'addition
- l'opérateur de négation et de soustraction
- l'opérateur de multiplication
- l'opérateur de division
- l'opérateur ``modulo''
* Par ailleurs, les expressions peuvent être groupées par deux
opérateurs consacrés :
- l'opérateur de début de groupement
- l'opérateur de fin de groupement
Fonctionnement général
----------------------
Votre bistromathique reçoit ses paramètres sur l'entrée standard,
dans un format détaillé plus loin.
Elle effectue tous les calculs sous forme FRACTIONNELLE (et non pas
entière).
Le résultat doit être affiché sur la sortie standard, dans un format
détaillé lui aussi plus loin.
Si une erreur survient, votre bistromathique doit le signaler.
=====================
Gestion des erreurs
=====================
Bien évidement, la machine est capable est gérer les erreurs comme
toute calculatrice de notre époque qui se respecte.
* Exemples de conditions d'erreur en RPN :
- Dans la base `artye', `rya a /' provoque une erreur arithmétique
(car `a' est l'élement neutre de l'addition dans la base) ;
- Dans la même base, `a a + +' provoque une erreur de pile ;
- De même pour l'expression isolée `a a a +'.
* Exemples de conditions d'erreur en infixe :
- Dans la base `artye', `rya/a' provoque une erreur arithmétique
(car `a' est l'élement neutre de l'addition dans la base) ;
- L'expression `a*/b' provoque une erreur de syntaxe.
- Si l'entrée est en notation infixe et que la bistromathique ne
gère pas cette notation, l'erreur de gestion doit être signalée.
* Il existe quatre messages d'erreur :
- l'erreur de pile ou de gestion ;
- l'erreur de division ou de modulo par zéro ;
- l'erreur de syntaxe dans une expression ;
- l'erreur relative à un problème système (allocation mémoire,
entrées-sorties ...) ;
Quand une erreur survient, le message correspondant doit
s'afficher sur la sortie standard en lieu et place du résultat, et
le programme doit se terminer avec un code d'erreur non nul.
Le texte de ces messages est donné en entrée à la bistromathique,
comme c'est expliqué dans la section suivante.
=================
Entrées-sorties
=================
Votre bistromathique doit pouvoir travailler avec n'importe quelle
expression arithmétique, dans n'importe quelle base, avec
n'importe quelle représentation des opérateurs, et avec n'importe
quels messages d'erreur.
Format des données d'entrées
----------------------------
Les données vous seront passées sur l'entrée standard, dans
l'ordre et la forme suivants :
- Les 4 messages d'erreur, sous la forme de chaînes de caractères
nul-terminées, dans l'ordre de présentation ci-dessus ;
- un octet qui vaut 51 si l'entrée est en notation RPN, ou 69 si
l'entrée est en notation infixe ;
- les 8 opérateurs (le dernier doit être ignoré si on est en mode
infixe), un caractère par opérateur, dans l'ordre de présentation
ci-dessus ;
- la taille de la base sur 8 bits, suivie de la base ;
- la taille de l'expression sur 32 bits, suivie de l'expression ;
* Notez bien les points suivants :
- ces différents champs ne sont pas séparés par un délimiteur
particulier, et le caractère de retour à la ligne devient donc un
caractère comme les autres.
- pour la base et les opérateurs, aucun caractère n'est interdit.
- la taille de l'expression est donnée en représentation
petit-boutiste (little-endian).
Format de la sortie
-------------------
Le résultat sera affiché sur la sortie standard, sans ajouter de
retour à la ligne terminal.
1) Si l'expression d'entrée est sous la forme RPN, le résultat doit se
conformer aux contraintes suivantes :
* Si le résultat a un dénominateur non unitaire, le nominateur et le
dénominateur seront affichés l'un après l'autre. Le nominateur
sera suivi de l'opérateur d'empilage, et le dénominateur de
l'opérateur de division.
* Si le dénominateur du résultat vaut 1, seul le nominateur sera
affiché, et ne sera pas suivi de l'opérateur d'empilage.
* Si le résultat est négatif, l'opérateur de négation sera affiché
en fin de résultat.
2) Si l'expression d'entrée est sous la forme infixe, le résultat doit
se conformer aux contraintes suivantes :
* Si le résultat a un dénominateur non unitaire, le nominateur et le
dénominateur seront affichés l'un après l'autre, _séparés_ par
l'opérateur de division.
* Si le dénominateur du résultat vaut 1, seul le nominateur sera
affiché.
* Si le résultat est négatif, l'opérateur de négation / soustraction
sera affiché en tête du résultat.
Garanties
---------
Un caractère donné ne figurera pas à la fois dans la base et comme
opérateur.
Chaque caractère de la base sera unique dans la base.
==========
Exemples
==========
(Vous trouverez ultérieurement des exemples précis de données
d'entrée sur le compte des ACUs.)
Forme RPN
---------
Voici quelques exemples d'expressions et leurs résultats, dans la
base décimale connue, et en utilisant les opérateurs ' ', '.', +,
N, -, *, /, %:
E: 10 5+3/
R: 5
E: 10N7+3/
R: 1N
E: 10 7+3/
R: 17 3/
E: 1 0.-
R: 1N
E: 101 69 42%3/20+3*./N
R: 69 101/N
Forme infixe
------------
(pas d'exemple pour l'instant)
=======================
Critères d'évaluation
=======================
Votre programme sera évalué comme suit :
- À la moindre erreur de conformité de vos sources avec le CSS ou les
modalités de rendu, vous vous verrez attribuer la note définitive et
non contestable de 0.
- Si votre programme ne gère pas la notation infixe, votre
bistromathique sera notée sur 10. Si elle gère cette notation, elle
sera notée sur 20.
- À la moindre erreur dans le resultat, vous vous verrez attribuer la
note définitive et non contestable de 0.
- Si tout fonctionne bien, plus votre programme effectuera les
opérations rapidement, meilleure sera votre note.
- Si vous ne rendez rien, ou s'il y a des erreurs de compilation, vous
vous verrez attribuer la note définitive et non contestable de -5,
pour ``fainéantise''.
- Si vous essayez de détourner le sujet, ou de produire un résultat
sans que votre code C n'en soit responsable, vous vous verrez
attribuer la note de -21, pour ``foutage de gueule''.
- La tricherie est sanctionnée de la note -42 et d'un entretien avec
les responsables pédagogiques.
42.
|
