J'AI UN ALGORITHME A ECRIRE ET A TRADUIRE EN LANGAGE C (IL S'AGIT D'UN DOSSIER "POLYNÔME").
JE DEBUTE EN PROGRAMMATION ET J'AI DU MAL A M'EN SORTIR CAR LES COURS NE SONT PAS TRES CLAIRS.
MERCI POUR UNE AIDE EVENTUELLE.
VOICI LE TEXTE INTEGRAL DU DEVOIR.
Dossier "Polynôme"
Présentation du problème
Les opérations immédiates sur les polynômes sont : calculer
>sa valeur en un point,
> son polynôme dérivé
> un polynôme primitif.
On remarque qu'un polynôme est entièrement défini par la suite de ses coefficients. Nous envisageons d'automatiser les trois opérations citées plus haut.
Cahier des charges
Cet automate sera écrit en langage C (celui de Borland) par un binôme d'étudiants, à partir d'un document établi par G. Desenfant. Le délai de réalisation sera d'un mois. Cet automate sera utilisable sur un microordinateur PC.
Analyse
1) Analyse mathématique
L'énoncé du problème décompose celui ci en trois parties
>le calcul d'une valeur,
> le calcul du polynôme dérivé,
>le calcul d'une primitive
Le rang des coefficients d'un polynôme indique le degré auquel il correspond.
Exemple :
Si (4, 2, 1, 5) est la suite des coefficients d'un polynôme, on sait que
*4 est le coefficient de degré 0,
*2 est celui de degré 1,
*1 est celui de degré 2
*que 5 est le coefficient de degré 3.
Il est évident que la suite (2, 2, 15) est celle du polynôme dérivée et que (0, 4, 1, 1/3, 5/4) est la suite du polynôme primitive qui vaut 0 pour x égal 0.
Le calcul de la valeur d'un polynôme en un point donné nécessite de connaître le schéma de Hömer. Le principe de ce schéma est de factoriser. Reprenons l'exemple ci dessus
3
P(x) = 4 + 2X - X² + 5X³
ou
P(x) = 4 + X (2 - X + 5 X²)
ou encore
P(x) = 4 + x (2 + x (-1 + 5 x))
Cette présentation du calcul montre qu'il n'y a plus de calcul intermédiaire (calcul des puissances de x), que ce calcul n'implique que des multiplications et des additions. On peut aussi démontrer qu'il accroît la vitesse de calcul (On a diminué le nombre de multiplications).
2
2) Analyse informatique
Nous avons vu que cet automate est composé de plusieurs parties indépendantes. Nous allons donc construire un processus principal de type menu. En plus des trois parties déjà citées, il faudra une partie pour saisir les coefficients. Ainsi le menu sera composé des rubriques
>Saisie
>Calcul de valeurs
>Calcul du polynôme dérivé
>Calcul d'une primitive
>Arrêt.
Pour pouvoir lancer les rubriques de calcul, il faut avoir un polynôme, aussi, avant de lancer le menu, le processus lance lune première saisie.
La suite des coefficients du polynôme est contenu dans un tableau de nombres noté P dont le premier indice est 0. Nous limitons la taille du tableau P à 100 éléments (de 0 à 99). Ainsi les calculs ne peuvent être traités que pour les polynômes de degré inférieur à 100. Ce tableau P est une variable globale tout comme la variable D (pour le polynôme dérivée) et la variable Q (pour le polynôme primitive). Il est clair que le tableau D a 99 éléments (d'indice allant de 0 à 98) et Q a 101 éléments (d'indice allant de 0 à 100). Nous avons une constante taille qui vaut 100.
Nous aurons 4 parties dans cette analyse.
a) Saisie
C'est une saisie d'un tableau. L'écriture habituelle d'un polynôme, nous apprend que nous connaissons toujours le degré (donc le nombre de coefficients à saisir). Nous écrivons d'abord le monôme de plus haut degré. L'écriture se fait selon l'ordre décroissant des exposants. La saisie devra en tenir compte. Le degré n du polynôme doit être un nombre compris entre 0 et 99. Le degré du polynôme est une variable globale comme P.
b) Calcul de valeur(s)
Il est rare qu'il n'y ait qu'une seule valeur à calculer.
En principe, l'opérateur entre une valeur de la variable et l'automate calcule la valeur du polynôme puis il entre une seconde valeur et ainsi de suite. Nous obtenons une boucle classique qui doit s'arrêter lorsque l'opérateur le décide. Habituellement, nous utilisons une valeur particulière de x pour arrêter, ici toutes les valeurs de x sont bonnes. Il faudra donc utiliser un caractère particulier ce qui implique que chaque valeur de x est saisie dans une chaîne de caractères et traduite en un nombre. Le caractère choisi sera la lettre F (en majuscule ou minuscule), F est préférée à A parce que la touche A est proche des louches numériques du clavier ordinaire.
Pour calculer nue valeur, il faut utiliser le schéma d'Hömer. Une analyse rapide permet de se convaincre que ce calcul s'effectue dans une boucle. Si on appelle bloc, une expression du schéma de Hörner comprise entre une paire de parenthèses et si on hiérarchise les blocs (le premier étant le plus intérieur, le dernier étant l'expression complète), on constate que la valeur d'un bloc pour une valeur donnée de x est le produit de la valeur du bloc précédent par x auquel on ajoute le coefficient approprié (ceci correspond à une boucle). Le premier bloc vaut an x + an 1. Nous nous apercevons aussi que cette boucle est en relation avec le degré correspondant au coefficient "approprié". Le premier est n 1 et le denier 0, ces degrés sont pris cri décroissant. Pour finir remarquons que la valeur initiale de bloc doit être an.
3
Il est possible de calculer des valeurs pour la dérivée ou pour la primitive. Ainsi, le processus de calcul commencera par demander de choisir entre le polynôme, sa dérivée ou sa primitive toutefois il faut que ceux ci soient calculés. Nous avons donc besoin de 2 booléens globaux b_d et b_q qui indiquent si le calcul a été fait (Ils sont ternis à "faux" lors de la saisie du polynôme initial). Le processus permettant de lancer les calculs selon le choix du polynôme est appelé Valeur. Il lancera le processus Calculs dont les paramètres seront : le polynôme (ou la dérivée ou le primitif) et le degré du polynôme (n, n 1 ou n+ 1), ainsi qu'un message indiquant quel est le polynôme.
Le processus "valeurs" commence par un menu (sauf si les polynômes dérivé et primitif ne sont pas encore calculés). Le menu sera «variable», il dépendra des polynômes calculés et le caractère de validité de la valeur choix est donc aussi variable. Le message d'erreur dépend de la valeur de choix et du fait que le polynôme dérivé ou du polynôme primitif a été calculé.
c) Dérivation
La formule est simple. Seule la présentation du résultat peut poser un problème. On retrouvera ce problème pour la présentation de la primitive. Il faut en faire une analyse distincte (cf. affichage d'un polynôme).
d) Intégration
Remarque analogue. Seulement, il faut demander la valeur de la primitive pour une valeur de la variable. Et effectuer le calcul. Ce calcul a déjà été analysé. L'algorithme est différent puisque nous n'effectuons qu'un seul calcul. En fait, nous n'avons besoin que de la partie proprement calcul du polynôme. Cette partie est appelée calcul et l'algorithme complet est appelé Calculs.
e) Affichage d'un polynôme
Il faut l'afficher sur une ou plusieurs ligne(s) (le degré du polynôme pouvant être au plus égal à 99). Lorsque le coefficient est nul le monôme n'est pas affiché. Tous les monômes sont précédés d'un signe '+' ou "-" selon que le coefficient est positif ou négatif, seul le premier monôme n'est précédé d'aucun signe si le coefficient est positif. En fait, il est plus simple de dire qu'on affiche successivement tous les monômes non nuls, les coefficients sont tous précédés de leur signe sauf celui de degré du polynôme et s'il est positif.
Le processus d'affichage est donc une répétition pour afficher un monôme. Le processus d'affichage d'un monôme est décomposé en l'affichage du signe (si nécessaire), de l'affichage de la valeur absolue du coefficient, du signe X (sauf si le degré du monôme est 0), de l'exposant (sauf si le degré du monôme est plus petit ou égal à 1). Nous simplifierons l'écriture de l'exposant en plaçant le signe ^ avant la valeur de celui-ci.
4
IV) Algorithmes
1) Processus principal
DEBUT
saisie
Menu:
1 Saisie
2 Calcul de valeur(s)
3 Calcul du polynôme dérivé
4 Calcul d'un polynôme primitive
0 Arrêt
Entrer "choix" > choix
SELON la valeur de (choix)
1 Saisie
2 Valeur
3 Dérivée
4 Primitive
0 Rien
Autre : Afficher message d'erreur
Fin Selon
FIN
2) Saisie
DEBUT Saisie
b_d < Faux
b_q < Faux
Répéter JQ b_valid
Entrer "Quel est le degré du polynôme ? " n
b_valid < (O ≤ n <taille)
SI NON b_valid ALORS Afficher message d'erreur
Fin JQ
Pour cpt < n à 0 (pas 1)
Entrer "Quel le coefficient de degré: ", cpt, " ? " P(cpt)
Fin Pour
FIN
5
3) Valeur
DEBUT Valeur
SI (b_d OU b_q) ALORS
Répéter JQ (O<choix<4)
Aff(" 1 Calcul de valeurs du polynôme")
SI (b_d) ALORS Aff("2 Calcul de valeurs de la dérivée")
SI (b_q) ALORS Aff("3 Calcul de valeurs de la primitive")
Entrer "Votre Choix:" > choix
Fin JQ
SELON la valeur de (choix)
1 Calculs(P,n, «polynôme»)
2 SI b_d ALORS Calculs(D, n 1, «polynôme dérivé»)
SINON Aff(Message d'erreur 1)
3 SI b_q ALORS Calculs(Q, n+1, «polynôme primitif»)
SINON Aff(Message d’erreur 2)
Autre : Aff(Message d’erreur 3)
Fin Selon
Fin ALORS
SINON Calculs(P, n, «polynôme»)
FIN
DEBUT Calculs(A, n, message)
b_vaIid, < Faux
Répéter JQ b_arrët
Répéter JQ b_valid OU b_arrêt
Entrer «Valeur de la variable ou F pour arrêter» > ch_x
mettre_en_minuscule(ch_x)
b_arrêt < (ch_x = «f»)
SI Non b_arrêt ALORS b _ valid < transformer_une_chaîne_en_nombre(ch_x, x)
FIN JQ b_valid OU b_arrêt
SI NON b_arrêt ALORS
p < calcul(A, n, x)
Aff(«La valeur du », message, « pour la valeur de », x, « vaut », p)
FIN SI
FIN JQ b_arrêt
FIN
DEBUT calcul(A, n, x)
p < A(n)
Répéter Pour cpt < n à 0 (pas -1)
p < p * x + A(cpt)
Fin Pour
RENDRE (p)
FIN
6
4) Dérivation
DEBUT Dérivation
Répéter Pour cpt< 1 à n
D(cpt-1) < cpt * P(cpt)
Fin Pour
Afficher(D, n-1)
b_d < Vrai
FIN
5) Intégration
DEBUT Intégration
Répéter Pour cpt < 0 à n
Q(cpt+ 1) < P(cpt) (cpt + 1)
Fin Pour
Q(0) < 0
Entrer "Valeur de la primitive" > y
Entrer "Valeur de la variable" > x
z < calcul(Q, n+1, x)
Q(0) < y - z
Afficher(Q, n + 1°)
b_q < Vrai
FIN
6) Affichage
DEBUT Afficher (A, n)
Pour Cpt < n à 0 (pas - 1)
Aff_monôme(A(cpt), cpt, n)
Fin Pour
pause
FIN
7
DEBUT Aff_monôme(a, d, n)
SI (a ≠ 0) ALORS
SI (a < 0)
ALORS mess "-"
SINON SI (d < n) ALORS mess "+"
mess mess + écriture_en_chiffres(abs(a))
SI (d > 0) ALORS
mess < mess + " X"
SI (d > 1) ALORS mess < mess + "^"+ écriture_en_chiffres(d)
Fin SI
Ig < longueur(mess)
c < position _colonne_du_ curseur
SI ((Ig + c) > 80) ALORS passer_à_la_ligne
Aff(mess)
Fin SI
7) Transf_chiffre_nb
8) Tableau des variables
V) Programme
VI) Jeux d'essai
Vil) Bilan