[c] énigme ....

Résolu

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention -
LAVACHENENETTE - 20 juin 2008 à 16:44

Salut !
Je voudrais résoudre une énigme mathématique en faisant un programme en C... le probléme, c'est que mon prog ne marche pas !
voici l'énigme :

Vous êtes face à une grande rangée de 12486 diodes bleues.
Au début, seule celle située complètement à gauche est allumée. Ensuite, toutes les secondes, l'opération suivante est réalisée:
Chaque diode change d'état si et seulement si celle située à sa gauche était allumée une seconde avant.
La diode située le plus à gauche reste allumée tout le temps. Le processus s'arrête lorsque la diode située à l'extrémité droite s'allume pour la première fois.
Combien de diodes sont alors allumées ?

voici mon code :

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

#define ALLUME 1
#define ETEIN 0
#define MAX 12486
int main(void)
{
    long i=0;
    int diodes[MAX];
    int dim1[MAX];
    int x=0,y=0,z=0,nb=0;
    
    for(x=0;x!=MAX;++x){
                       diodes[x]=0;
                       dim1[x]=0;}
    diodes[0]=ALLUME;
    dim1[0]=ALLUME;
    while(diodes[12485] != ALLUME)
                        {
                                  z=0;
                                 while(z!=12486)
                                 {
                                           if(z!=0 && dim1[z-1] == ALLUME)
                                           {
                                                   if(diodes[z] == ALLUME)
                                                                diodes[z] = ETEIN;
                                                   if(diodes[z] == ETEIN)
                                                             diodes[z] = ALLUME;
                                           }
                                           ++z;
                                 }
                                 for(x=0; x<= 12486;++x)
                                     dim1[x] = diodes[x];
                                  
                                  
                        }
    while(y!=12486)
    {
                   if(diodes[y] == ALLUME)
                                ++nb;
     ++y;
     }                
     printf("%d\n", nb);                                 
    system("pause");
}

Merci à ceux qui auront le courage de lire et de m'aider ;) !
Merci !

Afficher la suite

A voir également:

22 réponses

Réponse 1 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

Je ferais un truc dans ce genre (si j'ai bien compris l'énoncé) :

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

//Decommente les ligne suivantes si le type bool n'existe pas
//Si tu compiles avec g++ normalement le type bool existe
//typedef unsigned short int bool
//bool false=0; //éteint
//bool true=1;  //allumé

void change_etat(
  bool *diodes_avant,
  bool *diode_apres,
  unsigned int max
){
  unsigned int i=0;
  for(i=1;i<max;++i){
    if (diodes_avant[i-1]) diodes_apres[i]= !diodes_apres[i];
  }
}

void flush_diode(
  bool *diodes,
  unsigned int max
){
  unsigned int i=0;
  for(i=0;i<max;++i){
    diodes[i]=false;
  }
}

unsigned int compte_allume(
  bool *diodes,
  unsigned int max
){
  unsigned int i=0,res=0;
  for(i=0;i<max;++i){
    if (diodes[i]) ++res;
  }
  return res;
}


int main(){
  bool *diodes_avant;
  bool *diodes_apres;
  unsigned int max;
  scanf("%d",&max);

  // Allocation mémoire. Le calloc met les cases à 0 (ie false)
  diodes_avant=(bool *)calloc(max,sizeof(bool));
  diodes_apres=(bool *)calloc(max,sizeof(bool));
  diodes_avant[0]=true;

  while(!diode_avant[max-1]){
    change_etat(diodes_avant,diodes_apres,max);
    //On passe à l'etat suivant
    diodes_avant=diodes_apres;
    flush_diodes(diodes_apres,max);
  }
  // Afficher le résultat
  printf("%d diodes allumées\n",compter_allume(diode_avant,max);
  // On libère la mémoire
  free(diodes_avant);
  free(diodes_apres);
  return 0;
}

Je n'ai pas testé le programme mais à mon avis on n'est pas loin du bonheur ;)

Bonne chance

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

Salut,
merci pour ta réponse !
Ton prog ne marche pas :(
J'aimerais bien changer se qui ne va pas tout seul, mais je n'ai pas le niveau :D
Voici les erreur qu'a donner Dev-c ++ ( j'ai essayé avec et sans les com, je donne déja juste les erreurs sans les com ;D)

Ligne 27 & 54: 'diodes_apres' undeclared fonction (first use this function)

Il dit aussi que :
-diode_avant
-flush_diodes
-compter_allume
ne sont pas déclarés .......
Merci de votre aide !!!

Max

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27 > Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention

Nan, c'est bon, c'était just un probléme de s a la fi de diode(s), mais il me reste le flush_diodes que je ne comprend po ...

Réponse 2 / 22

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

C'est bon j'ai trouvé aussi pour flush_diode
J'ai lancé le prog et apparament, il y a une boucle infinie .....
sniffff

Réponse 3 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

Pour l'instant prend un max plus petit genre 10. Change la boucle while(!diode_avant[max-1]) par une boucle for qui fera une dizaine d'itérations. Si dessous (je ne remets pas tout le programme une idée du genre de choses que tu peux faire)

...
void show_diodes(bool *diodes,unsigned int max){
  unsigned int i;
  for(i=0;i<max;++i) printf("%d",diodes[i]);
  printf("\n");
}

int main(){
  unsigned int nb_iter;
  ...
  for(nb_iter=1;i<20;++i){ // à la place du while
    ...
    show_diodes(diodes_avant,max);
  }
  ...
}

Comme ça tu verras ce qui se passe ce qui devrait t'aider à debugger...

Là je n'ai malheureusement pas le temps de trop t'aider je suis désolée. De toute façon moi je suis juste là pour essayer de te donner des conseils mais au final il faut que ce soit toi qui arrive à faire le programme ;)

Bonne chance

Réponse 4 / 22

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

Je sias, il faut que j'y arrive tout seul, ....
ET c'est se que j'ai fait !!!
J'ai réussi !!!!!
j'ai juste repri mon prog ( le mien :D) et j'ai fait se qu'il devait faire sous excel ... j'ai trouvé mon erreur: il fallai prendrel'état de la diode AVANT et pas au moment de la changer ... Merci de votre aide !!!
@++

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question

Réponse 5 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

Héhé :) No pb ;)

Réponse 6 / 22

Char Snipeur Messages postés 9813 Date d'inscription Statut Contributeur Dernière intervention 1 299

Salut.
J'ai trouvé ce problème marrant, et je me suis amusé à le faire.
Voici le code:

#include <stdio.h>
#include <iostream>
int main()
    {
    FILE *fc;
    fc=fopen("diodes.txt","w");
    bool *d1,*d2;
    int max;
    std::cin>>max;
    d1=new bool[max];d2=new bool[max];for(int i=0;i<max;i++)d1[i]=false;
    d1[0]=d2[0]=true;std::cout<<d1[max-1];
    while (!d1[max-1])
        {
        for (int i=1;i<max;i++)
                if(d1[i-1])
                    d2[i]=!d1[i];
                else
                    d2[i]=d1[i];
        for(int i=0;i<max;i++)
                {fprintf(fc,"%d\t",(int)d1[i]);d1[i]=d2[i];}
        fprintf(fc,"\n");
        }
    return 0;
    }

C'est en ouvrant le fichier sous excel que je me suis rendu compte que c'est un problème super connu.
J'ai été super étonner de retrouver la figure au triangle type "fractale".
Je pense qu'il y a bien plus à en tirer que le nombre allumer une fois celle de droite allumer. Mais j'ai quand même remarquer que si le nombre de diode et une puissance de deux, ce sera 50%.
a+

Réponse 7 / 22

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

Salut !
Maintenant, je doit faire le meme, mais avec un tréésss grand nombre de diode ( environ 1200000 .... ) le probléme c'est que mon prog BUG dés que je le démarre, sa doit ê a cause de la taille des nombres, j'ai essayé evc des long, sa ne marche pas non plus :(
Pouriez vous m'aider ?
Comment faire pour travailler avec de grands nombres ?
D'avance Merci.

Réponse 8 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

Si tu fais des calloc/malloc vérifie que l'allocation a marché en regardant le code de retour de la fonction. Essaye de coder le tableau de diode avec les bool du c++ qui ne prennent qu'un bit. Et quand tu dis "bugge" ca veut dire qu'il plante ? qu'il est très lent et qu'il semble planté ?

Réponse 9 / 22

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

Salut,
quand je dit bug, c'est quand windows dit "le prog doit être fermer"
pour les bool du c++, je ne sais pas exactement ce que c'est, je b'ai fait que du C, et je suis seulement au début ....
Je vais quand meme voir si je trouve sur le net comment faire ....
Je pense que le probléme est dû au nombre d'entrée des tableaux, car j'ai :
diodes[1200000]
Merci pour ta réponse rapide :D

Réponse 10 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

En fait c'est vraiment très simple. Le type bool existe en C++ au même titre qu'un int. Mais je ne crois pas qu'il existe en C. Or le C est un cas particulier du C++ d'un point de vue code source. Ainsi tu peux directement compiler un programme C avec un compilateur C++, par exemple g++.

Il suffit donc de faire des tableau de bool pour gagner en mémoire. Peux tu nous donner ton code actuel ?

Bonne chance

Réponse 11 / 22

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

oui, voici mon code :

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

#define ALLUME 1
#define ETEIN 0
#define MAX 2097153  
int main(void)
{
    long i=0;
    long diodes[MAX];
    long dim1[MAX];
    long x=0,y=0,z=0,nb=0;
    
    for(x=0;x!=MAX;++x){
                       diodes[x]=0;
                       dim1[x]=0;}
    diodes[0]=ALLUME;
    dim1[0]=ALLUME;
        while(diodes[MAX-1] != ALLUME)
                        {
                                  z=0;
                                 while(z!=MAX)
                                 {
                                           if(z!=0 && dim1[z-1] == ALLUME)
                                           {
                                                   if(dim1[z] == ALLUME)
                                                                diodes[z] = ETEIN;
                                                   if(dim1[z] == ETEIN)
                                                               diodes[z] = ALLUME;
                                           }
                                           ++z;
                                 }
                                 for(x=0; x<= MAX;++x)
                                     dim1[x] = diodes[x];
                                  
                                  
                        }
    while(y!=MAX)
    {
                   if(diodes[y] == ALLUME)
                                ++nb;
     ++y;
     }                
     printf("%d\n", nb);                                 
    system("pause");
}

Les variables :
MAX : nobre de diodes
diodes[x] : etat actuel des diodes
dim1[x] : etat des diodes une seconde avant

Ce code marche trés bien pour les petits nombres mais avec grands .......
D'avance Merci ;)

Réponse 12 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

long diodes[MAX];
long dim1[MAX];

L'information n'est codée que sur un bit, il est donc complètement inutile de mettre des long ! Au contraire vu que le tableau est très grand il faut des cases qui prennent individuellement peux de places en mémoire.

Idéalement utilise des bool, sinon des unsigned short int.

bool diodes[MAX];
bool dim1[MAX];

Bonne chance

Réponse 13 / 22

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

sniff sa ne marche pas ...
pourriez-vous essayez sur votre PC ? car je commence à douter du mien ...
j'ai essayer avec les bool et les unsigned short int ...
toujours le meme bug, peut-être que le long ne convien pas pour les autres variables ...
existe il plus long que long ?mdr
D'avance merci !

Réponse 14 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

Quelques corrections mineures :

1) Corrections sur les types :

bool diodes[MAX];
bool dim1[MAX];
unsigned int x,y,z,nb=0;

Note que dans ton code vu que x,y,z n'interviennent pas simultanément on pourrait se contenter juste d'un compteur.
2) Replacer le system("pause"); par :

getchar();

3) Mettre à la fin du main un :

return 0;

4) En toute rigueur tu devrais écrire pour initialiser tes tableaux (soit dit en passant ETEIN s'écrit ETEINT :p :

for(x=0;x!=MAX;++x){
  diodes[x]=ETEIN;
  dim1[x]=ETEIN;
}

5) La variable i ne sert à rien.
6) Ta boucle while sur z s'écrit avec une boucle for, qui peut partir de 1 puisque tu zappes le cas z==0 :

for(z=1;z!=MAX;++z){
...
}

Idem pour la boucle sur y.

Ce qui ne va pas

A cet endroit du code :

for(x=0; x<= MAX;++x)
  dim1[x] = diodes[x];

tu perds un temps fout à recopier le tableau alors qu'il suffirait de considérer que le tableau dim1 commence désormais à l'adresse diodes.

Correction que je te propose

En fait si la mise à jour se fait de droite à gauche dans ton tableau diode tu peux te passer de dim1 (si je ne m'abuse) :

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

#define ALLUME 1
#define ETEINT 0
#define MAX 10

int main(void)
{
    bool diodes[MAX];
    bool dim1[MAX];
    unsigned int x=0,it,nb=0;

    // Initialisation
    for(x=0;x!=MAX;++x){
        diodes[x]=0;
        dim1[x]=0;
    }
    diodes[0]=ALLUME;
    dim1[0]=ALLUME;

    // Iteration
    for(it=0;it<10 && diodes[MAX-1] != ALLUME;++it){
        // Affichage
        for(x=0; x< MAX;++x) printf("%d",diodes[x]);
        printf("\n");

        // Mise a jour
        for(x=MAX-1;x>0;--x){
            if(diodes[x-1] == ALLUME){
                if     (diodes[x] == ETEINT) diodes[x] = ALLUME;
                else if(diodes[x] == ALLUME) diodes[x] = ETEINT;
            }
        }
    }
    // Affichage et calcul du resultat
    printf("\n\n");
    for(x=0; x< MAX;++x) printf("%d",diodes[x]);
    printf("\n");
    for(x=0;x<MAX;++x){
        if(diodes[x] == ALLUME) ++nb;
    }
    printf("%d\n", nb);

    return 0;
}

Ce qui à l'éxecution donne :

(mando@aldur) (~) $ g++ -W -Wall plop.c  && ./a.out
1000000000
1100000000
1010000000
1111000000
1000100000
1100110000
1010101000
1111111100
1000000010


1100000011
4

Bref si j'ai bien compris l'énoncé ca fait bien ce qu'on veut... En tout cas le gain en performance sera très net si tu évites la recopie de dim1 dans diodes

Bonne chance

Réponse 15 / 22

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

Salut !
Merci pour ta correction
un peu stricte mais efficace !
je vais me justifier pour toutes ces erreurs :
sa fait 1 an que je n'ai pas fait de C ....
et vous savez, le c c'est difficile quand on a 16 ans ....
Big merci !

Réponse 16 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

Ha mais attention la correction "stricte" n'a absolument rien d'un reproche ! Au contraire c'est des conseils pour t'aider à t'améliorer ^^ donc tu n'as pas besoin de te justifier ;) Et rassure-toi pour quelqu'un qui a fait un an de C c'est pas mal ce que tu as fait, surtout si tu es auto didacte :p

@+

Réponse 17 / 22

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

Je sais que ce n'étais pas un reproche ;)
Mais je suis trés fier de mon bout de code avec plein d'erreurs mdr !
Grand merci pour ton aide !

Réponse 18 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

Hihi de rien ;) Il était bien ton code, t'inquiète :p Continue comme ça

Réponse 19 / 22

Maxg59 Messages postés 275 Date d'inscription Statut Membre Dernière intervention 27

Salut ;)
au fait, j'ai oublié de te dire que ton prog ne marche pas :D
a partir de la 8éme diode, le reste est toujour de 0, tu n'as qy'a essayer avec par exemple 40, seul les 8 premiéres diodes marchent, le reste reste eteinT .....
j'ai tout juste réussi à comprendre ton code, et je n'ai pas trouvé le probléme ....
Merci ;D

Réponse 20 / 22

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

Ah oui lol. J'ai oublié de virer l'instruction debuggage qui limitait l'algo à dix itérations :

 for(it=0;it<10 && diodes[MAX-1] != ALLUME;++it)

est à remplacer par :

 while(diodes[MAX-1] != ALLUME)

On peut supprimer la décalaration de la variable it du coup...

Bonne chance

Discussions similaires

Le monde de max la réponse

Code Ascii

Enigme

aidez moi a trouver cette enigme

enigme

Votre réponse

Discussions similaires