- 1 - Algorithme de Pièces de monnaie avec glouton.
- 2 - Algorithme de Pieces de monnaie avec glouton en programmation dynamique.
- 3 - Algorithme de sac a dos.
- 4 - Algorithme de multiplication des matrices.
En plus 4 fichiers texte contenant des données en entre.
Source / Exemple :
/* **********************************************************************
REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE
MENISTRE D'ENSEIGNEMENT SUPERIEURE
ET DE LA RECHERCHE SCIENTIFIQUE
UNIVERSITE AMMAR TLAIDJI LAGHOUAT
DEPARTEMENT INFORMATIQUE ET MATHEMATIQUE
RECHERCHE OPERATIONELLE
IMPLIMENTATION DES ALGORITHMES DE RO
REALISER PAR :
ENCADRER PAR :
2012/1013
#include <iostream>
#include <fstream.h>
using namespace std;
ifstream gltn("Fichier/glouton.txt");
ifstream glpd("Fichier/gloutonpd.txt");
ifstream sac("Fichier/sacados.txt");
ifstream mul("Fichier/multimat.txt");
int start[100];int end[100];
//algorithme glouton
void piecem(int s)
{
int y;
y = 15;
int i,n,k,x[100],v[100];
cout<<""<<endl;
cout<<" nbr des piece a utiliser ";
gltn>>n;
cout<<n<<endl;
cout<<""<<endl;
cout<<" donner les piece utiliser :"<<endl;
cout<<""<<endl;
for (i=1;i<=n;i++)
{
cout<<" V["<<i<<"] = ";
gltn>>v[i];
cout<<v[i]<<endl;
}
cout<<""<<endl;
i=1;
if (s==0)
{
cout<<""<<endl;
cout<<" Arreter "<<endl;
cout<<""<<endl;
}
else
{
x[i]=s/v[i];
k=s;
for (i=1;i<=n;i++)
{
k=k%v[i];
x[i+1]=k/v[i+1];
}
cout<<""<<endl;
for (i=1;i<=n;i++)
{
cout<<" On va utilise "<<x[i]<<" piece(s) de "<<v[i]<<endl;
}
cout<<""<<endl;
}
}
//algorithme glouton avec la programmation dynamique
void valeur(int Z[100][100],int s,int n)
{
int i,j,t,l;
int x[100],v[100];
for (l=1;l<=n;l++)
{
cout<<" V["<<l<<"] = ";
glpd>>v[l];
cout<<v[l]<<endl;
}
cout<<""<<endl;
for (j=1;j<=n;j++)
{
x[j]=0;
}
j=1;
l=1;
i=n;
t=s;
while((s>0)&&(i>1))
{
if(Z[t][i]!=Z[t][i-1])
{
x[l]=s/v[l];
s=s%v[l];
l++;
}
else
{
i--;
l++;
}
}
cout<<""<<endl;
for (j=1;j<=n;j++)
{
cout<<" On va utilise "<<x[j]<<" piece(s) de "<<v[j]<<endl;
}
}
void glouton(int s)
{
int i,t,n;
int Z[100][100],v[100];
cout<<" nbr des piece a etuliser ";
glpd>>n;
cout<<n<<endl;
for (i=1;i<=n;i++)
{
cout<<" V["<<i<<"] = ";
glpd>>v[i];
cout<<v[i]<<endl;
}
//cout<<""<<endl;
for (i=1;i<=n;i++)
{
Z[0][i]=0;
}
for (t=0;t<=s;t++)
{
Z[t][1]=t;
}
for (i=2;i<=n;i++)
{
for (t=1;t<=s;t++)
{
if(t<v[i])
{
Z[t][i]=Z[t][i-1];
}
else
{
Z[t][i]=min(Z[t][i-1],(Z[t-v[i]][i])+1);
}
}
}
cout<<""<<endl;
for (i=1;i<=n;i++)
{
for (t=0;t<=s;t++)
{
cout<<" "<<Z[t][i];
if(t==s)
{
cout<<endl;
}
}
}
cout<<""<<endl;
cout<<" nbr de piece etulise est :"<<Z[s][n]<<endl;
cout<<""<<endl;
valeur(Z,s,n);
}
//algorithme de sac a dos
void sacados(int n,int g)
{
int i,v;
int c[10],w[10],x[10],Z[100][100];
for (i=1;i<=n;i++)
{
cout<<" c["<<i<<"] = ";
sac>>c[i];
cout<<c[i]<<endl;
}
cout<<endl;
for (i=1;i<=n;i++)
{
cout<<" w["<<i<<"] = ";
sac>>w[i];
cout<<w[i]<<endl;
}
cout<<endl;
for (v=1;v<=g;v++)
{
Z[v][0]=0;
}
for (i=1;i<=n;i++)
{
for (v=0;v<=g;v++)
{
if(v<w[i])
{
Z[v][i]=Z[v][i-1];
}
else
{
Z[v][i]=max(Z[v][i-1],Z[v-w[i]][i-1]+c[i]);
}
}
}
for (i=0;i<=n;i++)
{
for (v=0;v<=g;v++)
{
cout<<" "<<Z[v][i];
if(v==g)
{
cout<<endl;
}
}
}
cout<<endl;
cout<<" le cout maximum qu'on peut obtenir est : "<<Z[g][n]<<endl;
cout<<endl;
for (i=0;i<=n;i++)
{
x[i]=0;
}
int k=n;
while((g>0)||(k>0))
{
if (Z[g][k]!=Z[g][k-1])
{
x[k]=x[k]+1;
g=g-w[k];
}
k--;
}
cout<<""<<endl;
cout<<" On va prendre le(s) objet(s) : ";
for (int j=1;j<=n;j++)
{
if (x[j]==1)
{
cout<<" "<<j<<" , ";
}
}
}
//algorithme de multiplication de matrices
int indicemin(int n,int Z[100][100])
{
int i,j,d;
int deb;
int fin;
for(d=1;d<=n-1;d++)
{
int min=1000000;
for(i=1;i<=n-d;i++)
{
j=i+d;
if(Z[i][j]<min)
{
min=Z[i][j];
deb=i;
fin=j;
}
}
cout<<" le min est dans la diagonale "<<d<<" est : "<<min<<endl;
start[d]=deb;
end[d]=fin;
}
cout<<""<<endl;
}
int min(int i,int j,int Z[100][100],int d[100])
{
int min,M;
min=10000000;
for (int k=i;k<j;k++)
{
M=(Z[i][k]+Z[k+1][j])+(d[i-1]*d[k]*d[j]);
if(M < min)
{
min=M;
Z[j][i]=k;
}
}
return min;
}
void multimat(int n)
{
int h[100],y[100];
int i,j,s,d,k,D[100];
int Z[100][100];
for (i=0;i<=n;i++)
{
cout<<" D["<<i<<"] = ";
mul>>D[i];
cout<<D[i]<<endl;
}
for (i=1;i<=n;i++)
{
Z[i][i]=0;
}
for(d=1;d<=n-1;d++)
{
for(i=1;i<=n-d;i++)
{
j=i+d;
Z[i][j]=min(i,j,Z,D);
}
}
cout<<""<<endl;
for (i=1;i<=n;i++)
{
for (int t=1;t<=n;t++)
{
cout<<" "<<Z[i][t];
if(t==n)
{
cout<<endl;
}
}
}
cout<<""<<endl;
indicemin(n,Z);
for(int g=1;g<=n-1;g++)
{
if (end[g]-start[g]!=1)
{
cout<<" ( M"<<start[g]<<" *...* M"<<end[g]<<" )"<<endl;
}
else
{
cout<<" ( M"<<start[g]<<" * M"<<end[g]<<" )"<<endl;
}
}
}
void page_de_garde()
{
cout<<""<<endl;
cout<<" **********************************************************************"<<endl;
cout<<" REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE"<<endl;
cout<<""<<endl;
cout<<" MENISTRE D'ENSEIGNEMENT SUPERIEURE "<<endl;
cout<<""<<endl;
cout<<" ET DE LA RECHERCHE SCIENTIFIQUE"<<endl;
cout<<""<<endl;
cout<<" UNIVERSITE AMMAR TLAIDJI LAGHOUAT"<<endl;
cout<<""<<endl;
cout<<" DEPARTEMENT INFORMATIQUE ET MATHEMATIQUE"<<endl;
cout<<""<<endl;
cout<<" RECHERCHE OPERATIONELLE "<<endl;
cout<<""<<endl;
cout<<" IMPLIMENTATION DES ALGORITHMES DE RO"<<endl;
cout<<""<<endl;
cout<<""<<endl;
cout<<" REALISER PAR : "<<endl;
cout<<""<<endl;
cout<<" * BOURAS Mohamed *"<<endl;
cout<<""<<endl;
cout<<" ENCADRER PAR :"<<endl;
cout<<" "<<endl;
cout<<" * OUINTEN Youcef *"<<endl;
cout<<""<<endl;
cout<<" 2012/1013"<<endl;
cout<<""<<endl;
cout<<"**********************************************************************"<<endl;
}
int main()
{
bool b;
int c;
page_de_garde();
system ("pause");
system ("cls");
cout<<""<<endl;
cout<<""<<endl;
do
{
system ("cls");
b=true;
cout<<""<<endl;
cout<<""<<endl;
cout<<" Menu principale"<<endl;
cout<<""<<endl;
cout<<""<<endl;
cout<<" - 1 - Algorithme de Pieces de monnaie avec glouton "<<endl;
cout<<""<<endl;
cout<<" - 2 - Algorithme de Pieces de monnaie avec glouton en programmation dynamique "<<endl;
cout<<""<<endl;
cout<<" - 3 - Algorithme de sac a dos "<<endl;
cout<<""<<endl;
cout<<" - 4 - Algorithme de multiplication des matrices "<<endl;
cout<<""<<endl;
cout<<" - 5 - Quite l'application "<<endl;
cout<<""<<endl;
cout<<""<<endl;
cout<<" Saiser votre choix : ";
cin>>c;
cout<<""<<endl;
switch (c)
{
case 1:
{
system ("cls");
int s;
char questio='o';
while((questio=='o')||(questio=='O'))
{
cout<<""<<endl;
cout<<""<<endl;
cout<<""<<endl;
cout<<" donnee la somme ";
gltn>>s;
cout<<s<<endl;
piecem(s);
cout<<""<<endl;
cout<<""<<endl;
cout<<" voulez-vous repeter? (o)oui/(n)non ";cin>>questio;cout<<endl;cout<<endl;
system ("cls");
}
break;
system ("pause");
}
case 2:
{
system ("cls");
int s;
char questio='o';
while((questio=='o')||(questio=='O'))
{
cout<<""<<endl;
cout<<" donnee la somme ";
glpd>>s;
cout<<s<<endl;
cout<<""<<endl;
glouton(s);
cout<<""<<endl;
cout<<" voulez-vous repeter? (o)oui/(n)non ";cin>>questio;cout<<endl;cout<<endl;
system ("cls");
}
break;
system ("pause");
}
case 3:
{
system ("cls");
int n,g;
char questio='o';
while((questio=='o')||(questio=='O'))
{
cout<<""<<endl;
cout<<""<<endl;
cout<<""<<endl;
cout<<" donnee les valeurs de N ";
sac>>n;
cout<<n<<endl;
cout<<""<<endl;
cout<<" donnee les valeurs de W ";
sac>>g;
cout<<g<<endl;
sacados(n,g);
cout<<""<<endl;
cout<<""<<endl;
cout<<" voulez-vous repeter? (o)oui/(n)non ";cin>>questio;cout<<endl;cout<<endl;
system ("cls");
}
break;
system ("pause");
}
case 4:
{
system ("cls");
int n;
char questio='o';
while((questio=='o')||(questio=='O'))
{
cout<<""<<endl;
cout<<""<<endl;
cout<<""<<endl;
cout<<" saisi la taille de la matrice : ";
mul>>n;
cout<<n<<endl;
cout<<""<<endl;
multimat(n);
cout<<""<<endl;
cout<<""<<endl;
cout<<" voulez-vous repeter? (o)oui/(n)non ";cin>>questio;cout<<endl;cout<<endl;
system ("cls");
}
break;
system ("pause");
}
case 5:
{
b=false;
system ("cls");
cout<<""<<endl;
cout<<""<<endl;
cout<<" * Merci aurevoire * "<<endl;
cout<<""<<endl;
cout<<""<<endl;
break;
}
default:
{
cout<<""<<endl;
cout<<""<<endl;
cout<<" vous avez saisez une valeur incorrect"<<endl;
cout<<""<<endl;
cout<<""<<endl;
break;
}
}
system ("pause");
}
while (b==true);
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.