ALGORITHMES DE SAC A DOS ,MONNAIE ET MULTIPLICATION DE MATRICES

Soyez le premier à donner votre avis sur cette source.

Vue 9 128 fois - Téléchargée 1 570 fois

Description

- 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 : 

  • BOURAS Mohamed *
ENCADRER PAR :
  • OUINTEN Youcef *
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); }

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Bonjour et Merci de votre Algorithme.
j'ai une question : Ou ce trouve <fstream.h> , faut-il mettre <fstream>. Merci
> xetrix -
.h est l'extension du fichier bibliothèque fstream des fois ou le compilateur demande d'ajouter cette extension .
"ALGORITHMES DE SAC A DEAUX ,PIECE DE MONAIS ET MULTUPLICATION DES MATRICES"
Ce serait bien de corriger le titre et, surtout, les mots-clés :
"ALGORITHMES DE SAC A DOS ,PIECE DE MONNAIE ET MULTIPLICATION DE MATRICES"

Je sais, c'est un code source, mais éviter les grosses fautes d'orthographe le rendrait plus agréable à lire.
Autres exemples (les accents peuvent être omis, mais si c'est possible de les mettre, c'est encore mieux) :
"donner les piece utiliser" => "donner les pièces à utiliser"
"On va utilise " => "On va utiliser"
"nbr des piece a etuliser" => "nbr de pièces à utiliser"
"nbr de piece etulise est" => "nbr de pièces utilisées est"
"MENISTRE D'ENSEIGNEMENT SUPERIEURE" ="MINISTÈRE DE L'ENSEIGNEMENT SUPÉRIEUR"
"OPERATIONELLE" => "OPÉRATIONNELLE"
"IMPLIMENTATION" => "IMPLÉMENTATION"
"REALISER PAR" => "RÉALISÉ PAR"
"ENCADRER PAR" => "ENCADRÉ PAR"
"quite" => "quitte"
"donnee la somme" => "donner la somme"
"saisi la taille de la matrice" => "saisir la taille de la matrice"
"Merci aurevoire" => "Merci au revoir"
"vous avez saisez" => "vous avez saisi"

--------------
Ce serait bien de commenter beaucoup plus le code.
brsmed
Messages postés
9
Date d'inscription
lundi 9 janvier 2012
Statut
Membre
Dernière intervention
6 septembre 2017
> MClerc -
Merci beaucoup MClerc pour tous vos remarques je vais les corrige merci merci merci 1000 fois j'espère y a pas d'erreur dans ce commentaire

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.