Discussion :

[atuuh]

Bonjour/Bonsoir , j'ai un simple programme Récursif en Pascal ! & j'aimerais que quelqu'n le traduise pour moi en C ++ svp :/
Le porgramme :
Nb : Le type poly est un simple tableau d'entier représentant un polynome , Le resultat doit etre R=P*Q ! mércii

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
25
26
27
28
29
30
31
32
PROCEDURE Produit_Dicho(P,Q:Poly;Var R:Poly;Degre:Integer);
 
VAR
  P2,Q1,Q2,S1,S2     : Poly;
  I,D,D1,D2          : INTEGER;
 
BEGIN
  IF Degre=0
    THEN R[0]:=P[0]*Q[0]
    ELSE BEGIN
           D1:=((Degre+1) DIV 2);
           D:=D1-1;
           I:=0;
           FOR I:=0 TO D
             DO BEGIN
                  P2[I]:=P[I+D1];
                  Q2[I]:=Q[I+D1];
                  S1[I]:=P[I]+P2[I];
                  S2[I]:=Q[I]+Q2[I];
                END;
           Produit_Dicho(P,Q,P,D);
           Produit_Dicho(P2,Q2,P2,D);
           Produit_Dicho(S1,S2,S1,D);
           R:=P;
           D2:=2*D+2;
           R[D2-1]:=0;
           FOR I:=0 TO 2*D
             DO R[I+D2]:=P2[I];
           FOR I:=0 TO 2*D
             DO R[I+D1]:=R[I+D1]+S1[I]-(P[I]+P2[I]);
         END;
END;

[the Hound]

Bonjour,

Mais c'est d'une complexité phénoménale ce code ! Au moins trois jours de travail. Je te le facture 1500€ prix d'ami

[atuuh]

Bonjour,

Mais c'est d'une complexité phénoménale ce code ! Au moins trois jours de travail. Je te le facture 1500€ prix d'ami

Complexité ? :o j'ai presque pu le traduire mais y'a plusieurs erreurs !

[ternel]

Traduction de la réponse de The Hound, en version longue:

Cher atuuh, nous constatons que tu es inscrit sur notre forum.
Ce faisant, tu as évidemment accepté notre charte qui stipule

IV-N. Lycéen, collégien, étudiant, (bref un apprenti développeur)
Vous êtes les bienvenus ici pour vous former.

Vous former, cela veut dire lire les cours et tutoriels :
http://www.developpez.com/cours/

et éventuellement poser vos questions en français correct si vous avez besoin d'aide, dans un seul forum, et dans le respect des règles du forum.

Nous ne sommes pas là pour faire vos exercices.
Entendez par là que nous serons bien évidemment tout à fait d'accord pour vous aider à résoudre votre problème, pour autant que vous fassiez vous-même des efforts.
Postez votre question, mais proposez également un début de solution, un bout de code, etc. En aucun cas, nous ne ferons le travail à votre place.

Merci de votre compréhension.

PS : Merci aux étudiants qui participent à developpez.com en écrivant des tutoriels ou en répondant aux messages des autres sur des sujets qu'ils maîtrisent bien.

Cela signifie que nous sommes parfaitement enclins à t'aider, à hauteur du travail que tu nous montrera.
En l'occurence, tu nous montre un énoncé, nous ne pouvons rien faire.

A moins de recourir à un developpeur free-lance, qui demandera un salaire en proportion de la tache.
The Hound t'a proposé un devis gratuit.

[fenkys]

Bonjour

Complexité ? :o j'ai presque pu le traduire

Comment ?

mais y'a plusieurs erreurs !

Lesquelles ?

Bonne chance.

[atuuh]

Bonjour



Comment ?



Lesquelles ?

Bonne chance.

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;
typedef struct polynome
{
	int El[50];
}polynome;
polynome algo(polynome P,polynome Q,polynome R,int degre)
{
	polynome P2,Q1,Q2,S1,S2;
		 int I,D,D1,D2;
if(degre==0) 
{
	R.El[0]=P.El[0]*Q.El[0] ;
	return R;
}
else
{
	D1=(degre+1)/2;
	D=D1-1;// Taille du polynome Resultat R //
	I=0;
	for(I=0;I<D;I++)//Boucle de décomposition du polynome //
	{
				  P2.El[I]=P.El[I+D1];
                  Q2.El[I]=Q.El[I+D1];
                  S1.El[I]=P.El[I]+P2.El[I];
                  S2.El[I]=Q.El[I]+Q2.El[I];
	}
		   P=algo(P,Q,P,D);
           P2=algo(P2,Q2,P2,D);
           S1=algo(S1,S2,S1,D);
		    R=P;
           D2=2*D+2;
           R.El[D2-1]=0;
           for(I=0;I<2*D;I++)
			  R.El[I+D2]=P2.El[I];          
		   for(I=0;I<2*D;I++)
			  R.El[I+D1]=R.El[I+D1]+S1.El[I]-(P.El[I]+P2.El[I]);
 
}
	}
int  main()
{
	polynome P,Q,R;int degre=3;
	cout<<"        Polynome P : " ;
		for(int i=0;i<degre;i++)
		{
			cout<<" P ["<<i<<"]";
			cin>>P.El[i];
		}
		cout <<endl,"****************************************";
		for(int i=0;i<degre;i++)
		{
			cout<<" Q ["<<i<<"]";		
			cin>>Q.El[i];
		}
		R=algo(P,Q,R,degre);
		for(int i=0;i<2*degre-1;i++)
		 cout<<R.El[i]<<"       ";
 
 
 
}

Voici mon travail , j'ai mis le polynome dans une structure psk j'ai voulu inclure le degré au début & puis j'ai laissé tomber , bref le resultat est vrai pour le plus haut degré mais le reste C'est des 0 et des 1

[ternel]

Tu as deux erreurs.
La première, c'est de rester en style C.
Tu pourrais utiliser vector<int> pour représenter tes polynomes, inclure l'operateur [] pour accéder aux éléments, etc.

La seconde, c'est qu'il y a de grosses différences entre le C++ et le pascal.

Un argument déclaré Var en Pascal est une référence modifiante en C++ (donc polynome&).
une boucle FOR I:=0 TO D DO <> va de 0 à D inclus, ce qui se traduit par for (int i = 0; i<=D; ++i).

[fenkys]

En C++ les parametres de fonction sont envoyés par valeur :

Code :

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

polynome algo(polynome P,polynome Q,polynome R,int degre)

Toutes les modifications que tu pourrais donc apporter à ces variables ne seront pas transmis à la fonction appelante car elles sont crées au moment de l'appel de la fonction et détruites à sa sortie.
Par ailleurs, tu ne retournes un polynôme que dans le cas ou degres == 0. Donc dans tous les autres cas tu n'as pas de return, ton polynôme calculé est donc perdu à la sortie de la fonction.

Enfin il faut choisir : tu retournes une valeur ou tu fournis un paramètre à la fonction qui recevra cette valeur. Mais évite de faire les deux.

[ternel]

Voici ton code juste rectifié sur les points que j'ai soulevé.
J'ai introduit le code traduit en commentaire devant chaque ligne.
Je ferai mieux par la suite.

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <vector>
#include <iostream>
 
class polynome {
public:
	typedef int value_type;
	typedef unsigned int size_type;
 
private:
	std::vector<value_type> values;
 
public:
	size_type degre() const {return values.size()-1;}
 
	value_type   operator[](size_type degre) const {return values[degre];}
	value_type & operator[](size_type degre)       {return values[degre];}
};
 
 
//PROCEDURE Produit_Dicho(P,Q:Poly; Var R:Poly; Degre:Integer);
void algo(polynome p, polynome q, polynome& R, int degre) {
//  IF Degre=0
//  THEN R[0]:=P[0]*Q[0]
	if (degre==0) {
		R[0]=p[0]*q[0];
		//ELSE "tout le reste" équivaut à return.
		return;
	}
 
//VAR
//  P2,Q1,Q2,S1,S2     : Poly;
//  I,D,D1,D2          : INTEGER;
 
	polynome p2;
	polynome q1,q2;
	polynome S1,S2;
//      D1:=((Degre+1) DIV 2);
//      D:=D1-1;
//      I:=0;
	polynome::size_type d1 = (degre+1)/2;
	polynome::size_type d = d1-1;
 
	//Boucle de décomposition du polynome //
//      FOR I:=0 TO D DO
//      BEGIN
//          P2[I]:=P[I+D1];
//          Q2[I]:=Q[I+D1];
//          S1[I]:=P[I]+P2[I];
//          S2[I]:=Q[I]+Q2[I];
//      END;
	for(polynome::size_type i=0; i<=d; i++) {
		p2[i] = p[i+d1];
		q2[i] = q[i+d1];
		S1[i] = p[i]+p2[i];
		S2[i] = q[i]+q2[i];
	}
 
//      Produit_Dicho(P,Q,P,D);
//      Produit_Dicho(P2,Q2,P2,D);
//      Produit_Dicho(S1,S2,S1,D);
	algo(p,q, p, d);
	algo(p2,q2, p2, d);
	algo(S1,S2, S1, d);
 
//      R:=P;
//      D2:=2*D+2;
//      R[D2-1]:=0;
	R=p;
	polynome::size_type d2 = 2 * (d+1);
 
	R[d2-1]=0;
 
//      FOR I:=0 TO 2*D DO R[I+D2]:=P2[I];
	for(polynome::size_type i=0; i<=2*d; ++i) {
		R[i+d2] = p2[i];
	}
 
//      FOR I:=0 TO 2*D DO R[I+D1]:=R[I+D1]+S1[I]-(P[I]+P2[I]);
	for(polynome::size_type i=0; i<=2*d; ++i) {
		R[i+d1] = R[i+d1] + S1[i] - (p[i]+p2[i]);
	}
}
 
using namespace std;
 
int main() {
	polynome P,Q,R;
	int degre=3;
	cout<<"        Polynome P : " ;
	for(int i=0;i<degre;i++) {
		cout<<" P ["<<i<<"]";
		cin>>P[i];
	}
	cout <<"\n****************************************" << endl;
	for(int i=0;i<degre;i++) {
		cout<<" Q ["<<i<<"]";
		cin>>Q[i];
	}
 
	algo(P,Q,R,degre);
	for(int i=0;i<2*degre-1;i++) cout<<R[i]<<"       ";
}

A tout hasard, tu sais qu'un produit de polynome, ca peut aussi s'écrire ainsi:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
polynome operator*(polynome const& a, polynome const& b) {
	polynome resultat;
	for(polynome::size_type i = 0, last_i = a.degre()+1; i < last_i; ++i) {
		for(polynome::size_type j = 0, last_j = b.degre()+1; j < last_j; ++j) {
		    resultat[i+j] = a[i]*b[j];
		}
	}
	return resultat;
}

[ternel]

Voici comment j'ai réécrit ton code.
A cause de initializer_list, tu auras besoin de C++11

Je n'ai pas fait de template, pour rester simple.

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <vector>
#include <initializer_list>
#include <iostream>
 
//pour éviter des copies inutiles, operator*= est défini en appelant operator*
class polynome;
polynome operator*(polynome const& a, polynome const& b);
 
class polynome {
public:
	typedef int value_type;
private:
	typedef std::vector<value_type> values_type;
public:
	typedef values_type::size_type size_type;
 
private:
	values_type values;
 
public:
	size_type size() const {return values.size();}	
	size_type degre() const {return values.size()-1;}
 
	polynome() = default;
	explicit polynome(size_type degre) : values(degre+1, 0) {}
 
	polynome(std::initializer_list<value_type> values) : values(values) {}
 
 
	value_type   operator[](size_type degre) const {return degre<values.size() ? values[degre] : 0;}
	value_type & operator[](size_type degre)       {if (degre>=values.size()) values.resize(degre+1, 0); return values[degre];}
 
	polynome& operator *= (polynome const& other) {
		return *this = *this * other;
	}
 
	polynome& operator -= (polynome const& other) {
		for (size_type i = 0, last = other.size(); i < last; ++i) {
		    values[i]-=other[i];
		}
		return *this;
	}
 
	polynome& operator += (polynome const& other) {
		for (size_type i = 0, last = other.size(); i < last; ++i) {
		    values[i]+=other[i];
		}
		return *this;
	}
 
   polynome upper (size_type d) const {
		polynome res(d+1);
		for (polynome::size_type i = 0; i<=d; ++i) {
			res[i] = values[i+d+1];
	   }
		return res;
	}
 
	polynome lower (size_type d) const {
		polynome res(d);
		for (polynome::size_type i = 0; i<=d; ++i) {
			res[i] = values[i];
	   }
		return res;
	}
};
 
 
inline polynome operator+(polynome const& a, polynome const& b) {
	return polynome(a)+=b;
}
 
inline polynome operator-(polynome const& a, polynome const& b) {
	return polynome(a)-=b;
}
 
polynome operator*(polynome const& a, polynome const& b) {
	polynome resultat(a.degre()+b.degre());
	for (polynome::size_type i = 0, last_i = a.degre(); i <= last_i; ++i) {
		for (polynome::size_type j = 0, last_j = b.degre(); j <= last_j; ++j) {
		    resultat[i+j] += a[i]*b[j];
		}
	}
	return resultat;
}
 
 
 
void algo(polynome p, polynome q, polynome& R, int degre) {
	if (degre==0) {
		R[0]=p[0]*q[0];
		return;
	}
 
	polynome::size_type d = ((degre+1)/2)-1;
 
	polynome p2 = p.upper(d);
	polynome q2 = q.upper(d);
 
	polynome s1 = p.lower(d) + p2;
	polynome s2 = q.lower(d) + q2;
 
	algo(p ,q , p , d);
	algo(p2,q2, p2, d);
	algo(s1,s2, s1, d);
 
	R=p;
	polynome::size_type d2 = 2 * (d+1);
 
	R[d2-1]=0;
 
	for(polynome::size_type i=0; i<=2*d; ++i) {
		R[i+d2] = p2[i];
	}
 
	for(polynome::size_type i=0; i<=2*d; ++i) {
		R[i+(d+1)] += s1[i] - (p[i]+p2[i]);
	}
}
 
 
 
 
std::ostream& operator<<(std::ostream& stream, polynome const& p) {
	for (polynome::size_type i=0; i < p.size(); ++i) {
		if(p[i]!=0) {
			if (i>0 && p[i]>0) stream << '+';
			stream << p[i];
			if (i>0) {
				stream << 'X';
				if (i>1) stream << '^' << i;
			}
		}
	}
	return stream;
}
 
 
 
using namespace std;
 
int main() {
	polynome p{1,2,3};
	polynome q{8,4};
 
	cout << "modele: "<<(p*q)<<endl;
 
	polynome r(p.degre()+q.degre());
	polynome::size_type const size = (p.size()>q.size() ? p.size() : q.size());
	algo(p,q, r, size);
 
	cout << "valeur: "<< r <<endl;
	return 0;
}