[C] besoin d'aide aide problème en C

Fermé

Sportif_C - 24 juil. 2011 à 11:55
Hxyp Messages postés 401 Date d'inscription vendredi 28 janvier 2011 Statut Membre Dernière intervention 27 avril 2014 - 25 juil. 2011 à 16:42

Bonjour,

admettons qu'au on a des boites numérotées de 1 à 9.
Dans chaque boite on a un chiffre positif ou négatif.
Exemple 1 2 3 4 5 6 7 8 9
3 2 1 -2 -4 1 2 -1 -2

On cherche écrire un algorithme qui permet d'échanger la position de deux boites de telle façon que la somme des chiffres dans les boites soit toujours égale à zero.
Par exemple:
si i = 2 et j = 7
on aura 1 7 4 5 6 2 8 9
3 2 -2 -4 1 2 -1 -2

Bon, à première vu, si les deux chiffres sont positifs il n y a pas de problèmes. Par contre si on a un chiffre positif et un autre négatif c'est là problème car il faut voir caluler la somme des chiffres dans ce cas là qui doit etre zero pour accepter l'échange.

Voici l'idée que j'ai :
On fait une boucle for i de 0 à n (nbre de boites) et une autre boucle for j de i+1 à n(nbre boites)
et une autre boucle k de 1 à n
on permute la position de deux boites.
Puis on fait une boucle pour tester si la somme des chiffres est égales à zéro.
Si oui, je sorts. Sinon, on reboucle.
Je ne sais pas si j'ai fait le bon raisonnement ou le mauvais. Y a-til des cas auquel je n'ai pas pensé?
Auriez-vous d'autres pistes?
Merci par avance de vos aides
Voici mon programme en C. Je ne l 'ai pas encore tester.


void echange(int a, int b)
{
   int temp;
   temp = a;
   b = a;
   a = temp;


}


void calculeExchange(int tableau[], int n)
{
   int modifie, k;
   int somme = 0;
   
   do
   {
      modifie=0;

      int i,j;
      for(i=1;  i<n;i++)
      {
          for(j=i+1;j<n;j++)
          {
             
               if(tableau[i]>0 && tableau[j]>0)
               {
		   echange(i,j);
                   modifie ==1;
		}//if
                else
                {            
	           for(k=1;k<n;kj++)
          	   {
		     somme+= tableau[k];
                   }
                   if(somme == 0)
                   {
                      modifie=1;
                      printf("Modifie !     modifie==1\n");
                   }

                }//else

          } // for j
                        
      }//for i
 }while(modifie==1);

1 réponse

Réponse 1 / 1

Hxyp Messages postés 401 Date d'inscription vendredi 28 janvier 2011 Statut Membre Dernière intervention 27 avril 2014 54
25 juil. 2011 à 14:02

Bonjour,
Un petit problème dans la fonction échange, sinon est-ce que la première permutation valide (avec somme à zéro) est suffisante ou faut-il générer toutes les possibilités de permutation des boîtes ? Et dans ce cas il faut créer/utiliser un algo pour générer les permutations.

Un petit bout de code, j'ai créé un type "boite" pour simplifier :

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct{
    int n,v; /* n : numero de la boîte, v : valeur de la boite */
}boite;

int verif(boite *b,int n)
  { /* verif si la somme des boîtes fait bien zéro retourne 0 */
    int i,k;
    for(k=i=0;i<n;i++)
        k+=b[i].v;
    if(!k) return 0;
    return 1;
  }

void print_b(boite *b,int n)
  { /* affiche les positions des boîtes et leurs valeurs */
    int i; for(i=0;i<n;i++)
        printf("%d ",b[i].n);
    printf("\n");
    for(i=0;i<n;i++)
        printf("%d ",b[i].v);
    printf("\n");
  }

int echange(boite *b,int n)
  { /* simple fonction a améliorer pour l'échange des boîtes */
    int i,j;
    boite *temp=malloc(sizeof(boite));
    assert(temp);
    for(i=0;i<n;i++){
        for(j=0;j<n-1;j++){
            *temp=b[j];
            b[j]=b[j+1];
            b[j+1]=*temp;
        }
        if(!verif(b,n)){
            free(temp);
            return 0;
        }
    }
    free(temp);
    return 1;
  }

int main(void)
  {
    /* b est un tableau de boîtes : numéro,valeur,... */
    boite b[9]={1,3,2,2,3,1,4,-2,5,-4,6,1,7,2,8,-1,9,-2};
    if(!echange(b,9)){ /* si positions sont ok affichage des boîtes */
        printf("position ok :\n");
        print_b(b,9);
    }
    return 0;
  }

En retour ça me donne pour l'Exemple
1 2 3 4 5 6 7 8 9
3 2 1 -2 -4 1 2 -1 -2

position ok :
2 3 4 5 6 7 8 9 1
2 1 -2 -4 1 2 -1 -2 3
= 0

Faudrait améliorer la fonction échange en ajoutant un algo de permutation pour avoir toutes les possibilités j'imagine que ce serait mieux pour ne pas passer à côté d'une solution

Sportif_C
25 juil. 2011 à 14:51

Merci pour votre réponse.
En fait, je n'ai pas compris cette ligne

if(!k)

dans la fonction verification ()

Hxyp Messages postés 401 Date d'inscription vendredi 28 janvier 2011 Statut Membre Dernière intervention 27 avril 2014 54
25 juil. 2011 à 16:42

if(!k) c'est l'inverse de if(k)
if(k) = si l'expression k est vrai
if(!k) = si l'expression k est fausse

Newsletters