Discussion :

[Glopsos]

Bonsoir !

Je débute dans le C et j'me suis acheté un p'tit livre d'algo et ohhh grande surprise, certains exos ne sont pas corrigés .
Voila pour la petite histoire dont tout le monde se fou...

Je suis tombé sur un exo qui me dans la mesure où je ne vois absolument pas comment le résoudre. Je me suis donc dit qu'on pouvait peut être essayer de le faire ensemble, si cela ne vous dérange pas trop .

Voici l'énoncé:
Les N personnes du couloir de N chambres contenant chacune 1 ampoule se livrent à un jeu bizard. Chacun tour à tour change l'état des ampoules de certaines chambres : s'il trouve une ampoule allumée, il l'étein, et s'il trouve une ampoule éteinte, il l'allume.
La première personne change l'état de toutes les ampoules (qui étaient tout éteintes), la deuxième change l'état d'une ampoule sur deux, le troisième une ampoule sur trois, le quatrième une ampoule sur 4 etc... Et ce jusqu'à la dernière personne.

Écrivez une fonction qui prend en argument le nombre de personnes et de chambres (il y a autant de chambres que de personnes) N et un numéro d'ampoule A, et qui renvoie 1 si l'ampoule choisie à la fin du jeu est allumée, 0 sinon.

(On attendra donc en entrée deux entiers:

N, le nombre personnes(qui est égal au nombre de chambres)
A, le numéro de l'ampoules. 1 <= A <= N)

--------------------------------------------------

J'ai commencé à préparer le terrain:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int ampoules_on(int n, int a)
{
    //pour le moment c'est le flou totale ici, je vais essayer de comprendre grace à votre aide.
}
 
int main()
{
  int n,a,res;
  scanf("%d%d", &n, &a);
  res = ampoule_on(n,a);
  printf("%d\n",res);
  return 0;
}

ATTENTION, je ne veux pas que vous me le fassiez! je veux juste essayer de trouver grâce à votre aide. Il se peut qu'il y ai certaines notions que je ne connaisse pas encore bien. Dans ce cas j'essaierait petit à petit de me référer à des cours sur le net .

[Médinoc]

Je conseille de dérouler l'algorithme au lieu d'essayer de calculer mathématiquement le résultat (car je ne suis pas assez en forme pour ça).
Il te faudrait donc un tableau réprésentant les ampoules. Chaque case du tableau ne peut avoir que deux valeurs: Allumée ou éteinte.

Ensuite, il faudra deux boucles imbriquées. Une boucle "personnes" contenant une boucle "chambres".

Voici un squelette de fonction ampoule_on() qui prend en charge la création et la destruction du tableau.
La partie "déroulement" qu'il te faut à présent tenter de faire (je t'aiderai à la corriger) sera dans la fonction derouler_algo().

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define ON 1
#define OFF 42
 
void derouler_algo(int *pAmpoules, int n)
{
	/* À toi de mettre le bon code ici.
	   Avec deux boucles. */
}
 
/* Retourne 1 si allumée, 0 si éteinte, -1 si erreur. */
int ampoule_on(int n, int a)
{
	int ret = -1;
	/* Création d'un tableau d'ampoules */
	int * pAmpoules = malloc(n * sizeof *pAmpoules);
	if(pAmpoules!=NULL)
	{
 
		derouler_algo(pAmpoules, n);
		if(pAmpoules[n-1] == ON)
			ret = 1;
		else 
			ret = 0;
 
		free(pAmpoules);
	}
	return ret;
}

Ah, en fait, je viens de trouver la solultion mathématique, qui doit être plus simple:
Pour ton ampoule, tu prends les numéros de chaque personne, et tu regardes à chaque fois si c'est divisible.
Aucune création de tableau n'est nécessaire, il suffit d'une simple boucle, car on calcule l'état d'une seule ampoule (alors qu'en déroulant l'algorithme, on calculait l'état de toutes les ampoules).

[Glopsos]

Pour ton ampoule, tu prends les numéros de chaque personne, et tu regardes à chaque fois si c'est divisible.

Merci pour tes réponses Donc avec un simple modulo c'est faisable?
Je n'ai pas bien bien compris ton raisonnement, ce serait pas mal que tu réexplique (dsl).

Sinon dérouler l'algo prendrait beaucoup trop de temps (imagine qu'il y ai 1 millions de personnes qui jouent à ce jeux d'extinction d'ampoule :p)

[Médinoc]

En effet, pour le coup du déroulement de l'algo, c'est mon côté "Heath-Robinson first, simple later" (ou simplement mon côté Shadok) qui prend toujours le dessus dans les premières minutes où je lis la question.

Pour être précis dans ma réponse, ça doit être faisable avec une seule boucle et un modulo dans cette boucle.

• Pour chaque personne
• Si le numéro (en commençant à 1, pas à zéro) de l'ampoule est divisible par celui de la personne
  
  • Alors on change l'état.
• Et on retourne l'état final.

[Trap D]

Je crois que Medinoc a fait toute la lumière sur ce problème d'ampoule

[Glopsos]

En effet, merci bcp mon esprit s'éclaire .

Je poste lorsque j'aurait bien tout rédigé. Je suis dans mes débuts en C, donc ça peut me prendre du temps

Bon, j'ai un peu la nausée donc j'arette, je recommencerais demain.
Pour le moment ça compile même pas . Je ne comprend pas pourquoi...
Voici mon code, dites moi si je suis sur la bonne voie...

(très possible que j'ai fais n'importe quoi, je suis vraiment dans le coltare , à demain )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <stdlib.h>
 
 
int ampoules_on(int n, int a)
{
int etat_ampoule = 0;
  while(n != 0)
  {
    if(a % n == 0 && etat_ampoule = 0)   
         etat_ampoule = 1;  
    else if(a % n == 0 && etat_ampoule = 1)  
         etat_ampoule = 0;
  n = n - 1;
  }   
}
 
int main()
{
  int n,a,res;
  scanf("%d%d", &n, &a);
  res = ampoule_on(n,a);
  printf("%d\n",res);
system("PAUSE");	
return 0;
}

[c-candide]

Je débute dans le C et j'me suis acheté un p'tit livre d'algo

Par curiosité, voudrais-tu nous donner les références de l'ouvrage ?

Les N personnes du couloir de N chambres contenant chacune N ampoules se livrent à un jeu bizard.

contenant chacune : la formulation, je crois, est incorrecte. La suite de l'exercice semble montrer qu'il y a UNE ampoule par chambre (donc un total de N ampoules et on pas N*N comme le suggère ton énoncé).

Pour être précis dans ma réponse, ça doit être faisable avec une seule boucle et un modulo dans cette boucle.

En fait l'exercice ci-dessus est une reformulation de l'exercice 3 (intitulé "Les prisonniers") de la partie "Algorithmique" du concours Prologin 2008
La solution naïve de la boucle + modulo ne passera pas les contraintes imposées dans l'épreuve machine (faut s'incrire sur le site de prologin pour les connaître et pouvoir tester son code C (ou java, etc)) :

LIMITE DE MEMOIRE : 1000 ko
LIMITE DE TEMPS : 1000 ms
Nombre d'ampoules : 1000000000

[Médinoc]

Pourquoi ne passera-t-elle pas ?
Mémoire ? Elle ne consomme rien.
Vitesse ? Je ne pense pas qu'un modulo soit plus lent qu'une boucle imbriquée de 1 000 000 000 d'itération...

[Pacorabanix]

Sinon dérouler l'algo prendrait beaucoup trop de temps (imagine qu'il y ai 1 millions de personnes qui jouent à ce jeux d'extinction d'ampoule :p)

j'ai "déroulé" l'algo pour le cas N=20. Avec une petite feuille de papier et un crayon :
(0 = départ, c-à-d allumé)
(1 = changé, c-à-d eteint)

depart) 0000'0000'0000'0000'0000
etape 1) 1111'1111'1111'1111'1111
etape 2) 1010'1010'1010'1010'1010
...
etape 10) 1001'0000'1011'1110'1111
...
etape 20) 1001'0000'1000'0001'0000

on devine assez clairement que les résultats sont que les ampoules situées aux emplacements A = carré d'un nombre entier sont éteintes et les autres allumées.

ça doit pouvoir se démontrer, mais je n'ai pas le courage de chercher la preuve, et je doute que ce soit pertinent. (mais il peut etre très instructif de chercher à comprendre la raison!)

Il suffit donc de vérifier si la racine de A est encore un nombre entier . Si oui ce sera eteint sinon allumé.

Donc en effet il faut l'aide des maths pour calculer rapidement ce problème, mais peut etre que l'enoncé voulait dire qu'il fallait d'abord calculer naivement par une boucle tous les résultats puis accéder rapidement au résultat par simple accès au tableau des resultats?

EDIT : ça se confirme, j'ai vérifié jusqu'à N=25

[Glopsos]

j'ai "déroulé" l'algo pour le cas N=20. Avec une petite feuille de papier et un crayon :
(0 = départ, c-à-d allumé)
(1 = changé, c-à-d eteint)

Les ampoules étaient éteintes au départ, mais cela ne change rien au problème

Il suffit donc de vérifier si la racine de A est encore un nombre entier .

Simpas, j'ai également déroulé et ça m'a l'air correcte, je m'en vais tester un nouvel algo de ce pas

[Pacorabanix]

Les ampoules étaient éteintes au départ, mais cela ne change rien au problème

Euh c'est ce que je croyais :s, c'est pour ça que j'ai mis 0, mais en relisant, et sachant qu'il était tard je me suis embrouillé en relisant ton post ^^. En efet ça ne change rien !

Sur cette résolution (merci pour la preuve rapide et claire de pseudocode) je vous souhaite à tous une très heureuse année à venir !

Et faites attention au bug de 2008 !

[pseudocode]

jça doit pouvoir se démontrer, mais je n'ai pas le courage de chercher la preuve, et je doute que ce soit pertinent. (mais il peut etre très instructif de chercher à comprendre la raison!)

La lampe n°X change d'état a chaque fois que X est divisible par "i", avec "i" variant entre 1 et N (nombre total de lampe).

Par exemple la lampe 6 change d'état pour i = 1,2,3 et 6. Soit 4 fois, donc elle revient dans l"etat initial.

Pour que l'etat final de la lampe X soit different de l'etat initial, il faut qu'elle change d'état un nombre IMPAIR de fois.

Or pour chaque diviseur strictement inferieur a racine de X, on a forcement un autre diviseur strictement supérieur a racine X (X / a = b ==> X / b = a) et réciproquement.

Donc les diviseurs differents de racine de X peuvent etre associés par paire => ils ne changent pas l'état final.

Donc, pour changer l'état final, il faut que racine de X soit un diviseur entier de X. Comme c'est forcément un diviseur, il suffit que racine de X soit entier.

[c-candide]

Comme c'est forcément un diviseur, il suffit que racine de X soit entier.

Oui. En d'autres termes, il suffit que X soit un carré parfait.