|
/////////////////////////////////////////////
|
|
// Rapha�l DE MAGALHAES 06/10 - 13/10 //
|
|
/////////////////////////////////////////////
|
|
|
|
/*
|
|
On suppose un ensemble de longueur de plynthes rang�e dans un tableau de flottant.
|
|
Les plynthes faisant 250 cm de long, le but du programme est de trouver le nombre minimal de plynthes qui permette de couvrir toutes les distance.
|
|
|
|
En sortie, le programme donne le nombre de plynthes ainsi que la r�partition des longueurs sur chaque plynthes
|
|
*/
|
|
|
|
/* PRECONDITION LA LISTE DE DONNEE DOIT ETRE TRIER PAR ORDRE DECROISSANT */
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
|
|
int pas = 1; // LE PAS CORRESPOND AU CARACTERE DE DIVISIBILITE DES VALEURS DE LA LISTE plus le pas est �lev� plus le temps de calcul sera faible.
|
|
|
|
int recherche_elem(int liste[],int longueur,int elem){
|
|
int i=0;
|
|
int renvoi=0;
|
|
|
|
for (i=0;i<longueur;i++)
|
|
{
|
|
if (liste[i]==elem){
|
|
renvoi = 1;
|
|
break;
|
|
}
|
|
}
|
|
|
|
return renvoi;
|
|
}
|
|
|
|
int recherche_max(int liste[],int longueur){
|
|
int i , max =0;
|
|
|
|
for (i=0; i<longueur;i++){
|
|
if (liste[i]>max){
|
|
max = liste[i];
|
|
}
|
|
}
|
|
return max;
|
|
}
|
|
|
|
int recherche_indice(int liste[], int longueur, int nombre){
|
|
int indice = 0;
|
|
int i = 0;
|
|
|
|
for (i=0; i<longueur;i++){
|
|
if (liste[i]==nombre){
|
|
indice = i;
|
|
}
|
|
}
|
|
return indice;
|
|
}
|
|
|
|
void supp_liste(int liste[],int longueur,int indice){
|
|
int i = 0;
|
|
|
|
for (i=0;i<longueur;i++){
|
|
if (i>indice){
|
|
liste[i-1]=liste[i];
|
|
}
|
|
}
|
|
}
|
|
|
|
int check(int liste[],int entier,int longueur,int pas){
|
|
int a = entier;
|
|
int b = 0;
|
|
int cas_pos[10]={0,0,0,0,0,0,0,0,0,0};
|
|
int cpt_pos=0;
|
|
|
|
while (1){
|
|
if (cpt_pos == 10){
|
|
cpt_pos = 0;
|
|
}
|
|
if (recherche_elem(liste,longueur,a)==1){
|
|
b = entier - a;
|
|
cas_pos[cpt_pos]=a;
|
|
|
|
if (recherche_elem(liste,longueur,b)==1){
|
|
return a;
|
|
}
|
|
|
|
else if (b == 0){
|
|
a = recherche_max(cas_pos,10);
|
|
return a;
|
|
}
|
|
|
|
else {
|
|
a = a - pas;
|
|
b = b+pas;
|
|
}
|
|
}
|
|
else if (a==0){
|
|
a = recherche_max(cas_pos,10);
|
|
return a;
|
|
}
|
|
else {
|
|
a = a - pas;
|
|
}
|
|
cpt_pos++;
|
|
}
|
|
}
|
|
|
|
void afficher_liste(int liste[],int longueur){
|
|
int i=0;
|
|
for (i=0;i<longueur;i++){
|
|
printf("%d ",liste[i]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
|
|
int valeurFichier(char nom_Fichier[20]){
|
|
|
|
FILE *f;
|
|
int nbreVal = 0;//Compteur du nombre de valeur
|
|
char buff[5] = "";//buffer
|
|
|
|
|
|
f=fopen(nom_Fichier,"rt");//ouverture du fichier
|
|
|
|
if(f != NULL)//si le fichier s'ouvre
|
|
{
|
|
while(fgets(buff,5,f) != NULL ) //on lit et stock la ligne dans un buffer jusqu'à la fin du fichier
|
|
{
|
|
if(buff[0] != '\n'){//Si la premiere valeur de la ligne est different d'un retour a la ligne on affiche et compte la valeur
|
|
nbreVal = nbreVal+1;
|
|
}
|
|
}
|
|
fclose(f); // fermetrure du fichier
|
|
return nbreVal;
|
|
printf("\nLe nombre de valeur est : %d \n",nbreVal);
|
|
}
|
|
else
|
|
{
|
|
printf("Erreur Fichier");
|
|
|
|
}
|
|
return nbreVal;
|
|
}
|
|
|
|
void creerListe(char nom_Fichier[20],int liste[]){
|
|
|
|
FILE *f;
|
|
char buff[5] = "";//buffer
|
|
int i = 0;
|
|
|
|
f=fopen(nom_Fichier,"rt");//ouverture du fichier
|
|
|
|
if(f != NULL)//si le fichier s'ouvre
|
|
{
|
|
while(fgets(buff,5,f) != NULL ) //on lit et stock la ligne dans un buffer jusqu'à la fin du fichier
|
|
{
|
|
if(buff[0] != '\n'){//Si la premiere valeur de la ligne est different d'un retour a la ligne on affiche et compte la valeur
|
|
liste[i]=atoi(buff);
|
|
i++;
|
|
}
|
|
}
|
|
fclose(f); // fermetrure du fichier
|
|
liste[i]=-1;
|
|
}
|
|
else
|
|
{
|
|
printf("Erreur Fichier");
|
|
|
|
}
|
|
|
|
}
|
|
|
|
void trierListe(int liste[],int longueur){
|
|
int mem=0;
|
|
int i,j=0;
|
|
for (i=0;i<longueur-2;i++){
|
|
for (j=i+1;j<longueur-1;j++){
|
|
if (liste[i]<liste[j]){
|
|
mem=liste[i];
|
|
liste[i]=liste[j];
|
|
liste[j]=mem;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int main(int argc, char *argv[]){
|
|
int longueur = valeurFichier(argv[1])+1;
|
|
int liste[longueur];
|
|
creerListe(argv[1],liste);
|
|
int somme=0;
|
|
int n,a,indice_a,cpt_plinthe = 0;
|
|
printf("\n");
|
|
|
|
while(liste[0]!= -1){
|
|
if (liste[0]>250){
|
|
cpt_plinthe++;
|
|
printf("Vous avez utiliser la/les plinthe(s) : %d AVEC PLUS D'UNE PLINTHES",liste[0]);
|
|
somme+=liste[0];
|
|
supp_liste(liste,longueur,0);
|
|
}
|
|
else {
|
|
n = 250 - liste[0];
|
|
printf("Vous avez utiliser la/les plinthe(s) : %d ",liste[0]);
|
|
somme+=liste[0];
|
|
supp_liste(liste,longueur,0);
|
|
|
|
while(n!=0){
|
|
|
|
if (liste[0]>n && liste[1]==-1){
|
|
break;
|
|
}
|
|
if (liste[0]==-1){
|
|
break;
|
|
}
|
|
|
|
a = check(liste,n,longueur,pas);
|
|
if (a==n){
|
|
indice_a = recherche_indice(liste,longueur,a);
|
|
printf("| %d ",liste[indice_a]);
|
|
somme+=liste[indice_a];
|
|
supp_liste(liste,longueur,indice_a);
|
|
break;
|
|
}
|
|
else if (a<0){
|
|
n+=a;
|
|
}
|
|
else {
|
|
n -= a;
|
|
indice_a = recherche_indice(liste,longueur,a);
|
|
printf("| %d ",liste[indice_a]);
|
|
somme+=liste[indice_a];
|
|
supp_liste(liste,longueur,indice_a);
|
|
}
|
|
}
|
|
}
|
|
cpt_plinthe++;
|
|
printf(" = %d cm\n",somme);
|
|
somme=0;
|
|
}
|
|
printf("\nVous devez donc utiliser %d plinthes.",cpt_plinthe);
|
|
return 0;
|
|
}
|