Discussion :

[Inf0phile]

Bonjour,

Je commence à travailler sur le sujet 2007 de l'X : http://www.imprimerie.polytechnique...._MpInfo_4h.pdf

Question 1 : Ecrire la fonction valeur qui prend comme argument un polynôme U à coefficients dans K et un entier x, qui retourne la valeur U(x) dans K de ce polynôme en cet entier x.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Type poly = ^polycoeff;
     polycoeff = record
                 coeff : integer;
                 suivant : poly;
                 end;
 
Function valeur(U: poly ; x : integer) : integer;
 
Var somme, puissance : integer;
    p : poly;
 
Begin
     somme:=0;
     puissance:=1;
     p:=U;
     while p <> NIL do
           begin
           somme:=somme+puissance*p^.coeff;
           p:=p^.suivant;
           puissance:=puissance*x;
           end;
     valeur:=somme;
 
End;

Question 2 : Ecrire la fonction miroir qui prend comme argument un polynôme U à coefficients dans K tel que U(x) = a0 + ... + ak.x^k et qui retourne le polynôme V tel que V(x) = ak + ... + a0.x^k.

Voilà mon idée : On crée une nouvelle cellule, on parcourt la liste <a0,...,ak> jusqu'à l'élément ak que l'on injecte dans cette cellule, puis on supprime ak de la liste d'origine. Et on rajoute en tête la cellule à la liste <a0,...,ak-1>.

Juste ? Ou peut-être une méthode récursive ?

Merci !

PS : Je débute avec les pointeurs.

[darrylsite]

Je n' ai pas compiler le programme mais je crois que le programme fait bien ce que l' enonce dit.
Pour le second, c' est juste l' inverse qu' on veut. Au lieu, de considerer le premier element comme a0, on doit parcourir la liste, atteindre la fin et considerer ak comme premier element.
Pour ma part, je crois une bonne procedure reccursive fera l' affaire.

[droggo]

Fie,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
           puissance:=puissance*x;

Je ne vois pas ce que tu veux faire avec cette ligne :
prochaine puissance = puissance actuelle * x du point ?

Pour la structure, j'aurais plutôt vu

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Type poly = ^polycoeff;
     polycoeff = record
                 coeff, puissance : integer;
                 suivant : poly;
                 end;

car il faut bien avoir un moyen de connaître la puissance correspondant à un coefficient

[darrylsite]

Je n' avais pas vu ce point. Je considerais que les monome sont disposés suivant des puissances croissantes de 0 à n.
Avec cette declaration, je crois que ça simplifie vraiment les choses, enfin pour la question 2.
Il te faut maintenant crée une fonction qui permet d' elever x à la puissance n . Et utiliser une asctuce du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
somme=somme+coef*power(x,n-puissance);
//n est le degre du polynome

pour le question 2.

[Inf0phile]

Bonjour à tous les deux !

Je ne vois pas ce que tu veux faire avec cette ligne :
prochaine puissance = puissance actuelle * x du point ?

A la première itération on a : a0*1 (puisque j'ai initialisé puissance à 1).
A la deuxième itération on a : a1*x (puisque puissance devient 1*x).
Puis : a2*x² (puisque x devient x*x)
...etc

Non ?

Sinon je viens de lire le rapport http://www.imprimerie.polytechnique....nfo_MP_Rap.pdf et apparemment il vaut mieux passer par la récursivité pour ensuite calculer la complexité, donc je recommence ?

Merci !

[darrylsite]

Bonjour à tous les deux !
A la première itération on a : a0*1 (puisque j'ai initialisé puissance à 1).
A la deuxième itération on a : a1*x (puisque puissance devient 1*x).
Puis : a2*x² (puisque x devient x*x)

Le probleme n 'est pas là. En faite, revois la declaration suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
polycoeff = record
                 coeff, puissance : integer;
                 suivant : poly;
                 end;

chaque coefficient contient aussi son degre. Il se peut que les monomes ne sont pas rangés dans le meme ordre que leurs degres. Il faut utiliser le fruit de ton analyse que recrée ce que tu as defini autrement.

[Inf0phile]

En fait si par hypothèse ils sont rangés par ordre de leur monôme vu comment on a définit les listes associées aux polynômes.

Donc dans ces conditions la première question ça va ?

J'vais voir comment faire en récursif...

merci !