|
/////////////////////////////////////////////
|
|
// 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>
|
|
|
|
int liste[]={240,190,185,150,140,90,55,40,35,30,30,25,20,20,15,10,-1};
|
|
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 main(){
|
|
int n,a,indice_a,cpt_plinthe = 0;
|
|
int longueur = 17;
|
|
afficher_liste(liste,longueur);
|
|
while(liste[0]!= -1)
|
|
{
|
|
n = 250 - 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);
|
|
supp_liste(liste,longueur,indice_a);
|
|
break;
|
|
}
|
|
else if (a<0){
|
|
n+=a;
|
|
}
|
|
else {
|
|
n -= a;
|
|
indice_a = recherche_indice(liste,longueur,a);
|
|
supp_liste(liste,longueur,indice_a);
|
|
}
|
|
}
|
|
cpt_plinthe++;
|
|
afficher_liste(liste,longueur);
|
|
}
|
|
printf("vous devez utiliser %d plinthes.",cpt_plinthe);
|
|
return 0;
|
|
}
|