Partage

[Exercices] Venez vous entraîner !

Ce mois: Parseur de fonctions mathématiques

2 avril 2010 à 16:45:50

je veux ecrire un programme en c++ qui donne le binaire d'un nombre avec une base choisé entre 2et 9 !
8 avril 2010 à 16:14:00

Bonjour,

Je viens aux nouvelles en ce qui concerne le dernier exercice "d'endurance" du mois d'août 2009.
J'aimerais savoir où est ce que l'on en est. Y a t-il eu des réponses ? Si oui, quelles fonctionnalités ont été implémentées?

De mon côté, j'arrive péniblement à un peu plus de la moitié des fonctionnalités implémentées. Pour tout vous dire, j'avais commencé ce programme bien avant que cet exercice soit proposé. Depuis que ce programme répond à 5/8 des spécifications de l'exercice tout niveau confondu, je me suis dit qu'il serait bon de faire le point là dessus. (Oui, parce que je compte ronger mon os encore un bon moment pour les 3/8 restant. Je travaille dessus quand j'ai un peu de temps libre)

Voici donc l'état du développement de mon programme :

Citation : Carma001

Exercice du mois d'août 2009


Nom : Parseur de fonctions mathématiques
Sujet : Chaînes de caractères, algorithme


Niveau 1



  • Les priorités opératoires : les parenthèses, les puissances, les crochets (l'utilisateur pourra employer plusieurs parenthèses, plusieurs crochets, ou les deux s'il le désire), puis *, /, +, - ... : OK
  • Les multiplications implicites entre nombre-variable, nombre-fonction, nombre-parenthèse (ou crochet), variable-parenthèse (ou crochet), ainsi que fonction-parenthèse (et éventuellement d'autres, mais il faut que ce soit cohérent). : NO
  • Les principales fonctions dont voici la liste : sqrt(x) [racine carrée], pow(x,exp) [alternative à x^exp pour faire une puissance] : OK
  • Les hors-domaines de définition, c'est à dire que vous renverrez une erreur si on tente de calculer une division par zéro, ou encore la racine carrée d'un nombre négatif. : Partiel
  • La constante pi. : OK



Niveau 2


Si vous avez les connaissances et l'envie, vous pouvez implémenter plus de choses, par exemple :

  • Quelques autres fonctions : rt(x,n) [Racine n-ième], cos(x), sin(x) et tan(x) [les fonctions trigos de base], exp(x) et e^x [fonction exponentielle], ln(x) et log(x,b) [fonctions logarithme népérien et logarithme de base b] : OK
  • Les hors-domaines de définition de ces fonctions, c'est à dire que vous renverrez une erreur si on tente de calculer un logarithme négatif ou nul, ou encore la tangente d'un nombre égal à <math>\(\frac{\pi}{2}+k\pi \ , \ k \in \mathbb{Z}\)</math>. : NO
  • La constante e. : OK




Tout d'abord quelques remarques sur l'énoncé :

- La spécifications n°2 sur les multiplications implicites : ça me semble vraiment être un gadget couteux en temps de développement pour au final dérouter l'utilisateur qui doit réfléchir si il a le droit ou non d'utiliser la multiplication implicite. En particulier, il y a risque de confusion avec la syntaxe des appels de fonctions... J'ai donc délibérément choisi de passer ce point à la trappe pour l'instant.

- Les spécifications n°4 et n°7 sur les domaines de définition : c'est vraiment intéressant mais je ne vois pas ce que cela fait dans un niveau 1 (le sujet est déjà assez compliqué comme ça non ?). Quoi qu'il en soit mon programme repose entièrement sur iostream pour le support de cette fonctionnalité :-°
En effet, cout affiche "nan" (Not a Number) ou "inf" (Infinie) si le nombre (double) à afficher ne peut correspondre à une valeur correct. ("inf" est affiché pour le résultat d'une division par zéro).
Quoi qu'il en soit, pour avoir quelque chose de sérieux à ce niveau là, il faut vraiment se creuser les méninges à mon avis.. Bon après tout dépend des outils utilisés.


Sinon en ce qui concerne l'implémentation, je ne me suis autorisé que l'utilisation de la STL et celle de boost::shared_ptr. Avec un peu de mal, on finit par y arriver!

Voici un petit aperçu de ce à quoi on arrive avec un peu d'huile de coude ! >_<
InkaMath beta 0.5 by iNaKoll 2010

>> pow(x,exp)=x^exp
1

>> pow(2,3)
8

>> cos(x)_n=cos(x)_(n-1)+(-1)^n*(x^(2*n)/!(2*n))
1

>> cos(pi)_100
-1

>> (-3)^0.5
nan

>> 1/0
inf

>> A=[c c; c c]
0 0
0 0

>> c=[1 2;3 4]
1 2
3 4

>> A
1 2 1 2
3 4 3 4
1 2 1 2
3 4 3 4

>> A(c=3)
3 3
3 3

>> c
1 2
3 4

>> 3(4+5)
Error : Syntax error before '('
The operator '*' is probably missing.
0

>> 3*(4+5)
27


Comme vous pouvez le voir, le support des fonctions (avec paramètres par défauts) et des matrices est assuré.
Il reste encore pas mal de travail sur les définitions par récurrences, les séries et les suites, mais comme vous pouvez le voir (avec la fonction cos), on peut déjà arriver à quelques résultats amusants. (Note: à l'inverse de la notation mathématique la factorielle se place devant le nombre)
Par ailleurs, j'ai essayé de donner un maximum d'information à l'utilisateur en ce qui concerne les erreurs de syntaxe (une quinzaine de messages d'erreurs différents pour l'instant).

Si certains sont intéressés par les sources, je vais bientôt créer un dépôt svn sur code.google.com sous licence Apache 2.
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
9 avril 2010 à 12:50:29

Salut,

Merci pour tes remarques, je suis en accord avec toi. Le sujet a été modifié.
En tout cas, ton programme a l'air de bien marcher. Les matrices, bonne idée d'amélioration. Sinon, j'ai pas trop bien compris la syntaxe avec les "_".

Merci, bonne journée. :)
9 avril 2010 à 19:27:50

L'opérateur "_" me sert à définir des indices pour les suites, les séries et les définitions par récurrences en règle générale.

Par exemple, une suite arithmétique de raison 4 serait définie comme suit :
<math>\(U_n=U_{n-1}+4\)</math>
>> U_n=U_(n-1)+4
4

>> U_2
12


Bon ici on voit qu'il y a encore du travail sur l'initialisation (ici <math>\(U_0=4\)</math> quoi qu'il arrive et il n'y à pas grand chose à faire pour changer ca pour l'instant).

En ce qui concerne la définition de la fonction cosinus, on peut utiliser la définition à partir des séries :

<math>\(cos(x)=\sum_{0}^{\infty}(-1)^n \frac{x^{^{2 n}}}{2 n!}\)</math>
En pratique on va rarement jusqu'à l'infini, aussi on peut définir le cosinus comme suit :
<math>\(cos(x)_n=cos(x)_{n-1}+(-1)^n\times \frac{x^{^{2 n}}}{2n!}\)</math>
Il s'agit alors d'arrêter le calcul itératif lorsque la précision voulue est atteinte.

>> cos(x)_n=cos(x)_(n-1)+(-1)^n*(x^(2*n)/!(2*n))
1

>> cos(pi)_100
-1


Ici, j'ai choisi arbitrairement de calculer la somme des 100 premiers termes de la série.

Pour l'instant je travaille encore sur ces définitions par récurrence, il faudrait entre autre :
- permettre les initialisations (ex : <math>\(U_0=4\)</math>)
- calculer les expressions par itération plutôt que par récurrence (pour ne pas faire exploser la pile d'appel)
- lorsque l'indice n'est pas spécifié par l'utilisateur, le programme itère la relation jusqu'à ce que le résultat converge. Avec l'exemple de la fonction cos, cela donnerait :
>> cos(pi)
-1
Convergé en 0.015s

Si la relation ne converge pas au bout d'un certain temps, le programme se pause et demande à l'utilsateur ce qu'il souhaite faire. Avec tout ça, ça serait quand même plus sex =)

Sinon, j'ai encore pas mal d'idées pour la suite en ce qui concerne les accès aux coefficients d'une matrice, les définitions de vecteurs et le support des nombres complexes! (je ronge mon os jusqu'au bout)
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
26 juin 2010 à 11:36:56

Pour le parseur on a le droit d'utiliser LEX et YACC ?
Car si c'est le cas, j'en ai un de parseur, mais peut être (et à raison) considérez vous que c'est de la triche ?
26 juin 2010 à 12:07:56

C'est surtout sortir le canon pour tué la mouche...
26 juin 2010 à 12:46:58

Exactement ce que je me suis dit.
Bon, je m'y met serieusement, cet exo ressemble beaucoup à un exo de france ioi : http://www.france-ioi.org/train/algo/s [...] &sujet_id=525

Il n'y a pas de date limite pour le rendu des "copies" ?
26 juin 2010 à 14:34:31

iNaKoll> Une autre amélioration serait de pouvoir mettre le '!' de factorielle après le terme à "factorialiser".

The Doctor> En même temps, l'exo n'a pas grand chose à voir : tu as le droit de tout stocker en mémoire (à part entrer en mode raw, de toute façon, tu aurais du mal à faire autrement :p ). Le truc est donc (je pense, je n'ai pas encore trouvé le temps de le faire o_O ) de créer un arbre puis de le calculer (le plus dur étant de le construire).

Quand je le ferai, j'vais essayer de voir ce que donnerait les réseaux neuronaux, juste histoire de voir à quel point ils sont inadaptés à ce problème (en même temps, après avoir commencé à lire le livre là-dessus, je vais devoir trouver un moyen de l'utiliser, sinon je vais péter un câble :D )
26 juin 2010 à 14:37:46

Ne t'en fais pas, j'avais trouvé pour l'arbre, et le construire n'est pas si dur que ca.
Mon programme marche à peu près, je dois corriger des bugs et passer au niveau 2.
26 juin 2010 à 14:44:30

Carma001> Il faudra aussi gérer les cas où le résultat/l'opérande dépasse la taille maximale d'un long long int ? (En gros : il faut avoir fait BigInt d'abord ? Toujours eu la flemme de le faire celui-là :p )

The Doctor> J'ai dit que c'était le plus dur, pas que c'était dur :p
20 juillet 2010 à 20:56:48

Bonjour tout le monde
S'il vous plait est-ce que la maitrise des pointeurs dans le langage C est obligatoire pour commencer le C++ ??
20 juillet 2010 à 21:16:06

Citation : falcon

Bonjour tout le monde
S'il vous plait est-ce que la maitrise des pointeurs dans le langage C est obligatoire pour commencer le C++ ??



A mon avis, pour commencer non. Commence par apprendre avec la STL et donc un bon livre (Accelerate C++, C++ Primer...)
20 juillet 2010 à 21:20:16

Déjà, tu n'es pas dans le bon topic pour ça, ensuite, elle n'est pas obligatoire (d'ailleurs, le C n'est pas obligatoire pour apprendre le C++, contrairement à ce que fait croire, volontairement ou non, l'auteur donc les cours sont les plus lus de ce site).
Par contre, j'adule particulièrement les pointeurs, qui laissent toute la liberté au développeur (donc la liberté de faire aussi bien des trucs atroces que magnifiques).
C'est d'ailleurs pour ça, l'héritage multiple et les templates que je préfère le C++ (je sais, si ça n'avait été que les pointeurs j'aurais pû rester au C). En fait, tous ces éléments permettent de faire des choses abominables, ce dont les autres langages ne prennent pas le risque. Pour moi, d'autres langages dorlotent les développeurs : ils ne peuvent pas faire (trop) de bêtises. Par contre, le C++ permet de faire toutes les bêtises que tu veux. Dans l'autre sens, le C++ permet aussi de faire des choses bien plus belles que d'autres langages (même si il est un peu doublé sur certains points, mais les librairies évitent ce problème).
Mais je dérive, donc : Non, pas besoin des pointeurs, mais c'est conseillé pour un apprentissage approfondi.

neo2500> Conseiller des livres en anglais dès ce stage ne me semble peut-être pas le meilleur conseil à faire ;)

falcon> J'en profiterai pour te conseiller le tutoriel de Nanoc sur ce site à la fin de l'officiel, puis les cours de developpez.net ;)
20 juillet 2010 à 21:48:22

Citation : Equinoxe


neo2500> Conseiller des livres en anglais dès ce stage ne me semble peut-être pas le meilleur conseil à faire



Pourquoi?? Je suis vraiment, mais vraiment nul en anglais, pourtant j'arrive très bien à lire ces livres.
22 juillet 2010 à 22:27:08

@neo2500 et Equinoxe : Je vous remerci d'avoir répondu :)
30 septembre 2010 à 23:05:22

c'est mort ici pas de nouveau exercices?
23 octobre 2010 à 18:29:00

Un petit exo rapide (vraiment rapide) que j'ai récupérer sur un autre sujet :
Écrire la suite de lignes suivantes
1
11
21
1211
111221
etc...

Cela peut être envisagé de plusieurs manières, avec des tableaux ou des chaines de caractère (qui est un tableau de toute façon).
Bon c'est sur ce n'est pas le genre d'exercice qui occupe toute un journée mais bon.
Zeste de Savoirbépocode minimal  — Ge0 <3
23 octobre 2010 à 19:04:49

#include <iostream>
#include <string>

int main(int, char**) {
    std::string s = "1";
    std::string t;
    while (1) {
        std::cout << s << std::endl;
        t = "";
        char lastchar = s[0];
        char n = 0;
        for (std::string::iterator it = s.begin() ; it != s.end() ; ++it) {
            if (lastchar == *it) {
                ++n;
            } else {
                t += n + '0'; // Brute mais ne peut pas depasser 3
                t += lastchar;
                lastchar = *it;
                n = 1;
            }
        }
        t += n + '0';
        t += lastchar;
        s = t;
        std::cin >> t; // Pause
    }
}


Fait à la va-vite dans la boite code, mais je pense que ça marche, il y a sûrement mieux par contre ;)
23 octobre 2010 à 20:47:25

bon un petit exercice ultra-simple pour celui qui s'ennuie : (l'idée m'en vient ^^)

Exercice : Triangle de Pascal


Énoncé :


Afficher, dans une console, le triangle de pascal.
La console doit permettre a l'utilisateur de choisir un nombre fixé de lignes et d'afficher le triangle de pascal jusqu'à la ligne indiquée par l'utilisateur.
La console doit permettre a l'utilisateur d'afficher une ligne uniquement, en donnant son index.
La console doit permettre a l'utilisateur de demander une ligne N et une colone K, et afficher le résultat (qui est K parmi N)


Le triangle de pascal, mais c'est quoi ?


Le triangle de pascal sert en probabilités, et est utilisé notamment dans le binôme de Newton
Le triangle de pascal sert a donner la valeur de "K parmi N", représenté Image utilisateur.

Le triangle de pascal est :

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1

Comme vous voyez c'est... un triangle!

Comment le forme-t-on ?

Au début, on met des 1 comme présenté, donc que des 1 dans les premières et dernières cases de chaque ligne.
La première ligne comporte 1 case, la deuxième 2, la troisième 3 etc...
Le numéro de ligne représente le N, le numéro de case dans la ligne la colonne.
Donc si vous cherchez.... "3 parmi 5", on regarde 6eme ligne 4eme case (eh oui tout commence a zéro ^^) et on trouve :
"3 parmi 5" = 10.

Notez que :
"K parmi N" s'écrit <math>\(\begin{pmatrix} n \\ k \end{pmatrix}\)</math>
Image utilisateur
<math>\(\begin{pmatrix} n \\ k \end{pmatrix}\)</math> = <math>\(\begin{pmatrix} n \\ n-k \end{pmatrix}\)</math>
<math>\(\begin{pmatrix} n \\ k \end{pmatrix}\)</math> = <math>\(\begin{pmatrix} n-1 \\ k-1 \end{pmatrix}+\begin{pmatrix} n-1 \\ k \end{pmatrix}\)</math> => on lit la valeur d'une case en additionnant la case d'au dessus avec la case d'au dessus a gauche

en gros, que le triangle est symétrique...

Si vous ne m'avez pas compris, je vous invite a lire cet article sur wikipédia

La réponse de notre console


*Calcul du triangle de pascal*
1- afficher le triangle jusqu'a une ligne N.
2- afficher une ligne N.
3- afficher une case K,N.
Choix ?1
Choix de N ?4
1                  // ligne 0
1 1                // ligne 1
1 2 1              // ligne 2
1 3 3 1            // ligne 3
1 4 6 4 1          // ligne 4

Ou encore
*Calcul du triangle de pascal*
1- afficher le triangle jusqu'a une ligne N.
2- afficher une ligne N.
3- afficher une case K,N.
Choix ?2
Choix de N ?8
"K parmi 8 : " 1 8 28 56 70 56 28 8 1

Ou encore
*Calcul du triangle de pascal*
1- afficher le triangle jusqu'a une ligne N.
2- afficher une ligne N.
3- afficher une case K,N.
Choix ?3
Choix de K ?8
Choix de N ?12
"8 parmi 12" = 495


Difficultés à surmonter absolument


1- Dès que K parmi N dépasse la dixaine, la centaine etc... le triangle n'a plus la bonne forme, il faut quand même que les coefficients s'affichent les uns en dessous des autres
2- Il faut utiliser tous les raccourcis possible pour être rapide, sinon 14 parmi 120 va prendre trop de temps...
3- Ajouter une fonction (4) qui écrive <math>\((A+B)^N\)</math> avec comme entrée N. Ceci s'appelle le polynôme de Newton.
<math>\((A+B)^n = \sum_{k = 0}^n \begin{pmatrix}n \\k\end{pmatrix} \times A^k \times B^{(n-k)}\)</math>
Comme vous êtes maintenant capables d'afficher <math>\(\begin{pmatrix} n \\ k \end{pmatrix}\)</math>, vous pouvez donner l'expression littérale de la solution de <math>\((A+B)^n\)</math>
4- (optionnel) On peut chercher a mettre en forme le triangle pour qu'il ressemble a un triangle isocèle


Voila ce n'est pas très difficile comme exercice, mais il est possible sur cet exercice de créer un code hyper-hyper-mal optimisé comme très bien optimisé.
Je ne proposerai pas de solution sauf si beaucoup de personnes le demandent (et a mon avis ma solution ne serait pas la meilleure possible)

Bonne chance
A+
hilnius

23 octobre 2010 à 23:33:49

Dans ce cas, pourquoi ne pas en profiter pour donner un programme de développement de (A + B) ^ N (binôme de Newton + triangle de Pascal) ?

Un indice pour la route : <math>\((a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4\)</math>

Je n'ai pas le temps de le faire pour le moment, mais bonne chance ;)
23 décembre 2010 à 23:18:33

Pourquoi n y a t il pas de solution a cet exercice??
J ai essayer pendant un moment mais j ai eu des souci et un paquet de beug.
J'aimerai juste voir une solution de maniere a comprendre pourquoi ce que j ai fait ne fonctionne pas.
23 décembre 2010 à 23:36:39

si tu parles de l'exercice que j'ai proposé, ouvres un sujet sur le forum avec tes questions, et je me ferai une joie d'y répondre.
Anonyme
22 janvier 2011 à 13:17:16

est-ce que ce sujet et toujours valide???
et si oui est-ce que je peut savoir s'il y a un ex en cour????

merci d'avance

pierrotlefou
26 janvier 2011 à 19:22:57

Je pense qu'à se stade, on peut dire que le sujet est "mort". Quoiqu'il en soit, aucun exercice ne paraît plus.
Anonyme
26 janvier 2011 à 20:18:49

dans ce cas on devrai plutot faire de plus gros projets ou tout ceux qui veulent peuvent participer a leur guise par exemple celui qui propose le sujet écrit tout les prototypes et utilités des fonctions d'une classe puis tout ceux qui veulent code

vos avis svp
Anonyme
28 janvier 2011 à 7:39:36

Vous pouvez tout à fait proposer des exercices. ;-)

Après, je pense que de donner les prototypes et laisser la tâche aux autres de faire l'implémentation n'est pas le must du must : en effet, un exercices où tu dois aussi réfléchir à la conception est plus intéressant.
Anonyme
28 janvier 2011 à 7:45:21

OK ^^

sinon, il est où ce sujet parce que je ne le vois pas réapparaître à chaque fois que je poste ... :p
16 février 2011 à 0:05:04

C'est marrant, ça me rappelle un exercice que j'avais eu en API.

C'était la même chose (bon mis à part les cos sin etc... juste les opérations simples + = * - / ) mais en notation polonaise. Enjoy quoi ^^

Sinon, sympa l'exercice, je l'aurais bien fait si je manquais pas cruellement de temps =/

2 avril 2011 à 18:34:18

Ce sujet est-il obsolète ???
Si oui, peut-on proposer des exercices ?
2 avril 2011 à 19:03:33

oui on peut mais y'a plus persone qui répond malheuresement ^^ mais si tu as des sujets à proposer je suis preneur ^^ et j'aurais peut être des sujet qui pouraient servir pour autre chose que s'entrainer (par exemple deux classes Serveur et Client qui pêuvent communiquer gràce à boost.asio mais c'est un peu compliquer à réaliser ^^)